因为是蒟蒻，所以只有Div.2（的前几题）
一、构造与贪心
1. Round#735(Div.2) A. Cherry
题意：求一个序列任意连续子序列的最大值乘最小值的最大值。
思路：经过感性的分析我们发现，假如$ a_i \sim a_j $是一个序列，我们添加一个数$ a_k $进去，如果$a_k$大于该序列中的所有数，那么结果将会变好，但是不会好于从该序列中去掉$a_i$再加入$a_k$；如果$a_k$不是最大数，那么加入它不会使结果变得更好。所以经过一番不严谨的推理，我们得出只需检查相邻两数的乘积即可。时间复杂度：$O(n)$.
比赛时写了ST表查最大值，再单调栈维护最小值区间的$O(n\log{n})$算法，光荣第一题TLE。（为什么3e5的数据会TLE啊啊啊）顺便一提这期比赛质量真是绝佳。
2. Round#735(Div.2) D. Diane
题意：构造一个长度为$n$的字符串，使得所有子串出现奇数次。
思路：考虑这样一个长度为$k$的字符串$aa\cdots a$，$a$在其中出现$k$次，$aa$在其中出现$k-1$次，以此类推。所以如果有两个这样的长度分别为$k$和$k-1$的字符串，那么含有$a$的所有字符串出现的次数就是奇数次了，中间根据$n$的奇偶用$b$或者$bc$隔开即可。时间复杂度$O(n)$.
3. Edu Round#112(Div.2) D. Say No to Palindromes
题意：定义如果一个字符串不含长度至少为2的回文子串，则其为beautiful串。给定一个$abc$组成的字符串$s$，每次操作可以将一个字符变成$abc$之一，求将$s[l:r]$(inclusive)变成beautiful串的最小操作次数。
思路：考虑beautiful串的特点，$a$后面不能接$a$，只能接$b$和$c$；$ab$后面只能接$c$；$abc$后面只能接$a$。以此类推，我们发现，所有的beautiful串只能是$abc$的6种全排列的重复之一。所以我们遍历这六种情况，找出和原串差别最小的情况即可。时间复杂度$O(n)$.
4. Round#738(Div.2) D. Mocha and Diana
题意：两个森林，同时加边，问最多能加多少边使得仍然是森林
思路：第一问暴力$O(n^2)$，维护两个并查集即可。第二问，我们的目标转换过来就是，不成环的情况下，把所有点和1连上。我们首先将所有能够和1相连的连通块（两个森林中均未与1相连）都和1连接起来，然后我们就只需要把剩下的连通块利用某种方式合并到1所在的连通块上。我们发现，剩下这些连通块只有两种情况，一种是在一棵树中已经和1相连，但在另一棵书中未和1相连；另一种情况就是反过来。我们把这两种情况分成两个集合（存放的是节点对应的连通块，非节点本身），分别取出一个元素$u$和$v$，把他们连起来。懒狗可以像我一样写$O(n\log n)$的，可以用单调栈优化成$O(n)$. 算法分类不明，姑且认为是贪心。
官方思路：看不懂，但是大为震撼。
5. Round#740(Div.2) E. Bottom-Tier Reversal
题意：一个奇数长度排列，每次可以翻转开头的奇数长度子数组，找一种方法在$\frac{5n}{2}$次操作内排序。
思路：首先需要知道，翻转奇数长度数组不会改变下标的奇偶性，也就是说，我们可以检查数字的大小和下标的关系来判断是不是能够排序（因为是排列）。如果能够排序，可以证明的是，一定能在$\frac{5n}{2}$次操作内完成（属于是诈骗了）。具体的做法是假设$[x+1,n]$已经排序好了（$x$是奇数），首先将$x$换到下标$1$，再换到$x-1$，再翻转$[1,x+1]$，再翻转$[1,3]$，最后翻转$[1,x]$，这样就一次把$x,x-1$都放到了最后的位置上，每两个数需要5次，满足条件。时间复杂度$O(n^2)$.
6. Round#741(Div.2) D. Two Hundred Twenty One
题意：一个由-1和1构成的数组$a$，问$a[l:r]$最少删去哪几个元素后满足$\sum_{i=1}^{n}{(-1)^{i-1}a[i]}=0$.（下标自动reset从1开始了）
思路：我们先来看最少删去几个元素。首先如果本来就满足，那肯定就不用删了；然后我们感性的发现，如果一个区间和为0，那么在之前怎么删（相当于挪动这个区间），都不会改变其值；如果区间的和是单调的（按上面的公式计算和），那么删掉其中一个元素后，后一半会折过来，单调性改变。所以感性的分析配合一点理性的思考我们发现，如果是奇数个元素，就删掉中间那个（把起伏的区间想象成单调的，可以证明是满足的），如果是偶数个元素，就删掉两个（中间一个，尾巴一个）。但这样思考第二问就不好做了（因为实际上区间是起伏的，不好定位元素位置），我们来看官方怎么思考的。
7. Round#742(Div.1 + Div.2) C. Compressed Bracket Sequence
题意：给定一个括号序列用数字表示连续的括号个数，奇数下标表示左括号，偶数下标表示右括号，问能够匹配的子串个数。（我觉得是这篇文章中最离谱的题，极其难懂）
思路1：枚举所有奇数下标，计算出每个奇数下标$i$对应的那些左括号作为最左括号能生成的合理子串个数。我们用一个变量$left$表示这个下标的括号还剩多少没匹配，用变量$sum$记录从$i$开始到当前的$j$还剩余的左括号数，那么如果$left \ge max{sum, 0}$，可以在答案上累加$left - max{sum, 0}$，如果$j\ne i+1$，我们还需要给答案加上1，表示同一个层次的匹配括号和之前的连接了起来（比如”()()”这种），如果$left<0$，可以直接跳出循环。解释一下为什么会有$left<sum$，比如”()((()”，$i=1$时，会出现这种情况，但也不能贸然跳出循环，因为后面可能会有让其匹配的情况。时间复杂度$O(n^2)$.
思路2：维护一个栈，但是这个栈需要能取到栈底。每一次在答案中累加当前又消耗了几个左括号，用$sum$来维护还剩余的左括号数量，对于同一深度的括号，比如”()()()()”，有$1+2+3+4=10$种，我们每遇到一个深度一样的”()”（只是代指这一类的），就累加栈顶的值到答案中，并把当前栈顶的值加一。如果当前的深度小于栈顶的深度，就不断弹走栈顶的元素，并累加其深度（注意，深度可能是负数，但没有关系，比如第一步的累加反正是用$sum$和栈底的值做减法，$sum$也可能负的）。如果栈顶的深度和当前深度不同，栈空了，表示出现了比如”()))”这种，我们把当前的深度和数值0压栈；栈不空，把当前深度和1压栈，表示希望留着和后面的连起来。（可能说的非常抽象。。。）时间复杂度$O(n)$.
官方思路：看不懂，谢谢，希望说点人话。
8. Round#742(Div.1 + Div.2) E. Equilibrium
题意：给定两个序列$a$和$b$，每次操作可以选择一个偶数长度数组，其中偶数下标位置使该位置的值作为下标对应的$a$中的值+1，奇数位置使该位置的值作为下标对应的$b$中的值+1，问最少多少次能使$a$与$b$逐位相等。
思路：首先由于数组长度是偶数，所以$a$和$b$的和增加的值是相同的，也就是说如果要使最后$a$和$b$相等，那么必要条件是$a$和$b$的和相等。此外，如果我们令$sum$为$b-a$的前缀和，那么一定不能有位置使$sum<0$，这是因为每有一个使$b$增加一的下标，就一定对应了之前一个使$a$增加一的下标，所以前缀和没有发生变化，依然小于0。而对于一个$sum>0$的位置，我们则可以通过多次增加该位置$a$的值使$sum=0$，由于一次可操作多个位置，经过一些感性的判断，我们发现，答案就是$sum$的最大值。
二、数学与二进制
1. Round#735(Div.2) B. Cobb
题意：找到所有$i\cdot j-k\cdot (a_i|a_j)$的最大值。$(i < j)$
思路：因为$k$的上限很小，于是我们感性地认识到，$i$和$j$越大越好。我们考虑$i=n-1,j=n$时，上述式子的可能的最小值，因为$a_i \le n, a_j \le n$，所以有$a_i | a_j \le 2n$，也就是说在这种情况下，目标值不会小于$n(n-1)-2kn$。所以即使我们假设$j=n$那么$i$也一定需要满足$i \cdot n \ge i \cdot n - k \cdot (a_i | a_j) \ge n(n-1) - 2kn$，这样我们就找到了$i$的下限，也就是$n-1-2k$，这样我们就只需要在$n-1-2k \sim n$的范围内枚举$i$和$j$即可，复杂度$O(k^2)$.
2. Round#735(Div.2) C. Mikasa
题意：找到序列$n \oplus 0, n \oplus 1, \cdots , n \oplus m$的MEX值。
思路：首先需要知道一个基本性质$x\oplus y = z \Leftrightarrow x\oplus y\oplus x = z \oplus x \Leftrightarrow x \oplus z = y$，这样，我们就把问题转化为了找到最小的一个值$k$使得$n \oplus k > m$. 令$p=m+1$，我们从高位到低位顺次考虑各个二进制位，如果$n_i = p_i$，那么我们就设$k_i=0$；如果$n_i = 0 \wedge p_i = 1$，那么我们就别无选择，只能设$k_i=1$；如果$n_i = 1 \wedge p_i = 0$，那么我们就直接跳出循环（令剩下所有位为0），此时必然有$n \oplus k > p$成立，我们就算设剩下中某些位为1，那么也只会增大$k$，不满足我们希望$k$最小的要求。时间复杂度$O(\log{(max(n, m+1))})$.
3. Round#736(Div.2) D. Integers Have Friends
题意：如果$\exists m$使得子数组满足$a_i \equiv a_{i+1} \equiv \cdots \equiv a_j\ (mod\ m)$，则称之为friend group，找出这样的子数组的最大长度。
思路：上式等价于$a_i - a_{i+1} \equiv 0\ (mod\ m), a_{i+1} - a_{i+2} \equiv 0\ (mod\ m)\ \cdots$，也就是说，$m$是两两之差的公约数。那么我们只要求出这个区间的最大公约数，并检查是否大于1即可。我们可以利用双指针维护区间，利用ST表求出各个区间的最大公约数。时间复杂度$O(n\log{(n\log{10^{18}})})$.
4. Round#736(Div.2) E. The Three Little Pigs
题意：求$\binom{3}{x}+\binom{6}{x}+\cdots +\binom{3n}{x}$.
思路：令$dp[i][j]=\sum_{k=0}^{N}\binom{3k+j}{i}$，则答案即为$dp[x][0]$. 考虑方程组：
$$
\begin{cases}
\binom{3i+1}{x}=\binom{3i}{x}+\binom{3i}{x-1} \
\binom{3i+2}{x}=\binom{3i+1}{x}+\binom{3i+1}{x-1} \
\end{cases}
$$
方程组两边从$i=0$到$n$求和，便转换成了$dp$之间的关系。
此外，我们发现，$dp[x][0]+dp[x][1]+dp[x][2]=\sum_{i=0}^{3n+2}{\binom{i}{x}}=\binom{3n+3}{x+1}$，于是得出以下方程组：
$$
\begin{cases}
dp[x][0]+dp[x][1]+dp[x][2]=\binom{3n+3}{x+1} \
dp[x][1]=dp[x][0]+dp[x-1][0] \
dp[x][2]=dp[x][1]+dp[x-1][1] \
\end{cases}
$$
解这个方程组，我们便得到了想要的解。
数学知识复习：
$$
\begin{align}
& 1.\ \binom{n+1}{m}=\binom{n}{m}+\binom{n}{m-1} \
& 2.\ \sum_{i=x}^{n}\binom{i}{x}=\binom{n+1}{x+1} \
& 3.\ \sum_{x=0}^{y}\binom{n}{x}\binom{m}{y-x}=\binom{n+m}{y} \
& 4.\ k\binom{n}{k}=n\binom{n-1}{k-1}
\end{align}
$$
5. Round#737(Div.2) C. Moamen and XOR
题意：长度为$n$的数组$a$满足所有元素小于$2^k$，求出满足$a_1&a_2&\cdots&a_n \ge a_1\oplus a_2\oplus \cdots \oplus a_n$的数组个数。
思路：我们从低位向高位考虑，用$dp[i]$表示当前考虑到第$i$位的满足条件的个数。根据异或的性质，当前位的1的个数为偶数时，不等号右边为0，不等式一定满足（当且仅当$n$为偶数，且1的个数为$n$时不取等），此时，总共有$\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots = 2^{n-1}$种情况。注意到$n$为奇数时，左边不可能大于右边，加上第$i$位全是1的情况，所以$dp[i]=dp[i-1]\times (2^{n-1}+1)$. 而当$n$为偶数时，所有数均为1时左边大于右边，此时我们不要求更低位也满足上述不等式，所以需要加上低位不满足不等式的情况，共${(2^n)}^i-dp[i-1]$种。我们得到状态转移方程：
$$
\begin{cases}
dp[i]=dp[i-1]\times (2^{n-1}+1)& i\ is\ odd \
dp[i]=dp[i-1]\times 2^{n-1}+2^{i\times n}-dp[i-1]& i\ is\ even \
\end{cases}
$$
时间复杂度$O(n)$.
官方思路：好像差不多？分了当前位取不取等的情况，然后记忆化递归求解，略慢，没用数学公式化简。
6. Round#738(Div.2) E. Mocha and Stars
待填坑。。。
7. Round#740(Div.2) D. Up the Strip
题意：走楼梯，从$n$开始，可以通过减法运算走到$1\sim n-1$中任意一个，也可以通过除法运算，走到$\lfloor \frac{n}{z}\rfloor\ (2 \le z \le n)$，问共有多少种走法走到1，不同的运算（包括除数不同）走到同一格算不同种。
思路：关于减法运算，我们可以从$i+1\sim n$中的任意一个点走过来，所以有$dp[i]=\sum_{j=i+1}^{n}{dp[j]}+\cdots$，我们只需要通过一个前缀和维护一下即可。那么除法运算又有哪些地方可以走过来呢？对于$i$，所有位于$[i\times z, i\times z + z - 1]$之间的数都可以通过除以$z$走到$i$，所以我们得到了状态转移方程：$dp[i]=sum[i+1]+\sum_{z=2}^{n/i}{sum[i\times z]-sum[min(i\times z+z-1, n)+1]}$. 根据调和级数求和公式得到，时间复杂度：$O(n/2+n/3+n/4+\cdots +n/n)=O(n\log n)$.
官方思路：我们来逆向考虑这道题，从1走到$n$. 首先来看第一问，减法部分和上面一样，不再叙述。我们知道，对于一个数$x$，$\lfloor \frac{x}{z}\rfloor$最多只有$\sqrt{n}$种取值。我们按照如下的做法计算：首先遍历$z\le \sqrt{x}$的情况，那么此时对于剩下的数，$\lfloor \frac{x}{z}\rfloor < \sqrt{x}$，我们遍历$[1,\sqrt{x}-1]$的这些数，设当前遍历到$c$，根据不等式$c\le \frac{x}{z} < c+1$，我们计算得到$\frac{x}{c+1}<z\le\frac{x}{c}$，这样就得到了从$c$到$x$共有多少种$z$. 时间复杂度$O(n\sqrt{n})$.
再来看第二问，我们来考虑$dp[x]和$$dp[x-1]$差在了哪里，这样就可以递推求解了。首先$x$可以多走到$x-1$，也就是多一个$dp[x-1]$，其次对于$x$的每一个因子$i$，都取代了$i-1$的一次出现，比如说$\frac{5}{3}=1,\frac{6}{3}=2$，对于6的因子2，取代了$1$的一次出现（如果不考虑$\frac{6}{6}=1$的话，这个可以后面补上）。所以在遍历到$i$时，我们可以遍历每一个$i$的倍数，将$dp[i]-dp[i-1]$加到上面去。最后我们在递推的过程中把差值逐渐来累加起来就得到了$dp[x]$的值。略难懂，建议手动模拟一下。时间复杂度：$O(n\log{n})$.
8. Round#742(Div.1 + Div.2) D. Take a Guess
题意：交互题。有一个未知数组，可以询问第$i$个数和第$j$个数的$and$或者$or$，询问不能超过$2n$次，求第K个数。
思路：求第K个数排序就完事了，想用快速选择的也可以用。首先需要知道$(a&b)+(a|b)=a+b$，我们询问第$i$个数和第$i%n+1$个数的$and$以及$or$，因为我们发现每一位不会影响到其他位，所以只要检查第一个数的每一位能否为1就行，不用管能不能为0，因为是具体数组生成的，所以保证是有解的，不为1肯定为0. 我们检查的时候按照每相邻两个数$and$和$or$的4种情况决定是否合法，以及应该变成哪个数，最后走完一圈又回到了0，应当和初始值相同。求出第一个数后，其他数就能用两两和求出来了。时间复杂度$O(n\log{10^9})$.
官方思路：先询问得到$a1+a2,a2+a3,a3+a1$，然后就能把$a1$解出来了，然后就没有然后了，我是伞兵。时间复杂度$O(n)$.
三、数据结构
1. Edu Round#112(Div.2) E. Boring Segments
题意：给定$n$个区间，找出一个子集，使得能够覆盖$[1,m]$并且$w$的最大值减最小值最小。
思路：直觉告诉我们应该先按照$w$给所有区间排个序。然后正常人的第一反应应该都是枚举$w$最小值，二分查找最大值吧，于是就发现似乎不太好快速判断在这个范围内的区间是否覆盖了整个区间。让我们换一个角度，如果最小值和最大值具有某种单调的函数关系，那么就可以用双指针维护了。事实上，容易发现的是，在所选区间能够覆盖$[1,m]$的情况下，随着最小值的增加，最大值也是单调递增的（暂停思考一秒钟）。另一个关键问题是如何判断是否覆盖了$[1,m]$，我们可以维护一个最小值线段树，线段树的节点$i$表示有多少区间覆盖了区间$[i,i+1]$（精彩的一步），于是我们只需查看$query(1, m-1)$否为0即可。时间复杂度$O(n\log{n}+n\log{m})$
2. Round#737(Div.2) D. Ezzat and Grid
题意：对于一个beautiful的01组成的grid，任意相邻两行均至少有一列是1。求至少删去哪些行，使得the given grid becomes beautiful.
思路：首先我们需要对列的值进行离散化，不然列数太多。令$dp[i][j]$表示当前考虑到第$i$行（最后一行不必为$i$），同时最后一行第$j$列为1的最大beautiful行数，$grid[i][j]=1$时有$dp[i][j]=1+max{dp[i-1][k]}$，其中$k$属于第$i$行为1的那些列；如果$grid[i][j]=0$，那么$dp[i][j]=dp[i-1][j]$. 这样子时间复杂度为$O(nm^2)$，显然是不能接受的。我们利用线段树来维护第$j$列的$dp$的最大值，以及这一最大值对应的最后一行的位置，也就是说，类似于最长上升子序列问题（$O(n\log n)$版本)，对每一列，我们维护当前的最长序列长度和这个长度的最后一个位置是哪里。这需要我们对线段树做一点改造，线段树的$val$值应当是一个pair（pair自带的重载比较符号足以胜任）。同时在枚举时，事实上我们只需枚举每行中为1的那些线段即可，不必枚举每一个位置，反正为0的位置都是继承之前的，也就是总共只需枚举$m$条线段（按照行的顺序），每次枚举完成后用新的值更新线段树即可。代码略难写，时间复杂度$O(m\log m)$.
