2022/9/25 考试总结

时间安排

8.00~8.30

T1是构造，直觉觉得存在一种方案把所有给出的数放在最后。
那么就是要前边构造的b序列长度最少，那么显然构造单调下降的序列是最优的。
大样例很水，也没法对拍，因为不知道无解判的对不对。

8.30~9.00

想T2，啥也没想出来，甚至不会多项式做法。

9.00~9.20

T3考虑把大于x的数设为1，小于的设为-1，那么如果有-1,1的切换就要加一。
但是又发现-1,1,-1这种只需要一个代价就行了。整合了一下发现答案为所有连续切换的段的长度+1/2之和。用线段树维护元素的切换就好了。
保险起见先写了个暴力，但是因为没有大样例，不知道对不对。

9.20~10.00

写T3的$O(nlogn)$的做法，写完对拍拍出了一堆错，不过最好好在拍上了。

10.00~11.00

T4感觉和今年NOI D2T2我写的有一档暴力很像，于是就按照那个写，加个前缀和优化，写完过了样例，又改了改过了大样例，复杂度为$O(n\times （m中的不同的数的个数）)$，期望得分60分。

11.00~12.00

一直想T2的多项式做法，然后终于想出了一个$O(n^2\sum s_i)$的做法。
把所有数排序，那么分组后只有每组的第一个和最后一个有用。
那么就很好dp了，设$dp[i][j][k]$为前i个数，当前还有j个左端点没有匹配，选的数的和为k的方案数，转移时有三种选择，新建一个组，和之前某个组匹配并结束这个组，或者加入某个组。
感觉状态数不多就用map记录状态了，答案是对的，就是不知道能卡多少分。