CSP-J/S 2026 游记
willgaoxing · · 生活·游记
我无疑是糖丸的。
Day 0
体育课故意不小心摔倒了,下午请假去医院了,也算是停了半天课吧。所幸主包的腿还能走路。
Day 1
早上跟车
到了机房发现环境不错,眯了一会,静待开始。
上午解压密码是 Trick||Treat!。打开题面,T1 看起来十分正常,大概
看到 T2 有点脊背发凉。我立马看出这是个双指针,但是这个代码肯定不怎么好写。写完第一遍后过了前
2
2 a
4 b
过了之后又发现了另一组 hack:
2
4 a
2 b
当场气晕。此时大概是
打开 T4,和之前有一题好像比较类似。先是打了一个
后面又写了个 T3 的对拍,简略地乱搞了一下 T2,就睡觉了。最后
中午去了和去年一样的饭店吃饭。
下午差不多 Oct31==Dec25?,不得不说今年 CCF 还是很细节的。
:::info[FUN FACT]
在西方文化中,万圣节(
同时 Oct 是八进制的简称,Dec 是十进制的简称,而
:::
T1 十分经典,感觉以前有类似的,
T2 读题还是花了我不少时间。我是先直接按题面把站台和站厅作为节点暴力建图跑 Dijkstra。然后我就发现可以把每条线上的所有站台都缩成一个点。进一步地,我就发现可以以线路为节点建图。这个时候聪明的我认为边数很少,所以就没改之前打的 Dijkstra。在最后一个大样例跑了
看到 T3 第一眼想到的是线段树优化建图再 01-BFS 求最短路树然后在最短路树上乱搞。不过我不知道怎么乱搞,于是只能在线段树优化建图后暴力统计答案。但是第
T4 想到了要二分答案,但是想不出怎么判定。打了个
最后的时间基本上半睡半醒,
然后就发现 S 组 T2 挂了大分,当场心态爆炸。
晚上睡觉的时候想出了 T4 的正解。
Day 2
早上复现了 subway 的代码,交上去发现有
Day 3~5
复习期中考(实际上一直在颓)。
Day 6
中午回来发现能查分了。
J:
S:
完结撒花~
赛时代码
J
:::info[travel]
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool f1(string s1, string s2) {
return s1.substr(0, 2) == s2.substr(0, 2);
}
bool f2(string s1, string s2) {
int a = (s1[2] <= 'C'), b = (s2[2] <= 'C');
return a == b;
}
bool f3(string s1, string s2) {
char a = s1[2], b = s2[2];
if (a > b) swap(a, b);
return (a == 'D' && b == 'F') || b == (char)(a + 1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
freopen("travel.in", "r", stdin);
freopen("travel.out", "w", stdout);
string c1, s1, c2, s2;
cin >> c1 >> s1 >> c2 >> s2;
cout << (c1 == c2 ? 1 : 0);
cout << (c1 == c2 && f1(s1, s2) ? 1 : 0);
cout << (c1 == c2 && f1(s1, s2) && f2(s1, s2) ? 1 : 0);
cout << (c1 == c2 && f1(s1, s2) && f2(s1, s2) && f3(s1, s2) ? 1 : 0) << "\n";
return 0;
}
:::
:::info[string]
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 10;
ll a[maxn];
char c[maxn];
ll solve(int n) {
ll s1 = 0, s2 = 0;
ll ans = 0;
for (int i = 1, j = n; i <= n; i++) {
if (s1 < s2 && c[i] != c[j]) {
// cout << "1 " << i << " " << j << " " << s1 << " " << s2 << endl;
if (s1 + a[i] > s2) ans += s2 - s1;
else ans += a[i];
}
s1 += a[i];
while (j >= 1 && s2 < s1) {
// if (s1 == s2 + a[j]) {
// s2 += a[j];
// break;
// }
if (c[i] != c[j]) {
// cout << "2 " << i << " " << j << " " << s1 << " " << s2 << endl;
if (s2 + a[j] > s1) ans += s1 - s2;
else ans += a[j];
}
s2 += a[j];
j--;
}
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
freopen("string.in", "r", stdin);
freopen("string.out", "w", stdout);
int n;
cin >> n;
ll sum = 0;
for (int i = 1; i <= n; i++) cin >> a[i] >> c[i], sum += a[i];
if (sum <= 1e8) {
string s;
for (int i = 1; i <= n; i++) for (int j = 1; j <= a[i]; j++) s += c[i];
ll ans = 0;
for (int i = 0, j = s.size() - 1; i < j; i++, j--) ans += (s[i] != s[j]);
cout << ans << "\n";
exit(0);
}
ll ans1 = solve(n) / 2;
reverse(a + 1, a + n + 1); reverse(c + 1, c + n + 1);
ll ans2 = solve(n) / 2;
cout << min(ans1, ans2) << "\n";
return 0;
}
:::
:::info[and]
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 10;
int a[maxn];
vector <int> fail[32];
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
freopen("and.in", "r", stdin);
freopen("and.out", "w", stdout);
int n, m;
cin >> n >> m;
set <int> st;
for (int i = 1; i <= n; i++) {
cin >> a[i];
st.insert(i);
for (int j = 0; j < 30; j++) if (!(a[i] & (1 << j))) fail[j].push_back(i);
}
ll ans = 0;
for (int j = 29; j >= 0; j--) {
set <int> nst = st;
for (int x : fail[j]) nst.erase(x);
if (nst.size() >= m) ans += (1ll << j), st = nst;
}
cout << ans << "\n";
return 0;
}
:::
:::info[card]
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 5e5 + 10;
int a[maxn], lst[maxn];
int cnt[maxn];
bool vis[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
freopen("card.in", "r", stdin);
freopen("card.out", "w", stdout);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) lst[a[i]] = i;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j = lst[a[j]] + 1) {
if (!vis[a[j]]) cnt[a[j]]++;
vis[a[j]] = true;
}
for (int j = i; j <= n; j = lst[a[j]] + 1) vis[a[j]] = false;
}
for (int i = 1; i <= m; i++) cout << cnt[i] << (i < m ? " " : "\n");
return 0;
}
:::
## S
:::info[crystal]
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 5e5 + 10;
ll a[maxn], sum[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
freopen("crystal.in", "r", stdin);
freopen("crystal.out", "w", stdout);
int n;
ll m;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) sum[i] = sum[i-1] + a[i];
ll ans = 0;
for (int i = 1; i <= n; i++) {
int l = 0, r = i - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (a[i] * (i - mid) - (sum[i] - sum[mid]) <= m) r = mid - 1;
else l = mid + 1;
}
ans = max(ans, (ll)i - l);
}
cout << ans;
return 0;
}
:::
:::info[subway]
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e6 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
struct Node {
int u;
ll d;
bool operator > (const Node &o) const { return d > o.d; }
};
int w[maxn];
vector <Node> g[510], e[maxn];
ll dis[510][510], d[510];
bool vis[510];
void dijkstra(int s) {
memset(d, 0x3f, sizeof(d));
memset(vis, false, sizeof(vis));
priority_queue <Node, vector<Node>, greater<Node> > q;
d[s] = 0; q.push({s, d[s]});
while (!q.empty()) {
int u = q.top().u; q.pop();
if (vis[u]) continue;
vis[u] = true;
for (auto p : g[u]) {
int v = p.u, w = p.d;
if (d[u] + w < d[v]) {
d[v] = d[u] + w;
q.push({v, d[v]});
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
freopen("subway.in", "r", stdin);
freopen("subway.out", "w", stdout);
int c, n, m, dd, q;
cin >> c >> n >> m >> dd >> q;
for (int i = 1; i <= m; i++) cin >> w[i];
for (int i = 1; i <= n; i++) {
int k;
cin >> k;
for (int j = 1; j <= k; j++) {
int a, t;
cin >> a >> t;
e[a].push_back({i, t});
}
}
for (int i = 1; i <= m; i++) {
for (auto e1 : e[i]) {
for (auto e2 : e[i]) if (e1.u != e2.u) {
g[e1.u].push_back({e2.u, e1.d + e2.d});
g[e2.u].push_back({e1.u, e1.d + e2.d});
}
}
}
for (int i = 1; i <= n; i++) {
dijkstra(i);
for (int j = 1; j <= n; j++) dis[i][j] = d[j];
}
while (q--) {
int u, v;
cin >> u >> v;
ll ans = 1e18;
for (auto e1 : e[u]) {
for (auto e2 : e[v]) {
ans = min(ans, dis[e1.u][e2.u] + e1.d + e2.d);
}
}
cout << ans + w[u] + w[v] << "\n";
}
return 0;
}
:::
:::info[migrate]
```c++
#include <bits/stdc++.h>
#define lc ((u) << 1)
#define rc (((u) << 1) | 1)
using namespace std;
using ll = long long;
const int maxn = 2e6 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
vector <pair<int, int> > g[maxn*4];
ll x[maxn], cnt[maxn*4], dis[maxn*4];
int id[maxn], tot, qx, qy, qk;
void build(int u, int l, int r) {
tot = max(tot, u);
if (l == r) {
id[l] = u;
return;
}
g[u].push_back({lc, 0});
g[u].push_back({rc, 0});
int mid = (l + r) / 2;
build(lc, l, mid);
build(rc, mid + 1, r);
}
void add(int u, int l, int r) {
if (qx <= l && r <= qy) {
g[qk].push_back({u, 1});
return;
}
int mid = (l + r) / 2;
if (qx <= mid) add(lc, l, mid);
if (qy > mid) add(rc, mid + 1, r);
}
void bfs(int s) {
deque <int> q;
dis[s] = 0; q.push_front(s); cnt[s] = 1;
while (!q.empty()) {
int u = q.front(); q.pop_front();
for (auto p : g[u]) {
int v = p.first, w = p.second;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
cnt[v] = cnt[u];
if (!w) q.push_front(v);
else q.push_back(v);
} else if (dis[u] + w == dis[v]) cnt[v] += cnt[u];
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
freopen("migrate.in", "r", stdin);
freopen("migrate.out", "w", stdout);
int c, T;
cin >> c >> T;
while (T--) {
int n;
ll d;
cin >> n >> d;
if (n > 5000) {
cout << "0\n";
continue;
}
for (int i = 1; i <= n; i++) cin >> x[i];
// build(1, 1, n);
// for (int i = 1; i <= n; i++) {
// qx = lower_bound(x + 1, x + n + 1, x[i] - d) - x;
// qy = upper_bound(x + 1, x + n + 1, x[i] + d) - x - 1;
// qk = id[i];
// add(1, 1, n);
// }
tot = n;
for (int i = 1; i <= n; i++) {
id[i] = i;
qx = lower_bound(x + 1, x + n + 1, x[i] - d) - x;
qy = upper_bound(x + 1, x + n + 1, x[i] + d) - x - 1;
for (int j = qx; j <= qy; j++) g[i].push_back({j, 1});
}
// for (int i = 1; i <= tot; i++) {
// cout << i << ": ";
// for (auto j : g[i]) cout << j.first << " " << j.second << "/";
// cout << "\n";
// }
ll ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= tot; j++) dis[j] = inf, cnt[j] = 0;
bfs(id[i]);
for (int j = 1; j <= n; j++) if (cnt[id[j]] == 2) ans++;
}
// for (auto p : st) cout << p.first << " " << p.second << "\n";
cout << ans / 2 << "\n";
for (int i = 1; i <= tot; i++) g[i].clear();
}
return 0;
}
:::
:::info[hub]
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e6 + 10;
vector <int> g[maxn];
int fa[maxn][20], dep[maxn], siz[maxn];
ll dp[maxn];
int n, k;
void dfs(int u, int p) {
fa[u][0] = p; dep[u] = dep[p] + 1; siz[u] = 1;
for (int i = 1; i < 20; i++) fa[u][i] = fa[fa[u][i-1]][i-1];
for (int v : g[u]) {
if (v == p) continue;
dfs(v, u);
siz[u] += siz[v];
}
}
void dfs2(int u, int p) {
for (int v : g[u]) if (v != p) {
dfs2(v, u);
dp[v] = dp[u] + n - 2 * siz[v];
}
}
int lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (int i = 19; i >= 0; i--) if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
if (u == v) return u;
for (int i = 19; i >= 0; i--) if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
return fa[u][0];
}
int dis(int u, int v) {
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
int f[maxn];
int Find(int u) {
return f[u] = (f[u] == u ? u : Find(f[u]));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
freopen("hub.in", "r", stdin);
freopen("hub.out", "w", stdout);
srand(time(0));
int c, T;
cin >> c >> T;
while (T--) {
cin >> n >> k;
for (int i = 0; i < n; i++) g[i].clear();
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
u--; v--;
g[u].push_back(v);
g[v].push_back(u);
}
if (n > 20) {
cout << rand() % (n / __lg(n)) + 1 << "\n";
continue;
}
dep[0] = 0;
dfs(0, 0);
int ans = 1e9;
for (int S = 0; S < (1 << n); S++) {
if (__builtin_popcount(S) != k) continue;
for (int i = 0; i < n; i++) f[i] = i;
for (int i = 0; i < n; i++) if (S & (1 << i)) {
for (int j : g[i]) if (S & (1 << j)) f[Find(i)] = Find(j);
}
int cnt = 0;
for (int i = 0; i < n; i++) if (S & (1 << i)) cnt += (f[i] == i);
if (cnt > 2) continue;
int mx = 0;
for (int i = 0; i < n; i++) if (!(S & (1 << i))) {
int mn = 1e9;
for (int j = 0; j < n; j++) if (S & (1 << j)) mn = min(mn, dis(i, j));
mx = max(mx, mn);
}
ans = min(ans, mx);
}
cout << ans << "\n";
}
return 0;
}
:::