结婚！结婚！还是踏码的结婚！想到结婚后有杏菜在背后辅佐，补偿着生活的开销，心里就感到非常踏实。和杏菜结婚的话，女友，妻子，同学三个愿望一次满足，实在是人生的至福。啊，好想给杏菜戴上结婚戒指，一边听着杏菜说【这些钱我也要还吗？】，一边看着她把戒指当作一生宝物，一脸幸福的表情。
Day -inf
初赛。啥也不会。过线就行。不过是不是教练有神权不过也行？同学都考的好高啊，还有 \(91\) 大神。
Day 0
昨晚 CF 唐完了。D 没开 longlong，要不然能上 50 分/fn/fn。
熬到 2 点才睡觉，困死我了。今天上午睡睡睡，高强度摆烂。
下午在车上睡了一路。感觉有点头晕。还是住在熟悉的钓鱼岛大酒店，和杨至玉一个房间。晚上去试机感觉设备还不错，默写了一遍缺省源和 prufer 序列就走了。面基到了 zqh，可惜 lkw 不知道有试机就没来(?)。
晚上回来一直在颓废，刷 b 站，没干别的。屋里就我自己，他们都跑去打杀戮尖塔了。昨晚打 CF 没洗澡，今天正好洗了。早点睡。也不是很早啊
Day 1
睡得还不错。但是据说我说梦话把杨至玉吵醒了，难绷。早饭怎么感觉比去年好吃了？还有汤圆，感觉煮汤圆的汤很甜很好喝。还喝了一碗豆浆喝一碗粥，感觉喝太多了。
上午并没有发手机。听歌默写缺省源，并没有打板子。后来因为网太差，也玩不了游戏，看不了视频，就一直在玩沙威玛传奇。太魔性了。
午饭没吃多少，并不饿。回来之后打算睡一会，躺在床上之后发现根本睡不着，非常紧张，心突突的乱跳。打着再看一眼线性建笛卡尔树地目的又把电脑打开了。看完之后就听歌，总比胡思乱想好些。
上车之后有些犯困，狂喝能量饮料。之后就进考场了，很热，想脱卫衣，不过嫌麻烦就算了。敲了好久缺省源。还带了一瓶东鹏特饮。
到点了。第一次解压咋还输错密码了。先读了一遍题目。T1 感觉要上个 BIT。T2 没看懂啊？还考上物理了怎么。T3 感觉像个 ds 题（并不是）。T4 感觉像不可做题，也没读太懂题目。
于是决定顺序开题。思考了一小会，基本确定了 T1 的做法。先从小到大排序，然后维护一个前缀和，我写了 BIT。有些细节没想明白，快 20min 才过大样例。不会写暴力，就没拍，不要挂啊！
之后开 T2。又读了一遍题，第一问显然可以用二分求解。简单推了推二分的细节，在纸上画了画。之后决定想完整个题再开写，毕竟没有只有第一问的部分分。发现对于每辆车，合法的 \(p_i\) 都是一个区间。于是就转化成了有一些区间，选最少的点使得每个区间都至少有一个点。想到这里，我脑海中直接弹出了四个字：动态规划。不过看起来要先排序啊，推了推发现按照右端点排序比较好做（这我都没想到可以直接贪心，哈哈），然后设 \(f_{i,j}\) 表示第 \(i\) 个区间被第 \(j\) 个点覆盖的情况所需的最小点数。转移时，考虑上一个区间。两个区间相交的部分肯定是直接继承，不相交的地方就是等于上一个区间的 \(\min+1\)。有些边界情况没想清楚，这就是后面的事情了。于是就开写，这时三点刚过一点点。加速度三种情况我写了三个函数来算。不过我最初以为和物理题一样加速度小于零时会先减速再加速，差点就开写这个东西了。写完大于零的函数之后我才发现速度为零就认为已经驶出了，那么就简单了，很快写完二分的部分。测了一下发现第一问全对了。
然后就是唐氏操作了。由于我想的并不是很明白，dp 的转移调了很久，包括一些奇奇怪怪的边界问题。后来我发现样例三会 RE，然而去掉多测就没问题。问题是我的第二组数据 \(m\) 明明是 \(1200\) 多，可是我有一个 \(R_i\) 达到了 \(1608\)，这玩意明明最大才等于 \(m\) 的啊！我不断输出中间变量，把所有数组都初始化也无济于事。好在最后我发现有一个地方我把 \(n\) 和 \(m\) 写反了。是哪个写成哪个了不太记得了。总之改过来以后就通过了所有样例。此时是五点半（两个半小时就这么过去了？）。当时我还以为线段树优化 dp 就是 T2 的做法，心想这么难的东西我也能写出来，太牛啦！哈哈。并将东鹏特饮一饮而尽。不知道是这玩意管用还是紧张，反正确实不困。
手握 \(200\) 分，已经比去年的我强太多太多了。之后我决定先去写 T3 再回来对拍。不写个拍子还是心里没底啊。T3 读完题后我决定拼包，不想正解了，因为时间只有不到一个小时了。看了看，最低档直接搜就可以了。第二档随便写个暴力 dp 也是好做的。这时候已经有 \(35\) 分了。我感觉这已经挺多了，不过 \(n^2\) 有 \(50\) 分，我还是决定再想想，虽然我也不指望想出正解就是了。然后发现 \(n^2\) 只需要把第二档暴力 dp 的第一维去掉就好了。\(f_{x,y}\) 表示当前两个颜色的最后一个分别是 \(x\) 和 \(y\)。转移是一个一个往后填，显然是填到 \(\max(x,y)+1\)，稍稍讨论一下即可。这样就获得了 \(50\) 分，还是很顺利的。打算先写完 T2 的拍子再来写 T3 暴力。我当时觉得第一问我肯定写对了，而且我也不知道怎么打暴力，就只拍了第二问。暴力是 \(2^m\) 的，只能拍很小的数据，也没拍出来什么错，希望它就是对了吧！然后 T3 也很快写完了。这时候就只剩下不到半小时了。去读了一遍 T4，然而并不会写 \(8\) 分。不过特殊性质 A 似乎直接模拟就好了啊。可惜的是写到最后也没写对，含泪删掉了。
其实直到和大家交流前我都一直认为我赢了很多。结果发现这不过是大众分。或者大众分是 \(300\)？出来问了 yzh，发现他也是 \(250\) 分，不过后来他说 T3 数组开小了，并没有这么多分。天天摆还能有这种分数的。definieren，WA90，cyl 都实力强劲，没什么好说的。lkw T2 被卡精度了，T3 被 hack 了，其实我不是很懂。zqh 250+，无敌了。被 definieren 告知了 T2 直接贪就是对的以及 T3 你再想 10min 就会了。我人都傻了。我真傻，真的，就这么葬送了 T3 的另外五十分。不过无所谓了，我的水平也就这样了。所以能混一个七级勾么？
其实总体来讲心情还是不错的。但是想到接下来就只有最后一次的 noip 了，还是有点高兴不起来。感觉这次前三题难度没那么大，区分度都在 T3。然而我并没有做 T3，还差点让 T2 给区分了。总结就是，只会大众分，有区分度的东西还是会被区分掉。虽然已经否定了自己的水平一万年，还是有点高兴不起来啊。我的 T2 一定不要挂分啊啊啊啊啊啊啊。
上车后吃了汉堡和薯条，还有可乐。我把可乐都喝掉了。上高速之前大家都下去上厕所了，我当时没啥感觉，就没去。之后看了看各个群里群友的讨论。感到有些头晕，害怕是看手机看的，就带上 U 型枕听歌了。唉，我居然忘记了自己喝了一整瓶东鹏特饮，然后还喝了一整杯可乐。在发车后的半个小时就突然想上厕所了，呜呜呜，排尿反射能不能暂时消失啊。询问得知最近的服务区还有将近 \(40\) 公里！这不是要杀了我吗？（好像上一个服务区刚过去不久……）差点死在车上。还好服务区及时到来了。之后和初中同学聊天。然后听歌。然后和高中同学聊天，想你了，伟豪/ll。然后和 gxd 和 yx 聊天。摸摸 gxd/hug。大家都辛苦了啊。
回到家已经快十二点了。并不想睡觉。那就索性晚点睡吧，整理整理思绪。不要让自己再在 noip 留下遗憾了。还有就是，千万别挂分啊！！！！！！！
后记
谢谢你们/qq/qq
标签：暴力,T2,T3,之后,2024,感觉,游记,CSP,dp From： https://www.cnblogs.com/LHLeisus/p/18501392