首页 > 其他分享 >NOI2024 游记

NOI2024 游记

时间:2024-07-21 23:11:52浏览次数:13  
标签:rt int text texttt tr merge NOI2024 游记

\(\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 好玩。

标签:rt,int,text,texttt,tr,merge,NOI2024,游记
From: https://www.cnblogs.com/No-play-Yes-splay/p/18315077/noi-2024

相关文章

  • SJTU 智能驾驶暑期营游记
    - 最初开始我其实是没有底的,完全不知道我们会做什么,需要做什么,要用到什么,不过既然这边说只需要一点 python 的基础,那么问题应该是不大的。- 前两天这两天可谓是轻轻松松,当时想要提前了解后面的内容,但是没给。所以处于自己去自由探索和摸索的过程。 过程很有趣,也很有意义。......
  • NOI2024 集合 题解
    给个链接:集合。很神秘的题目。基本上看到之后就可以想到哈希。首先想到一个比较神秘的暴力。就是对于每个询问,扫一遍所有\(a\)中的数出现的位置,把它弄成一个哈希值(具体怎么弄随意)存到set里,然后看看是不是和\(b\)中的数出现的位置这样操作后的集合完全相等。事实上就是判断......
  • NOI2024 总结
    赛时经历Day1想了1h的t1,然后思路不是很清晰,写了1h。想t2,顺着擂台赛想下去,可以分成\(k\)个一组,每组\(\dfrac{k(k-1)}2\)次查询,然后选出一个最大的组成一个新的序列。过了一会儿,想到dp这个过程,得到82pts。剩下大约1h30min,想t3,一直在往计数+容斥的方向......
  • NOI2024游记
    终于还是到了这一天。NOI,无论金牌与否,都会是我OI生涯中最后一场正式比赛了——哪怕进入了集训队也是这样。那么,走完最后这一程吧。Day-6(7.11)结束学考,抵达重庆,最后四天集训。Day-5(7.12)模拟赛挂分,原因是不会贪心。感觉真是越学越菜了。晚上和Clonoth,A_zjzj,275307894......
  • NOI 2024 游记
    https://www.cnblogs.com/fjy666/p/-/NOI2024NOI2024游记。建议你立刻关掉这个页面捏。7/16(Day-1)到达育才中学。上一次来育才是什么时候呢?WC2024(Cu)。在育才没有什么比较好的回忆。去领身份牌未果,再去的时候看到了zxx。7/17(Day0)上午开幕式,开场满屏NOI有文......
  • $NOI2024$游记
    day-?~day-?考了期末考后打省队集训,刚开始打的很差,bai了几天状态恢复。打进前4了,好吃捏。$day-1$报道日,育才宿舍真难泵,真独立卫浴,全是蚊子受不了,想不通育才学生一间住八个人怎么活下去的(。育才辣椒不辣,开心!没洗澡,不嘻嘻。day0今年竟是NOI四十周年,dzd英雄人物上位救赎ccf(bu......
  • NOID2024 游记
    流水账。Day-13中考7.2考完,7.4就被gj叫过来集训了。和同学讨论了一下,发现自己语文作文很可能会偏题,很可能考不上JellyFish中学。Day-12背笔试,比较简单,很快就背完了。mx这几天每天都有模拟赛,比较累。Day-6丢失了一场模拟赛。中午去吃饭去晚了,被迫吃屎。Day-4......
  • NOI2024退役记
    本文仍在不断更新中不知不觉我的OI生涯就结束了,走到这一步才突然发觉。才想起来我还有好多感兴趣的内容没学,还有好多有趣的题没做,还有好多流逝的时间没有抓住。但是都已经走到这一步了,高中的OI之旅就也只能到此为止了。Day-?提前两周来到了重庆,跟着梦熊的模拟赛,又认识了一个......
  • UNR2024 游记
    Day-2高考结束之后一直在摆烂。每天大概就是,打游戏,看视频,聊天,随机胡题。果然,假期是很难有动力认真干什么事情的。又把元气骑士下回来了。这太童年了。打了几把,感觉现在元气的难度低了好多了。\(\color{orange}{\text{serenity}}\)一枪\(\color{red}{\text{120}}\),开个双......
  • NOI2024游记
    DAY-1昨天晚上熬夜有点晚了,今天上午睡了俩小时。下午午觉又睡了一个小时。啥?笔试和试机?太平凡了不想去考。笔试前几天考了一下,考了640.5分,比全场任何人笔试成绩都高。试机不想试,因为电脑上没有冰与火之舞。晚上又熬夜到十二点才睡觉,舒服。DAY1早上七点起的床,然后回笼觉......