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 22:52] jjleo [F] |
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===== | ||
| 行 31: | 行 31: | ||
| * 题意:给定两个长度为$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$的序列$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$相同即可。 | + | * 题解:首先$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.1590763955.txt.gz · 最后更改: 2020/05/29 22:52 由 jjleo
