CF1946B Maximum Sum
这道题是一道贪心题。
对于第 \(1\) 次操作，选择的话肯定是选最大的好，所以我们会找出原序列的最大子段和进行插入，为了使下一次的插入子段更大，所以我们一定会插入原序列的最大子段和中。进行 \(m\) 次操作，执行 \(m\) 次上述操作即可。
直接模拟的话肯定不行，我们考虑找找规律，由于每次插入都是插入现在序列的最大子段和中，所以每次插入的值都是翻倍增长的，易发现这是一个等比数列的求和。我们如果模拟上述操作，复杂度为 \(\mathcal{O}(m)\)，可以接受。
最后注意取模。
CF1004B Sonya and Exhibition
设区间 \([l,r]\) 中 \(1\) 有 \(x\) 个，\(0\) 有 \(y\) 个，当 \(x\) 和 \(y\) 最接近的时候，\(x \times y\) 最大，此结论可以用二次函数进行证明。接下来，考虑怎样构造使得 \(x\) 与 \(y\) 最接近。策略是交替输出 \(0\) 和 \(1\)，这样做的正确性是显然的。
CF899C Dividing the numbers
一道很好的构造题。
令 \(f(x)\) 表示 \(n=x\) 时的答案。
当 \(x=0\) 时，\(f(x)=0\)。
当 \(x=1\) 时，\(f(x)=1\)。
当 \(x=2\) 时，\(f(x)=1\)。
当 \(x=3\) 时，因为 \(3=1+2\)，所以 \(f(x)=0\)。
当 \(x>3\) 时，因为有 \((x-1)+(x-2)=(x-3)+x\)，所以 \(f(x)=f(x-4)\)。
依据 \(n \bmod 4\) 分类讨论即可。
如何证明次做法的正确性呢？令 \(a=\sum \limits_{i=1}^{n} i\)，如果 \(a\) 是奇数，那么最优答案就是 \(1\)，否则是 \(0\)，利用高斯公式依次计算出上述情况下的 \(a\)，并判断即可证明，在此不再赘述。
CF78B Easter Eggs
令 \(s=\texttt{ROYGBIV}\)，对于前 \(i\) 个彩蛋 \((1 \le i \le n-3)\)，第 \(i\) 个为 \(s_{(i-1) \bmod 4}\)，这样可以保证 \([1,n-3]\) 这段区间满足条件 \(2\)，对于后 \(3\) 个彩蛋，直接输出 \(\texttt{BIV}\)，这样就满足了条件 \(1\)，由我们的构造做法可知，\([n-6,n]\) 这个区间是 \(\texttt{ROYGBIV}\)，\([n-2,4]\)（题目要求是环）这段区间是 \(\texttt{BIVROYG}\)，都是符合条件的，故整个环符合条件 \(2\)，然后就做完了。
CF1759C Thermostat
分类讨论题
-
如果 \(a=b\)，那么不需要移动，\(ans=0\)。
-
如果 \(\lvert a-b \rvert \ge x\)，移动 \(1\) 次就可以了，那么 \(ans=1\)。
-
为了使移动距离尽可能大，最好的方法是移动到边界，即先移动到 \(l\) 或 \(r\)，再到 \(b\)，那么 \(ans=2\)。判断条件为 \(\left\{ \begin{array}{} a-l \ge x\\ b-l \ge x \end{array} \right.\) 或者 \(\left\{ \begin{array}{} r-b \ge x\\ r-a \ge x \end{array} \right.\)。
-
如果上述情况还是不满足，我们可以通过两个端点进行 \(3\) 次移动，即 \(a \rightarrow l \rightarrow r \rightarrow b\) 或 \(a \rightarrow r \rightarrow l \rightarrow b\)，判断条件为 \(\left\{ \begin{array}{} a-l \ge x\\ r-b \ge x \end{array} \right.\) 或者 \(\left\{ \begin{array}{} r-a \ge x\\ b-l \ge x \end{array} \right.\)。
由于两边端点都已经尝试过了，再移动已经没有意义了，故最多只能有 \(3\) 步，其余的情况都是无解，输出 \(-1\)。
CF1768B Quick Sort
易发现如果要让序列排序，那么原序列中 \(x \sim x+1\) 之间的所有数字都是需要移动的，所以原序列中只有一个最长的连续上升子序列是不需要动的，设其长度为 \(m\)，那么需要移动的数字数量为 \(n-m\)，由于每次可以移动 \(k\) 个且自动排序，故答案为 \(\left \lceil \frac{n-m}{k} \right \rceil\)。
CF1832B Maximum Sum
比较坑的一道题，直接双指针模拟贪心是不行的。
先将序列排序，设大的数删了 \(x\) 个，那么小的数删了 \(2 \times (k-x)\)，由于它是从头和尾删数，所以我们可以确定删了那些，统计前缀和和后缀和，枚举 \(x\)，更新答案即可。
CF1903B StORage room
考虑按位或运算的性质，即 \(a\) 和 \(b\) 某一位上都为 \(0\)，那么它们或起来的那一位上也是 \(0\)，反之，如果 \(M_{i,j}\) 的第 \(x\) 位上是 \(0\)，那么 \(a_i\) 和 \(a_j\) 的第 \(x\) 位上也是 \(0\)，所以我们可以先将 \(a\) 的每一位上都赋值为 \(1\)，再枚举 \(M\)，利用与运算执行上述操作（将 \(a_i\) 或 \(a_j\) 与上 \(M_{i,j}\)，由于与是只有两个 \(1\) 才是 \(1\)，所以如果 \(M_{i,j}\) 的某一位上是 \(0\)，那么 \(a_i\) 或 \(a_j\) 的相应位置上也是 \(0\) 了），最后将生成的 \(a\) 再代回检查一遍，如果不满足就是无解，否则输出即可。
CF1918B Minimize Inversions
将 \(a\) 数组排序，就可以最小化两个序列中逆序对的个数的和了，证明如下：
标签：移动,1300,Codeforces,ge,right,序列,array,800,rightarrow From： https://www.cnblogs.com/zhuluoan/p/18240636当 \(a\) 排序了之后，对于任意一对 \(i\) 和 \(j\)，两数组中逆序对之和数量 \(x\) 最大为 \(1\)，当 \(x=0\) 时，交换后 \(x\) 为 \(2\)，当 \(x=1\) 时，交换后 \(x\) 为 \(1\)，所以再怎么交换都不可能更优了，故现在的序列即为最优解。