专栏文章

NOI2024 游记

DDisjoint_cat
生活·游记参与者 12已保存评论 11

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
11 条
当前快照
1 份
快照标识符
@mhza1qz6
此快照首次捕获于
2025/11/15 03:55
4 个月前
此快照最后确认于
2025/11/29 04:47
3 个月前
查看原文

NOI[D] 2024\texttt{NOI[D] 2024}

Day 7/3\texttt{Day 7/3}

中考完了。
坐火车来到了重庆。

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

模拟赛。
怎么打了一场仨暴力 rk1 啊？？怎么有个 A 题唐氏 100→0100\to0 啊？？怎么有场人均题坐牢 3h 不会，非人均题 30min 切了啊？？
总结：mt19937 rng;int my_rank=rng()%people_count+1;

Day 7/13\texttt{Day 7/13}

被拉去锻炼了 /dk
走了 ??km，腿走废了。

Day 7/14\texttt{Day 7/14}

搬到了 YCZX 附近。
晚上被拉出去了。

Day 7/15\texttt{Day 7/15}

摆了一天。

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

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

Day 0\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;}

Day 1\texttt{Day }1

这几天不知道喝了多少罐雪碧了。
密码是 kmfrjf。科目繁荣解法？
怎么有 pretest 啊。那什么时候能变成 IOI 赛制。
看 T1。这么签到。Θ(m!q)\Theta(m!q) 有 60pts60\text{pts}。哦可以直接哈希维护啊。哦可以莫队，Θ(nq)\Theta(n\sqrt q)。这能过吗。想了 20min。没想出来咋优化。不管了先写了。啊最后俩点怎么 T 了。Test19 跑了一点零几秒。加了个快读，卡过了 test19。期望得分 [90,100][90,100]。扔了。
看 T3。这么不可做。非多项式暴力写了。A 性质直接 dfs，写了。B 性质不是 2-SAT 吗。这玩意不是求不了字典序最小解吗。推了下，发现这个题的 2-SAT 有性质，可以做。写了。36pts36\text{pts}，扔了。
看 T2，sub1 写了。sub2，哦直接分治可以 t=20t=20。写了，11pts11\text{pts}。发现可以分治 1212 次然后直接询问所有的，t=13t=13。写了，37pts37\text{pts}。发现每次可以不止二分。取了个 t=9t=9 的，随便过了 63pts63\text{pts}。然后搞 t=8t=8，搞不出来。写了个爆搜。搜出来一个 67pts67\text{pts} 的序列 {2,2,2,2,3,6,19,183}\{2,2,2,2,3,6,19,183\}，s=1099960s=1099960。感觉把一些 1919 换成 1818 或者 2020 可以减少次数。又写了个打表，发现第七轮分 179179 个 1919 和 44 个 1818 可以做到 s=1099954s=1099954。写写写，诶怎么挂了。我草我怎么找最大值初值设了 00，改成 −1-1 过了 70pts70\text{pts}。
期望得分 [90,100]+85+36=[211,221][90,100]+85+36=[211,221]。
中午继续打块，手感怎么没了。输了三把。三点去查分。怎么不开门。怎么不开门。怎么不开门。热死了。开门了，登录，查分。95+85+36=21695+85+36=216。我草怎么人均 200+200+。这是 NOI 吗。OU 打了 247247，拜谢。Ranker 218218，小 D 206206。
下午讲题。我草 T2 正解是从上往下构造。唐完了。T3 听说数据极其抽象，Θ(2nn)\Theta(2^nn) 冲过了 n=105n=10^5？？

Day 499122178\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。

Day 2\texttt{Day }2

密码：fmdrpk。父母大人 PK？
看 T1。抽象。看 T2，抽象。看 T3，抽象。
想 T1，发现 Θ(nm)\Theta(nm) 是显然的。写了。然后没思路了。
想 T3，以为想出了 Θ(n2)\Theta(n^2) 的做法，写写写，样例挂了，发现假了，只能过其中 A 或 B 性质。慌了，扔了。扔之前发现 A 性质是直接缩 SCC，还有暴力，但是都只有 5pts5\text{pts} 所以暂时没写。
想 T2，发现单个点可以 Θ(n2)\Theta(n^2) dp，然后倒过来就能 Θ(n2)\Theta(n^2) 算所有点的答案。写的时候发现细节有点多，扔了。
想 T1，发现答案的量级很小（有人说是 Θ(nlog⁡n)\Theta(n\log n) 的？），于是考虑 Θ(answer)\Theta(\mathrm{answer})。发现集合生成过程等价于重复执行 a←a+2ba\gets a+2b 或 b←2a+bb\gets 2a+b，可以直接爆搜。写完立刻过了 10610^6，结果 8×1068\times10^6 跑了 9s9\texttt s 多。卡了下变成了 6.6s6.6\texttt s。卡不动了。85pts85\text{pts} 扔了。
写 T2，大概 12:00 写完了 Θ(n2)\Theta(n^2)。发现 h=0h=0 且是链的情况可以直接前缀和优化。写了。扔了。
冲 T3，把 tarjan 缩点写了。最后几分钟发现还有指数级暴力没写，结果写到了 12:58 然后没过。。。
期望得分 85+35+20=14085+35+20=140。
三点去查分，没挂。这 pretest 真够强。为啥不直接 IOI 赛制得了。
晚上去参加了活力嘉年华。把所有单人游戏全都玩了。说了八八七十四。投壶最后一个极限绝杀投中。
20:00 打 ABC。G 被 OU 一眼原了。但还是看不懂题解。赛后在 CF 上锐评被 downvote 了 /fn
打完回去睡觉了。

Day 3\texttt{Day }3

上午是文艺汇演。各路神仙们纷纷展示了自己的才华。我有啥才华啊？？
下午颁奖典礼。不是哥们，为啥让我去替 yyq 领奖啊？？废了好大一番折腾才搞完。
hf 一共一 Au 五 Ag。拜谢 OU Au。拜谢各位 Au 的神仙。
我也算是拿了个有向无环图（D Ag）。
所以我初三这一年勾子从 5→CSP-S7→APIO8→NOID95\xrightarrow{\text{CSP-S}}7\xrightarrow{\text{APIO}}8\xrightarrow{\text{NOID}}9？是不是可以算达成了一个成就。
明年再见。
如果还有下文就写点吧。
总结一下这场比赛吧。
  • 打得好的：拿到了大众分。
  • 打得不好的：只拿到了大众分。
  • 社交：社恐无社交。
  • 饮食：挺好吃的。就是有时候饭盛太多了没吃完。
  • 休闲：词语接龙好玩。嘉年华好玩。Ground table tennis 好玩。

评论

共 11 条评论，欢迎与作者交流。

正在加载评论...