2020-2021:teams:farmer_john:jjleo:codeforces_round_645_div._2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:jjleo:codeforces_round_645_div._2 [2020/05/29 20:48] jjleo [E] |
2020-2021:teams:farmer_john:jjleo:codeforces_round_645_div._2 [2020/08/19 22:54] (当前版本) jjleo [D] |
||
|---|---|---|---|
| 行 21: | 行 21: | ||
| * 题意:一年有$n$个月，每个月$d_i$天，每个月的第$i$天权值为$i$。要求连续选$x$天使得权值和最大，注意一年是循环的，最后一个月完了是第一个月，保证$x$不超过一年的时间。 | * 题意:一年有$n$个月，每个月$d_i$天，每个月的第$i$天权值为$i$。要求连续选$x$天使得权值和最大，注意一年是循环的，最后一个月完了是第一个月，保证$x$不超过一年的时间。 | ||
| - | * 题解:容易发现最优答案一定是结尾正好过完一个月，因为不是的话把多余的日期往前放肯定更优。因此只需要破链成环然后维护两个指针扫一编就可以。 | + | * 题解:容易发现最优答案一定是结尾正好过完一个月，因为不是的话把多余的日期往前放肯定更优。因此只需要破链成环然后维护两个指针扫一遍就可以。 |
| =====E===== | =====E===== | ||
| - | * 题意:给定一个长度为$n$的数列，问是否存在$k$使所有长度为$k$的区间和均为正数。保证这个数列的后$\lfloor \tfrac{n}{2} \rfloor$个元素都一样。 | + | * 题意:给定一个长度为$n$的数列，问是否存在$k$使所有长度为$k$的区间和均为正数。保证这个数列的后$\lfloor \tfrac{n}{2} \rfloor$个元素都为$x$。 |
| - | * 题解: | + | * 题解:如果存在$k$，把这个$k$扩大两倍，类似倍增，依然成立，因此也一定存在一个$> \lfloor \tfrac{n}{2} \rfloor$的$k$。因此我们只需要考虑$> \lfloor \tfrac{n}{2} \rfloor$的$k$。我们考虑$n-k+1$个区间和的差分数组，为$[s_1,\ x-a_1,\ x-a_2,\ \ldots,\ x-a_{n-k}]$，每次将$k$增大$1$，这个数组变为$[s_1+x,\ x-a_1,\ x-a_2,\ \ldots,\ x-a_{n-k-1}]$，可以发现只是第一项增大了$x$，然后减少了最后一项。而在$k$增大的过程中只要有存在一个$k$，使得这个数组的前缀和数组的最小值为正数，即存在满足条件的$k$，否则不存在。 |
| =====F===== | =====F===== | ||
| - | * 题意: | + | * 题意:给定两个长度为$n$的序列$a$和$b$，问$a$能否经过数次__翻转操作__和__求前缀和操作__变成$b$，要求第二种操作的次数最小。$(1\le n \le 2\cdot 10^5, 1 \le a_i \le 10 ^ {12}, 1 \le b_i \le 10 ^ {12})$ |
| - | * 题解: | + | * 题解:首先$n=1$的时候只有$a_1=b_1$才符合条件否则不符合条件。对于其他情况，考虑前缀和的逆过程，差分。因为所有数均为正整数，因此如果一个序列为严格单增，那么可以进行差分，如果一个序列为严格单减，那么可以进行翻转后可以进行差分，否则这个序列无法再往回变了。因此我们对序列$b$进行上述操作，验证直到变不了为止能不能变成$a$即可，注意这个过程是唯一的从而保证了正确性。可以看到前缀和操作使得整个序列最值增长速率是$O(x^{n-1})$的，因此可以得到下面的操作次数上界。{{:2020-2021:teams:farmer_john:jjleo:cf1358f.png?200|}}可以看到$n \ge 3$的情况时间复杂度是可以接受的。当$n=2$时，差分的过程和辗转相除是相同的，在这个过程中判断能不能有一步使得和$a$相同即可。 |
2020-2021/teams/farmer_john/jjleo/codeforces_round_645_div._2.1590756523.txt.gz · 最后更改: 2020/05/29 20:48 由 jjleo
