A ⑨ 勤
知识点：区间交、构造
两人的 $\mathrm{COMBO}$ 分别为 $a,b$，只需要让两段连续命中区间尽量错开。长度分别为 $a,b$ 的两个区间放在长度 $n$ 的序列中，最小必然重叠为：
$$
\max(0,a+b-n)
$$
当 $a+b\le n$ 时可以完全错开，否则至少重叠 $a+b-n$ 个位置，并且直接贴两端放置即可达到。
时间复杂度 $\mathcal{O}(1)$。
void solve() {
int n, a, b;
cin >> n >> a >> b;
cout << max(0LL, a + b - n) << endl;
}B ⑨ 数
知识点：构造、十进制性质
令 $y=x-9$。如果 $y$ 本身含有数字 $9$，直接输出 $9$ 和 $y$。否则由于 $x\ge 99$，有 $y\ge 90$，设 $r=y\bmod 10$，可以构造：
$$
a=90+r,\quad b=x-a
$$
其中 $a$ 的十位是 $9$，而 $b$ 的个位是 $9$，所以二者都是合法的「⑨ 数」。
时间复杂度 $\mathcal{O}(1)$。
void solve() {
int x;
cin >> x;
int y = x - 9;
if (y % 10 == 9) {
cout << 9 << " " << y << endl;
} else {
int a = 90 + y % 10;
cout << a << " " << x - a << endl;
}
}C ⑨ 积
知识点：数论、分类讨论
乘积是 $9$ 的倍数，等价于存在一个数是 $9$ 的倍数，或至少有两个数是 $3$ 的倍数。因此对每个 $a_i$ 分别计算它变成下一个 $9$ 的倍数的代价，以及变成下一个 $3$ 的倍数的代价。
答案就是单个数补到 $9$ 的最小代价，和两个数分别补到 $3$ 的最小总代价，两者取最小。
时间复杂度 $\mathcal{O}(n)$。
void solve() {
const int inf = 2e18 + 9;
int n;
cin >> n;
int ans = inf, mn1 = inf, mn2 = inf;
for (int i = 0; i < n; ++i) {
int a;
cin >> a;
ans = min(ans, (9 - a % 9) % 9);
int x = (3 - a % 3) % 3;
if (x < mn1) {
mn2 = mn1, mn1 = x;
} else if (x < mn2) {
mn2 = x;
}
}
cout << min(ans, mn1 + mn2) << endl;
}#
D ⑨ 战
知识点：栈、博弈、消去模型
把每个数只看作模 $9$ 的余数，能删除的相邻对满足二者互为相反数。这个过程等价于括号匹配式的相邻消去，最终消去次数的奇偶性是固定的，所以胜负只由总操作次数奇偶决定。
用栈从左到右扫描：若当前数能和栈顶相消，就弹出栈顶并翻转一次奇偶；否则入栈。若最终消去次数为奇数，先手胜，否则后手胜。
时间复杂度 $\mathcal{O}(n)$。
void solve() {
int n;
cin >> n;
vector<int> st;
int f = 0;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
if (!st.empty() && (st.back() + x) % 9 == 0) st.pop_back(), f ^= 1;
else st.push_back(x);
}
cout << (f ? "Yes" : "No") << endl;
}E ⑨ 串
知识点：循环同余、DP、分类讨论
一个长度为 $9$ 的十进制数能被 $9$ 整除，只和数字和模 $9$ 有关。相邻两个长度为 $9$ 的循环窗口都要满足和为 $0$，两式相减可得：
$$
s_i \equiv s_{i+9}\pmod 9
$$
因此位置会按 $g=\gcd(n,9)$ 分组，同组位置最终必须改成同一个模 $9$ 余数。再保证任意一个窗口的 $9$ 个余数和为 $0$ 即可。
- $g=1$：所有位置同余，任选出现次数最多的余数。
- $g=3$：只需三组余数和模 $3$ 为 $0$，枚举三组的模 $3$。
- $g=9$：九组余数和模 $9$ 为 $0$，做一遍 DP。
令 $dp_j$ 表示已经确定前若干组后，当前选出的余数之和模 $9$ 为 $j$ 的最小修改次数。处理第 $i$ 组时，若把这一组全部改成余数 $k$，代价就是 $\text{siz}i-\text{cnt}{i,k}$，于是有转移：
$$
ndp_{(j+k)\bmod 9}=\min(ndp_{(j+k)\bmod 9},dp_j+\text{siz}i-\text{cnt}{i,k})
$$
最后 $dp_0$ 就是九组余数和为 $0$ 的最小代价。
时间复杂度 $\mathcal{O}(n)$。
void solve() {
const int inf = 2e18 + 9;
int n;
string s;
cin >> n >> s;
int g = __gcd(n, 9LL);
vector<vector<int>> cnt(g, vector<int>(9));
vector<int> siz(g);
for (int i = 0; i < n; ++i) {
siz[i % g]++;
cnt[i % g][(s[i] - '0') % 9]++;
}
if (g == 1) {
int mx = 0;
for (int i = 0; i < 9; ++i) mx = max(mx, cnt[0][i]);
cout << siz[0] - mx << endl;
} else if (g == 3) {
vector<vector<int>> cost(3, vector<int>(3, inf));
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 9; ++j)
cost[i][j % 3] = min(cost[i][j % 3], siz[i] - cnt[i][j]);
int ans = inf;
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 3; ++j)
for (int k = 0; k < 3; ++k)
if ((i + j + k) % 3 == 0)
ans = min(ans, cost[0][i] + cost[1][j] + cost[2][k]);
cout << ans << endl;
} else {
vector<int> dp(9, inf);
dp[0] = 0;
for (int i = 0; i < 9; ++i) {
vector<int> ndp(9, inf);
for (int j = 0; j < 9; ++j)
if (dp[j] != inf)
for (int k = 0; k < 9; ++k)
ndp[(j + k) % 9] = min(ndp[(j + k) % 9], dp[j] + siz[i] - cnt[i][k]);
dp.swap(ndp);
}
cout << dp[0] << endl;
}
}F ⑨ 团
知识点：模 $9$、线性方程、树状数组
平方模 $9$ 只可能是 $0,1,4,7$。合法三元组的平方余数类型只有：
$$
(0,0,0),(1,1,7),(1,4,4),(4,7,7)
$$
设区间内四类数量为 $c_0,c_1,c_4,c_7$。首先要有 $c_0$ 能被 $3$ 整除。再设后三种三元组数量分别为 $x,y,z$，则：
$$
2x+y=c_1,\quad 2y+z=c_4,\quad x+2z=c_7
$$
解得：
$$
x=\frac{4c_1-2c_4+c_7}{9},\quad
y=\frac{c_1+4c_4-2c_7}{9},\quad
z=\frac{-2c_1+c_4+4c_7}{9}
$$
只要三个值都是非负整数，就可以完成划分。用树状数组维护四类数量，单点修改、区间查询即可。
时间复杂度 $\mathcal{O}((n+q)\log n)$。
array<int, 10> id;
void init() {
for (int i = 1; i <= 9; ++i) {
int x = i * i % 9;
if (x == 0)
id[i] = 0;
else if (x == 1)
id[i] = 1;
else if (x == 4)
id[i] = 2;
else
id[i] = 3;
}
}
void solve() {
int n, q;
cin >> n >> q;
vector<int> a(n + 1);
vector<BIT<int>> tr(4);
for (int i = 0; i < 4; ++i) tr[i].init(n);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
tr[id[a[i]]].update(i, 1);
}
while (q--) {
int op, l, r;
cin >> op >> l >> r;
if (op == 1) {
int i = l, x = r;
if (id[a[i]] != id[x]) {
tr[id[a[i]]].update(i, -1);
tr[id[x]].update(i, 1);
}
a[i] = x;
} else {
int c0 = tr[0].ask(l, r), c1 = tr[1].ask(l, r), c4 = tr[2].ask(l, r), c7 = tr[3].ask(l, r);
int A = 4 * c1 - 2 * c4 + c7, B = c1 + 4 * c4 - 2 * c7, C = -2 * c1 + c4 + 4 * c7;
bool ok = (c0 % 3 == 0 && A >= 0 && B >= 0 && C >= 0 && A % 9 == 0 && B % 9 == 0 && C % 9 == 0);
cout << (ok ? "Yes" : "No") << 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;
}树状数组
template <class T> struct BIT {
vector<T> a;
int n;
BIT() {}
BIT(int n) {
init(n);
}
void init(int n) {
this->n = n;
a.assign(n + 1, T());
}
void update(int x, T k) {
for (; x <= n; x += x & -x) {
a[x] += k;
}
}
T ask(int x) {
T ans = 0;
for (; x; x -= x & -x) {
ans += a[x];
}
return ans;
}
T ask(int x, int y) {
return ask(y) - ask(x - 1);
}
};