T1 刷怪塔
现在我们证明取 x=0 总是最优的。令最高层刷怪平台为 t=n−x，考虑通过接收平台满足目标的平台个数，即满足 i≤t 且 pi>t 的 i 的个数，由于 p 是一个排列，这个数量一定等于 pi≤t<i 的 i 的个数，因此将 x 改为 0 后仍然满足 pi≤i，原来合法的仍然合法，不会变得更劣。
因此问题等价于求有多少 i 满足 pi≤i，直接维护即可，时间复杂度 O(n+q)。
T2 染色
先将 1∼n−1 的所有奇数颜色排成 …,5,3,1,?,1,3,5,… 的形式，再将 1∼n−1 的所有偶数颜色排成 …,6,4,2,?,?,2,4,6,… 的形式，将两者并排放置可以得到：
…,5,3,1,X,1,3,5,…,6,4,2,Y,Z,2,4,6,…
此时还剩下 0,n,n 三个颜色要放在 X,Y,Z 的位置，而不难发现 X 与 Z 下标差恰好是 n+1，因此令 X=Z=n,Y=0 即可构造出一个符合条件的序列，时间复杂度 O(n)。
T3 数学题
当整式 P 的次数 n 固定时，所求即为 a0+a1+⋯+an=n+S 的方案数，其中 a0,a1,…,an−1 为自然数，an 为正整数。这可以转化为 (a0+1)+(a1+1)+⋯+(an−1+1)+an=S，其中 a0+1,a1+1,…,an−1+1,an 均为正整数。由插板法可得方案数为 (nS−1)。
对于第一问，好的整式 P 的个数即为 (0S−1)+(1S−1)+⋯+(S−1S−1)，这等价于从 S−1 个物品中选出来任意多个物品的方案数，所以第一问的答案为 2S−1。
对于第二问，由于次数为 n 的好的多项式的个数为 (nS−1)，我们可以从小往大枚举 n，统计次数小于等于 n 的好的多项式个数之和，直到数量大于等于 k 时输出答案。由于当 (nS−1) 随着 n 增大是指数级别增长的，复杂度可以接受。
实现时可能需要使用 __int128。
T4 探索
显然移动后 x+y 的奇偶性不会改变，所以每个方格都只会有一条对角线可能被经过。考虑对于所有 x+y 为偶数的点建图，在每一个方格能经过的对角线两点间连边。问题转化为在这个图上至少要删除几条边才存在一条从 (0,0) 到 (x,y) 的欧拉路径。
这张图上两个点间的最短路长度很容易计算：d(P,Q)=max(∣xP−xQ∣,∣yP−yQ∣)。
而一张图存在欧拉路径的充要条件是起点和终点的度数为奇数，其余点度数均为偶数。不难发现这张图上度数可能为奇数的点只有四个：A(0,0),B(n,0),C(0,m),D(n,m)。具体地，按照 n,m 的奇偶性可以得到：
- n,m 都是奇数：奇度点是 A,D。
- n 是偶数，m 是奇数：奇度点是 A,B。
- n 是奇数，m 是偶数：奇度点是 A,C。
- n,m 都是偶数：奇度点是 A,B,C,D。
先考虑 n,m 中至少有一个是奇数时的做法。此时图中只有两个奇度点 A 和某一个角 Z。若终点是 T，我们的目标就是删除一些边使得只有 A,T 的度数为奇数。不难发现这本质上相当于找到一条从 T 到 Z 的最短路并删除，之后跑欧拉路径即可。
现在考虑 n,m 均是偶数的做法。类似地，我们要将 T,B,C,D 四个点分成两对，删去这两条最短路。可以证明，存在一种选这两条最短路的方案使得这两条最短路不重合。枚举配对方案，找到答案最小的一组即可。
注意上述讨论中没有考虑 T=A,B,C,D 的情况，实现时需要精细讨论。
时间复杂度 O(nm)。
有帮助，赞一个