Educational Codeforces Round 151
T1
就是大水题但写了很长时间。
构造题。首先分类讨论:
- 当 \(x\ne1\) 时我们构造的序列长度就为 \(n\) ,序列就是 \(n\) 个 \(1\) 。
- 当 \(x= 1\) 时,
- 当 \(n\) 为偶数,我们就枚举 \(1\sim k\) 且 \(i \ne x\) ,只要 \(n\) 能整除 \(i\) ,长度为 \(n \div i\) 每个数即为 \(i\) 。
- 当 \(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\) 。(代码特别好实现)
T5
不会
T6
不会
标签:151,Educational,sum,Codeforces,操作,Round From: https://www.cnblogs.com/messiljk/p/17608123.html