CSP 2022 第二轮 部分题解
由于疫情无法举办 CSP ，学校组织周六晚上 vp CSP-J2，周天早上 vp CSP-S2。
J 组 T1T2 都是纯纯送分， T3 大模拟有点难调（到现在还没调出来），T4 是不太难的 dp，不过场上只写了 $k=0$ 的部分分。赛后洛谷测只有$245pts$。
S 组 T1 写了 $O(n^4)$ 暴力，剪了枝有 $70pts$。 T2 思维难度小但是码量大，导致 T3T4 都没时间写暴力。赛后发现 T2 有一种情况忘记分类了，挂到 $[40,75]$ 分。赛后洛谷测只有$145pts$，下午讲评时老师听完 $crc$ 的讲评说 “看来 T1T2 都很简单，大家应该都有 $200pts$ 吧”，我谔谔。不过也能接受吧，毕竟没学多久。T1 的正解都看不懂，以后多学点图论再补题吧。
11.9 更新：补了 S 组 T1。官方数据出了，J-240pts，S-200pts。
11.11 更新：补了 J 组 T3。
11.24 更新：补了 S组 T3。
- CSP-J T1 pow
- CSP-J T2 decode
- CSP-J T4 point
- CSP-J T3 expr
- CSP-S T2 game
- CSP-S T1 holiday
- CSP-S T3 galaxy
CSP-J T1 pow
请你计算 $a^b$。当它的值超过 ${10}^9$ 时，输出一个 -1 进行警示，否则就输出正确的 $a^b$ 的值。
$1 \le a, b \le 10^9$
题解
时间复杂度 $O(\log_a 10^9)$。特判一下 $a=1$ 的情况即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mx = 1e9;
inline ll read() {...}
inline void write(ll x) {...}
int main() {
ll a = read(), b = read(), ret = 1;
if(a == 1) {write(1); return 0;}
for(int i = 1; i <= b; i++) {
ret *= a;
if(ret > mx) {write(-1); return 0;}
}
write(ret);
return 0;
}
CSP-J T2 decode
给定一个正整数 $k$，有 $k$ 次询问，每次给定三个正整数 $n_i, e_i, d_i$，求两个正整数 $p_i, q_i$，使 $n_i = p_i \times q_i$、$e_i \times d_i = (p_i - 1)(q_i - 1) + 1$。如果无解，输出 NO。
$1 \leq k \leq {10}^5$；
对于任意的 $1 \leq i \leq k$，$1 \leq n_i \leq {10}^{18}$，$1 \leq e_i \times d_i \leq {10}^{18}$ ，$1 \leq n - e \times d + 2 \leq {10}^9$。
题解
注意到 $\cases {p\times q=n=\text{constant}\ p+q=n-e\times d + 2 = \text{constant}}$
于是用韦达定理逆定理构造方程，则 $p, q$ 为方程 $x^2 -(n-e\times d + 2)x + n = 0$ 的两实根，暴力用求根公式即可。注意判一下是否是整数解。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int k = read();
while(k--) {
ll n = read(), e = read(), d = read();
ll sum = n - e * d + 2;
ll delta = sum * sum - 4 * n;
ll s = sqrt(delta);
if(s * s != delta || ((sum - s) & 1) || ((sum + s) & 1)) {
printf("NO\n");
}
else {
ll p = (sum - s) >> 1, q = (sum + s) >> 1;
write(p), putchar(' '), write(q);
putchar('\n');
}
}
return 0;
}
CSP-J T4 point
给定平面直角坐标系中的 $n$ 个整数点 $(x_i, y_i)$，此外你还可以自由添加 $k$ 个整数点。在自由添加 $k$ 个点后，从 $n + k$ 个点中选出若干个整数点并组成一个序列。
合法的序列满足任意相邻两点之间有 $x_{i+1} - x_i = 1, y_{i+1} = y_i$ 或 $y_{i+1} - y_i = 1, x_{i+1} = x_i$。求合法序列的最大长度。
$1\le n \le 500, 0 \le k \le 100$
题解
用 $dp_{i,m}$ 表示考虑前 $i$ 个点，已经添加 $m$ 个点的最长上升点列的长度。那么转移方程如下：
\[dp_{i,m} = \max\limits_{1\le j < i}^{f(j, i) \le k}(dp_{i, m}, dp_{j, m-f(j,i)}+f(j,i)+1)\]其中 $f(j, i)$ 表示点 $A_j$ 到 $A_i$ 能够接上最少要用几个额外点。
答案相比于 dp 的状态， 还需要加上剩下的点数 $(k - m)$，因为一定可以把剩下的点加到点列中。
那么 sort 一遍，暴力 dp 即可。时间复杂度： $O(n^2k)$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX_N = 510;
pii a[MAX_N];
ll dp[MAX_N][MAX_N], ans, n, k;
inline ll read() {...}
inline void write(ll x) {...}
inline bool cmp(pii A, pii B) {return A.first == B.first ? A.second < B.second : A.first < B.first;}
inline ll dis(pii A, pii B) {return B.second - A.second + B.first - A.first;}
int main() {
n = read(), k = read();
for(int i = 1; i <= n; i++) a[i].first = read(), a[i].second = read();
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; i++) {
dp[i][0] = 1;
for(int j = 1; j < i; j++) {
ll q = dis(a[j], a[i]) - 1;
if(a[i].first < a[j].first || a[i].second < a[j].second) continue;
for(int m = q; m <= k; m++) {
dp[i][m] = max(dp[i][m], dp[j][m - q] + q + 1);
ans = max(ans, dp[i][m] + k - m);
}
}
}
write(ans);
return 0;
}
CSP-J T3 expr
给定一个逻辑表达式，其中数字只有 $0$ 和 $1$，运算符只有 & 和 |，另外还有左右小括号 ( 和 )。规定 & 的优先级大于 |。
给定一个逻辑表达式，计算它的值。计算过程中如果出现 a&b 的部分且 a=0 的情况，则不用计算 b 的值了，我们称其为一次形如 a&b 的短路。同理还有 a|b 在 a=1 时会短路。
输出逻辑表达式的计算结果，以及形如 a&b 的短路次数、形如 a|b 的短路次数。
题解
本来觉得要建树很麻烦，结果看到一个直接分治的题解，代码十分简单，于是就用这种方法写了。那篇博客的连接：LINK。
具体实现方面他讲的比较细节。其实就是对于一段区间 $[l,r]$，我们找到它同级的表达式中最右边的 |，以它为分界线分为左右两边计算。其次找到同级的表达式中最右边的 &，以它为分界线分为左右两边计算。对于某一位置 $i$，我们可以先扫一遍，预处理出与 $s_i$ 同级的运算符中最右边的 | 的位置 和 & 的位置。于是时间复杂度严格 $O(n)$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e6 + 10;
int lst1[MAX_N], lst2[MAX_N], s1[MAX_N], s2[MAX_N], cnt1, cnt2;
char s[MAX_N];
int cal(int l, int r) {
if(s1[r] >= l) {
int lval = cal(l, s1[r] - 1);
if(lval == 1) {cnt1++; return 1;}
else return (lval | cal(s1[r] + 1, r));
}
else if(s2[r] >= l) {
int lval = cal(l, s2[r] - 1);
if(lval == 0) {cnt2++; return 0;}
else return (lval & cal(s2[r] + 1, r));
}
else if(s[l] == '(' && s[r] == ')') return cal(l + 1, r - 1);
else return (s[l] ^ 48);
}
int main() {
scanf("%s", s + 1);
int n = strlen(s + 1);
int k = 0;
for(int i = 1; i <= n; i++) {
if(s[i] == '(') k++;
else if(s[i] == ')') k--;
else if(s[i] == '|') lst1[k] = i;
else if(s[i] == '&') lst2[k] = i;
s1[i] = lst1[k], s2[i] = lst2[k];
}
int ans = cal(1, n);
printf("%d\n%d %d", ans, cnt2, cnt1);
return 0;
}
CSP-S T2 game
小 L 和小 Q 在玩一个策略游戏。
有一个长度为 $n$ 的数组 $A$ 和一个长度为 $m$ 的数组 $B$，在此基础上定义一个大小为 $n \times m$ 的矩阵 $C$，满足 $C_{i j} = A_i \times B_j$。所有下标均从 $1$ 开始。
游戏一共会进行 $q$ 轮，在每一轮游戏中，会事先给出 $4$ 个参数 $l_1, r_1, l_2, r_2$，满足 $1 \le l_1 \le r_1 \le n$、$1 \le l_2 \le r_2 \le m$。
游戏中，小 L 先选择一个 $l_1 \sim r_1$ 之间的下标 $x$，然后小 Q 选择一个 $l_2 \sim r_2$ 之间的下标 $y$。定义这一轮游戏中二人的得分是 $C_{x y}$。
小 L 的目标是使得这个得分尽可能大，小 Q 的目标是使得这个得分尽可能小。同时两人都是足够聪明的玩家，每次都会采用最优的策略。
请问：按照二人的最优策略，每轮游戏的得分分别是多少？
$1 \le n, m, q \le {10}^5$，$-{10}^9 \le A_i, B_i \le {10}^9$，$1 \le l_1 \le r_1 \le n$，$1 \le l_2 \le r_2 \le m$。
题解
考虑到小 L 的决策首先取决于 小 Q 能选的数中是 全正 还是 全负 还是 有正有负。
我们 取其中一种情况 来具体分析：
如果小 Q 能选的数全正，那么小 L 为了使得分尽量大，会作出这样的决策：手里有正数就会选最大的正数(决策 $1$)，手里没有正数就会选最大的负数(决策 $2$)。
对于决策 $1$，小 Q 的回应必然是选他手里 最小的正数。对于决策 $2$，小 Q 的回应必然是选他手里 最大的正数。
对于其他情况，同样分两类即可。特别的，一正一负的分类有可能两种决策都可能发生，那么需要取两种决策中的最大值。
可以选择线段树或 ST 表维护区间最值。线段树代码长但好调试，ST 表代码短但难调试。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10, MAX_LOG = 19, INF = 1e9 + 10;
int log_2[MAX_N];
void init_log() {
log_2[1] = 0, log_2[2] = 1;
for(int i = 3; i < MAX_N; i++) log_2[i] = log_2[i >> 1] + 1;
}
struct st {
int minn[MAX_N][MAX_LOG], maxn[MAX_N][MAX_LOG], len;
void init() {
for(int j = 1; j <= MAX_LOG; j++) {
for(int i = 1; i + (1 << (j - 1)) - 1 <= len; i++) {
minn[i][j] = INF, maxn[i][j] = -INF;
minn[i][j] = min(minn[i][j - 1], minn[i + (1 << (j - 1))][j - 1]);
maxn[i][j] = max(maxn[i][j - 1], maxn[i + (1 << (j - 1))][j - 1]);
}
}
}
int query(int l, int r, int type) {
int t = log_2[r - l + 1];
if(type == 1) return min(minn[l][t], minn[r - (1 << t) + 1][t]);
else return max(maxn[l][t], maxn[r - (1 << t) + 1][t]);
}
} st1, st1_m, st2;
inline ll read() {...}
inline void write(ll x) {...}
int main() {
int n = read(), m = read(), q = read();
init_log();
for(int i = 1; i <= n; i++) {
int x = read();
if(x >= 0) {
st1.maxn[i][0] = st1.minn[i][0] = x;
st1_m.maxn[i][0] = -INF;
st1_m.minn[i][0] = INF;
}
else {
st1_m.maxn[i][0] = st1_m.minn[i][0] = -x;
st1.maxn[i][0] = -INF;
st1.minn[i][0] = INF;
}
}
for(int i = 1; i <= m; i++) {
int x = read();
st2.maxn[i][0] = st2.minn[i][0] = x;
}
st2.len = m; st1.len = st1_m.len = n;
st1.init(), st2.init(), st1_m.init();
while(q--) {
ll ans = 0;
int l1 = read(), r1 = read(), l2 = read(), r2 = read();
if(st2.query(l2, r2, 1) < 0 && st2.query(l2, r2, 2) >= 0) {
if(st1.query(l1, r1, 2) == -INF) ans = 1ll * (-1) * st1_m.query(l1, r1, 1) * st2.query(l2, r2, 2);
else if(st1_m.query(l1, r1, 2) == -INF) ans = 1ll * st1.query(l1, r1, 1) * st2.query(l2, r2, 1);
else ans = max(1ll * (-1) * st1_m.query(l1, r1, 1) * st2.query(l2, r2, 2), 1ll * st1.query(l1, r1, 1) * st2.query(l2, r2, 1));
}
else if(st2.query(l2, r2, 1) < 0 && st2.query(l2, r2, 2) < 0) {
if(st1_m.query(l1, r1, 2) == -INF) ans = 1ll * st1.query(l1, r1, 1) * st2.query(l2, r2, 1);
else ans = 1ll * (-1) * st1_m.query(l1, r1, 2) * st2.query(l2, r2, 2);
}
else {
if(st1.query(l1, r1, 2) == -INF) ans = 1ll * (-1) * st1_m.query(l1, r1, 1) * st2.query(l2, r2, 2);
else ans = 1ll * st1.query(l1, r1, 2) * st2.query(l2, r2, 1);
}
write(ans); putchar('\n');
}
return 0;
}
CSP-S T1 holiday
小熊的地图上有 $n$ 个点，其中编号为 $1$ 的是它的家、编号为 $2, 3, \ldots, n$ 的都是景点。部分点对之间有双向直达的公交线路。如果点 $x$ 与 $z_1$、$z_1$ 与 $z_2$、……、$z_{k - 1}$ 与 $z_k$、$z_k$ 与 $y$ 之间均有直达的线路，那么我们称 $x$ 与 $y$ 之间的行程可转车 $k$ 次通达；特别地，如果点 $x$ 与 $y$ 之间有直达的线路，则称可转车 $0$ 次通达。
很快就要放假了，小熊计划从家出发去 $4$ 个不同的景点游玩，完成 $5$ 段行程后回家：家 $\to$ 景点 A $\to$ 景点 B $\to$ 景点 C $\to$ 景点 D $\to$ 家且每段行程最多转车 $k$ 次。转车时经过的点没有任何限制，既可以是家、也可以是景点，还可以重复经过相同的点。例如，在景点 A $\to$ 景点 B 的这段行程中，转车时经过的点可以是家、也可以是景点 C，还可以是景点 D $\to$ 家这段行程转车时经过的点。
假设每个景点都有一个分数，请帮小熊规划一个行程，使得小熊访问的四个不同景点的分数之和最大。
对于所有数据，保证 $5 \le n \le 2500$，$1 \le m \le 10000$，$0 \le k \le 100$，所有景点的分数 $1 \le s_i \le {10}^{18}$。保证至少存在一组符合要求的行程。
题解
考虑我们可以用 bfs/dijkstra 在可接受的时间复杂度 ($O(n^2)/O(n^2 \log n)$) 之内处理出任意两个点是否可达。接下来如果你用可达的点对建一个新图，跑 $O(n^4)$ 暴力根本跑不满，官方数据能拿下 $75pts$ ( Code )。
不过这题正解的复杂度应该是 $O(n^2)$。所以我们需要折半查找，考虑对于行程 $1\to a\to b\to c\to d\to 1$，只枚举 $b$ 和 $c$。我们在 bfs 的时候，对于每个节点 $u$，预处理出 能到家的 且 能到 $u$ 的 所有节点 $v$ 中分数前三大的节点，构成集合 $f_u$。然后 $a$ 就必须贪心地从 $f_b$ 中选， $d$ 就必须从 $f_c$ 里选。
之所以要维护前三大，是因为选出来的 $a$ 与 $d$ 可能和 $b$ 或 $c$ 重复，如果维护前三大，就总能往下选直到不重复。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 2510;
vector<int> G[MAX_N], f[MAX_N];
bool r[MAX_N][MAX_N], vis[MAX_N];
ll s[MAX_N], dis[MAX_N], n, m, k, ans;
inline ll read() {...}
inline void write(ll x) {...}
bool cmp(int x, int y) {return s[x] > s[y];}
inline void bfs(int u) {
queue<int> q;
for(int i = 1; i <= n; i++) vis[i] = 0;
q.push(u); dis[u] = 0; vis[u] = 1;
while(!q.empty()) {
int v = q.front(); q.pop();
if(u != v) {
r[u][v] = 1;
if(r[1][v]) {
f[u].push_back(v);
sort(f[u].begin(), f[u].end(), cmp);
if(f[u].size() > 3) f[u].pop_back();
}
}
if(dis[v] == k + 1) continue;
for(int i = 0; i < G[v].size(); i++) {
int t = G[v][i];
if(vis[t]) continue;
vis[t] = 1;
dis[t] = dis[v] + 1;
q.push(t);
}
}
}
int main() {
n = read(), m = read(), k = read();
for(int i = 2; i <= n; i++) s[i] = read();
for(int i = 1; i <= m; i++) {
int u = read(), v = read();
G[u].push_back(v); G[v].push_back(u);
}
for(int i = 1; i <= n; i++) bfs(i);
for(int b = 2; b <= n; b++) {
for(int c = 2; c <= n; c++) {
if(r[b][c]) {
for(int i = 0; i < f[b].size(); i++) {
for(int j = 0; j < f[c].size(); j++) {
int a = f[b][i], d = f[c][j];
if(a != d && a != c && b != d) ans = max(ans, s[a] + s[b] + s[c] + s[d]);
}
}
}
}
}
write(ans);
return 0;
}
CSP-S T3 galaxy
给定一个 $n$ 个点 $m$ 条边的无向图，每条边可以激活也可以失活。
有 $q$ 次操作，每次操作有以下 $4$ 种：
-
失活某条边。
-
失活以某点为终点的所有边，
-
激活某条边。
-
激活以某点为终点的所有边。
每次操作后，输出目前激活的边构成的图是否满足以下条件：
-
所有的点出发都可以走到一个环。
-
所有点的出度为 $1$。
$1\le n,m,q\le 5\times 10^5$
题解
以下时间复杂度分析的 $n$ 基于 $n,m,q$ 的范围同阶。
其实所有点的出度为 $1$ 就等价于所有的点出发都可以走到一个环，满足条件的图叫做内向基环树森林。所以只需要判断出度即可。
但是如果暴力判断出度，操作 $2,4$ 最坏都是 $O(n)$，因为最多要修改 $n$ 个点的出度。这样时间复杂度变成了 $O(n^2)$。
考虑如何优化这个判断。事实上，一个图的入度和会等于出度和。如果我们改为修改入度，所有操作都是 $O(1)$ 的，其中 $1,3$ 操作让边的终点入度 $\pm 1$，而 $2,4$ 操作让这个点的入度变为 $0$ 或变为初始入度。
如果我们维护入度和，判断它是否等于 $n$，我们可以说，不等的时候一定不满足条件，但相等的时候也不一定满足。
这是因为例如 $n=3$，我们想要的出度和为 $1+1+1$，入度和却可能是 $2+1+0$。
看到这个形式，容易想到我们学习哈希函数时，举过这个例子，即字符串哈希不能直接把所有字符的 ASCII 码加起来得到哈希值，而是用进制哈希来降低冲突概率。
这里我们也考虑哈希，把每个点附上一个随机权值 $w$，入度的定义修改为 ${in}v = \sum\limits{u\to v} w_u$。然后如果当前的入度之和恰好为每个点的权值和 $\sum\limits_{i=1}^n w_i$，我们就可以说当前的图满足条件。这是因为方程
\[\sum\limits_{i=1}^n k_i\cdot w_i = \sum\limits_{i=1}^n w_i\]的非负整数解在 $w$ 随机的情况下极有可能只有 $k_1=k_2=\dots = k_n = 1$ 这一个。
那么我们操作时顺便维护一下当前的入读之和，判断它与目标是否相等即可。时间复杂度是 $O(n)$ 的。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 5e5 + 10;
ll inn[MAX_N], in[MAX_N], w[MAX_N], n, m, q, sum, now;
inline ll read() {...}
inline void write(ll x) {...}
int main() {
mt19937 rng(random_device{}());
n = read(), m = read();
for(int i = 1; i <= n; i++)
w[i] = rng(), sum += w[i];
for(int i = 1; i <= m; i++) {
int u = read(), v = read();
in[v] += w[u], now += w[u];
}
for(int i = 1; i <= n; i++)
inn[i] = in[i];
q = read();
while(q--) {
int op = read();
if(op == 1) {
int u = read(), v = read();
inn[v] -= w[u], now -= w[u];
}
else if(op == 2) {
int u = read();
now -= inn[u], inn[u] = 0;
}
else if(op == 3) {
int u = read(), v = read();
inn[v] += w[u], now += w[u];
}
else if(op == 4) {
int u = read();
now += (in[u] - inn[u]), inn[u] = in[u];
}
puts(now == sum ? "YES" : "NO");
}
return 0;
}
♥