Codeforces Round 868 Div 2
A. A-characteristic (CF 1823 A)
题目大意
要求构造一个仅包含\(1\)和 \(-1\)的长度为 \(n\)的数组 \(a\)，使得存在 \(k\)个下标对 \((i, j), i < j\)满足 \(a_i \times a_j = 1\)。
解题思路
当有\(x\)个 \(1\)， \(y\)个 \(-1\)时，其满足条件的下标对数量为 \(\frac{x (x - 1)}{2} + \frac{y (y - 1)}{2}\)。
由于\(n\)只有 \(100\)，直接枚举 \(x\)即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while(t--){
int n, k;
cin >> n >> k;
int one = 0;
for(; one <= n; ++ one){
int neg = n - one;
if (neg * (neg - 1) + one * (one - 1) == 2 * k)
break;
}
if (one > n)
cout << "No" << '\n';
else{
cout << "Yes" << '\n';
for(int i = 0; i < one; ++ i)
cout << 1 << ' ';
for(int i = 0; i < n - one; ++ i)
cout << -1 << ' ';
cout << '\n';
}
}
return 0;
}
B. Sort with Step (CF 1823 B)
题目大意
给定一个排序，问能否仅通过交换相隔\(k\)的俩元素，使得有序。不能的话问能否事先通过一次任意交换操作后，再通过之前的操作交换得到有序。
解题思路
考虑每个元素的原始位置和最后所在的位置，它们对\(k\)的取模应该相同。否则就不能有序。
而如果恰好有两个元素其对\(k\)的取模不同，且交换之后是相同的，则可以。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while(t--){
int n, k;
cin >> n >> k;
vector<int> a(n);
for(auto &i : a){
cin >> i;
i --;
}
bool ok1 = true;
map<pair<int, int>, int> cnt;
for(int i = 0; i < n; ++ i){
if (i % k != a[i] % k){
ok1 = false;
cnt[{min(i % k, a[i] % k), max(i % k, a[i] % k)}] ++;
}
}
if (ok1)
cout << 0 << '\n';
else if (cnt.size() == 1 && cnt.begin()->second == 2)
cout << 1 << '\n';
else
cout << -1 << '\n';
}
return 0;
}
C. Strongly Composite (CF 1823 C)
题目大意
给定一个数组\(a\)，构造数组 \(b\)，要求最大化数组的元素数量，使得俩数组的所有元素的乘积相同，且数组 \(b\)的每个数都是强合数。
强合数的定义为，合数因子数量\(\geq\)质数因子数量。
解题思路
乘积相同，相当于将数组\(a\)里的质数重新组合；数量最大，相当于尽可能少用质数来组成一个新的数。
可以发现，两个相同的质数组成一个强合数，或者三个不同的质数可以组成一个强合数。
由此我们统计数组 \(a\)中的每个质数的数量，同个质数俩俩组合，不同质数三三组合，就能最大化答案了。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while(t--){
int n;
cin >> n;
map<int, int> cnt;
auto fac = [&](int a){
for(int i = 2; i * i <= a; ++ i){
while (a % i == 0){
cnt[i] ++;
a /= i;
}
}
if (a != 1)
cnt[a] ++;
};
for(int i = 0; i < n; ++ i){
int a;
cin >> a;
fac(a);
}
LL ans = 0;
int left = 0;
for(auto &[_, value] : cnt){
ans += value / 2;
left += (value & 1);
}
ans += left / 3;
cout << ans << '\n';
}
return 0;
}
D. Unique Palindromes (CF 1823 D)
题目大意
要求构造一个仅包含小些字母的字符串\(s\)，长度为\(n\)，且满足 \(k\)个限制。
每个限制表述为\((x_i, c_i)\)， 字符串\(s\)的长度为 \(x_i\)的前缀满足有 \(c_i\)个本质不同的回文串）
解题思路
通过打表发现本质不同的回文串数量不会超过字符串长度。
注意到\(k\)最大只有 \(20\)，这启示我们每个限制可以用一个字符去满足。
思考朴素的构造方法，对于一个长度为 \(n\)的字符串，我们可以 \(aaaaaaaabcabcabc\)这样去构造，一开始连续的 \(a\)的数量就能控制这个字符串的本质不同的回文串的数量。这样的构造方法满足其数量在 \([3, n]\)之内，这刚好符合题意里 \(c_i \geq 3\)的限制。
因此我们可以先根据第一个限制构造出如上的字符串，对于之后的限制进行增量构造，增加的回文数量用 \(dddd\)， \(eeeee\)这样构造，剩下的长度用 \(abc\)这样不会增加回文串数量的形式去填充。
注意用于填充的字符串，在每次填充时应该继续前面的，而不是从头（从\(abc\) ）开始（如代码的fill_cur），不然可能会新增回文串。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--){
int n, k;
cin >> n >> k;
vector<int> x(k), c(k);
for(auto &i : x)
cin >> i;
for(auto &i : c)
cin >> i;
string ans;
int fill_cur = 0;
auto fill = [&](int x){
while(x--){
ans.push_back('a' + fill_cur);
fill_cur = (fill_cur + 1) % 3;
}
};
auto ok = [&](){
int cur = 0;
for(int i = 0; i < k; ++ i){
int dis = x[i] - c[i];
if (dis < 0)
return false;
if (cur > dis)
return false;
cur = dis;
}
ans += string(c[0] - 3, 'a');
fill(x[0] - ans.size());
for(int i = 1; i < k; ++ i){
ans += string(c[i] - c[i - 1], 'c' + i);
fill(x[i] - ans.size());
}
return true;
};
if (ok()){
cout << "YES" << '\n';
cout << ans << '\n';
}else {
cout << "NO" << '\n';
}
}
return 0;
}
E. Removing Graph (CF 1823 E)
题目大意
两人博弈。
给定\(n\)个环，每个人可以从\([l, r]\) 中选一个数\(x\)，然后选择由\(x\) 个点组成的连通子图，将点及其边去掉。不能操作者输。
在绝顶聪明的情况下，问先后手谁必赢。
解题思路
每个环都是一个独立局面，因此我们求出每个环的\(sg\)值，异或起来，非零就先手赢，否则后手赢。
对于一个环来说，取了一次之后就变成一条链了。因此一个环的 \(sg\)值就是所有可能的链的长度对应的\(sg\)值的 \(mex\)。
对于一个链来说，取了一次之后就变成两条链，这两条链分别都是一个独立局面，因此一个链的 \(sg\)值，就是一些操作值的 \(mex\)， 而操作值就是取了之后（有取的长度和取的位置两个因素）的两个链的\(sg\)值的异或。
abc287g和abc297g就是要求一个链的\(sg\)值。
注意到题目保证了 \(l \neq r\)，对于一条链来说，如果它能取（即长度 \(\geq l\)），则必定能分成两条长度一样的链，之后先手就模仿后手的操作，就能必赢了。
也就是说，对于一个环来说，如果其长度\(len \geq l + r\)，那么先手取了一次后，变成的链因为后手必定可以再取（\(len - r \geq l\) )，所以对于后手来说必定是个必胜态，所以这样的环对于先手来说必定是个必败态，其 \(sg\)值为 \(0\)。
而长度小于 \(l\)，不能取，那肯定是必败态，其 \(sg\)值为 \(0\)。
考虑环长度 在 \([l, l+r)\)之间的\(sg\)值，其对应的链长度有 \(len - l, len - l - 1, len - l - 2, ..., len - r\)。其\(sg\)值就是这些可能的链长度的 \(sg\)值取 \(mex\)。
考虑链长度，小于 \(l\)，是必败态，其 \(sg\)值为 \(0\)。 而\(sg(l) = sg(l + 1) = sg(l + 2) ... = sg(l + l - 1) = 1\)，
\(sg(2l) = mex(sg(l), sg(l - 1), sg(l - 2), ..., sg(1), sg(0)) = mex(1, 0, 0, 0, ..., 0) = 2 = sg(2l + 1) = sg(2l + 2)\)
\(sg(3l) = mex(sg(2l), sg(2l - 1), ..., sg(l), sg(l - 1), ..., sg(0)) = mex(2, 1, ..., 1, 0, ..., 0) = 3 = sg(3l + 1) = sg(3l + 2)\)
上述的\(mex\)里的每一项都是取最边边的结果（即取了之后还有一个链），至于有两条链的结果，是长度更小的两个链的\(sg\)的异或值，其不会超过上面的最大值。
由此（或打表）可以发现长度为\(sg(len) = \lfloor \frac{len}{l} \rfloor(l \leq len < l + r)\)
进而环的 \(sg_c(len) = mex(sg(len - l), sg(len - l - 1), ..., sg(len - r)) = \lfloor \frac{len}{l} \rfloor(l \leq len < l + r)\)
环的\(sg\)值求出来了，异或一下就知道谁赢了。
至于环大小，用并查集或\(BFS\)一下就知道了。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
class dsu {
public:
vector<int> p;
vector<int> sz;
int n;
dsu(int _n) : n(_n) {
p.resize(n);
sz.resize(n);
iota(p.begin(), p.end(), 0);
fill(sz.begin(), sz.end(), 1);
}
inline int get(int x) {
return (x == p[x] ? x : (p[x] = get(p[x])));
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
p[x] = y;
sz[y] += sz[x];
return true;
}
return false;
}
};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, l, r;
cin >> n >> l >> r;
dsu d(n);
for(int i = 0; i < n; ++ i){
int u, v;
cin >> u >> v;
-- u;
-- v;
d.unite(u, v);
}
int ans = 0;
for(int i = 0; i < n; ++ i){
if (d.get(i) == i){
if (d.sz[i] >= l && d.sz[i] < l + r)
ans ^= d.sz[i] / l;
}
}
if (ans)
cout << "Alice" << '\n';
else
cout << "Bob" << '\n';
return 0;
}
F. Random Walk (CF 1823 F)
题目大意
树上随机游走，从点\(s\)到点 \(t\)，问每个点访问次数的期望值。
解题思路
每次的期望题感觉都比较神仙。
注意到这是棵树，点\(s\)到点\(t\)的路径是唯一的，设路径为\(s, u_0, u_1, ..., u_k, t\)。
一开始设状态\(dp[s][v][t]\)表示从 \(s\)点到 \(t\)点，期望访问到 \(v\)号点的次数，然后枚举到相邻点的状态，即\(dp[s][v][t] = \sum_{(s, u) \in E}dp[u][v][t]\)，但感觉怎么都算不出来。
然后想着从点 \(s\)出发，它可以往很多个相邻点走，只有一个点\(u_0\)是更接近点 \(t\)的， 且最终到点\(t\)时立刻停下来，这意味着点\(t\)之后的点的访问次数的期望值一定是 \(0\)。
考虑到一旦走到点\(u_0\)时，发现问题貌似变成了一个子问题了，可以认为是从点\(u_0\)出发，到点 \(t\)的情况。换句话说，我们可以将 点\(s\)到点 \(t\)的步骤分成若干步，分别是点 \(s\)到点 \(u_0\)，点 \(u_0\)到点 \(u_1\)... 点\(u_t\)到点 \(t\)，由于期望的线性可加性，每个点的期望访问次数，可以由这些的每个步骤的影响依次累计。
设 \(dp[s][w]\)表示从 \(s\) 点往更接近点\(t\)的方向走（即走到 \(u_0\)点），对 \(w\)点的期望访问次数。
设点 \(s\)的度数为 \(du_s\)，其余字母定义看图，根据期望定义，可以得到：
这里有三个部分：
- 有\(\frac{1}{du_s}\)的概率选择走到 \(u_0\)，然后就停下来了，此时对 \(v\)的访问贡献是\(0\)。
- 有\(\frac{1}{du_s}\)的概率往 \(w\)所在的子树走（即点 \(x\)），此时对\(w\)的访问贡献是由\(x \to s\)和\(s \to u_0\)组成，即 \(dp[x][w] + dp[s][w]\)。
- 有\(\frac{du_s - 2}{du_s}\)的概率往其他子树走（即点 \(y\)表示的其他所有点），此时对\(w\)的访问贡献是由\(y \to s\)和\(s \to u_0\)组成，即 \(dp[y][w] + dp[s][w]\)。但由于从点\(y\)到点\(w\)必须经过点 \(s\)，而一旦到点 \(s\)就会停下来（ \(dp[y][w]\)即表示从点 \(y\)到更接近 点\(t\)的方向走（即往点 \(s\)），对点 \(w\)的访问贡献），因此 \(dp[y][w] = 0\)。
这样上述式子移一下项，就得到
即点\(s\)往点 \(u_0\)走时的对点\(w\)访问次数的贡献是等价于点 \(x\)往点 \(s\)走时，对点 \(w\)的贡献。由此就可以得到
剩下的就是求 \(dp[w][w]\)。根据期望定义，可以得到
这里有两部分：
- 有\(\frac{1}{du_s}\)的概率选择走到 \(u_0\)，此时就停下来了，因此对\(s\)的访问贡献是\(1\)（一开始在\(s\)时的贡献）。
- 有\(\frac{du_s - 1}{du_s}\)的概率选择走到除点\(u_0\)之外的其他点(设点\(o\)，即 \(x\)或 \(y\))，因此对\(s\)的访问贡献是\(o \to s\)和 \(s \to s\)，即\(dp[o][s] + dp[s][s]\)，而因为点\(o\)到点 \(s\)就会停下来（点 \(s\)是更接近点 \(t\)的点），因此 \(dp[o][s] = 1\)（一开始在\(s\)时的贡献包含在 \(dp[s][s]\)里）。
这样上述式子移一下项，就得到
综合上述的两个式子\(dp[s][w] = dp[w][w] = du_w\)，可以得出，每当进行一次 \(s \to u_0, u_0 \to u_1,\cdots, u_k \to t\) 时，其他点\(w\)的期望访问次数都会增加 \(du_w\)，其中点\(w\)是点 \(s\)除了 \(u_0\)方向的其他方向的点（见上图的虚线包括起来，就是对应颜色的箭头的影响）。
也就是说一个点\(a\)的期望访问次数就是\(du_a \times cnt_a\)，其中 \(cnt_a\)等于该点与路径\(s \to t\)的交点（以上图为例，就为 \(u_{k-1}\)）到 \(t\)的点数（见上图的点\(a\)）。
剩下的就是如何求 \(cnt_w\)，我们可以以点 \(s\)为根，然后我们从点 \(t\)开始，一路沿着 父亲节点上去，就回到点\(s\)，其中每往父亲跳一次时， \(cnt_w\)就会加一，比如从\(t \to u_k\)时， \(cnt = 0 + 1 = 1\)，此时再遍历一下除了\(t\)和 \(u_{k - 1}\)方向的所有点 \(w\)，它们的答案就是 \(du_w \times cnt\) 。
最终的时间复杂度是\(O(n)\)。
虽然答案不会超过\(n^2\)，但记得对\(998244353\)取模。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mod = 998244353;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, s, t;
cin >> n >> s >> t;
-- s, -- t;
vector<vector<int>> edge(n);
vector<int> du(n);
for(int i = 1; i < n; ++ i){
int u, v;
cin >> u >> v;
-- u, -- v;
edge[u].push_back(v);
edge[v].push_back(u);
++ du[u];
++ du[v];
}
vector<int> fa(n);
function<void(int, int)> dfs = [&](int u, int f){
fa[u] = f;
for(auto &v : edge[u]){
if (v == f)
continue;
dfs(v, u);
}
};
dfs(s, s);
vector<int> ans(n);
int cnt = 1;
ans[t] = 1;
function<void(int, int, int)> dfs2 = [&](int u, int f, int cnt){
ans[u] = 1ll * du[u] * cnt % mod;
for(auto &v : edge[u]){
if (v == f)
continue;
dfs2(v, u, cnt);
}
};
do{
int cur = fa[t];
ans[cur] = 1ll * cnt * du[cur] % mod;
for(auto &u : edge[cur]){
if (u != fa[cur] && u != t)
dfs2(u, cur, cnt);
}
t = cur;
++ cnt;
}while(s != t);
for(auto &i : ans)
cout << i << ' ';
cout << '\n';
return 0;
}