CSP-J/S 2026 游记

· · 生活·游记

我无疑是糖丸的。

Day 0

体育课故意不小心摔倒了,下午请假去医院了,也算是停了半天课吧。所幸主包的腿还能走路。

Day 1

早上跟车 7:45 就到考场了。当时下起了小雨,老师让我们直接进去了。

到了机房发现环境不错,眯了一会,静待开始。

上午解压密码是 Trick||Treat!。打开题面,T1 看起来十分正常,大概 10\min 就做完了。

看到 T2 有点脊背发凉。我立马看出这是个双指针,但是这个代码肯定不怎么好写。写完第一遍后过了前 3 个样例,但第 4 个样例怎么调都过不去。随后我在 9:39 写了个对拍,发现一组 hack:

2
2 a
4 b

过了之后又发现了另一组 hack:

2
4 a
2 b

当场气晕。此时大概是 10:00,赶紧写了个 68 分的暴力就去看 T3 了。T3 先想到一个假做法:排序后取最大的 m 个按位与起来。但很快我就发现可以在二进制下从高到低按位贪心。10\min 切掉。

打开 T4,和之前有一题好像比较类似。先是打了一个 O(n^2\log n) 的纯暴力模拟。然后我注意到每个数肯定会跳到他最后一次出现的位置加一(这个性质可以看样例理解一下)。这样我就保证了每次游戏每种类型的数只被统计一次,复杂度最劣 O(nm)。其实这里只要想到让 i 和 lst_{a_i}+1 连边就做完了,可惜没有意识到这一点。

后面又写了个 T3 的对拍,简略地乱搞了一下 T2,就睡觉了。最后 100+68+100+56=324 离场。

中午去了和去年一样的饭店吃饭。

下午差不多 14:00 进的考场,也是简单眯了一会。压缩包密码是 Oct31==Dec25?,不得不说今年 CCF 还是很细节的。

:::info[FUN FACT] 在西方文化中,万圣节(10 月 31 日)被视作年底大型节日季的开端。接下来紧接着就是感恩节(11 月下旬)和圣诞节(12 月 25 日)。所以很多人在万圣节时会感叹“这一年快结束了,圣诞节马上就要到了”。

同时 Oct 是八进制的简称,Dec 是十进制的简称,而

(31)_8=(25)_{10}

:::

T1 十分经典,感觉以前有类似的,14:39 就切掉了。

T2 读题还是花了我不少时间。我是先直接按题面把站台和站厅作为节点暴力建图跑 Dijkstra。然后我就发现可以把每条线上的所有站台都缩成一个点。进一步地,我就发现可以以线路为节点建图。这个时候聪明的我认为边数很少,所以就没改之前打的 Dijkstra。在最后一个大样例跑了 0.2\text{s} 后,我就放心地去看 T3 了。

看到 T3 第一眼想到的是线段树优化建图再 01-BFS 求最短路树然后在最短路树上乱搞。不过我不知道怎么乱搞,于是只能在线段树优化建图后暴力统计答案。但是第 3 个大样例挂了。于是我只能暴力建图然后暴力 BFS 算答案。

T4 想到了要二分答案,但是想不出怎么判定。打了个 O(2^nn^2) 的暴力就回去看 T3 的特殊性质了。

最后的时间基本上半睡半醒,100+100+24+15=239 离场。

然后就发现 S 组 T2 挂了大分,当场心态爆炸。

晚上睡觉的时候想出了 T4 的正解。

Day 2

早上复现了 subway 的代码,交上去发现有 76\text{pts},长出一口气。又复现了 card 的代码,获得了 68\text{pts} 的好成绩。

Day 3~5

复习期中考(实际上一直在颓)。

Day 6

中午回来发现能查分了。

J:100+76+100+68=344,没错 T2 那个错误的正解骗了 8\text{pts}。

S:100+100+24+15=239,T2 没 挂 分!!!

完结撒花~

赛时代码

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;
}
:::