2025CSP-S模拟赛33
| T1 | T2 | T3 | T4 |
|---|---|---|---|
| 100 AC | 90 RE | 0 TLE | 30 RE |
总分：220；排名：4/20
T1 切了。T2 本是正确的，但是基环树找环写炸了，我的做法甚至是爆标的。T3 暴力写假了，T4 是部分分。
T1 机器人
按照体面模拟写个 dfs 即可。
#include <bits/stdc++.h>
#define il inlineusing namespace std;const int N = 20 + 5;
int n;
char s[N];
struct node {int x, y;bool operator < (const node & cmp) const {return x != cmp.x ? x < cmp.x : y < cmp.y;}
};
map<node, int> ans;
int tag[60][60];
il void dfs(int x, int y, int now) {if (now > n) {ans[(node){x, y}] = 1;return;}tag[x + N][y + N]--;int xa = x, ya = y;if (s[now] == 'L') xa--;if (s[now] == 'R') xa++;if (s[now] == 'D') ya--;if (s[now] == 'U') ya++;if (tag[xa + N][ya + N] == 1) {dfs(x, y, now + 1);} else {dfs(xa, ya, now + 1);if (tag[xa + N][ya + N] == 0) {tag[xa + N][ya + N] = 1;dfs(x, y, now + 1);tag[xa + N][ya + N] = 0;}}tag[x + N][y + N]++;
}
int main() {ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);cin >> n >> (s + 1);dfs(0, 0, 1);cout << ans.size() << "\n";map<node, int>:: iterator it;for (it = ans.begin(); it != ans.end(); it++) {cout << it->first.x << " " << it->first.y << "\n";}return 0;
}
T2 旅行
提供一种接近线性的做法。
我们先考虑如果是一棵树如何处理。
我们关注到一条边从一个颜色变到另一种颜色会收到影响的连通块个数是极小的。如果我们令修改前的颜色为 \(a\)，修改后的颜色为 \(b\)，称这条边两个端点所连接的其他边是否含有该颜色为两头有/没有某种颜色，所以改变一条边产生的贡献就是：
- 把原来一个 \(a\) 的分成两部分，产生 \(+1\) 的贡献（两头都有 \(a\)）
- 减少这条边自己即一个 \(a\) 的连通块，产生 \(-1\) 的贡献（两头都没有 \(a\)）
- 把原来两个 \(b\) 的连成一部分，产生 \(-1\) 的贡献（两头都有 \(b\)）
- 增加这条边自己即一个 \(b\) 的连通块，产生 \(+1\) 的贡献（两头都没有 \(b\)）
然后考虑有环的情况。
如果这条边不在环上，那么和上面一样。如果在环上，就需要特判一下。直接说结论了，如果环上除了当前边的所有边的颜色都是 \(a\)，那么这条边就不产生（忽略）上面的 1,2 的贡献；如果都是 \(b\)，则忽略 3,4。这些结论都挺显然的。
然后就没了啊。初始随便跑一边统计初始联通块的数量，然后每次 \(O(1)\) 更新答案并维护一些信息即可。
#include <bits/stdc++.h>
#define il inlineusing namespace std;const int bufsz = 1 << 20;
char ibuf[bufsz], *p1 = ibuf, *p2 = ibuf;
#define getchar() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, bufsz, stdin), p1 == p2) ? EOF : *p1++)
il int read() {int x = 0; char ch = getchar(); bool t = 0;while (ch < '0' || ch > '9') {t ^= ch == '-'; ch = getchar();}while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}return t ? -x : x;
}
const int N = 1e5 + 10;
int n, m, qq;
struct edge {int y, w, id;
};
vector<edge> G[N];
int u, v, col;
int fa[N];
il int getfa(int x) {return x == fa[x] ? x : fa[x] = getfa(fa[x]);
}
int cnt;
il void link(int x, int y) {x = getfa(x), y = getfa(y);if (x != y) {fa[y] = x;cnt--;}
}
int lst[N];
int tag[N], inst[N], st[N], head, st1[N], head1, vis[N];
il void dfs(int x, int fr) {vis[x] = 1;inst[x] = 1;st[++head] = x;st1[++head1] = fr;for (edge i : G[x]) {if (i.id == fr) continue;if (inst[i.y]) {tag[i.id] = 1;for (int j = head; st[j] != i.y; j--) {if (inst[st[j]]) tag[st1[j]] = 1;}} else if (!vis[i.y]) {dfs(i.y, i.id);}}head--, head1--;inst[x] = 0;
}
unordered_map<int, int> mp[N], id[N];
int xx[N], yy[N], ww[N];
int t[N];
int solve() {n = read(), m = read();for (int i = 1; i <= n; i++) {int x = read(), y = read(), w = read();G[x].push_back({y, w, i});G[y].push_back({x, w, i});mp[x][w]++;mp[y][w]++;id[x][y] = id[y][x] = i;xx[i] = x, yy[i] = y, ww[i] = w;}for (int i = 1; i <= n; i++) fa[i] = i;cnt = n;for (int x = 1; x <= n; x++) {for (edge i : G[x]) lst[i.w] = 0;for (edge i : G[x]) {if (lst[i.w]) link(lst[i.w], i.id);lst[i.w] = i.id;}}for (int i = 1; i <= n; i++) tag[i] = inst[i] = vis[i] = 0;head = head1 = 0;dfs(1, 0);int len = 0;for (int i = 1; i <= n; i++) t[i] = 0;for (int i = 1; i <= n; i++) {if (tag[i]) {len++;t[ww[i]]++;}}for (int k = 1; k <= m; k++) {u = read(), v = read(), col = read();int ii = id[u][v];int w = ww[ii];mp[u][w]--, mp[v][w]--;if (tag[ii]) t[w]--;if (!tag[ii] || (tag[ii] && t[w] < len - 1)) {if (mp[u][w] > 0 && mp[v][w] > 0) cnt++;if (mp[u][w] == 0 && mp[v][w] == 0) cnt--;}if (!tag[ii] || (tag[ii] && t[col] < len - 1)) {if (mp[u][col] > 0 && mp[v][col] > 0) cnt--;if (mp[u][col] == 0 && mp[v][col] == 0) cnt++;}printf("%d\n", cnt);if (tag[ii]) t[col]++;mp[u][col]++, mp[v][col]++;ww[ii] = col;}for (int i = 1; i <= n; i++) G[i].clear(), mp[i].clear(), id[i].clear();return 0;
}
int main() {qq = read();while (qq--) {solve();}return 0;
}