Update On 11.18 出分Day−1 这几天在学数学，有了点反演基础，然后学了波杜教筛，找点例题？网上好像没很多题可做，找了个题，NOI的，听说是好题，一个黑的，刚了一天（推了5页），也算是一半是自己推的吧（我还没有独立完成过反演题），想到明天NOIP出分，不知道还能不能继续学下去，就在这里随便写点东西吧 September 暑假还是一如既往的颓废了（六月份还在天天做橙题，真不知道我暑假第六是哪来的，要是不退役，真的就不能再刷水题的，也是给大家一个警告吧：难题不会？看题解可以，只做水题不行） 刚开学，前五就停课了，而我处于尴尬的第六（而且我之前还挺喜欢学高考），有些人也是要停课，但是教练没有允许。 才发现自己已经不适应学高考的生活了，随着前五都一个个停课了，我才意识到NOIP快到了，本身就菜的我如果不能停课，差距只会增大。 接下来就是力求停课，一开始是见缝插针，把下午的课和晚自习停掉了（副科高一就停了），然后看到别人有的班管的松，已经基本上是全天停了，做出了最终停课的决定，就利用楼下楼上的信息不对称，跳过了批准，基本上是全天停的了 九月份开始，考试就挺多的了，暑假完之后成绩稍有退步，一开始不以为然，只是觉得不稳定，然后有次考了个120，这种分原来也不是没有过，只是这次真的是NOIP题，教练也警告了我 下午就不知所干，无心做题，在外面走了走，平复了下心情，做出了让我NOIP能上四百的最重要的一个决定 下午晚上就什么都没有干，针对NOIP制定了一个超详细的复习计划，涵盖接下来的三个月 命名为“秋季风暴”，希望能像风暴一样扫清一切发展的障碍 没错，它就像一场风暴 九月底，NOIP前的可以说是最辉煌的一个时期了，从第十左右一路反杀，稳定在前五，Rank前三也拿过好多次 随即收到消息，说是国庆假期培训，本来考虑了，可能会影响我计划的执行，但是最后还是决定培训完动态调整 培训前一天晚上，和同学出去吃了点饭，然后颓了会 October 培训如期而至，只是和我所想的略有不同，Day1省选数学（就是我这几天刚学的），走了不到一分钟神吧，一天连定义都搞不懂，晚上未来的队爷跟我QQ上说不会，我说都说了是省选内容了，我不用会。然后他fAKe了句，嗯有理。后来应他要求，我还是推荐了个集训队大爷的博客给他（那时候我还没看过），然后他就会了（我还能说什么。。。） 之后几天是一如既往的懵逼，都不知道干什么了 然后发现我原来的整个计划都被打乱了，“秋季风暴”走向了崩溃 有的人就是听课特别有用，但是我，应该是因为思维慢，容易跟不上，然后一旦一个地方跟不上，一天就凉了 我就是自己找资料自己学的效果更好，毕竟学什么的时候，想到的扩展的东西也比较多 整个十月就变成了一个耻辱的历史，月底我也试图制定其他计划来挽救，但是为时已晚，只能看着名次一步一步掉到倒数 November 最后还是要NOIP了，考前再熟悉下模板吧，然后就花了好几天敲板子，“秋季风暴”的遗产也给了我很大的帮助，熟悉了下各种巧妙的解题思路，但是心态还是不太稳定，各种杂事挺多，总之就是打板子的几天 Day−1 挺平常的一天，当时应该是为退役准备最充分的人了吧，想到四机房能用的机子本来就不多，就在电脑上新建了个没密码的账户，以后给学弟学妹用 晚上没上晚自习，回家收拾了下明天的东西，本来说要早点睡，之后也没早睡成。。。 Day0 在火车上，旁边是一个学弟，不知道是哪个校区的，他之后就做到其他同学旁边去了，然后开神犇就坐过来了 火车上颓了会，然后就是吃饭以及跟开神犇聊了会天，之后稍微睡了会，也没睡着就到了 到宾馆，住的房间比省选摸鱼的时候要好，然后去试机，他们都在敲各种数据结构，但是我一个也不会，也是不想敲了，敲了个Hello World，A+B还有个快速幂就走了，wzy和tbl也走的挺早（不知留在那试机能干啥） 晚上回宾馆，有些记的不太清楚的板子，又看了下，然后就没怎么学习，习惯考前不学习了，跟他们联机玩了会，但是网速实在是慢，不是很爽啊 之后学长讲了些注意事项，回去就没干什么，早点睡了 Day1 考前 Day1呢，本来就打算着尽量往高里拿分的 早晨，不知几点（后来知道是五点半），感到周围一阵巨响，强烈的震动感，大概有些意识了，发现是手机振动，一看是铃声，我就掐了 然后是5:40,5:50,6:00，直到wyt醒了，他没关手机铃声。。。然后就多睡了会 基本上是最后一批去吃饭的，被催了半天，随便吃了点很随便的伙食，教练送了条士力架带进考场吃 考试开始 密码一次就输对了，很开心，也算是占得先机吧 T1 读懂题意之后，有点惊讶，这不是那个积木。。积木什么来着 贪心思路还记得，但是一时竟忘了怎么做，只是记得挺简单 后来想了想，扫一遍就好了（想看题解自己去找吧，我就不再说了） 然后直接过两个样例 做完T1，看了看表，才过了十分钟 T2 现在是绿的，感觉自己很菜 读懂题意，看了下样例，突然想到，如果一个数能被其他数线性表出，那肯定不用选 但是不知道选择截然不同的数有没有更优方案，假装没有了吧。。。（这种做题态度，我还能说什么） 然后问题就转化为了考虑一个数能否被其他数线性表出 然后就懵逼了 想了半个多小时，瞎歪歪出来一个计数DP做法，能拿80分，当时觉得T2能拿80不亏，就做T3去了 T3 一眼二分，然后就懵逼了，考虑各种DP啊，贪心啊什么的 最后一种没有被我自己Hack的方案脱颖而出，大致证了下正确性就上手去写 写完过了编译，测了发样例，三个全过，当时都想喊出来，280分了 啊啊啊特别激动，激动的我一下吃了一整个士力架（平时吃不了太甜的，所以哪能一下吃了这么甜的东西） 看时间，还有一个半小时 优化与调试 T3看数据范围复杂度应该是O(nlognlogn)的，但是我在set上二分有三个log，而且有大常数，虽然其中两个log都是假的，但是菊花图就能卡回原形 造了个数据，果然跑不过去，考虑优化，卡了波二分边界，然后就稳过了 之后怕二分边界卡错了（虽然证出来，这样是阔以的，但是反正也闲得慌），拿卡了的和没卡的拍 拍着我就去看T2了，还是没什么正解思路，但是发现我的技术DP最后只用判可行性，于是加了个大剪枝 O(25000∗25000∗20)的算法跑随机的数据稳定在五六百毫秒 然后看T3，竟然拍WA了，出人意料，原来从来没想过会拍出错来 经过不断努力，发现菊花图容易死，当时有点懵，不知道是咋，最后也就没时间了 考完 本来是说考完坚决不对答案的，结果一想能拿至少二百多，就不慌了，说说也无妨嘛，可能是一样的心态，大家也都在说 回宾馆之后，验完程序，大部分人都没事（wzy少了两个，不过都找回来了），打开洛谷，民间数据还没有登陆，就把T1交到积木大赛，AC虽然是意料之中，但是也是挺开心 有点累，就躺了会，等到了T2的民间数据，交上去，A了！暴力加剪枝把民间数据碾过去了！ 但是随后就传来噩耗，说数据加强了，象征性地把我卡到95了（笑哭） T3的数据咕咕了，然后我就到处翻点东西，看都在说什么，才知道Day1三道都是原题。。。ε=(´ο｀*)))唉我还能说什么，只做过一个 之后听说甚至一个题是考前教练给的复习幻灯片上的题，很多人都做过，而我恰好没看 下午按计划去看海，zzh挺早就来找wyt了，他们本来还叫上我，但是我因为提前跟yzh,zyc,zyz约好一块去的，就没有去。@某人，亏我还等你 之后才看到QQ上，yzh大概半个小时之前叫我去，然后我就问他在哪，他就发了个马路的照片。。。（什么人啊，也不来找我） 那还去个毛线啊，之后就等wyt和zzh回来一块吃的晚饭 吃完饭回来，看到T3的数据到了，测了发，80，跟别人讨论了下做法，都说我的做法是假的，就是个骗分（这里留坑待填） 算了算了，不管了，骗到80就跑，所以洛谷上Day1最终是275分 晚上看到大家好多人都说要Day2翻盘，我当时很天真啊，一个是认识到自己很菜，Day2不被拉开差距就好，另外也是觉得275挺高了（后来才知道那么多290以上的） 晚上又强调了点东西，一个是说题简单，拉不开差距，另外就是说明天题可能很难，写好暴力 之后听两个教练说考的不错，嗯，那第二天继续加油 Day2 考前 Day1之后，我的目标就从保省一变成了冲省队 早晨的铃已经被wyt关了，睡了个好觉，早起去吃饭，没什么人，精挑细选了一番，发现真没什么好吃的，草草吃完，教练又发了两个脆脆鲨 考试开始 密码还是一次输对 T1 旁边是个唐山一中的大佬，我还没读懂题，他就好像把T1切了，然后我发现，这不就是个裸的prim吗 花了几分钟敲完，过不了第二个样例 然后发现自己读错题了，感觉T1受旁边人干扰挺大的 之后看了会，不会，先敲好暴力，60分，明显不够啊，又想了想，最后还是没想出来，算了 时间：开考一小时 T2 好不容易读懂题意，毫无思路，看数据范围，像是状压，但是时空复杂度好像都不对 不妨先写个爆搜，看有什么收获，想了想，不好写？容斥一下好像就比较轻松了 于是一个O(2n∗m)的爆搜就诞生了，2∗2的样例轻松过掉，但是3∗3的就萎了 当时是真的懵逼了，搜索写萎，心态爆炸 于是啃了个脆脆鲨，然后去厕所遛了一圈，调整心情 手画了下2∗3的情况，和程序跑出来的一样，就拿一个自己都不确定正确性的程序打了个表 做好了20分的准备，时间：开考两小时 T3 好像做过原题，就是在树上覆盖的问题，一个点打标记能覆盖与之相邻的所有点，在每个点打标记有个不同的权值 写完发现过不了第二个小样例，不知道为啥，还好是小样例，手画了下，和程序结果一样 果然是又读错题了，改了发转移方程，就顺利过了所有样例，44分get 没时间再干什么了 然后就只剩十几分钟了，查了下文件，T3的.out写成.ans了，还好查出来了，其他的就没有问题了 考完 大巴已经在门口接了，回宾馆拿上行李，直接赶往火车站，yjc一句枚举删边，我T1直接会了，蛮可惜的，但是谁让自己想不到呢 好像很多人都切掉T1了，大佬们都很厉害，我估的154，这个分呢，洛谷上高点是159，牛客和校内数据是154 火车站吃了点德克士，就赶火车去了 才知道很多大佬Day2都有点炸，我发现他们有一个共性，就是刚T1太久了，然后导致没给T2T3留够时间，这样一慌乱，就容易出错，或者该拿的暴力没拿到（当然还有一类神仙是刚T3，调动态DP） 其实我这个小蒟蒻Day2也是因为时间的关系，没拿全暴力分的，读错题和暴力写萎确实耽误时间 所以发现时间分配是很重要的啊，平时考试一个都不会的时候的时间分配的经验教训让我不至于死在NOIP上，毕竟yjc那种一个小时拿满两道题的暴力分的神仙极为罕见orz 回去的火车上，不知道该干啥（没有网），心情复杂，看看窗外的景色吧，问自己一切都结束了吗？ 经过两天的大起大落，真的累了，就睡了会 回家在洛谷上测是434，牛客上是429，听说学校内部数据是444，看来成绩还是比较稳定的 不知道是因为在车上睡了还是心事太重，晚上睡不着，在真正面临退役之前，从没体会到过这是一件如此可怕的事 算法竞赛，不敢说是一种信仰，但是当你走入其中，它一定是一种无法舍弃的情怀 设计出一种算法，通过不懈的优化，以优秀的时间和最少的资源占用解决一个问题，这真的是一个无比快乐的过程 既然说是一种情怀，用语言自然是难以形容，该懂的人，自然会懂https://www.cnblogs.com/ivanovcraft/p/9980165.html