\texttt{NOI[D] 2024}

\texttt{Day 7/3}

中考完了。

坐火车来到了重庆。

\texttt{Day 7/4-7/12}

模拟赛。

怎么打了一场仨暴力 rk1 啊？？怎么有个 A 题唐氏 100\to0 啊？？怎么有场人均题坐牢 3h 不会，非人均题 30min 切了啊？？

总结：mt19937 rng;int my_rank=rng()%people_count+1;

\texttt{Day 7/13}

被拉去锻炼了 /dk

走了 ??km，腿走废了。

\texttt{Day 7/14}

搬到了 YCZX 附近。

晚上被拉出去了。

\texttt{Day 7/15}

摆了一天。

\texttt{Day }\mathrm{-1}\texttt{ (7/16)}

报到。

签到完想和同学们去打乒乓球的，但是找不到乒乓球馆，于是在篮球馆对着地打起了球。所以这种运动叫啥？Ground table tennis？

饭挺好吃的。

\texttt{Day }0

开幕式看到 dzd 讲话就开始玩手机了。

下午笔试。试机题这不是我们的 NOIP 2023 吗。乱打了点东西上去。笔试怎么挂了一个啊。/fn

晚上想着不能再颓了。打了 Dinic，NTT，FHQ Treap。下面是我 FHQ 的代码：

mt19937 R(chrono::steady_clock::now().time_since_epoch().count());
struct info{unsigned p;int v,l,r,sz;info(int v):v(v),p(R()),l(0),r(0),sz(1){}info(){}}tr[1100005];int tot,rt;
void pushup(int x){tr[x].sz=1+tr[tr[x].l].sz+tr[tr[x].r].sz;}
void split_v(int x,int &l,int &r,int v){if(!x)return void(l=r=0);if(tr[x].v<=v)l=x,split_v(tr[x].r,tr[l].r,r,v),pushup(l);else r=x,split_v(tr[x].l,l,tr[r].l,v),pushup(r);}
void split_s(int x,int &l,int &r,int s){if(!x)return void(l=r=0);if(1+tr[tr[x].l].sz<=s)l=x,split_s(tr[x].r,tr[l].r,r,s-1-tr[tr[x].l].sz),pushup(l);else r=x,split_s(tr[x].l,l,tr[r].l,s),pushup(r);}
void merge(int &x,int l,int r){if(!l)return void(x=r);if(!r)return void(x=l);if(tr[l].p>=tr[r].p)x=l,merge(tr[x].r,tr[l].r,r);else x=r,merge(tr[x].l,l,tr[r].l);pushup(x);}
void ins(int x){int p;split_v(rt,p,rt,x),tr[++tot]=info(x),merge(p,p,tot),merge(rt,p,rt);}
void del(int x){int p,q;split_v(rt,p,rt,x),split_v(p,p,q,x-1),merge(q,tr[q].l,tr[q].r),merge(p,p,q),merge(rt,p,rt);}
int rnk(int x){int p,r;split_v(rt,p,rt,x-1);r=1+tr[p].sz;merge(rt,p,rt);return r;}
int kth(int x){int p,q,r;split_s(rt,rt,p,x-1);split_s(p,q,p,1);r=tr[q].v;merge(p,q,p);merge(rt,rt,p);return r;}
int pre(int x){int p,q,r;split_v(rt,p,rt,x-1);split_s(p,p,q,tr[p].sz-1);r=tr[q].v;merge(p,p,q);merge(rt,p,rt);return r;}
int nxt(int x){int p,q,r;split_v(rt,rt,p,x);split_s(p,q,p,1);r=tr[q].v;merge(p,q,p);merge(rt,rt,p);return r;}

\texttt{Day }1

这几天不知道喝了多少罐雪碧了。

密码是 kmfrjf。科目繁荣解法？

怎么有 pretest 啊。那什么时候能变成 IOI 赛制。

看 T1。这么签到。\Theta(m!q) 有 60\text{pts}。哦可以直接哈希维护啊。哦可以莫队，\Theta(n\sqrt q)。这能过吗。想了 20min。没想出来咋优化。不管了先写了。啊最后俩点怎么 T 了。Test19 跑了一点零几秒。加了个快读，卡过了 test19。期望得分 [90,100]。扔了。

看 T3。这么不可做。非多项式暴力写了。A 性质直接 dfs，写了。B 性质不是 2-SAT 吗。这玩意不是求不了字典序最小解吗。推了下，发现这个题的 2-SAT 有性质，可以做。写了。36\text{pts}，扔了。

看 T2，sub1 写了。sub2，哦直接分治可以 t=20。写了，11\text{pts}。发现可以分治 12 次然后直接询问所有的，t=13。写了，37\text{pts}。发现每次可以不止二分。取了个 t=9 的，随便过了 63\text{pts}。然后搞 t=8，搞不出来。写了个爆搜。搜出来一个 67\text{pts} 的序列 \{2,2,2,2,3,6,19,183\}，s=1099960。感觉把一些 19 换成 18 或者 20 可以减少次数。又写了个打表，发现第七轮分 179 个 19 和 4 个 18 可以做到 s=1099954。写写写，诶怎么挂了。我草我怎么找最大值初值设了 0，改成 -1 过了 70\text{pts}。

期望得分 [90,100]+85+36=[211,221]。

中午继续打块，手感怎么没了。输了三把。三点去查分。怎么不开门。怎么不开门。怎么不开门。热死了。开门了，登录，查分。95+85+36=216。我草怎么人均 200+。这是 NOI 吗。OU 打了 247，拜谢。Ranker 218，小 D 206。

下午讲题。我草 T2 正解是从上往下构造。唐完了。T3 听说数据极其抽象，\Theta(2^nn) 冲过了 n=10^5？？

\texttt{Day }499122178

上午去了社会活动。但是重庆博物馆我上次就来过了啊，怎么又看一遍啊。。。

回来吃完饭 12:05，开始五人开黑 hdu 多校！（我和 OU、ranker、小 D、yyq）

我签了三个到，其他人也纷纷过题。13:25 就签完了九个题。

14:29 过的 J。然后五个人唐氏了一个小时 G 才反应过来三元环计数是典题。15:48 切了。Ranker 一直在赤石 K 题，最后居然 16:54 绝杀 AK！

晚上无聊切了入门赛。和同学们玩了词语接龙：

一个人出题，另外四个人依次说一个字，连成一句话。

例：ymh：这个寝室里的人的共同特点？

ranker：giao，OU：批，小 D：反，yyq：动

好吧我其实都不是

你也可以“拆”人家意思，有时甚至能救场。

例：OU：【数据删除】和【数据删除】最喜欢做什么？（你可以理解为想要进行人身攻击）

小 D：爱，yyq：上，ymh：层，ranker：楼

睡觉前无聊翻手机，突然发现我入门赛 B 题实际上没有过掉，只是唐氏排行榜上显示了绿色。那我岂不是痛失 rk1。

\texttt{Day }2

密码：fmdrpk。父母大人 PK？

看 T1。抽象。看 T2，抽象。看 T3，抽象。

想 T1，发现 \Theta(nm) 是显然的。写了。然后没思路了。

想 T3，以为想出了 \Theta(n^2) 的做法，写写写，样例挂了，发现假了，只能过其中 A 或 B 性质。慌了，扔了。扔之前发现 A 性质是直接缩 SCC，还有暴力，但是都只有 5\text{pts} 所以暂时没写。

想 T2，发现单个点可以 \Theta(n^2) dp，然后倒过来就能 \Theta(n^2) 算所有点的答案。写的时候发现细节有点多，扔了。

想 T1，发现答案的量级很小（有人说是 \Theta(n\log n) 的？），于是考虑 \Theta(\mathrm{answer})。发现集合生成过程等价于重复执行 a\gets a+2b 或 b\gets 2a+b，可以直接爆搜。写完立刻过了 10^6，结果 8\times10^6 跑了 9\texttt s 多。卡了下变成了 6.6\texttt s。卡不动了。85\text{pts} 扔了。

写 T2，大概 12:00 写完了 \Theta(n^2)。发现 h=0 且是链的情况可以直接前缀和优化。写了。扔了。

冲 T3，把 tarjan 缩点写了。最后几分钟发现还有指数级暴力没写，结果写到了 12:58 然后没过。。。

期望得分 85+35+20=140。

三点去查分，没挂。这 pretest 真够强。为啥不直接 IOI 赛制得了。

晚上去参加了活力嘉年华。把所有单人游戏全都玩了。说了八八七十四。投壶最后一个极限绝杀投中。

20:00 打 ABC。G 被 OU 一眼原了。但还是看不懂题解。赛后在 CF 上锐评被 downvote 了 /fn

打完回去睡觉了。

\texttt{Day }3

上午是文艺汇演。各路神仙们纷纷展示了自己的才华。我有啥才华啊？？

下午颁奖典礼。不是哥们，为啥让我去替 yyq 领奖啊？？废了好大一番折腾才搞完。

hf 一共一 Au 五 Ag。拜谢 OU Au。拜谢各位 Au 的神仙。

我也算是拿了个有向无环图（D Ag）。

所以我初三这一年勾子从 5\xrightarrow{\text{CSP-S}}7\xrightarrow{\text{APIO}}8\xrightarrow{\text{NOID}}9？是不是可以算达成了一个成就。

明年再见。

如果还有下文就写点吧。

总结一下这场比赛吧。

• 打得好的：拿到了大众分。
• 打得不好的：只拿到了大众分。
• 社交：社恐无社交。
• 饮食：挺好吃的。就是有时候饭盛太多了没吃完。
• 休闲：词语接龙好玩。嘉年华好玩。Ground table tennis 好玩。