CF-Div3

¶Codeforces Round 895 (Div. 3)

A.Two Vessels
一次操作可以让两个杯子的差减少$2\\*c$，所以答案是两个杯子的差除$2\\*c$ 上取整，即$(abs(a-b)+2*c-1)//2*c$。$O(1)$

B.The Corridor or There and Back Again
对于每个陷阱，都满足$s>2*(k-d)$，即$k<s/2+d$，即$k$ 最大可取$ceil(s/2+d-1)$。$O(N)$

C.Non-coprime Split
求$[l,r]$ 中的一个合数，很容易找到，所以不用筛，直接暴力枚举判断即可。注意最小从4开始枚举。

D.Plus Minus Permutation
下标为$x$ 和$y$ 的公倍数的数最终会被抵消，所以考虑非公倍数的$x$ 的倍数和$y$ 的倍数。
前$x$ 大的数减去前$y$ 个小的数，即为答案。

E.Data Structures Fan
先求出未修改时的初始答案，再求个异或前缀和，每次区间反转，都将答案异或上区间异或和。
这样原本有这个数就会消去，原本没有这个数就会异或上这个数。$O(N)$

F.Selling a Menagerie
每个动物都有害怕的动物，但未必每只动物都被其他动物害怕。
将这些动物卖出能得到双倍收益,且卖出后可能会得到新的不被其他动物害怕的动物。
所以将这些动物先卖出必是最优解。
卖出之后，剩下的动物必定有害怕的动物且被其他动物害怕。
由此构成一个个循环节,每个循环节相互独立，分别考虑。
对每个循环节来说，从任何一个节点开始卖出，都必定有一个动物只能卖出单倍价格。
根据贪心，使其为价格最低的那只，将其最后卖出即可。$O(N)$

G.Replace With Product
暴力枚举：将所有不为1的数的下标取出，枚举左右边界，计算新数组的最大值，得出答案。
但直接暴力会超时，考虑优化。
双指针将范围从$[1,n]$ 缩小到左右边界都不为$1$，对于这个范围长度为$n$ 的区间，考虑是否能直接取整个区间。
对当前区间求前缀积，假设某个前缀积$p$，当前的情况最坏可能是$p1111111……11112$。
如果取整个区间为最优解，则$2\\*p>p+2+n-2→p>n$，则$2\\*p>2\\*n$,可能当前前缀积已经到了最后，即最坏情况是$p>2\\*n$。

¶Codeforces Round 943 (Div. 3)

C. Assembly via Remainders
$a_i=k*a_{i-1}+x_i$,$a_{i-1}>x_i$,$2<=i<=n$,$1<=x_i<=500$。
取$a_1$ 为某个大于$500$ 的数，一直递推$a_i=a_{i-1}+x_i$，满足$a_{i-1}>x_i$。

D. Permutation Game
最优策略为走到某个能走到的分数最高的点后一直停在那，因为后面的点分数都比这个点小。

E. Cells Arrangement
在倒数第二行的最右边放一个，其余的都放在对角线上，即$(i,i),1<=i<=n-2$ 和$(n-1,n),(n,n)$ 。
$(n-1,n)$ 和对角线上的点距离相差为$2$ ，$(n,n)$ 和对角线上的点的距离也差$2$ ，且补充了$(n-1,n)$ 形成的距离的空位。

F. Equal XOR Segments
先做一遍异或前缀和。
若$k$ 为偶数，可变成$k=2$ 的情况，只需要$a[r]==a[l-1]$ 即可。
若$k$ 为奇数，可变成$k=3$ 的情况，就分成$[l,x],[x+1,y],[y+1,r]$ 这三段。
则$a[y]==a[l-1],a[r]==a[x]$，只要找到$[l,r]$ 内最靠左边的$x,a[x]==a[r]$ 和$[l,r]$ 内最靠右边的$y,a[y]==a[l-1]$,且$x<y$ 即可。
查找$x,y$ 可以先按$a[i]$ 分类，按顺序存下标，再二分即可。

G1. Division + LCP (easy version)
二分答案，用$KMP$ 或者$Z$ 函数进行$check$ 。

G2. Division + LCP (hard version)
对于$k<=\sqrt(n)$ ，仍然二分，$O(\sqrt(n)nlog_2(\sqrt(n)))$ 。
对于$k>\sqrt(n)$ ，$LCP\\*k<=n$ ,$LCP<=\sqrt(n)$ ，枚举$LCP$ ,对于固定的$LCP$ ，它的最大划分个数$k$ 可以在$O(n)$ 的时间内得到，总的复杂度为$O(nlog_2n)$ 。
对于那些没有得到答案的划分个数$k$，说明它不是某个$LCP$ 的最大划分个数，但它等于$ans[k+1]$ ，反向扫一遍即可。