NOIP 2024 游记

· · 生活·游记

坐标 GD DG DH

Day -inf

在 CSP 中取得了 300 pts 的成绩，这确实是令人振奋的。在校内的高一年级中可以排到 rk 1 ，全校 rk 3。遗憾是因为精力问题连 T4 的题面都没有看下去。

考完 CSP 之后，颓废了一段时间，后来重新规划了一下要做什么，决定刷刷 CF。花了一些时间研究了一下从洛谷上爬带翻译的 CF 题面，并打印出来文化课上摸鱼看。

然后就是真题训练，开头的 NOIP 2020 给我的打击不小，T1 原以为是模拟水题，结果因为数据类型的原因给我卡到 60pts，T2 不会做，只会 O(N\sqrt{N})。这让我意识到如果我离滑下一等并不遥远，OI 什么事情都可以发生，这是我焦虑了一段时间。我原本对我水平的预估是稳切蓝题的，但是 T2 直接使我发生了严重的自我质疑。

NOIP 2021 由于花的时间太少了，只做了 T1。

NOIP 2022 。T1 一道 DP 水题，半个小时切了。由于我预先知道喵了个喵的恶名，我直接跳了 T2 去想 T3。T3 的样例过于离谱，第一和第二样例经过缩点之后只剩下两个点，屁用没有，最终不停地猜测转移式，终究是场切了。赛后一看竟然是紫题，使我振奋了不少，然而 T1 因为忘记换行，然而样例都是单测，挂到 1 分。二等并非不可能发生的事情。

NOIP 2023 。T1 签到题，T2 并查集毒瘤，写了近一个半小时才过大样例。T3 骗分骗到 70 pts。

Day -week

与同学开黑打了一场 CF，想着借此上 1600，切了 A,B,C1,C2。我原本预计我只能切到 C2，所以做题的时候就有很明显的心理暗示——做完这题就下班。然而 AC C2之后见讨论 D 更简单，然而大脑已经罢工不干了，最终直接贺了同学的思路。

1581 差一点上 1600，算是一个遗憾吧。不过有点令人疑惑的是，我同学赛前 rating 比我低，赛时分比我高，然而加分比我少。

周二教练组织了模拟赛，个人评估 1 绿 + 3 蓝，直接狂砍 384 pts ，给我自信了。在同一天，经过不懈努力，本人终于学会了三阶魔方的全流程，这时魔方界的一小步，却是 Dangerise 的一大步 !

不过我感觉我的状态越来越差，做题的思考不再集中，反而开始更加依赖注意力。

周四的一整个晚上尝试自己做一道紫题，虽然有思路，但是调不出来，我的实力大抵是止步于此了。

Day -1

机房摸鱼，开始写这篇游记。

准考证发下来了，第一考场的第一座位，算是一个吉利。

和机房的同学对了一下准考证，结果都在同一个考场！！！有一位同学直接在第三座位。

比赛日

由于学校是某 新一线城市 ，所有我们必须极早地出发。本来闹钟定的 5:30，但大抵是心理暗示的作用，醒来的时候只有 5:10 。

5:50 离开宿舍，前往学校大门集合，准备乘车出发。

5:55 在车上，领队提醒检查一下证件，我自己检查了一下，并没有发现身份证，于是急忙告知一位老师，他带着我骑小电驴回教室找。回教室疯找一通，没有找到，但是突然回忆起自己有将身份证和准考证放在一起的动作，于是打电话回车上，发现身份证确实被准考证和另一张资料夹在一起。

6:10 天边方显现出一丝光亮，我们循着曙光出发。学校将早餐送到了车上，我喝了豆奶，感觉味道不错，但是我的肠胃并不这么觉得，开始翻江倒海地抗议，本打算在车上休息，然而因为肚子，休息不了一点。

7:20 我们抵达了考场，于是不得不感慨 新一线城市 和真正的一线城市的区别。我们是最早一批到达考场的，门口的似是老师的人很惊讶，问是哪来的，答：“DGDH”。然后我们谈到了今年学校在 CSP 中的获奖，DH 竟然是全市获奖人数最多的，有五十多位三等奖，属实蚌埠住了。还有横幅上为什么是 GDCA 而不是 CCF，我还要 **** 它呢。

7:35 进入报告厅。我与另外两位同学一同去厕所窜，进到厕所就不得不再一次地感慨，这就是倾一座一线城市全市之力打造的学校吗 ! 厕所恰好有三个蹲位，直接开始三排。在厕所里规划了一下开题，前两题硬干，以我的实力应该能稳稳拿下，后两题先打暴力。

7:50 原本以为报告厅要讲些什么，原不过只是集合，到点之后直接将选手带到机房。到考场一看，有些惊人，考场一半是我校的，另一半是同市的另一个学校，错位相坐。主办方是会排座位的。

8:10 进考场，考场准备了农夫山泉的绿瓶纯净水。其中一位监考老师看起来还挺年轻的，还穿着 ICPC 的衣服。

开考 !

8:27 开考 不过写让我码一会头文件 完全版

8:33 PDF 的密码输了三次都没有输对，有点红温，不过先来看题。第一题的题面看起来像是一个很简单的贪心，有思路了先写。

8:40 输出是 0 但是为什么呢？我靠原来 t 有两个。

8:45 完了有点不会啊，小 D 啊小 D 你可以要拿 NOIP 一等的人啊，你总不能 T1 就废了啊！你不是觉得你赛时可以稳切蓝吗 !

8:47 冷静下来，就当 CF 在打。

8:50 我好像会了 ！！！开写

8:55 WA on example 1

9:00 重新检查了一下思路，我觉得非常对。

9:05 我超！我都写的啥。改了

WA on example 2

9:10 我懂了，并查集救我 !

9:20 WA on example 2

继续回顾思路，还是感觉对得不能再对，发现代码又是写得依托，改改改。

9:30 examples passed

复刻的赛时代码如下

struct S {
    int fa[N];
    void init(int x) {
        L(i, 1, x) { fa[i] = i; }
    }
    int find(int x) {
        if (fa[x] == x) {
            return x;
        } else {
            return fa[x] = find(fa[x]);
        }
    }
    void join(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            fa[fx] = fy;
        }
    }
};

S as, bs;
int n;
char a[N], b[N], ta[N], tb[N];
int ac[N][2], bc[N][2];
signed main() {
    int T = qread();
    while (T--) {
        n = qread();
        as.init(n), bs.init(n);
        me(ac, 0);
        me(bc, 0);

        scanf("%s%s%s%s", a + 1, b + 1, ta + 1, tb + 1);

        L(i, 1, n - 1) {
            if (ta[i] == ta[i + 1] && ta[i] == '1') {
                as.join(i, i + 1);
            }
            if (tb[i] == tb[i + 1] && tb[i] == '1') {
                bs.join(i, i + 1);
            }
        }

        L(i, 1, n) {
            ac[as.find(i)][a[i] - '0']++;
            bc[bs.find(i)][b[i] - '0']++;
        }

        int ans = 0;
        L(i, 1, n) {
            int af = as.find(i), bf = bs.find(i);
            L(v, 0, 1) {
                if (ac[af][v] > 0 && bc[bf][v] > 0) {
                    ac[af][v]--;
                    bc[bf][v]--;
                    ans++;
                }
            }
        }

        printf("%lld\n", ans);
    }
    return 0;
}

完了，我怎么 T1 就花了那么久。

9:32 开 T2

9:35 有点震撼，没什么思路。

9:40 开始使用注意力

9:45 样例很良心地涉及了每一个特殊性质，太好了。注意到，当 m=1 ，ans=v^{n-1}

9:50 然而为什么呢？好怪好怪

10:00 我超，看错题了。我看成了 当 x_i=a_i，须有 x_{i+1}\not=b_i

10:20 然而这个性质是是怎么来的呢？

10:30 我超！又看错了题了，原来二元限制只有 n-1 个，这样一切都说的通了。

10:40 思考相邻两个单元约束直接的关系

10:50 我感觉会了，开写 !

11:15 WA on example 2

11:30 漫无目的地调试

11:35 注意到错误的数据，应该是不相邻的单元约束的式子写错了，重新推式子。

11:50 passed examples

复刻代码

constexpr int N = 114514;

struct R {
    int c, d;
};

R r[N], inp[N];
int rc[N], rcn;

int n, m, v;
signed main() {
    int T = qread();
    while (T--) {
        n = qread(), m = qread(), v = qread();
        me(r, 0);
        rcn = 0;
        L(i, 1, m) {
            inp[i].c = qread(), inp[i].d = qread();
            rc[++rcn] = inp[i].c;
        }
        sort(rc + 1, rc + 1 + rcn);
        rcn = unique(rc + 1, rc + 1 + rcn) - (rc + 1);

        bool fail = 0;
        L(i, 1, m) {
            int p = lower_bound(rc + 1, rc + 1 + rcn, inp[i].c) - rc;
            if (r[p].d && r[p].d != inp[i].d) {
                fail = 1;
                break;
            }
            r[p] = inp[i];
        }

        if (fail) {
            puts("0");
            continue;
        }

        int ans = qpow(v, 2 * (r[1].c - 1));
        L(i, 1, rcn - 1) {
            int nw;
            if (r[i].c == r[i + 1].c - 1) {
                nw = (v * (v - 1) % mod + 1) % mod;
            } else {
                nw = (qpow(v, 2 * (r[i + 1].c - r[i].c)) -
                      qpow(v, r[i + 1].c - r[i].c ) +
                      qpow(v, r[i + 1].c - r[i].c - 1) + mod) %
                     mod;
            }
            ans = ans * nw % mod;
        }
        ans = ans * qpow(v, 2 * (n - r[rcn].c)) % mod;
        printf("%lld\n", ans);
    }
    return 0;
}

11:52 看 T3

11:55 不看了，看 T4

12:00 感觉 T4 的暴力比 T3 好写很多，用 ST 表可以轻松拿下 O(n^2) 和特殊性质 B 的部分分。

12:30 写了特殊性质 A 和 B,准备看回去做 T3

12:40 头好痛，看不下去，并且突然意识到自己 T4 的特殊性质 A 的复杂度是错的，明明样例跑得还挺快的。

12:50 不会改

1:00 Bye Bye

期望分数 100+100+0+40=240

T2 感觉很多人都会做，240 应该是一个非常大众的分数了。

车上和同学讨论了一下，感觉 T2 确实很多人都会做，去年 GD 的分数线来到了 199 pts，虽然是因为去年有签到题，但是我感觉今年的 T1 也挺签到的，只是我太菜了写太久罢了，没想到上洛谷看到难到了不少人。

CCF 似乎要砍一等的名额，总不能上 200pts 吧。

周一周二中段考，滚回去复习了。