Educational Codeforces Round 151

T1

就是大水题~~但写了很长时间~~。

构造题。首先分类讨论：

当 \(x\ne1\) 时我们构造的序列长度就为 \(n\) ，序列就是 \(n\) 个 \(1\) 。
当 \(x= 1\) 时，
1. 当 \(n\) 为偶数，我们就枚举 \(1\sim k\) 且 \(i \ne x\) ，只要 \(n\) 能整除 \(i\) ，长度为 \(n \div i\) 每个数即为 \(i\) 。
2. 当 \(n\) 为奇数，跟偶数差不多，只需要将 \(a\) 的第一项改为 \(3\) 即可。

T2

~~一眼题~~

本题的思路就是将一个二维的坐标系转换为两个一维的线段，能计算公共部分的前提显然是b、c基于点a的偏移量的正负性相同，那么分别计算两个一维线段的贡献即可。赛时10minAC。（比T1快了 \(7\) 倍）。

T3

这题没什么时间，看完题目以后以为是 数位dp ，没想出来转移方程。~~题解发现就是个暴力~~。

用两个指针 \(i\) 和 \(j\) ，其中 \(i\) 指向 \(s\) ， \(j\) 指向 \(t\) 。在 \(i\) 遍历的同时，判断当前的 \(s_i\) 是否将当前的 \(t_j\) 所有可能性全都试过。如果全都试过了，代表 \(l_j\) 到 \(r_j\) 的所有可能性都会是字符串 \(s\) 子序列的一部分，再往后看下一个 \(t_j\) 即可。如果没全都试过，将当前出现的 \(s_i\) 标记。

若是当前的 \(j\) 超过了 \(m\)，说明字符串 \(t\) 的所有可能性都是字符串 \(s\) 的一部分，即构造不出符合要求的字符串 \(t\)。

T4

这题主要是思路。

这题我们要先记 \(sum_i\) 为前 \(i\) 个数的前缀和。那么很显然 \(k\) 的一种取值为 \(sum_i\) ，其中 \(1\le i \le n\) 。那么我们考虑进行了前 \(i\) 次操作且 \(x\ge k\) 成立后，进行第 \(i + 1\) 到 \(n\) 此操作对 \(s\) 产生的影响。那么在不考虑 \(k\) 的保底作用下，\(x + sum_n-sum_i\) 就为最终的答案，且这个数会小于真实的答案。接着我们考虑真是答案，当 \(x\) 达到了某个极大值刚好达到 \(k\) ，后面的若干次操作使它在保底作用下不小于 \(k\) ，最后可能有若干次操作使其增长，其中 \(x\) 一直不小于 \(k\) 。那么既然我们已经在最后的若干次操作中拜托了 \(k\) 的限制，我们就枚举这个摆脱限制的起始位置。那么第 \(i\) 次操作中 \(sum_i\) 的最大值，这个最大值就是 \(k\) 。此时在 \(x\) 达到最大值 \(k\) 后，经历第 \(i\) 次操作后，\(s=k\) 。（代码特别好实现）