0. 感而有言
考之前就有股预感，感觉这次要靠爆，果不其然，T4写半天写假了，导致T3的优化那50分都没拿到。
距离noip就只有一个月不到的时间了，倘若noip跟今天一样，怕是只能等着退役了吧。
首先，以下是我的考试流程，\(10\)分钟切T1,做完T2还剩3个小时，大概撇了一眼T3，50分会了，然后看看T4,想了一会，T4的我的解题的结论不知是否是假的，当时手算算不出来有反例，但倘若这个结论对了，可以拿到T4的绝大部分分，于是花了20分钟写了T3 50分，此时大概还剩2小时,决定开写T4，
或许是已经拿到了250分，或许是时间还充裕，又或许是我本来的实现能力不如人意，为了写出这个东西，我花了1个小时20分钟完成本来30分钟的事情，这也是导致我此次考试失利的一大原因，写出来后，更令人绝望的是，它假了，我直至现在仍不知道哪里出了问题，于是我还在T4上尝试各种细节性的东西是否出错，但是我的心态早已不平静，这是另一原因，即使我真的只是实现有问题，这种心态也不足以让我将其查出来，我几乎在最后半小时在绝望里度过，考场上的抉择将我推下了深渊。
但是这一切的原因真的是我的运气不足吗？我想不然，T3的50分优化让我不敢碰的原因，其实就是我对dp优化这一章节的不熟悉。在以往历次考试中，这种题常常给我一种难做的暗示，我退却了，在最后一个月中，这将成为我复习的重中之重。T4的假也与我平时证明不严谨的不好习惯有关，更与我的代码实现能力有关，这也是我在最后一个月中的重点--培养静态查错能力，我之前的检查太过于依赖数据了，相应地，静态差错更依赖思路的清晰性。而心态问题，不好解决，但我必须尝试从最后几次模拟赛获得经验。
说起来，能遇上竞赛这条路也是一种缘分，打心眼里，即使退役了，我也并不后悔。但是，我不想这成为我的遗憾，因为我还没有尽人事，自然也不愿安天命，我必须考虑这是否是我此生唯一的机会，我必须做到，哪怕回首，也能喊出那一句：
“衣带渐宽终不悔，为伊消得人憔悴。”
1.题目简析
T1
观察题，注意到相同元素的在最后一定被比他们大的值打败，一定有至少相同元素数量这么多的在最后打败不了，然后排序后从前往后地扫就是对的，答案是\(\max\limits_j \{ \sum\limits_{1 \le i \le n} [a_i = j] \}\)
T2
考虑一个车被检测出超速的照相机一定是一个区间，也就是说，给你若干个区间，让你选出最少的点，使得每个区间内至少都有一个点，这是个经典问题，贪心排序再加个什么\(BIT\)维护一下加点与检查的操作就行。
T3
最遗憾的一集，我是sb，我™为什么会放了T3去开T4?明明T3优化是如此显然，我去，赛上我思考T3正解的时间没有20分钟，10分钟50，然后我就认为足够了，去看T4，本来这一步还没啥问题，但是我看了T4后得到了一个无法证明的结论，然后求开始冲T4了，结果花了大量时间假了，这简单优化50分没时间也没心态拿到，那个啥T4也不知道多少分。赛下不超过20分钟就做出来了。
你考虑\(dp_{i, j,0/1}\)表示第i个是红/蓝,上一个与第i个颜色不同的位置是j的最大分数。显然有$$dp_{i + 1, j,1} = dp_{i , j , 1} + a_{i + 1} \times [a_i = a_{i + 1}] , dp_{i + 1 , i , 0} =\max\limits_j{ dp_{i , j , 1} + a_{i + 1} \times [a_{i + 1} = a_j] } $$
0的状态同理,然后你会发现0/1是完全等价的，所以你可以把0/1直接去掉，也就是
然后把\(dp[i]\)看作函数\(f_i\)，\(j\)看作自变量，则会发现，对于\(0 \le j < i ,f_{i + 1}(j) = f_{i}(j) + a_i \times [a_i = a_{i + 1}]\),也就是整体加,而对于第二个式子，真正会\([a_{i + 1} == a_{j}] * a_{i + 1}\)以贡献转移只会是其左边第一个与之相等的数，这很简单，因为如果相邻两个同色且值相等的中间还有一个值相等的，把它染成与这两个同色肯定不劣，于是就是维护一个整体最大值，加一个数在末尾，整体加，这个很容易用桶解决，复杂度 \(\text{O}(n + V)\)
T4
傻逼，现在也不知道为啥错了
标签：20,T4,T3,50,2024,游记,times,CSP,dp From： https://www.cnblogs.com/Cmr-/p/18508113