A 小红的整数操作
这也是题？
知识点： 分类讨论、绝对值判断
题目只做一次操作，$x$ 只能变成 $x+d$ 或 $x-d$，因此能否得到 $y$ 的充要条件就是 $|x-y|=d$ 。直接判断即可。
时间复杂度 $\mathcal{O}(1)$。
void solve() {
int x, y, d;
cin >> x >> y >> d;
cout << (abs(x - y) == d ? "Yes" : "No") << endl;
}B 小红砍小苯
知识点： 贪心、最大值分类
每一刀都会让所有仍存活的小苯同时少 $1$ ，所以总分只和“最后还剩几只、最大血量是否唯一”有关。设 $sum$ 为总血量，$mx$ 为最大值，$sec$ 为次大值，$c$ 为最大值出现次数。
- 如果 $n=1$，直接结束，答案为 $0$ 。
- 如果 $mx$ 出现至少两次，那么这些最大值会一起死掉，不存在“只剩一个人还要多砍”的情况，答案就是 $sum$ 。
- 如果 $mx$ 只出现一次，那么当其他小苯都死掉时还会剩下这一个最大值，它还会剩下 $mx-sec$ 点血，最后答案为 $sum-(mx-sec)$ 。
时间复杂度 $\mathcal{O}(n)$。
void solve() {
int n, sum = 0, mx = 0, sec = 0, c = 0;
cin >> n;
for (int i = 0, x; i < n; ++i) {
cin >> x;
if (x > mx)
sec = mx, mx = x, c = 1;
else if (x == mx)
c++;
else if (x > sec)
sec = x;
sum += x;
}
if (n == 1) return cout << 0 << endl, void();
cout << sum - (c > 1 ? 0 : c * (mx - sec)) << endl;
}C 异或或配对计数
知识点： 按位拆分、位运算、乘法原理
对每一位单独考虑 $(p_i, q_i)$ 的取值：
- 若 $y$ 的这一位是 $0$ ，则 $p_i=q_i=0$ ，所以 $x$ 的这一位也必须是 $0$ ，否则无解。
- 若 $y$ 的这一位是 $1$ ：
- $x_i=1$ 时，只能是 $(1,1)$ ，只有 $1$ 种；
- $x_i=0$ 时，只能是 $(0,1)$ 或 $(1,0)$ ，有 $2$ 种。
由于每一位的情况独立，所以枚举每一位计算方案数即可。
时间复杂度 $\mathcal{O}(\log V)$ 。
void solve() {
int x, y;
cin >> x >> y;
int ans = 1;
for (int i = 0; i <= 32; ++i, x >>= 1, y >>= 1) {
int a = x & 1, b = y & 1;
if (b) {
if (a) ans <<= 1;
} else {
if (a) return cout << 0 << endl, void();
}
}
cout << ans << endl;
}D 小红的正方形
有点屎
知识点： 几何、分类讨论、线段相交、去重
一个与坐标轴平行的正方形，可以拆成 $4$ 条边，两个正方形一共只有 $16$ 对边需要检查。每一对边只有三种情况：
- 两条竖边或两条横边，若共线且重叠长度大于 $0$ ，则交点无穷多个，直接输出 $inf$ ；若只碰一个端点，就把这个点加入答案集合。
- 一条竖边一条横边，只需判断横纵坐标是否都落在对方线段范围内，若是则得到一个交点。
由于不同边对可能得到同一个点，最后用集合去重即可。
时间复杂度 $\mathcal{O}(1)$。
struct E {
int x1, y1, x2, y2;
bool v() const {
return x1 == x2;
}
};
void solve() {
auto read = [&]() {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int lx = min(x1, x2), rx = max(x1, x2);
int ly = min(y1, y2), ry = max(y1, y2);
return array<E, 4>{E{lx, ly, rx, ly}, E{lx, ry, rx, ry}, E{lx, ly, lx, ry}, E{rx, ly, rx, ry}};
};
auto A = read(), B = read();
set<pii> s;
for (auto a : A)
for (auto b : B)
if (a.v() && b.v()) {
if (a.x1 != b.x1) continue;
int l = max(a.y1, b.y1), r = min(a.y2, b.y2);
if (l > r) continue;
if (l < r) return cout << "inf" << endl, void();
s.insert({a.x1, l});
} else if (!a.v() && !b.v()) {
if (a.y1 != b.y1) continue;
int l = max(a.x1, b.x1), r = min(a.x2, b.x2);
if (l > r) continue;
if (l < r) return cout << "inf" << endl, void();
s.insert({l, a.y1});
} else {
auto check = [&](E a, E b) { return a.x1 <= b.x1 && b.x1 <= a.x2 && b.y1 <= a.y1 && a.y1 <= b.y2; };
if (check(a, b)) s.insert({b.x1, a.y1});
if (check(b, a)) s.insert({a.x1, b.y1});
}
cout << s.size() << endl;
}E 小红的异或和
知识点： 前缀异或和性质
由于好数是 $x$ 的倍数，不妨令 $L = \lceil\frac{l}{x}\rceil, R = \lfloor\frac{r}{x}\rfloor$ ，则区间内的好数为
$$Lx, (L+1)x, \cdots, Rx$$
由于好数是 $2$ 的幂的倍数，所以在计算异或和的时候，后 $k$ 一定均为 $0$ ，我们只需要考虑剩余的有效位，所以答案可以改写为
$$ans = \bigoplus\limits_{i=L}^{R} ix = (\bigoplus_{i=L}^{R}i) << k = (F(R)\oplus F(L-1)) << k$$
其中，$F(x) = \bigoplus\limits_{i=1}^{x} i$ 。
而 $1\sim x$ 的异或有以下结论（证明见文章末尾）
$$F(n) = \begin{cases}n&,n=0\pmod 4\\1&,n=1\pmod 4\\n+1&,n=2\pmod 4\\0&,n=3\pmod 4\end{cases}$$
直接求解即可。
时间复杂度 $\mathcal{O}(1)$。
void solve() {
int l, r, x;
cin >> l >> r >> x;
int k = __lg(x);
auto F = [&](int n) {
switch (n & 3) {
case 0:
return n;
case 1:
return 1LL;
case 2:
return n + 1;
default:
return 0LL;
}
};
cout << ((F(r / x) ^ F((l + x - 1) / x - 1)) << k) << endl;
}F 小红的最长子序列
加了路径还原就是一大坨
知识点： 线性 $\texttt{DP}$、路径还原、模意义下拼接
对子序列 $b$ ，要满足
$$\left(\sum b_i\right)\bmod m = S\bmod m$$
其中 $S$ 是把 $b$ 顺序拼接得到的整数。关键是把这两个量都看成模 $m$ 下的状态：
- $s$ 表示模 $m$ 意义下当前选出的数之和；
- $c$ 表示模 $m$ 意义下当前顺序拼接后的值。
加入一个新数 $a_i$ 时：
$$s’=(s+a_i)\bmod m,\qquad c’=(c\cdot 10^{len_i}+a_i)\bmod m.$$
于是设 $f[i][s][c]$ 表示只看前 $i$ 个数时，能选出的最长长度。每个数只有“选”或“不选”两种转移，转移完后在所有满足 $s=c$ 的状态里取最大值即可。
恢复方案时，只需要检查 $i-1$ 的哪个值可以推出当前为的值即可。
时间复杂度 $\mathcal{O}(nm^2)$。
void solve() {
int n, m;
cin >> n >> m;
vector<int> p(11, 1 % m);
for (int i = 1; i < 11; ++i) p[i] = p[i - 1] * 10 % m;
vector<int> a(n + 1), len(n + 1);
for (int i = 1; i <= n; ++i) cin >> a[i], len[i] = to_string(a[i]).size();
vector<array<array<int, 201>, 201>> dp(n + 1);
for (auto &v : dp[0]) v.fill(-1);
dp[0][0][0] = 0;
for (int i = 1; i <= n; ++i) {
dp[i] = dp[i - 1];
for (int s = 0; s < m; ++s) {
for (int c = 0; c < m; ++c) {
if (dp[i - 1][s][c] < 0) continue;
int ns = (s + a[i]) % m, nc = (c * p[len[i]] + a[i]) % m;
dp[i][ns][nc] = max(dp[i][ns][nc], dp[i - 1][s][c] + 1);
}
}
}
int mx = 0, loc = -1;
for (int i = 0; i < m; ++i)
if (dp[n][i][i] > mx) mx = dp[n][i][i], loc = i;
vector<int> ans;
int s = loc, c = loc;
auto find = [&](int i, int S, int C) -> pii {
for (int s = 0; s < m; ++s)
for (int c = 0; c < m; ++c)
if ((s + a[i]) % m == S && (c * p[len[i]] + a[i]) % m == C && dp[i - 1][s][c] + 1 == dp[i][S][C]) return {s, c};
return {-1, -1};
};
for (int i = n; i >= 1; --i) {
if (dp[i][s][c] == dp[i - 1][s][c]) continue;
auto [ps, pc] = find(i, s, c);
ans.push_back(i);
s = ps, c = pc;
}
reverse(ans.begin(), ans.end());
cout << ans.size() << endl;
for (auto v : ans) cout << a[v] << " ";
cout << endl;
}约定
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii array<int, 2>
#define endl "\n"
void solve() {
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(20);
int t = 1;
cin >> t;
for (int i = 0; i < t; ++i) {
solve();
}
return 0;
}对于前缀异或和的证明
对于每个四元组 $(4k,4k+1,4k+2,4k+3)$ ，将其两两分组 $(4k,4k+1),(4k+2,4k+3)$ ，组内两个数只差最后一位，所以每组的异或均为 $1$ ，所以四元组的异或和为 $0$ 。
我们不妨将整个式子异或上 $0$ ，即序列为 $0,1,2,\cdots,n$，设 $n = 4k + c$ ，前 $k$ 个四元组（第一组为 $(0,1,2,3)$）的异或和为 $0$ ，只需要考虑最后的 $c+1$ 个元素即可。
- 当 $c = 0$ ，答案为 $n$ 。
- 当 $c = 1$ ，答案为 $n-1\oplus n = 1$ 。
- 当 $c = 2$ ，答案为 $n\oplus 1$ ，由于 $n$ 为偶数，所以 $n\oplus1=n+1$。
- 当 $c = 3$ ，恰好为 $k+1$ 个四元组，答案为 $0$ 。
虽然 $n\oplus1$ 和 $n+1$ 的性能几乎没有差别，但是写成 $n+1$ 有利于部分题目的化简，故这里也使用 $n+1$ 的写法。