近期模拟赛
A. 考试
http://222.180.160.110:61235/contest/6624/problem/1
\(m\) 道题，分数是一个 \(m\) 的排列（初始未知），做对得满分，做错得 0 分
给定 \(n\) 个人对于这 \(m\) 个题的过题情况矩阵，且第 \(i\) 个人有一个预期分数 \(x_i\)。
求每到题的分数，使得每个人实际得分与期望的分差的绝对值之和最大。输出该排列。
\(n\le 10,m\le 10^4\)。
- 绝对值是贪心一个很大的阻碍
一个典型的『钦定』型贪心，枚举每个人的绝对值是否取反，就可以得到每个题对应的系数。
因为『就算错了也不会影响最优解』，所以是对的。
#include <bits/stdc++.h>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("test.in", "r", stdin);
std::freopen("test.out", "w", stdout);
int T;
for (std::cin >> T; T--; ) {
int n, m;
std::cin >> n >> m;
std::vector<int> s(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> s[i];
std::vector<std::vector<int> > pos(n + 1);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
char t;
std::cin >> t;
if (t == '1')
pos[i].push_back(j);
}
auto res = 0ll;
int siz = 1 << n;
std::vector<std::vector<int> > id(2 * n + 1);
std::vector<int> cnt(m + 1), ans(m + 1), p(m + 1);
for (int i = 0; i < siz; ++i) {
std::fill(cnt.begin() + 1, cnt.end(), 0);
for (int j = 0; j <= 2 * n; ++j)
id[j].clear();
for (int j = 1; j <= n; ++j)
if ((i >> (j - 1)) & 1)
for (auto k : pos[j])
++cnt[k];
else
for (auto k : pos[j])
--cnt[k];
for (int j = 1; j <= m; ++j)
id[cnt[j] + n].push_back(j);
for (int i = 2 * n, k = m; ~i; --i)
for (auto j : id[i])
p[j] = k--;
auto now = 0ll;
for (int i = 1; i <= n; ++i) {
int sum = 0;
for (auto j : pos[i])
sum += p[j];
now += std::abs(sum - s[i]);
}
if (now >= res)
res = now, ans = p;
}
// std::cout << res << '\n';
for (int i = 1; i <= m; ++i)
std::cout << ans[i] << ' ';
std::cout << '\n';
}
return 0;
}B. 围棋
http://222.180.160.110:61235/contest/6624/problem/2
给定 \(n \times n\) 的棋盘，上面有黑棋、白棋和空地，定义白棋的『气』为四个方向空地的数量，若一个白棋四连通块中所有白棋的『气』都为 0，则认为这个白棋四连通块中的所有白棋是『死的』。
现枚举每个棋子，并将其反转颜色，问『死的』白棋数量。操作是独立的。
3s，\(n\le 10^3\)。
- 分讨题，需要想清楚。首先需要一次 floodfill 完成染色，记录哪些连通块死了。
若反转黑棋：
若黑棋自己有气，或和黑棋相连的白棋四连通块有气，那么黑棋自己，以及所有和黑棋相连的白棋四连通块都是活的。
此时需要找到所有和黑棋相连的，且死了的白棋四连通块的大小，答案需要减去之。
否则，黑棋自身贡献 \(1\) 的答案。
若反转白棋：
- 若白棋本身是死的：答案 \(-1\)。
否则，需要考虑有多少个原本是活的白棋此时与有气的白棋不连通，这种情况发生当且仅当有气的白棋是被反转的白棋自身，或者被反转的白棋是割点。
很奇妙的一个想法是建立超级源点，向所有空地连边，再建圆方树，这样这个点的所有儿子就是待求。圆方树并不需要显式地建出来。
代码：不会
C. 相互抵消
https://www.becoder.com.cn/contest/6624/problem/3
给定 \(a_{1\sim n}\)，维护 \(m\) 次操作：
- 区间加。
- 给定 \(l,r\)，查询 \(\left(\sum\limits_{i=l}^r\sum\limits_{j=i}^r ((\sum_{k=i}^j a_k)^2 + (r-l+2)\times(j-i)\times a_i\times a_j)\right) \bmod 998244353\)。
\(n,m\le 5\times 10^5\)，强制在线。
- 题目名字是真在降低难度吧，强制在线就排除离线历史和了；猜测询问所求可以化成一个比较简单的东西。
推一下：
（省略）
\[ =-\left(\sum_{i=l}^r i\cdot a_i\right)^2 + (1-l)(r+1)\left(\sum_{i=l}^r a_i\right)^2+(l+r)\left(\sum_{i=l}^r i\cdot a_i\right)\left(\sum_{i=l}^r a_i\right) \]
- 故线段树维护 \(\sum a_i\) 和 \(\sum i\cdot a_i\) 即可。
喜提最优解，不得不说 bit 的速度优势还是很明显的。
#include <bits/stdc++.h>
const int mod = 998244353;
const int inv2 = (mod + 1) >> 1;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("offset.in", "r", stdin);
std::freopen("offset.out", "w", stdout);
#else
std::freopen("./test/20251008/offset/ex_offset5.in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int T, n, q;
std::cin >> T >> n >> q;
std::vector<long long> bit(n + 1), bit1(n + 1), bit2(n + 1);
auto lowbit = [&](int x) {
return x & -x;
};
auto add = [&](long long x, long long v) {
auto v1 = x * v % mod, v2 = x * x % mod * v % mod;
for (; x <= n; x += lowbit(x)) {
(bit[x] += v) %= mod;
(bit1[x] += v1) %= mod;
(bit2[x] += v2) %= mod;
}
return;
};
auto ask = [&](long long x) {
auto res = 0ll, res1 = 0ll, res2 = 0ll;
for (int i = x; i; i -= lowbit(i))
(res += bit[i]) %= mod, (res1 += bit1[i]) %= mod, (res2 += bit2[i]) %= mod;
return std::make_pair(((x + 1) * res + mod - res1) % mod, (x * (x + 1) % mod * res % mod + res1 + mod - res2) * inv2 % mod);
};
for (int i = 1, x; i <= n; ++i)
std::cin >> x, add(i, x), add(i + 1, mod - x);
for (int op; q--; ) {
static auto la = 0ll;
std::cin >> op;
if (op == 1) {
int l, r, d;
std::cin >> l >> r >> d;
if (T == 1)
l ^= la, r ^= la, d ^= la;
add(l, d), add(r + 1, mod - d);
}
else {
long long l, r;
std::cin >> l >> r;
if (T == 1)
l ^= la, r ^= la;
auto t1 = ask(r), t2 = ask(l - 1);
auto res1 = t1.first + mod - t2.first, res2 = t1.second + mod - t2.second;
la = (mod - res2 * res2 % mod + mod - (l - 1) * (r + 1) % mod * res1 % mod * res1 % mod + (l + r) * res1 % mod * res2 % mod) % mod;
std::cout << la << '\n';
}
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}A. Happy·Lovely·Everyday!
https://www.becoder.com.cn/contest/6639/problem/1
给定一个长为 \(n\) 的 01 序列，可以执行任意次（可以为 \(0\)）『把相邻两个数合并为其异或值』的操作，问最终能得到的本质不同的序列个数。
\(n\le 2\times 10^6\)。
- 对于一个最终序列，如果认为它是由某个存活元素『吞并』它左侧的连续死亡元素得到的，会发现最终序列中，此处的前缀异或值就是原序列的前缀异或值。
- 经典 trick：前缀和可以唯一对应原数组。所以『最终本质不同序列』会和『包含第 \(n\) 个元素的，原序列前缀异或和的本质不同子序列』形成双射。
统计包含第 \(n\) 个元素的，原序列前缀异或和的本质不同子序列即可。复杂度 \(O(n)\)。
How to 本质不同子序列？
令 \(f_i\) 表示 DP 到 \(i\)，且强制选 \(i\) 的本质不同子序列数量，记 \(pre_i\) 为 \(i\) 的前驱（没有则为 \(0\)）。令 \(f_0=1\)，那么：
\[ f_i\gets \sum\limits_{j=pre_i}^{i-1} f_{j} \]
或，令 \(f_i\) 表示 DP 到 \(i\) 时（不强制选 \(i\)）本质不同子序列数量，记 \(pre_i\) 为 \(i\) 的前驱（没有则为 \(0\)）。令 \(f_0=0\)，那么：
\[ f_i=\begin{cases} 2\cdot f_{i-1}+1&pre_i= 0\\ 2\cdot f_{i-1}-f_{pre_i-1}&\text{otherwise} \end{cases} \]
How to 强制选第 \(n\) 个元素的本质不同子序列？
令 \(f_i\) 表示 DP 到 \(i\)，且强制选 \(i\) 的本质不同子序列数量，则答案为：
\[ \sum\limits_{a_i=a_n} f_i \]
或，令 \(f_i\) 表示 DP 到 \(i\)，且不强制选 \(i\) 的本质不同子序列数量，则答案为：
\[ \sum\limits_{a_i=a_n}\begin{cases} f_{i-1}+1&pre_i= 0\\ f_{i-1}-f_{pre_i-1}&\text{otherwise} \end{cases} \]
#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("a.in", "r", stdin);
std::freopen("a.out", "w", stdout);
#else
std::freopen("./test/20251014/a/a1.in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int T;
for (std::cin >> T; T--; ) {
std::string s;
std::cin >> s;
int n = (int)s.length();
s = "#" + s;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i)
a[i] = a[i - 1] ^ (s[i] - '0');
auto res = 0ll;
std::vector<long long> f(n + 1), la(2);
for (int i = 1; i <= n; ++i) {
if (la[a[i]])
f[i] = (2 * f[i - 1] + mod - f[la[a[i]] - 1]) % mod;
else
f[i] = (2 * f[i - 1] + 1) % mod;
if (a[i] == a[n]) {
if (la[a[i]])
res += (f[i - 1] + mod - f[la[a[i]] - 1]) % mod;
else
res += f[i - 1] + 1;
}
la[a[i]] = i;
}
std::cout << res % mod << '\n';
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}B. 敬启，致那时的我
https://www.becoder.com.cn/contest/6639/problem/2
定义 \(f_0=f_1=1,f_i=f_{i-1}+f_{i-2}\)，给定 \(n,k\)，求：
\[ \left(\sum_{i=0}^n f_{i}\cdot [\text{popcount}(i)=k]\right)\bmod 10^9+7 \]
\(n\le 2^{2000},0\le k\le \log_2(n)\)。
- 考虑数位 DP，那么需要能够由
...xxx向...0xxx和...1xxx转移。 显然只关心向
...1xxx的转移，那么需要再转移 \(2^{?}\) 次，记录转移矩阵的 \(2^{?}\) 次方即可。这一步也可以不用矩阵，而是用斐波那契 \(f(ab)=...\) 的性质，但显然二者是等价的，无甚必要
根据数位 DP 的实现方式，常数上顺序结构肯定是会吊打递归的。然而并不惯写顺序结构的数位 DP，whatever.
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
struct matrix {
long long a[2][2];
matrix() {
a[0][0] = a[0][1] = a[1][0] = a[1][1] = 0ll;
return;
}
long long* operator[] (const int q) {
return a[q];
}
matrix operator* (matrix &q) const {
matrix res;
res[0][0] = (a[0][0] * q[0][0] + a[0][1] * q[1][0]) % mod;
res[0][1] = (a[0][0] * q[0][1] + a[0][1] * q[1][1]) % mod;
res[1][0] = (a[1][0] * q[0][0] + a[1][1] * q[1][0]) % mod;
res[1][1] = (a[1][0] * q[0][1] + a[1][1] * q[1][1]) % mod;
return res;
}
matrix& operator+= (matrix q) {
if ((a[0][0] += q[0][0]) >= mod) a[0][0] -= mod;
if ((a[0][1] += q[0][1]) >= mod) a[0][1] -= mod;
if ((a[1][0] += q[1][0]) >= mod) a[1][0] -= mod;
if ((a[1][1] += q[1][1]) >= mod) a[1][1] -= mod;
return *this;
}
};
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("b.in", "r", stdin);
std::freopen("b.out", "w", stdout);
#else
std::freopen("./test/20251014/b/b4.in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
int n, k;
std::cin >> n >> k;
std::vector<int> up(n);
for (int i = 1; i <= n; ++i) {
char t;
std::cin >> t, up[n - i] = t - '0';
}
matrix init, zmat;
init[0][0] = init[0][1] = 1ll;
std::vector<matrix> mat(n);
mat[0][0][1] = mat[0][1][0] = mat[0][1][1] = 1ll;
for (int i = 1; i < n; ++i)
mat[i] = mat[i - 1] * mat[i - 1];
std::vector<std::vector<int> > tag(n, std::vector<int> (k + 1));
std::vector<std::vector<matrix> > f(n, std::vector<matrix> (k + 1));
std::function<matrix(int, int, int)> DFS = [&](int x, int k, int fl) {
if (x == -1) {
if (k == 0)
return init;
return zmat;
}
if (!fl && tag[x][k])
return f[x][k];
matrix res = DFS(x - 1, k, fl && !up[x]);
if (k && (!fl || up[x]))
res += DFS(x - 1, k - 1, fl) * mat[x];
if (!fl)
tag[x][k] = 1, f[x][k] = res;
return res;
};
std::cout << DFS(n - 1, k, 1)[0][0] << '\n';
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}C. Lead to shine more
https://www.becoder.com.cn/contest/6639/problem/3
第 \(0\) 次操作时变量 \(x=1\)，此后每次操作使 \(x\gets x+\text{popcount}(x)\)，给定 \(m\) 次询问：
- 给定 \(x'\)，问 \(x\) 在第几次操作后变为 \(x'\)，或报告 \(x'\) 不会被经过。
\(m\le 10^5,x'\le 10^{18}\)。
- 一个朴素的想法是分高低位，则因为每次操作带来的变化量不超过 60，远远低于低位的 \(2^30\)，所以一次操作至多给高位带来 1 的变化量。
高位对整体的贡献只取决于其 popcount，所以可以枚举高位 1 的数量，再枚举初始值，找到第一次让高位变化花的次数。
初始值的可能值有 \(60\) 个，而外层循环有 \(30\) 次，内层循环大概是 \(\dfrac {2^{30}}{60}\) 的，总之无法通过。
题解说方法是对上面的拓展。理解不能。出发点大概是考虑到让第 \(i\) 位变化相当于让 \(i+1\) 位变化两次，所以会有一个递推的关系。
令 \(f_{i, s, d}\) 为前 \(i-1\) 位的 popcount 为 \(d\)，初始值为 \(s\)，让 \(i\) 位变化一次的操作次数；\(g_{i,s,d}\) 为上述变化后 \(x\) 的值。记 \(pos=g_{i-1,s,d}\)，那么有：
\[ g_{i,pos,d}=g_{i-1,pos,d+1}\\ f_{i,pos,d}=f_{i-1,s,d}+f_{i-1,pos,d+1} \]
其实是一个类似倍增的结构。但恕我实在无法解释怎么想到的。
- 显然这个式子在 \(i\le 5\) 时是有问题的，这部分我们暴力跑即可。忽略这一部分常数，预处理总复杂度 \(O(\log^3 n)\)。
考虑查询，按照类似数位 DP 的方法从高位到低位模拟进位过程即可。复杂度 \(O(\log n)\)。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("c.in", "r", stdin);
std::freopen("c.out", "w", stdout);
#else
std::freopen("./test/20251014/c/c1.in", "r", stdin);
std::freopen(".out", "w", stdout);
const auto stime = std::chrono::steady_clock::now();
#endif
using arr = std::vector<long long>;
using brr = std::vector<arr>;
using crr = std::vector<brr>;
crr f(61, brr(256, arr(61))), g(61, brr(256, arr(61)));
for (int s = 0; s < 256; ++s)
for (int d = 0; d <= 60; ++d)
if (d || s) {
int x = s, cnt = 0;
for (; x < 256; x += __builtin_popcount(x) + d, ++cnt);
f[8][s][d] = cnt, g[8][s][d] = x & 255;
}
for (int i = 9; i <= 60; ++i)
for (int s = 0; s < 256; ++s)
for (int d = 0; d < 60; ++d) {
int pos = g[i - 1][s][d];
g[i][s][d] = g[i - 1][pos][d + 1];
f[i][s][d] = f[i - 1][s][d] + f[i - 1][pos][d + 1];
}
int m;
std::cin >> m;
for (long long x; m--; ) {
std::cin >> x;
auto pos = 1ll, cnt = 0ll, tot = 0ll;
for (int i = 60; i >= 8; --i)
if ((x >> i) & 1) {
cnt += f[i][pos][tot];
pos = g[i][pos][tot++];
}
for (; pos < (x & 255); pos += __builtin_popcountll(pos) + tot, ++cnt);
// std::cout << pos << ' ' << cnt << '\n';
if (pos == (x & 255))
std::cout << cnt << '\n';
else
std::cout << -1 << '\n';
}
#ifndef ONLINE_JUDGE
std::cerr << std::fixed << std::setprecision(6) << std::chrono::duration<double> (std::chrono::steady_clock::now() - stime).count() << "s\n";
#endif
return 0;
}C. Query On A Tree 17
https://codeforces.com/gym/102759/problem/I
给定一个以 \(1\) 为根的树，点权初始为全 \(0\)。维护 \(m\) 次修改：
1 u，表示把 \(u\) 子树内的点权加一。2 u v，表示把 \(u,v\) 简单路径上的点权加一。每次修改后，输出树深度最小的带权重心。
\(n,m\le 10^5\)。
考虑链上的问题，考虑一点小奥做法，把所有点重复其出现次数次，从左到右排列，发现答案在中位数上。
（据组题人所言），这是用来提示正解的。事实上，这是一个和带权重心有关的 trick：
若一个点 \(u\) 是深度最小的带权重心，则其子树权值和必须严格大于总权值的一半。
证明显然，但结论不显然。Whatever.
由这一点会得到，（参照链上的做法），把点重复点权次，并按 dfn 排成一行，取中位数，那么取到的一定在深度最小的重心子树内，（这就是组题人说的提示正解）。
这一点反而没那么显然，推导过程是，深度最小的重心的子树占了大于一半，而其 dfn 又是连续的，（类似滑动窗口），故总能够到中位数。
考虑非深度最小的重心，此时就从严格大于变为不严格大于，导致没有办法很好地精准找到，需要从中位数左右偏移一位，显然是很丑陋的。
因此可以考虑线段树上二分找到中位数（容易发现线段树的 \(x\) 轴本来就是 dfn），然后从这个中位数往上跳，一直跳到满足『子树权值和严格大于总权值一半』的点，就是最浅的重心。
这一点采用倍增即可。