首页 > 其他分享 >NOIP2024游记

NOIP2024游记

时间:2024-12-01 21:23:16浏览次数:12  
标签:max T4 T3 然后 T1 mathcal 游记 NOIP2024

NOIP2024 游记

第三次参加 NOIP 了,但是是第一次正式参加。

Day 0

考前一天我们三点半就放学了,然后打了两个小时排球,回去很累了,摆了一晚上。然后快要睡觉了,我又突然想起来打了个网络流的板子。最后差不多在 22:40 睡觉了,睡眠质量还不错。

Day 1

早上 6:30 就醒了,但是由于比较紧张,后面就没有睡着了,但是还是眯了一会儿。吃完早饭马上赶往考点,考点在七高,仍然是主场作战。在这里遇到了其他同学,我好像是最后一个到的?

现在大概是 8:10,我打开虚拟机,把板子敲上,然后就开始趴着睡觉,快到考试的时候,旁边的 @11111118m 问我怎么写重载运算符,我小声告诉了,然后紧接着是 @X2H_tato 问我虚拟机在哪里,然后他不是很听得清我说的话,于是就找了监考老师。

8:30,开题,我先通读了一下 T1,然后迅速花了 5min 思考了一下,没有什么头绪,于是就通读了一下四道题。T2 不知道是个啥,但是应该不会太难,T3 的题面太长了,懒得看,T4 是一道 DS,我觉得我有希望能做出来。

然后我就开始看 T1 了。想了一会儿就有个贪心做法,就是在前面能匹配就尽量多匹配,直觉上这一定是最优的,然后再分这一位 \(t1_i,t2_i\) 是什么值分类讨论。写了 20min 就写完了,一测大样例,发现挂了两个点。我又看了下代码,没找到啥错误,我就开始有一点慌,不会 T1 就做法假了吧。我又对着我的代码瞪了 10min,突然想到我两个需要分类的地方为了简便直接合在一起写了,但是写错了。于是我老老实实把所有要分类的情况都写完,没有图简便。并通过了大样例,我松了口气,此时是 9:20。

然后开始想 T2,仔细读完题我就发现这是个唐题,这不是直接 \(f_i=f_{i-1}\times (v^{2(a_i-a_{i-1})}-v^{a_i-a_{i-1}-1}(v-1))\) 就结束了吗,15min 写完代码,结果有个小细节没注意到,小调了一下。最终在 9:40 通过了大样例,剩余的时间还比较充裕,

接着,我花了点时间弄懂了 T3 的题意,看懂了样例,又用了点时间想了想,发现没有任何思路,甚至连 \(k=1\) 都不太会。于是我就果断地去思考 T4(还有个原因就是最近有好几次考试 T4 都比 T3 简单,所以我就潜意识的认为 NOIP 也会是如此)。

T4 是一个区间子区间求 \(\max\) 的问题,我首先想到了一个子集的 lca 等于 dfn 最小和最大的 lca,然后在这个出发点上面想了二三十分钟,却始终没找到突破口。于是我又换了个思路,我联想到了暑假时 lxl 给我们考试的一道题。大概思路就是处理出有哪些区间的 lca 是某个点 \(u\),所有的区间可以构成 \(\mathcal{O}(n\log n)\) 个矩形,可以用启发式合并来求解。询问的话根据错解不优发现只需要求满足 \(l'\le r,r'\ge l,r'-l'+1\ge k\) 的区间 \([l',r']\) 即可。那么一个矩形只有左上角的点有用,于是决策点就只有 \(\mathcal{O}(n\log n)\) 个了,为了卡常还可以去掉有偏序关系的区间

现在的问题是对一个询问 \(l,r,k\) 求出 \(\max\limits_{l'\le r,r'\ge l,r'-l'+1\ge k}d_u\),这个就是个三维偏序问题,直接用 cdq 分治求解即可。但是,我考场上没有反应过来!我以为这是个单点修改,矩形求 \(\max\) 的问题,认为要写个树套树,并以为时间复杂度是 \(\mathcal{O}(nlog^3 n)\)。在大概 11:00 时想到了全部的思路,我开始有点激动,觉得自己做出了 T4 很厉害,但是想起了霉好的回忆,于是我就去上了个厕所冷静一下(其实在思考的时候我还上了好几个厕所)。然后我觉得很有希望能写出来,虽然不知道能过多少分。

然后我就一直写,写到了大概 11:40 左右过了小样例,但是大样例一直输出比答案要大。我就开始有点慌了,但是很快就冷静了下来,我发现我求矩形 \(\max\) 写的是 \([1,r],[l,n]\),会把一些不应该计入答案的算进去,实际上应该是 \([1,r-k+1],[l+k-1,n]\),这样子就过了。原本我都不打算通过最大的样例的,但是我一测发现只有 2.2s,于是就开始疯狂卡常。我甚至把 fwrite 也给加上了,最后再测,1.6s,非常好啊。这个时候已经是 12:30 了。

最后半小时开始冲 T3 暴力,写了15min 之后发现暴力非常难写,直接开始摆烂。然后看到了链,直接输出 \(1\)。菊花图,推了下式子就是 \((\frac{k*(k-1)} 2-k(n-1-k))(n-3)!\),可以获得 16 分(但是因为时间不多,我连 \(k=1\) 都没有细想了)。最后只剩 5min 了,我就检查了下代码,离开考场。

估分:100+100+16+(100-\(\epsilon\))=?,最好肯定是 316,最坏应该不会低于 300。

然后跟同学讨论,发现大家都考得不理想,高一的都只有少数的上了 200,因为被 T1 浪费了大量时间,导致 T2 都没有细想。高二的大众分在 270,我似乎算考的比较好的了,当然还是有考的比我好的大佬(@H_W_Y,@Union_of_Britain)。

然后下午和晚上都在摆烂。

Day 1.5

我从考完到当天睡觉前一直对外声称我的做法是 \(\mathcal{O}(n\log^3n)\) 的,直到晚上我才突然反应过来,决策点去掉无用的之后只有 \(\mathcal{O}(n)\) 个,并且矩形求 \(\max\) 的左端点一定是 \(1\),于是整个的复杂度就变成了 \(\mathcal{O}(n\log^2n)\) 了。

Day 2

洛谷有数据了,把 T1T2T4 代码都默写出来了,T1T2 通过了(吓我一跳,我听好多人说贪心是假的,以为 T1 就要挂分了)。T4 先写了个 cdq 分治的做法,直接无压力通过。然后又写了考场上树套树的做法,并怀着激动的心情测了一发,92 分((

T1 评测记录T2 评测记录,T3 暴力懒得写了,T4 cdq 做法T4 考场树套树做法。现在我只能祈祷 CCF 数据水点、机子快点了。

总结

这次考试的总体发挥还不错,T4 能实现出来已经很好了。但是仍有一些遗憾,比如 T4 没反应过来可以 cdq 分治,T3 \(k=1\) 的部分分都没有打之类的。可以看出我还是比较擅长偏 DS 的东西,但是 math 仍有一些不足,后面应该着重整一下数学方面的内容。

标签:max,T4,T3,然后,T1,mathcal,游记,NOIP2024
From: https://www.cnblogs.com/max0810/p/18579598

相关文章

  • NOIp2024游记
    Day998244852打板子,发现不会板子。Day0开考,看t1,开始写,假掉了,急急急。然后重新想,继续写,还是过不了样例,急急急。。怎么感觉在写Div2D?1h过了t1,感觉要完蛋了。。开t2,怎么逝计数啊,稍微观察一下,怎么这么唐,10:00过了。开t3,不太会啊,如果枚举开始的边好像会重复很多啊。。......
  • NOIP2024游记
    11.27Day-2发烧了。\(38.5\)。11.28Day-1上午请假卷whk,反正没看一点。11.29Day0和往常一样颓废的一天。11.30Day1\(6:15\)起床,随后去杭州,\(8:00\)左右到。402机房,和CSP-S一个。\(8:30\)开赛。看T1。wc,瞪了\(10\)分钟,居然不会。。此时,我选择开T2。......
  • NOIP2024游记
    Day-1同学掏出了珍藏的游戏(指神秘scratch小游戏),或许是最后的狂欢。去年的今日似乎已经考完了呢……当时的心态真好啊,有点羡慕。现在的我似乎只是夹杂在阴暗b和现充之间的路边一条、的说。恭谨而牵扯地迎接吧,终幕或者楔子,命运的既定就在前方了。拉线,祝自己rp++,早上能睡醒Da......
  • NOIP2024总结
    超长延迟vp。没有一点思维能力,成功被T1创飞。实际上赛时T2是想出来了,但真被T1给干红温了。实际上T4链的分是没调出来的。实际上稳定着打应该有[60,80]+100+0+64=[224,244],但显然没有。赛时把T2题看错了,活该。可能这种ARC状物真的得多训一下,而且一定要稳定自己的心态。可能......
  • P11361 [NOIP2024] 编辑字符串
    题目大意详细题目传送门两个\(01\)串,可以对两个串中任意相邻的字符进行交换,没有代价可以进行任意多次。可是两个串有的位置的字符是定死的,无法被交换,求任意次操作后最多让两个串的多少个位置\(01\)相等。即\(\sum[a_i=b_i]\)。\(n\leq10^5\)思路首先根据冒泡排序的性......
  • 洛谷P11361 [NOIP2024] 编辑字符串
    ProblemSolve首先任意更换相邻元素任意次等同于在可交换范围内随便移动这题是求最优解,直观想到DP和贪心,但是容易反应过来本题DP的话很难做到无后效性,且状态较多,故尝试贪心不难发现,我们从左往右遍历的某个时刻进行交换后所得到的局部最优解总是答案的一种方案的一部分原因......
  • NOIP游记
    \(NOIP\)\(Day-N\)~\(Day-1\)考前三周开始停课,每天自己列着计划安排学习复习过的比较充实。隔一两天就有联考,总体成绩也还算不错。除了一次\(tarjan\)建圆方树的题没调出来其他时候\(T1\)都能稳定很快切掉,还有一次场切了一道紫题!!!虽然赛后在\(OJ\)上提交发现自己的记忆化搜......
  • NOIP2024游寄
    Day-2赛前最后一场模拟赛,教练说要打压一下我们心态,找了一套特别无语的题让我们做,虽然数据水,但我还是没有到\(100pts\),心态确实挺炸裂的(考前还在保佑NOIP不会出这样的毒瘤题)Day-1早上想复习,就开始带动全机房的人民学习模拟退火。(甚至还去网上找了几个大冤种一起写)然后下午睡......
  • NOIP 2024 游记
    TheendofmyOIday998244320开始停课一个月day998244320~998244329DP很弱,练。图论很弱,练。DS很弱,练~。打打摸你塞day0打打板子~。day16:30起床,要我命啊。7:00坐大巴过去。8:00到了,进去了。8:15试机,TM的郑大你的<-这么小到底给谁用的,妈的每次\n直接物......
  • 2024 NOIP 游记
    Day0不知道说什么好。前一天完全没有注意到下一天就是NOIP。输麻了,就会越输越麻。Day1候考的时候看了一个小时雅礼宣传片,看得我热血沸腾。进考场的时候发现忘带身份证了,心态有点慌,不过后面发现监考员也没有再找过我。30min先开题,把T1,T2,T4的题看了,T3有点像大模拟,就......