成都外国语供的题,说实话由于成外上次给的题直接爆原题,印象非常不好,本来就没怎么看好,结果这场质量竟然还不错?
》
T1
==noip T1贪心+分讨,细节比较多,就是要让位数最少,然后注意一些特殊情况,创死人了
》
T2
==noip T2破题在于发现当某个线段的长度小于d时,这个线段至多被经过一次,而当某个线段长度大于d时,这个线段一定会被经过,然后有许多不同的做法,我写的是数论分块的,也有两只老哥的
》
T3
<=noip T3非常有意思的发现性质的题目。首先发现是计数题,大喜,然后发现限制非常的直观,已经没有什么转化的空间了,然后就思考一些特殊情况,发现假如某个大于等于 $3$ 的数后面的数比自己大,那么就非法,因此对于每个大于等于 $3$ 的数,其后面的数必须比自己小,然后再思考一下 $1 , 2$ 发现本质上就是把 $3,4,5,...,n-1,n$ 划分成两个子序列,使得子序列单调递减且大模小 $\le 3$ 。然后有一个 $O(n^2)$ 的 dp ,就是 $f[i][j]$ 表示从大往小插数插到 $i$ ,然后 $i$ 不在其中的另外一个子序列的最后一个数 $j$ ,然后参考P4728 [HNOI2009]双递增序列的交换序列的转移方法(我写的题解的那种不行),实际上时间复杂度是调和级数的 $O(n\ln n)$ ,可以通过。
感觉思维难度是有了,但是码量上缺乏一点。