SDOI2019R2游记

约定不等于承诺〃 2021-12-24 08:39 214阅读 0赞

## Day 0 ##

上午到了济南，住在了山下。下午颓颓颓，zhy在玩炉石，我在...打元气！我的机器人终于不掉HP通关了呢，送的皮肤好好看啊。

## Day 1 ##

到考场后，打开题面，一看第一题似乎很可做啊，好像可以全局打标记，我先写个线段树吧。调好了发现，这样怎么就过了啊，随便造了一组数据不开O2都不用跑2s，那是不是这样就过了啊。(flag)

第二题一脸的不可做，就是第三题好像还有部分分。然后就开始做第三题。

第一个点和n=1都很简单，n=2怎么我考前不久还做过了啊，也是[SDOI原题][SDOI]？这一场怎么这么轻松啊，那就扫雷吧，顺便把第一题拍了拍。

出成绩后，结果只有80？大众分是120？我是不是退役了啊。zhy比我还惨，只有70。T1数据随机为什么没过啊，我本机都过了的。T3n=1的怎么写挂了啊，这么简单还能挂？完了，我退役了，明天肯定回不来了。准备好学文化课了。

讲题什么的就不说了。orz \_rqy orz ckw。

晚上继续颓。我打了好久的generals攒了好多rp(flag)。zhy一直在看炉石直播，这个术士打的真快乐啊。

## Day 2 ##

快考完明天就可以学文化课了，难不成今天还能200+翻盘？

考试的时候一点压力都没有啊，反正就这样了，就当是来玩一玩吧，主要玩扫雷好了。

拿到题目看了十几分钟，一脸不可做的样子。那么从T1开始看吧。哎第一问不就是让最小的度数最大吗，第二问不是最大点独立集吗。哎最大点独立集不是NP的吗，那怎么搞啊。第一问好像可以直接把度数最小的删掉，那第二问怎么搞啊。不管了，直接按照度数排个序扫一遍得了。用assert拍了一下好像没有问题。

再来看T2。这个博弈怎么不会啊，哎这不就是把前一堆的石子放到后一堆里啊，这个就是阶梯nim吧，结论好像是奇数层的石子数异或和？设奇数位有k位，然后枚举每一位，考虑这一位前面的一定是偶数个，这一位一定是奇数个，那么答案就是\\(\\sum\_\{bit\}C\_k^i\\sum\_\{4jbit\}f\_\{4jbit\}\\sum\_kg\_kh\_\{n-m-ibit-4jbit\}\\)。然后f,g都可以\\(O(nm\\log n)\\)枚举，所以时间复杂度是\\(O(nm\\log n)\\)？看起来很有道理的样子。写完发现要跑0.9s，又想起来昨天T1的惨案，然后就发现g和h卷积的部分可以每次预处理一下，于是就只要0.3s了。哎我是不是就200分了，那我是不是翻盘了啊？不对，这题这么简单，肯定翻不了了。

T3直接莽一个sam，40pts过不了就过不了吧，反正已经翻盘了。于是扫了2个多小时的雷。

于是就rk10卡线进队？zhy rk13好可惜啊。那么下一站就是CTS和APIO？

我竟然没有退役？那我一定要把CF打到International Master。（完了，flag立下了。

转载于:https://www.cnblogs.com/shanxieng/p/10829868.html

[SDOI]: https://www.lydsy.com/JudgeOnline/problem.php?id=3995