^  A  ^  B  ^  C  ^  D  ^  E  ^
|  +  |  +  |  +  |  O  |  O  |
rank:1074
 
=====A=====
  * 题意:输出两个合数使得两者之差的等于$n$。

  * 题解:输出$9n,8n$。

=====B=====
  * 题意:给出序列$a$和$b$，求一个最小的$x$使得$a$中每个元素$a_i=(a_i+x) \mod m$后可以通过排列使其和$b$相等，保证存在答案。$(1 \leq n \leq 2000, 1 \leq m \leq 10^9, 0 \leq a_i,b_i < m)$

  * 题解:枚举$a_1$要变成$b$里哪个元素，然后枚举验证即可。

=====C=====
  * 题意:给出数字$a$和小于其位数的正整数$k$，求最小的数字$b$，使得$b \ge a$，而且对于$b$的每一位有$b_i = b_{i+k}$。

  * 题解:因为$b$有循环节，因此我们只用考虑前$k$位。先考虑前$k$位和$a$完全一样，遍历每一位进行比较，如果可行，直接输出即可；否则如果不可行，那么只需要让前$k$位加个$1$即可。

=====D=====
  * 题意:给出一个由方格组成的图形，每一列由数个格子组成，底部对齐，保证每一列的高度不增，最多能放多少个$1 \times 2$或$2 \times 1$的多米诺骨牌。

  * 题解:黑白染色，答案是两者颜色的最小值。因为每一个多米诺骨牌一定是占据一个黑格和一个白格，因此这是上界。我们将多余颜色的格子从某一列的顶端删掉使得两种格子数量相等，下面证明两种格子数量相等时一定可以铺满：从最矮的一列开始以此进行如下操作，设它右侧一列的高度为$x$，在满足这一列高度$\ge x$的情况下不断铺$1 \times 2$使得这一列的高度减少；如果这一列的高度和右侧一列的高度相同，则可以直接将这两列全部删去，否则不做任何操作考虑下一列，此时这列的高度一定比右侧一列高$1$，整个操作过程中始终保持两种格子数量相等。这样下去如果存在没有被删去的方格，此时每一列的高度一定为$n,n-1,...,2,1$，可以发现此时两种颜色的格子数量不等，因此不可能达到这种状况，最终一定可以全部铺满。

=====E=====
  * 题意:给定一个$1$到$n$的排列，定义$f(i)$为最少交换两个元素的次数使得$1,2,...,i$连续出现，求$f(1),f(2),...,f(n)$。$(1 \leq n \leq 200\,000)$

  * 题解:对于$f(i)$，最优方案一定是先将$1,2,...,i$放在一起，然后再进行冒泡排序。冒泡排序交换元素的次数就是逆序对的个数，比较好处理，考虑将这些数字放到一起需要的次数。移动方案一定是某一个数不动，然后左右其它数全部聚过来，考虑选择哪个数移动次数最小。一个数字移动到中心的次数就是$距离-中间数字的个数$，因此可以发现最中间的位置即中位数是最优的。因此只需要开个树状数组维护位置和，还有前面求逆序对是树状数组，以及求中位数用的树状数组求第k小。
  * 才知道树状数组也可以求第k小。