CVBB ACM Team

题意:比比谁更快

题解:我慢死了

题意:$n$个人，每个人有一个权值$a_i$，一开始家里只有自己一个人，每次可以邀请数个人来，他们会同时到达。必须保证每个人到的时候看到的其他人的数量$\ge a_i$，问最多能有多少人到自己家里（算自己）。

题解:按照$a_i$排序。最优方案一定是让一个前缀的人一起来。从大到小遍历，计算此时最多能有多少人到以判断这个人能不能来，如果不能则将数量$-1$继续判断即可。

题意:如图，问从某个格子走到右下的另一个格子，路径权值之和有多少种不同取值。

题解:容易发现只要最值是先右再下和先下再右，中间的值都可以取到。然后我花了很长时间找规律得到了一个很长的鬼畜还正确的式子。其实只需要发现每早往下走一下就会让答案多$(y_2-y_1)$（其实一开始想到了这里但是没往后想）。因此答案就是$(x_2-x_1)\cdot(y_2-y_1) + 1$。

题意:一年有$n$个月，每个月$d_i$天，每个月的第$i$天权值为$i$。要求连续选$x$天使得权值和最大，注意一年是循环的，最后一个月完了是第一个月，保证$x$不超过一年的时间。

题解:容易发现最优答案一定是结尾正好过完一个月，因为不是的话把多余的日期往前放肯定更优。因此只需要破链成环然后维护两个指针扫一遍就可以。

题意:给定一个长度为$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$，否则不存在。

题意:给定两个长度为$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})$的，因此可以得到下面的操作次数上界。可以看到$n \ge 3$的情况时间复杂度是可以接受的。当$n=2$时，差分的过程和辗转相除是相同的，在这个过程中判断能不能有一步使得和$a$相同即可。