复习一下。
A. 串
计算长度不超过 $n$ 且蕴含 us 作为子串的字符串有多少个。
分析
读错题目了，还以为是容斥。对 “出现 us”、“出现 u”、“其他” 三种情况分别 DP。
int main() {
int n;
cin >> n;
ll ans = 0;
ll dp0 = 1, dpu = 0, dps = 0;
for (int i = 1; i <= n; i++) {
ll t0 = dp0 * 25 % P;
ll tu = (dpu * 25 + dp0) % P;
ll ts = (dpu + dps * 26) % P;
dp0 = t0, dpu = tu, dps = ts;
ans = (ans + dps) % P;
}
cout << ans;
return 0;
}
全部代码请看：Nowcoder/NC9981/A.cpp。
实际上计算可以做到 $\log n$。记三种情况分别为 $o_n, u_n, s_n$，可以解得
$$ o_n = 25^n, \quad u_n = n 25^{n-1}, \quad s_n = 26^n - o_n-u_n $$
因此计算得
$$ \sum_{i=2}^n s_i = \frac{1}{14400}(576 \cdot 26^{n+1} - (599+24n)25^{n+1}-1) $$
B. 括号
构造长度不超过 $10^5$ 的括号串，使得恰好包含 $k$ 个括号对。
分析
考虑弄 $5 \times 10^4$ 个 (，再考虑如何把 $k$ 拆分成 $k_i$，在 $k_i$ 后加上右括号即可。
拆分可以从 $5\times10^4$ 开始，逐渐递减。若是从小到大，长度会超。
int main() {
ll k;
cin >> k;
vector<int> vis(N + 1);
for (int i = N; i >= 1; i--) {
if (k >= i) {
k -= i;
vis[i] = 1;
}
}
string s;
for (int i = 1; i <= N; i++) {
s.push_back('(');
if (vis[i])
s.push_back(')');
}
cout << s;
return 0;
}
全部代码请看：Nowcoder/NC9981/B.cpp。
C. 红和蓝
给定一棵 $n$ 个节点的树，需要用红色和蓝色把树染色：
- 每个红点周围有且仅有一个红点，每个蓝点周围有且仅有一个蓝点。
分析
显然颜色是以二元对的形式分组。下证这样的分组形式唯一。
- 如果该点是叶子，其必须和父节点同色，形式唯一。
- 如果该点不是叶子，则只有两种可能：
- 已经被子节点标记，形式唯一。
- 未被标记，依 DFS 序知子节点全是已经标记，且确定唯一的。故只能和父节点同色。
对于每个叶子，其必须和其父节点同色，从而可以赋给他们相同的编号。如果某个叶子其父节点已经被标记，则说明此树不可染色。
const int N = 1E5;
vector<int> G[N];
int main() {
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
vector<int> vis(n + 1), col(n + 1);
int cnt = 0;
std::function<void(int, int)> dfs1 = [&](int x, int fa) {
for (auto u : G[x]) {
if (u != fa)
dfs1(u, x);
}
if (!vis[x]) {
if (vis[fa]) {
cout << "-1";
exit(0);
}
vis[fa] = vis[x] = ++cnt;
}
};
std::function<void(int, int)> dfs2 = [&](int x, int fa) {
for (auto u : G[x]) {
if (u == fa)
continue;
if (vis[u] == vis[x]) {
col[u] = col[x];
} else {
col[u] = !col[x];
}
dfs2(u, x);
}
};
vis[0] = 1, col[1] = 1;
dfs1(1, 0), dfs2(1, 0);
for (int i = 1; i <= n; i++) {
cout << (col[i] ? 'R' : 'B');
}
return 0;
}
全部代码请看：Nowcoder/NC9981/C.cpp。
D. 点一成零
给定一个 $n \times n$ 的 01 方阵，每次修改可以把一处格子由 $0$ 改为 $1$。
然后回答询问：每次点击可以把一个 $1$ 的连通块变为 $0$，问有几种操作能够全部为 $0$。
分析
若方阵中有 $a$ 个连通块，每个连通块的大小是 $b_i$，那么答案是
$$ ans = a! \prod b_i $$
因此我们需要维护连通块的个数，和每个连通块的大小。用带权并查集实现即可。
同时需要维护连通块的乘积，在合并时维护乘积。
const int N = 500 + 10;
char ss[N][N];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> ss[i];
}
pre_all(n * n + 10);
int cnt = 0, mul = 1;
DSU dsu(n * n);
auto merge = [&](int x1, int y1, int x2, int y2) {
if (x2 < 0 || x2 >= n || y2 < 0 || y2 >= n)
return;
if (ss[x2][y2] == '0')
return;
int p1 = x1 * n + y1, p2 = x2 * n + y2;
if (dsu.find(p1) != dsu.find(p2)) {
mul = 1ll * mul * Inv[dsu.size(p1)] % P * Inv[dsu.size(p2)] % P;
dsu.merge(p1, p2);
mul = 1ll * mul * dsu.size(p1) % P;
cnt--;
}
};
auto change = [&](int i, int j) {
if (ss[i][j] == '1')
return;
ss[i][j] = '1';
cnt++;
merge(i, j, i, j - 1);
merge(i, j, i, j + 1);
merge(i, j, i - 1, j);
merge(i, j, i + 1, j);
};
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (ss[i][j] == '0')
continue;
ss[i][j] = '0';
change(i, j);
}
}
int Q;
cin >> Q;
while (Q--) {
int x, y;
cin >> x >> y;
change(x, y);
cout << 1ll * mul * fac[cnt] % P << "\n";
}
return 0;
}
全部代码请看：Nowcoder/NC9981/D.cpp。
E. 三棱锥之刻
计算几何，不讲。
const double PI = acos(-1.0);
int main() {
double a, r;
cin >> a >> r;
double a2 = a * a, r2 = r * r;
double s2 = r2 - a2 / 24;
double ans = 0;
if (s2 > 0) {
double s = sqrt(s2);
if (s2 < a2 / 12) {
ans = PI * s2;
} else if (s2 < a2 / 3) {
double costh = a / s / 2 / sqrt(3);
double th = acos(costh);
double sinth = sqrt(1 - costh * costh);
double t = s * sinth;
ans = t * a / sqrt(12) + (PI / 3 - th) * s2;
ans *= 3;
} else {
ans = a * a * sqrt(3) / 4;
}
}
printf("%.10lf", ans * 4);
return 0;
}
全部代码请看：Nowcoder/NC9981/E.cpp。
F. 对答案一时爽
给定 $n$ 道选择题，以及牛牛和牛妹的选择。
问两人得分之和有可能达到的最大值和最小值。
分析
显然最小值是 $0$。
当两人答案相同时，可能得两分；否则得一分。
int main() {
int n;
cin >> n;
int sum = 0;
vector<char> s1(n), s2(n);
for (auto &si : s1)
cin >> si;
for (auto &si : s2)
cin >> si;
for (int i = 0; i < n; i++) {
if (s1[i] == s2[i]) {
sum += 2;
} else {
sum += 1;
}
}
cout << sum << " " << 0;
return 0;
}
全部代码请看：Nowcoder/NC9981/F.cpp。
H. 幂塔个位数的计算
计算 $a \uparrow \uparrow n$ 的个位数。
分析
去年我是打表找规律，但是很容易误认为解只和 $a \bmod 10$ 有关。
更朴素的想法是欧拉降幂。
a = int(input())
n = int(input())
if(n == 1):
print(a % 10)
elif(n == 2):
print(pow(a, a % 4 + 4, 10))
else:
x = pow(a, a % 2 + 2, 4)
print(pow(a, x + 4, 10))
全部代码请看：Nowcoder/NC9981/H.py。
还有些题解误认为 $a, n$ 都对 $100$ 取模，这里给出一个 Hack。
INPUT: 2 1001
==============
OUTPUT: 6
I. 限制不互素对的排列
构造一个长为 $n$ 的排列，使得其中恰有 $k$ 对相邻的数，其 $\gcd(a_i, a_{i+1}) > 1$。
分析
怎么感觉这题见过。
注意到偶数序列是两两 $\gcd \geqslant 2$ 的，而相邻整数一定有 $\gcd(i, i+1) = 1$。
令 $1$ 作为奇偶分界点，对于 $k < n / 2$ 我们已经有了构造方法。
对于 $k = n / 2$，需要额外再找出一对。我找的是 $(6, 3)$。
int main() {
int n, k;
cin >> n >> k;
if (n < 6 && k == n / 2) {
cout << -1;
exit(0);
}
vector<int> vis(n + 1), ans;
for (int i = 2; i <= n; i += 2) {
if (i == 6)
continue;
ans.push_back(i);
}
ans.push_back(6);
ans.push_back(3);
for (int i = 0; i <= k; i++) {
cout << ans[i] << " ";
vis[ans[i]] = true;
}
for (int i = 1; i <= n; i++) {
if (!vis[i])
cout << i << " ";
}
return 0;
}
全部代码请看：Nowcoder/NC9981/I.cpp。
J. 一群小青蛙呱蹦呱蹦呱
给定一个集合 $A = {1, \cdots, n}$，在其中划去所有质数的幂次 $p_j^k$，组成集合 $B$。问集合 $B$ 所有数的 $\lcm$ 是多少。
分析
注意到 $\lcm$ 再取模，只可能是对于所有因子独立计算贡献。
int main() {
ll n;
cin >> n;
if (n <= 5) {
cout << "empty";
return 0;
}
Euler(n / 2);
ll ans = 1;
for (auto pj : primes) {
ll tn = n;
if (pj == 2) {
tn /= 3;
} else {
tn /= 2;
}
tn /= pj;
while (tn > 0) {
tn /= pj;
ans = ans * pj % P;
}
}
cout << ans;
return 0;
}
全部代码请看：Nowcoder/NC9981/J.cpp。