NOI 2024 退役记

· · 生活·游记

OI 始末

小学的时候，我觉得编程很酷，在路上捡到一张机构的宣传单，就高高兴兴去学了。考了一个叫普及组的东西，拿了二等奖，跟我一起学的 sleeping_crawlers 当年拿了一等奖，然后就不去上课外班了，我以为这就是终点了，于是在初二拿到 CSP-J 一等奖之后，就专心准备中考了。

中考后来石家庄二中，有个竞赛体验营，我一看，怎么还有信息竞赛，试听，这不就是我小学学过的东西嘛！跟教练交流了一下，我还是很喜欢这门学科的，决定试一试，于是暑假开始从语法学起（小时候边玩边学的全给忘了）。这时候发现原来 sleeping_crawlers 拿了普及一等之后不是不学了，而是被石家庄二中挖走了。可恶，石家庄二中怎么不挖走我，这样我就不是零基础了！

不过发现自己水平进步挺快的，最后走到了国赛，拿了银，也是符合自己高一的预期了。感觉零基础拿银很厉害，需要显摆一下，于是有了这一段话。

从 2022 年 7 月 5 日在洛谷提交第一道教练留的题 P5703 开始，到 2024 年 7 月 21 日 NOI 2024 闭幕，我的 OI 生涯大约是 747 天。

结束了！——杜子德

7 月 10 日

石家庄这个鸟不拉屎的地方竟然办市赛了，阿克之。监考老师问我是不是来体验生活的，随机回答了一下，但是心里很爽（

7 月 11 日

前往重庆，早上起来鼻子不通气，到重庆后更加严重了，感冒了，不知道是不是前几天 haosen 的室友传给 haosen，haosen 又传给我的。吃蹄花，一顿饭花了 18 块，一个猪蹄，一堆小菜，一份豆花，超级好吃还实惠，但是我不应该吃辣啊！买了感冒药和水果，感冒药是华北制药的，家乡货。

7 月 12 日

南夫拉斯模拟赛，被 haosen 爆杀了。中午和 haosen 一起吃米线，量好大，好饱，但是我又没忍住吃了辣的。晚上和 haosen 一起在外面找饭店。

重庆的地是不平的，haosen 和我一起走，指着下面：“看，樱雪喵！”

我一看好像是樱雪喵和她妈妈在一起走，我不太认识，我以为 haosen 跟樱雪喵挺熟但是不敢叫樱雪喵，于是远远地喊了一声“【樱雪喵真名】！”声音有点小，没听见，于是超大声又喊了一遍，樱雪喵就过来了：“大街上有人喊自己名字真恐怖”。

结果 haosen 不说话，我们面面相觑，我俩自我介绍了一下，非常尴尬地溜走了，原来 haosen 跟樱雪喵不熟啊。感觉还是很尴尬，托 Cx330qwq 跟樱雪喵解释了一下。haosen 去加樱雪喵 QQ，成功了。我这也是成人之美了，RP++。

和 haosen 吃刨猪汤饭，撑。吃完了打 UNR 笔试，阿克。

7 月 13 日

UNR Day 1。早上在路边看见有一只小狗欺负小猫，正义制裁了小狗，RP++。有一些分没打上，发挥比较正常。继续疯狂吃饭，好吃。吃完饭往回走的时候突然下大暴雨，带伞了还是没有全部防出去，成落汤只因了。

7 月 14 日

早上吃豌杂面，豌豆明明就是软的，石家庄二中你为什么往豌杂面里面放一堆炸豌豆。UNR Day 2。乱写 T2 拿了 40 分，T3 又是我擅长的 ds，发挥得很好，单日 rk 55 了。fzj Day 2 崩了，于是我总榜 HE rk 2，打 Ag 了，开心。APJ Au 了，太恐怖。

中午和 haosen 吃了银牌豌杂面（不是早上那一家），对 fzj 和 APJ 来说太晦气了，对我俩来说很吉利！拍 haosen。

7 月 15 日

最后一场模拟赛了，开场没多久会了 T1 的根号 \log，感觉过不去，但是全机房都开敲了，心态受到打击，不如换个赛道开摆，弃掉前两题，写了四个小时 T3（提答题）喜提超低分。就当叠 RP 了。这几天教练总是在我快睡觉的时候来找我聊半小时，然后让我早点休息；或是在我快吃饭的时候来找我聊半小时，然后让我早点吃饭。

晚上想少吃点，打算去 KFC 买个汉堡，但是有个秘汁全鸡好想吃啊，然后吃了一整只只因。KFC 里全是原神。

7 月 16 日

报到日，和 fzj，_LAP_，ReTF 一屋，纪念品不是毛绒玩具，差评。中午饭水平高于 WC，喜，又吃了一堆。HE 省队到齐了，进行经典的互相拍照。拍 haosen。

去自习室，猫把我电脑霸占了。

晚上教练要带我们吃饭，出去之前教练想给我们在门口拍点照片，刚给 fzj 拍完，杜子德等一大帮领导过来了，和杜子德合了个影，RP++ 还是 RP-- 呢，我不知道。

教练嘱咐我们不要在宿舍玩牌，然后晚饭前就带我们打麻将，谔谔。晚饭辣的别的人不吃，就我吃吃吃，有点不好意思。吃晚饭时 HE 的徽章到了，我是徽章志愿者，吃完饭搬到宿舍发了。藏了若干次 haosen 的水杯和徽章，haosen 可爱捏。

夜宵有看起来很诡异的南瓜绿豆汤，但是很好喝。勾式育才宿舍，床比我还短，睡觉很难受。但是感冒终于好了。

7 月 17 日

开幕式，水平不高，有意义不明的抽象节目和与 WC 重复的节目。去年开幕式叫河北代表队起立挥手的时候，我非常激动和忐忑，但是今年却没有任何感觉，也没啥劲换徽章。真是“欲买桂花同载酒，终不似，少年游”啊。

晚上笔试，我无论是去年 NOI 还是这两年的 UNR，再刁钻的题都阿克了，笔试题库倒背如流，不慌。跟 haosen 坐一起。开考之后还没刷新出来呢，全场开始爆笑，原来是把 std 发下来了。haosen 也收到了 std。

广播说笔试推迟，我就去看 haosen 电脑上的 std，有一题是问考前能否触摸键盘鼠标，答案竟然是能，还好没有真考这一题，要么我可能就该错了。过一会儿笔试重新开始了，卧槽，题竟然跟刚才那个一样！那我赢麻了，得亏看了 std，仔细检查若干遍就交了。出分一看卧槽，99！考前不能触摸键盘鼠标！std 是假的！被晃飞了！

看见 fzj 和 _LAP_，他俩的 std 都是对的，而且都得满分了，怀疑 haosen 误触修改了 std。虽然知道笔试没用，但莫名其妙被扣一分还是很难受，看群里，原来今年题跟去年完全相同（除了第一题问今年是第几届 NOI 的不同，但两年都是选 A），下发的不是 std 而是去年同考号考生的作答。那我还挺倒霉的，一样的题去年没错今年被下发的玩意坑了。

晚上睡觉，似乎有点紧张，ReTF 在我对面一直大喘气和翻身，育才的床还巨响无比，每次快睡着的时候就会被 ReTF 的翻身声搞醒，急急急，过亿会儿 ReTF 来找我问我紧张不，我说你别翻身了。然后 ReTF 回去不翻身了，过一会儿就传来均匀的呼吸声。

坏了成小丑了，现在宿舍只有我没睡着了，越睡不着，大脑越混乱，完全不会睡觉了。不会再过两小时就起床了吧？不会我要通宵了吧？急急急急急，实在忍不住了看了一眼表，才三点，还有三个半小时起床，然后莫名安心了，睡着了。

7 月 18 日 Day 1

早上非常精神，但还是尽量少说话保存体力。进场后有点想答辩，怕昨天没睡好会头疼，憋着。

开考了，看题目摘要。怎么有二十个预测试点？意识到不对劲，预测试点远比样例多，坏了，变成近乎 IOI 赛制了（事实上，比 IOI 赛制还多大样例）！感觉 T1 很难啊，尝试用数据结构维护二分图，无果，怎么开考没多久就一堆人开始敲了！急，迅速更换思路，半小时会哈希了，过了一会儿写完了，调试稍有波折，问题不大。

T2 这不是我们快速选择算法嘛，结果一看朴素快选根本没分，稍微改一下就是 \log n 组共 n 次询问了，可以获得 11 分。n 应该是询问次数的下界，发现满分给的询问次数大于 n。牺牲询问次数换更少的询问组数？感觉这题真无意义（fzj 后来告诉我，工程中这样并行运算很有意义）。

比 n 多的那部分询问次数一定是关键，前若干次询问两两配对，最后一次直接像第一个包一样问完全图，就有三十多分。注意到本质上这个做法就是每次把 n 拆成若干完全图，写个 DP 算算最优次数吧。

DP 完一看，竟然有 78 分！给我整不会了，我没咋想过这交互 T2 拿这么多分啊，感觉够了，又想了一会儿，不会 100，100 肯定不是这种只问单一形式的完全图的唐氏做法，而是必有高论，比如若干图叠起来什么的，开摆。看了看 T3，去答辩。答辩的时候会了 T3 的 48 分，回来只剩两小时了，疯狂写，最后 T3 有 12 分的立方无性质暴力没写完。

感觉没有写什么有意义的部分分，但是 100+78+36=214 应该很高了啊，出去大概了解了一下，比 fzj 低 14，那还是很高了。APJ 只有 151 分。考前我怕 APJ Day 1 万一寄了心态不好，跟 APJ 说 Day 1 之后千万要搞好心态，但我感觉 151 确实没戏了，只能在觉得没戏的情况下仍然安慰 APJ 说有戏，不过我俩心里应该都有数吧。

fzj 把 T2 过了，原来 T2 根本没啥高妙东西，全是询问完全图，正解就是我那个做法稍微修改一点点，那真没意思，感觉被随机区分了。下午打明日方舟的新肉鸽，好玩。晚上我父母到重庆来旅游了，国赛后会再带我玩几天。

回了宿舍还是不困。怕睡得太少，明天社会活动会让我头疼，于是不想去，但是教练说得去，而且感觉明天在学校待一天的话缺乏运动容易睡不着啊，于是没有请假。

7 月 19 日

社会活动日，HE 是上午去，我还得早起，但是还算精神，在车上睡了一会儿。三峡博物馆还是有点意思的，但越往后的展厅越没意思。

回宿舍，看见穿着白衬衣，黑短裙黑长袜的于行健正在下楼，我一把就把他抱了起来，抱到了宿舍玩。

回宿舍又睡了一会儿，然后去自习室充电。晚上我妈给我发吃火锅的照片，好馋啊。晚上 ReTF 虽然不翻身了，但是他肚子疼，我快睡着的时候被他上厕所吵醒了，最后大约是十二点半睡着的。

7 月 20 日 Day 2

早上也挺精神的，吸取教训，在宿舍答辩，然后七点五十多才进场。由于我 Day 1 分比较高，而我不像 fzj APJ 那样高一已经有一块 Ag 了，决定保守打，先稳住 Ag 再说。

右面是叶隽霖，考完了才知道他是个 D 类金牌（去年 Day 2 我右面是魏佳泽）。这回场上敲代码的人远远少于 Day 1 了（不过我 Day 1 周围坐了一圈集训队，可能跟这个也有关系），看来 T1 较难，这对我很有利，我省选 2024 和 NOI 2023 都是靠过掉 Day 2 T1 比别人高了好多，不慌。

然后刚了俩小时，笑死，根本不会，卡常 90 分爆搜跑路。可能我不太会打顺风局，状态不太好，T2 假了一会儿，然后发现是数据结构。可是现在只剩两小时了，我后两题一分没得，只能放弃思考正解，求稳拼暴力。

学了两年 OI，我认为我唯一有点优势的就是数据结构，可惜最后一道数据结构题摆在面前，我却没有切掉，有点失落。

然后是无聊的拼暴力环节，拼上了 45+20，T3 的平方无性质暴力没打完，指数级的也没打，失 15 分，也算正常发挥了吧。

考后听见许淇文说他不会 T1，那我 90 分没啥问题。出考场见了 haosen，haosen 说完了，我说没事今天难，一问，他 160，我说你比我高啊，haosen 好像高兴多了。fzj Day 2 爆炸，无缘集训队了，APJ 过了 T2，总分 210 恐怖如斯，但 Day 1 确实太低，无力回天。

查分 90+45+20=155 没挂，事实上我考试快结束的时候发现我 T3 B 性质对于缩点后图的处理有问题，四个点就能卡掉，如果图不是强连通图很可能挂，但是过了 pretest，也过了 systemtest，看来 pretest 和 systemtest 的数据应该生成方式相同。稍微打听了一下，我这个分肯定是 Ag，上不去下不来，没有啥悬念，也没啥可期待的，就看看能不能进前一百了，于是开摆。haosen 好像有点悬，不过他看起来精神状态良好。

教练说我几乎零基础，学到 Ag 已经很不容易了，开心。下午在自习室教 haosen 打明日方舟的肉鸽，自习室有一些人大附中的，黄洛天也来了，了解到今天最难的题是 T1，不会组题可以不组。教练叫我出去跟我聊了聊文化课的事，回来之后继续和 haosen 玩粥。

吃完饭嘉年华，走到门口发现贴着榜，还是很炸裂的，因为知道自己是 Ag 所以没仔细研究。嘉年华比去年简单多了，好热好热，拿完唐龙奖品就回自习室，开始写游记了。

和 APJ 聊天，即使是把 fzj 的 Day 1 和他的 Day 2 拼起来，也只是 100+100+100+28+90+100+20=538，不算 A 队加分只是擦线 Au，感觉 HE 的前途一片黑暗。不过 NOI 2023 的时候大家也觉得 Au 很难拿，几个月之后再重新审视，结论可能会不一样吧。

回宿舍得知 fzj 已经先走了，宿管说可以提前走，那我明天下午就开溜去找我爸妈玩。

7 月 21 日

早上在床上写游记，没去食堂，把考试的时候发的面包牛奶吃了。想发游记，结果洛谷专栏爆炸了，怎么也上不去。

选手才艺展示，唱歌挺好，演讲也挺深刻，没啥 P 话，好评，换到了 xht 徽章和粉兔帆布袋。中午收拾东西，haosen 似乎很不高兴，然后我说了句不该说的话，haosen 更不高兴了。录到了 APJ 唱歌。

闭幕式的一堆领导讲话乏善可陈，但是节目比开幕式强多了，颁奖还没开始就把整个礼堂的人全弄出去排队站了，根本看不见礼堂内，差评。

和 swiftc 同一批拿到了一块 Ag，证书编号 118，应该就是排名了，跟 APJifengc 去年的排名一样。haosen 离 Ag 线差了 12 分，遗憾 Cu，希望他文化课运气爆棚！今年 HE 仍无人进前一百，HE 的未来交给 ReTF 他们了。

注意到我的得分等于金牌线和银牌线的平均数（下取整）。注意到 NOI 2023 和 NOI 2024 的 HE 前 5 名的全国排名的 LCS 高达 3。

信竞的学习大大开拓了我的眼界，增长了我的见闻，使我认识了五湖四海的，志同道合的朋友。希望无论结果如何，我们都在 OI 中能有所收获，期待我们于顶峰再相聚！

记得游记好像忘了写什么东西，但具体是啥想不起来了，到时候再补。

徽章

换出去了约 65 个徽章，面基了很多网友！加上去年换的，大概是九十多个，一起拍了张照片。上传了数次照片才成功，可能是有人的头像太像辣脆。徽章排列方法为随机打乱后依次拿出。

还帮 Dr_Gilbert 换了 10 个徽章，内含 MLE 大帝大头照一个。

代码

把考场代码拍下来了，谨以此纪念我最后一次 OI 比赛。

set.cpp

线性随机哈希做法，十个异或哈希，仍然飞快。随机数种子是乱填的。结构体里忘缩进了，混乱邪恶。

#include<bits/stdc++.h>
namespace IO{
const int L=(1<<20)+30;
char buf[L],*s,*t;
#define gf() (s==t&&(s=buf)==(t=buf+fread(buf,1,L,stdin))?-1:*s++)
void rd(int&x){
    x=0;char c=gf();
    while(c<48) c=gf();
    while(c>=48) x=x*10+(c^48),c=gf();
}
}
using IO::rd;
using namespace std;
const int N=200005,M=10,S=600005;
int n,m,q,ans[N],a[N][3],b[N][3];
mt19937 R(754674);
struct HSH{
unsigned f[N],g[S],res;
unsigned hsh(unsigned x){
    static unsigned a=R(),b=R(),c=R(),d=R();
    return x^=a,x+=b,x^=c,x+=d,x;
}
void add(int x,int y){
    res-=hsh(g[x]),g[x]+=f[y],res+=hsh(g[x]);
}
void sub(int x,int y){
    res-=hsh(g[x]),g[x]-=f[y],res+=hsh(g[x]);
}
}f[M][2];
bool chk(){
    for(int i=0;i<M;++i)
        if(f[i][0].res!=f[i][1].res)
            return 0;
    return 1;
}
void ins(int x){
    for(int i=0;i<M;++i){
        f[i][0].add(a[x][0],x);
        f[i][0].add(a[x][1],x);
        f[i][0].add(a[x][2],x);
        f[i][1].add(b[x][0],x);
        f[i][1].add(b[x][1],x);
        f[i][1].add(b[x][2],x);
    }
}
void del(int x){
    for(int i=0;i<M;++i){
        f[i][0].sub(a[x][0],x);
        f[i][0].sub(a[x][1],x);
        f[i][0].sub(a[x][2],x);
        f[i][1].sub(b[x][0],x);
        f[i][1].sub(b[x][1],x);
        f[i][1].sub(b[x][2],x);
    }
}
int main(){
    freopen("set.in","r",stdin);
    freopen("set.out","w",stdout);
    rd(n),rd(m),rd(q);
    for(int i=1;i<=n;++i) rd(a[i][0]),rd(a[i][1]),rd(a[i][2]);
    for(int i=1;i<=n;++i) rd(b[i][0]),rd(b[i][1]),rd(b[i][2]);
    for(int i=0;i<M;++i)
        for(int j=1;j<=n;++j)
            f[i][0].f[j]=f[i][1].f[j]=R();
    for(int l=1,r=0;l<=n;++l){
        while(r<=n&&chk()) ins(++r);
        del(l),ans[l]=r;
    }
    for(int l,r;q--;) rd(l),rd(r),puts(r<ans[l]?"Yes":"No");
    return 0;
}

richest.cpp

代码最短的一集，其实重要的代码是那个不用提交的 DP 打表程序。

#include"richest.h"
#include<bits/stdc++.h>
using namespace std;
const int A[9]={2,2,2,2,2,3,5,15,140};
const int N=1000005;
int c[N],m,a[N],n,b[N],tp;
void work(int k){
    for(int i=n/k*k;i<n;++i) b[tp++]=a[i];
    vector<int>u(n/k*k*(k-1)/2),v(n/k*k*(k-1)/2),w;
    int tu=0,tv=0;
    for(int i=0;i+k<=n;i+=k)
        for(int x=0;x<k;++x)
            for(int y=x+1;y<k;++y)
                u[tu++]=a[i+x],v[tv++]=a[i+y];
    w=ask(u,v);
    for(int i=0;i<m;++i) c[i]=0;
    for(int i=0;i<tu;++i) ++c[w[i]];
    for(int i=0;i<n;++i) if(c[a[i]]==k-1) b[tp++]=a[i];
    for(int i=0;i<tp;++i) a[i]=b[i];
    n=tp,tp=0;
}
int richest(int _n,int T,int S){
    m=n=_n;
    for(int i=0;i<n;++i) a[i]=i;
    if(T==1) work(n);
    else for(int i=0;i<9;++i) work(A[i]);
    // assert(n==1);
    return a[0];
}

tree.cpp

各种拼包，还有一个很长的没写完的包，一共 157 行，懒得抄了。

fraction.cpp

在这题上浪费的时间过多了，否则可以冲冲 T2 的。

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long ans;
void dfs(int x,int y){
    ans+=x<=n,ans+=y<=n;
    if(x<2*y) for(int X=x;(X+=y*2)<=m;) dfs(X,y);
    if(y<2*x) for(int Y=y;(Y+=x*2)<=m;) dfs(x,Y);
}
int main(){
    freopen("fraction.in","r",stdin);
    freopen("fraction.out","w",stdout);
    scanf("%d%d",&n,&m);
    if(n>m) swap(n,m);
    dfs(1,0);
    printf("%lld\n",ans-2);
}

mountain.cpp

145 行，谁爱抄谁抄，摆。

graphee.cpp

这位更是 148 行，摆。