切 5 道。
A
\([a_1=1]\)
B
\(\max(\max(xy),\max(x^2),\max(y^2))\)
第一部分可以选整个数组，第二部分和第三部分是最大连续 0 段和 1 段。
C
操作等价于 \(a_{l \sim r} \oplus 1\)，\(b_{l \sim r} \oplus 1\)，\(b_{1 \sim n} \oplus 1\)。
考虑先把 \(a\) 全部变成 \(0\)，使用 i i 操作完成。
那么，只有当这样操作结束后 \(b\) 是全部相同的情况下，才可能有解。
如果 \(b\) 是全 \(1\)，那么就进行如下操作：
1 1
2 2
1 2
于是可以在 \(n+3\) 次操作内完成任务。
D
\[\prod_{i=1}^{n-1}\sum_{j=1}^{m}[\operatorname{gcd}(a_i,j)=a_{i-1}] \]莫反变为
\[\prod_{i=1}^{n-1}\sum_{d|\frac{a_i}{a_{i+1}}}\mu(d)\lfloor \frac{m}{a_{i+1}d} \rfloor \]直接对着式子求即可。
E
先考虑单个串的代价怎么求，容易发现是 \(\max(左括号数量,右括号数量)-匹配括号对数\)。
这个是曾经的模拟赛套路。
求匹配括号对数直接在原串上匹配，对于每一对在 \((l,r)\) 的匹配括号，匹配括号对数加上 \(l(n-r+1)\)。
怎么求 \(\max(左括号数量,右括号数量)\) 呢？
将 \(\max(a,b)\) 转化为 \(\frac{a+b+|a-b|}{2}\)。
\(a+b\) 非常好求，\(|a-b|\) 比较难求，考虑将左右括号转化为 \(\pm 1\) 序列，那么问题就是子串绝对值和，将前缀和序列排序，答案即为 \(\sum_{i=1}^{n}\sum_{j=1}^{n}s_j-s_i\)，这里注意到每一个 \(i\) 被小于 \(i\) 的位置加一次，被大于 \(i\) 的位置减一次，因此化简为 \(\sum_{i=1}^{n}a_i(2i-n)\)。
假如计数排序，有复杂度 \(O(n)\)。
标签：Rated,匹配,max,sum,括号,Prizes,Div,oplus From： https://www.cnblogs.com/acwing-gza/p/18212138