提个建议吧，题目下面能不能加个Note，至少讲下示例是怎么获得的……
就比如说第三题和第四题，我感觉很多人都是不知道算什么东西，输出是什么。像第三题没加数据前根本不知道输出的是什么东西……
2018.3 月赛题解
kblack edited 6 年前
野鸡验题人评价：说好的 Div.2 难度，结果出成了 Div. 1.5。kblack 还是稳啊！
A. 打工是不可能打工的
温暖的签到题，只要按打工收入排序，按收入高的选择即可。注意 $2 \times 10^{10}$ 需要 long long。
kblack’s comment: 有很多奇怪的错误提交都是读错了题意，所以到底是题意不清还是[数据删除]
B. 蛇形矩阵
注意到数字每转一圈后，会一次性增加当前未知部分最上一行和最下一行的和，并将他们之间的行的和加上一个定值，简单归纳一下就可以依次计算这些值，得到答案了。注意答案会达到 $n^3$ 级别，也需要使用 long long。
ultmaster’s comment: 其实是我出的，如果太难了我背锅。这题之前机考出过。因为题目不够，临时拉过来充数的。
C. 劫持选举
首先我们定义 $c_i = a_i - b_i$，$sum = \sum_{i=1}^{n}c_i$，于是我们要做得事情，就是得到一个非空 ${1 , 2, \ldots n}$ 的真子集 $S$，使得 $ 1 \leq \sum_{i \in S} c_i \leq sum-1$，$1 \leq \sum_{i \notin S} c_i \leq sum-1$。
我们可以通过背包构造方案，记 $d_i$ 为达到 $\sum_{j \in S} c_j = i$ 的第一个 $S$ 中的最大元素，枚举 $S$ 即可。背包时可以只遍历有数值的范围，虽然总复杂度看似超过了 $1.6 * 10^8$，实际上跑不到，而且 EOJ 超快哒。:)
好像也有其他更简单的算法可以通过此题，求指教。
ultmaster’s comment: 本题听起来很像是假算法能过的题。卡掉了一些容易想到的假算法。至于其他的，各位可以放心尝试。
D. 笋尖爆炸
我们先解决在数列上加斐波那契数列的操作。注意到斐波那契数列是可加的，即斐波那契数列之间相加仍旧是斐波那契数列，切斐波那契数列可以由他的前两项完全表示（且可加），于是我们就可以把数列的前两项作为懒标记线段树的标记。下方标记时，计算数列的和以及数列第若干项的值（用于构造右区间的标记）的参数，都可以预处理出来（因为最多只会用到 $n$ 项），接下来只要你的线段树正确实现，就没有问题了。
注意到题目并没有保证 $x \leq y$，即可能会从右往左加斐波那契数列，两个方向的斐波那契数列没法统一成一个标记，最简单的处理方式是干脆建两棵线段树，一棵处理 $x \leq y$，一棵处理 $x > y$。
ultmaster’s comment: 最坑爹的地方在于居然是双向的。而且 kblack 起初居然还想去把春笋采走（区间置零）！
kblack’s additional comment: 其实原本是在树上的，路径加数列和子树清零，后来被削了。路径/山路等都是树上版本的遗留物，双向操作也是树上的必须品。
E. 五彩地砖
注意到五彩矩阵最后会有四种形态，即横竖 $2$ 个方向公差为 $1$ 或 $-1$。
你可以枚举形态，之后将整个矩阵膜意义下减去 $x+y$，$x-y$，$y-x$ 或 $-x-y$，此时你就是要计数内部值全部相同的矩阵了。这是一个经典问题，可以使用单调栈来解决。注意到长或宽为 $1$ 的矩阵会被重复计数，所以我们需要在计算时减去他们。
特别要注意在 $c = 1$ 或 $c = 2$ 的时候，五彩矩阵的形态都会塌缩成只有一种，只需要计算一次即可。
本题考虑了某些输入较慢的语言，所以并没有放很大的数据，实际上 $n = 2~000$ 是完全可以处理的，如果因为时限过宽，导致 $n^3$ 被放过，那只能说常数是真的秀QAQ。
ultmaster’s comment: 写起来真的很恶心。谁写谁知道。写完单调栈还不知道对不对。因为你没写容斥。写完容斥之后就只能听天由命了。某验题人一遍过样例，不管了，不管了。。。
恭喜 @gispzjz @illusory @palayutm 获得冠亚季军！
Comments
其实题目已经说得比较清楚了啊？如果第四题你看完题目还看不出要算什么，那很大可能本来就不知道如何解这类题。
第三题的描述可能的确略微简略了点，但验题人们并没有认为不够清楚，只提出样例比较弱（对调试意义不大），下次可以考虑增加一点解释。
第四题我倒是知道啊，在想每次要不要重新置0的问题。WA了就有点顾虑，毕竟题目描述感觉有点少，而且第三题的印象……（抱脸哭
某人的样例太 NB 了。