NOI2024 游记
Disjoint_cat
2024-07-13 21:50:06
# $\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 的代码：
```cpp
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 好玩。