赛事信息
比赛地址：https://codeforces.com/contest/1447
出题人：Meet IT
施工状态：未完成
题目与解答
CF1447A – Add Candies
题意
给定一个长度为n(2\leq n\leq 100)从小到大的自然数数列a_n=n.
求一个正整数m(1\leq m\leq 1000)，表示进行m次操作. 求一个正整数数列b_m，使得对于第j \in [1, m]次操作，将除了a_{b_j}以外的所有数都加上j.
m次操作之后，数列{a_n}中的所有数相等. 求任意一个可行的m和数列{b_m}.
题解
我们考虑刚好有m=n次操作，且每个数能且只能被选择一次。此时对于a_i，得到结果一定为a_i加上等差数列b_m的和1+2+\cdots +m，再减去它被选择的那一次的值j，即：
{a_i}'=i+\sum_{i=1}^{m}i-j
\\
其中b_j=i因此对于任意的n，一定可行的结果为m=n，b_n=n=a_n，最终a_n中的每个数都为\sum_{i=1}^{m}i.
算法时间复杂度\Theta(n)
CF1447B – Numbers Box
题意
给定一个n行m列的矩阵，其中第i行j列的数-100 \leq a_{ij}\leq 100.
你可以进行任意次操作，每次可以选择将两个相邻的（同行或同列；且不同的行或列下标恰好差1）两个数同时取相反数。求矩阵中所有数之和的最大值.
题解
讨论这个问题之前我们其实可以考虑一下在线性代数中学过的逆序数问题。直接交换两个数对于逆序对数目的贡献难以统计时，我们可以考虑不断交换相邻两个数，考虑多次交换相邻两数所得到的结果就是直接交换两个数。
对于此处也是一样的，对于任意两个数，我们都可以通过选择其中一个，连环（每次操作相邻两个数）进行操作直到接触到另外一个数。因此，这个操作实质上是对任意两个数同时取相反数。因此，我们只需要考虑非正数的奇偶性。
因此我们只需要统计正数与负数的个数：
- 当非正数个数得到的值为偶数时，说明所有负数均可以变为正数，答案为所有数的绝对值之和
- 当非正数个数得到的值为奇数时，说明最佳的矩阵中仍然有1个负数，答案为其它数的绝对值之和+矩阵中绝对值最小的数的相反数
算法时间复杂度为\Theta (nm)
CF1447C – Knapsack
题意
给定长度为n的一个正整数数列，一个正整数W表示容量。选择任意一个可行的子列，使得子列之和为C，满足\lceil \frac{W}{2}\rceil \leq C \leq W. 输出子列的长度以及子列中的所有数在原数列当中的下标.
题解
先排序，如果能找到一个数X恰好满足\lceil \frac{W}{2}\rceil \leq X \leq W，则直接输出X.
找不到的话，枚举小于\lceil \frac{W}{2}\rceil的数，扔掉大于W的数.
由于这些数至大为\lceil \frac{W}{2}\rceil - 1，所以不会出现添加一个数导致总和大于W的情况. 因此，在不满足\lceil \frac{W}{2}\rceil \leq C \leq W时依次不断加入数即可.
若最终仍不满足，输出-1即可. 这个过程可以用一个栈/队列/vector等来维护.
算法时间复杂度\Theta(n)