[ABC349] AtCoder Beginner Contest 349 题解

news/发布时间2024/5/16 15:07:54

[ABC349] AtCoder Beginner Contest 349 题解

[ABC349] AtCoder Beginner Contest 349 题解
- A - Zero Sum Game
- B - Commencement
- C - Airport Code
- D - Divide Interval
- E - Weighted Tic-Tac-Toe
- F - Subsequence LCM
- G - Palindrome Construction
- 总结

A - Zero Sum Game

~~零和博弈~~，观察到和为0，就完了。

B - Commencement

模拟，多读几遍题。

C - Airport Code

直接在 S 后面插入一个 X，然后就变成第一种情况，贪心即可。

D - Divide Interval

一个位置的方案可能是去掉若干个后缀 0，然后加一，再加回来后缀 0。

根据贪心的思路，尽可能去掉最多个后缀 0，发现跑得很快然后过了。

int l, r;
int cnt (int x) {int c = 0;while(x) {if(x & 1) break;x /= 2;c ++;}return c;
}
int al[N], ar[N];
void work() {cin >> l >> r;int ans = 0;for(int i = l; i < r; ) {int k = cnt(i);if(i == 0) k = 61;for(int j = k; j >= 0; j --) {int p = (((i >> j) + 1) << j);if(p <= r) {ans ++;al[ans] = i, ar[ans] = p;i = p;break;}}}cout << ans << '\n';for(int i = 1; i <= ans; i ++)cout << al[i] << ' ' << ar[i] << '\n';return ;
}

E - Weighted Tic-Tac-Toe

博弈论板子，爆搜即可，不放心加记忆化。

// Problem: E - Weighted Tic-Tac-Toe
// Contest: AtCoder - AtCoder Beginner Contest 349
// Author: Moyou
// Copyright (c) 2024 Moyou All rights reserved.
// Date: 2024-04-13 20:33:25#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#define int long long
using namespace std;
const int N = 10 + 10;int a[N][N], g[N][N], n;
int S(int g[][N]) {int ans = 0;for(int i = 1, w = 1; i <= n; i ++)for(int j = 1; j <= n; j ++, w *= 3) ans += ((g[i][j] == -1 ? 2 : g[i][j]) * w);return ans;
}
int check(int g[][N]) {for(int i = 1; i <= n; i ++) {bool flg = 1;if(g[i][1] == -1) continue;for(int j = 1; j < n; j ++) {if(!(g[i][j] != -1 && g[i][j + 1] != -1)) {flg = 0;break;}if(g[i][j] != g[i][j + 1]) {flg = 0;break;}}if(flg)return g[i][1];}for(int i = 1; i <= n; i ++) {bool flg = 1;if(g[1][i] == -1) continue;for(int j = 1; j < n; j ++) {if(!(g[j][i] != -1 && g[j + 1][i] != -1)) {flg = 0;break;}if(g[j][i] != g[j + 1][i]) {flg = 0;break;}}if(flg)return g[1][i];}if(g[1][1] != -1 && g[1][1] == g[2][2] && g[1][1] == g[3][3]) return g[1][1];if(g[1][3] != -1 && g[1][3] == g[2][2] && g[1][3] == g[3][1]) return g[2][2];int x = 0, y = 0;for(int i = 1; i <= n; i ++)for(int j = 1; j <= n; j ++) {if(g[i][j] == -1) return 2;if(g[i][j] == 0) x += a[i][j];else y += a[i][j];}return (x < y);
}
int f[60000];
int dfs(int u) {int s = S(g);if(check(g) != 2)return f[s] = check(g);if(f[s] != 0x3f3f3f3f3f3f3f3f) return f[s];bool flg = 0;for(int i = 1; i <= n; i ++)for(int j = 1; j <= n; j ++) {if(g[i][j] == -1) {g[i][j] = u;int ne = dfs(u ^ 1);g[i][j] = -1;if(ne == u)return f[s] = ne;if(ne == 2) flg = 1;}}return f[s] = (flg ? 2 : (u ^ 1));
}signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);n = 3;for(int i = 1; i <= n; i ++)for(int j = 1; j <= n; j ++)cin >> a[i][j];memset(f, 0x3f, sizeof f);memset(g, -1, sizeof g);dfs(0);cout << (f[19682] ? "Aoki" : "Takahashi") << '\n';return 0;
}
/*
0 -1 -1 
-1 0 -1 
-1 -1 1 */

F - Subsequence LCM

本场我最喜欢的题。

考虑质因数分解，然后要求取若干个数使得 $\text lcm = M$，可以发现，去掉不合法的数字之后，如果某个位 $p_i^{\alpha _i}$ 上所有 $< \alpha_i$ 的数都是一样的，这一位上可选可不选，所以可以用一个 01 串来表示每个数。

那么就转化为了：

给出一个序列，取出一个集合使得它们的或为 $M$，方案数多少。

有一个显然的 DP：$f_{i, s}$ 表示选取前 $i$ 个数，或为 $s$ 的方案数。

这样是 $O(n2^{w(M)})$，看似可过实际上会爆掉。

然后发现如果两个数的 01 串是相同的它们的转移也一样，所以可以优化把状态数优化成 $2^w$，总时间复杂度是 $O(4^w)$，可过。

考虑更优的做法。

很容易想到用容斥做这个计数，也就是算出来$ g_i$ 表示：

\[\sum_{t\subset i}g_t \]

也就是一个 SOSDP（子集卷积，Zeta 变换）。

然后子集容斥算出来答案。

// Problem: F - Subsequence LCM
// Contest: AtCoder - AtCoder Beginner Contest 349
// Author: Moyou
// Copyright (c) 2024 Moyou All rights reserved.
// Date: 2024-04-13 21:31:08#include <algorithm>
#include <iostream>
#include <queue>
#define int long long
using namespace std;
const int N = 2e5 + 10, M = (1 << 13) + 10, mod = 998244353;int n, m, a[N], b[M], f[M], k;
vector<pair<int, int> > primes;
void get_p(int a) {for(int i = 2, cnt; i * i <= a; i ++) {if(a % i == 0) {cnt = 0;while(a % i == 0) a /= i, cnt++; primes.push_back({i, cnt});}}if(a > 1) primes.push_back({a, 1}); k = primes.size();return;
}
int qmi(int a, int b) {int res = 1;while(b) {if(b & 1) res = 1ll * res * a % mod;b >>= 1, a = 1ll * a * a % mod; }return res;
}signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> m;get_p(m);for(int i = 1, s, j; i <= n; i ++) {cin >> a[i];s = 0, j = 0;for(auto [p, r] : primes) {int c = 0;while(a[i] % p == 0)c ++, a[i] /= p;if(c == r) s |= (1 << j);if(c > r) {s = -1;break;}j ++;}if((~s) && a[i] == 1) f[s] ++;}if(m == 1) return cout << (qmi(2, f[0]) - 1 + mod) % mod << '\n', 0;/* O(4^k) solution, optimizing brute dp by uniquing transf[0][0] = qmi(2, b[0]);for(int i = 0; i < (1 << k); i ++) {for(int s = 0; s < (1 << k); s ++) {(f[i + 1][s | i] += 1ll * f[i][s] * (qmi(2, b[i + 1]) - 1) % mod) %= mod;(f[i + 1][s] += f[i][s]) %= mod;}}cout << (f[(1 << k) - 1][(1 << k) - 1] % mod + mod) % mod << '\n';*/// O(k2^n) solution, SOSDP + inconclusion exclusion pincipleint ans = 0;for(int i = 0; i < k; i ++)for(int s = 0; s < (1 << k); s ++)if(s >> i & 1) (f[s] += f[s ^ (1 << i)]) %= mod;for(int s = 0; s < (1 << k); s ++)f[s] = qmi(2, f[s]);for(int s = 0; s < (1 << k); s ++)(ans += ((__builtin_popcount(s) + k & 1) ? -1 : 1) * f[s]) %= mod;cout << (ans % mod + mod) % mod << '\n';return 0;
}

G - Palindrome Construction

类似 Manacher 从前往后构造原串。

如果一个位置有回文半径覆盖就使用对称位置的字符，否则就贪心选择可以选择的字符里最小的，每次确定之后要给后面的$i + a_i$ 打上不等于 $i - a_i$ 的标记。

这样搞出来是最优解，判断有无解跑一遍 Manacher 即可。

时间复杂度：$O(n)$。

// Problem: G - Palindrome Construction
// Contest: AtCoder - AtCoder Beginner Contest 349
// Author: Moyou
// Copyright (c) 2024 Moyou All rights reserved.
// Date: 2024-04-14 16:55:53#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
const int N = 4e5 + 10;int n, a[N], b[N], d[N], c[N];
vector<int> g[N];
bool st[N];
bool manacher() {d[1] = 1;int m = 0;c[++ m] = -1;for(int i = 1; i <= n; i ++) c[++ m] = b[i], c[++ m] = -1;for(int i = 2, l = 0, r = 0; i <= m; i ++) {if(i <= r) d[i] = min(r - i + 1, d[r + l - i]);while(i - d[i] >= 0 && i + d[i] <= m && c[d[i] + i] == c[i - d[i]]) d[i] ++;if(i + d[i] - 1 > r) l = i - d[i] + 1, r = i + d[i] - 1;}for(int i = 2; i <= m; i += 2)if(d[i] / 2 != a[i / 2]) return 0;return 1;
}signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n;for(int i = 1; i <= n; i ++) cin >> a[i], a[i] ++;for(int i = 1, l = 1, r = 0; i <= n; i ++) {if(i <= r) b[i] = b[r - i + l];else {for(auto x : g[i])st[x] = 1;for(int j = 1; j <= n; j ++)if(!st[j]) {b[i] = j;break;}for(auto x : g[i])st[x] = 0;}if(i + a[i] - 1 > r) l = i - a[i] + 1, r = i + a[i] - 1;g[i + a[i]].push_back(b[i - a[i]]);}if(!manacher()) return cout << "No\n", 0;cout << "Yes\n";for(int i = 1; i <= n; i ++) cout << b[i] << ' '; cout << '\n';return 0;
}