Codeforces Round 1006 (Div. 3) A/B/C/D/E/F

A

题意

给定一个长度为$n$的数列$a$，一开始每个数字都是$0$，每次操作可以将一个数字变为$[-p,p]$中的任意整数，问最少进行几次操作后，可以使得数列中所有数字的总和恰为$k$，或不可能达到

解法

显然地，最好的方法是尽可能多地使用$p$或者$-p$，因此如果$|k|\gt n\times p$，则不可能达到，否则答案就是$\lceil\frac{k}{p}\rceil$
复杂度$O(1)$

B

题意

定义一个由-和_组成的字符串的价值为形如-_-的子序列的数量，现在给定一个由-和_组成的字符串，要求重新排列，使得字符串的价值最大

解法

对于一个_，其贡献为左边的-数量乘以右边的-数量，因此最优解显然是把所有的_放在中间，而两边的-如何分配呢？总和相等时，两数越接近，乘积越大，因此只要尽可能平分即可，因此总分为_的数量乘以-尽量平分之后的两数的积
复杂度$O(n)$

C

题意

给定$n$和$x$，找到一个长度为$n$的数列$a$，满足数列中所有数进行按位或之后恰等于$x$，且使得数列中未出现过的最小自然数最大

解法

考虑从$0$开始的自然数的二进制表示，会发现实际上可能达到的数字，取决于$x$的二进制表示中，后缀的连续$1$的个数，也就是小于等于这部分二进制表示的所有自然数都可以选择。考虑到实际上前$n-1$个数字只要其二进制表示是$x$的子集，就可以随意选择，因此前$n-1$个数字可以按这个规则尽可能地添加，直到达到$n-1$个数字或者使用完为止，之后的数字填上$x$来兜底即可。
需要注意有一个特例，假如$n-1$也在$x$的后缀$1$框定的范围内，并且前$n-1$个数字的或已经达到了$x$，则第$n$个数字应为$n-1$而不是$x$
复杂度$O(n)$

D

题意

给定一个数列$a$，可以进行一次操作，选择一个区间$[L,R]$，将区间$[L,R]$中的数字向左循环移位一次，要求操作后数列$a$的逆序对数量最少，输出任意一个合法解选择的区间$[L,R]$

解法

注意到数据范围，$n$和$a_{i}$均为$2000$，因此$O(n^{2})$的算法可以通过
考虑如果选择了区间$[L,R]$，则对数列的逆序对数量的影响是，减去区间$[L+1,R]$中小于$a_{L}$的数字的数量，加上区间$[L+1,R]$中大于$a_{L}$的数字的数量
因此暴力枚举开头，之后往右一路枚举结尾，维护对答案的影响即可
实际上，这里可以使用数据结构优化
考虑将枚举的顺序改为按数字从小到大枚举，那么一开始，所有的位置都是比当前数字大的，因此对答案的贡献都是$-1$（我们考虑求最大的顺序对数量的情况），而对于枚举完成的数字，他一定比之后枚举的数字小，因此对答案的贡献是$1$
因此随着枚举数字，每一轮把当前数字的值置为$0$，计算答案，之后再置为$1$，这样我们的问题就变成，求从当前位置开始，最大的前缀和及其下标
由于对于每个位置，后缀总和是确定的，因此问题可以转化成最小的后缀和，而这个最小的后缀和则可以使用线段树进行维护，修改时区间修改前缀，查询时区间查询后缀即可
复杂度$O(n^{2})$或$O(nlog_{2}(n))$

E

题意

构造题，给定一个$k$，要求在二维平面上构造不超过$500$个坐标均为整数的点，使得其中恰好有$k$对点的欧氏距离等于曼哈顿距离，且不存在完全重合的点

解法

欧式距离等于曼哈顿距离的意思就是两点的横坐标或纵坐标相同
一个比较简单的构造方法是，考虑到$i$个点共线时，会产生$\frac{i(i-1)}{2}$个满足条件的点对，因此从大到小枚举共线点的数量$i$，当点对的数量小于等于$k$时，就构造$i$个共线的点，然后从$k$中减去$\frac{i(i-1)}{2}$，重复直到$k\lt\frac{i(i-1)}{2}$为止，之后枚举下一个$i$
复杂度$O(n)$

F

题意

给定一个初始数$k$，构造一个无限大的三角形，其中第$i$行有$i$个数字，第$1$行的数字为$k$，之后每一行，第$1$个数字为上一行的第$1$个数字，最后一个数字为上一行的最后一个数字，对于中间的每个数字，第$j$个数字为上一行的第$j$个数字和上一行的第$j-1$个数字的异或和，现在给定一个$n$，要求输出这个三角形的第$n$行

解法

首先，由于异或的性质，相同的数字异或后为$0$，任何数与$0$异或后不变，而题目中所有构造新数字的方法都是异或，因此三角形中只会出现$k$和$0$，因此$k$可以先忽略，以$1$代替，之后替换为$k$即可
考虑到构造方法，手动模拟找规律或者推一推式子后可以发现，这个三角形具有类似分形的性质，比如其前$16$行如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1
1 1
1 0 1
1 1 1 1
1 0 0 0 1
1 1 0 0 1 1
1 0 1 0 1 0 1
1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 1
1 1 0 0 0 0 0 0 1 1
1 0 1 0 0 0 0 0 1 0 1
1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 0 0 0 1 0 0 0 1
1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

可以看出，前两行构成一个小三角形，第$3-4$行实际上是两个这样的小三角形并排，第$5-8$行是前$4$行的三角形并排
因此这里只要递归处理即可，每次递归行数至少减少一半，需要调用两次，因此总的复杂度不超过元素数量
复杂度$O(n)$