2022-10-19
成都外国语供的题，说实话由于成外上次给的题直接爆原题，印象非常不好，本来就没怎么看好，结果这场质量竟然还不错?
》
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)\) ，可以通过。
感觉思维难度是有了，但是码量上缺乏一点。