2018.3 月赛题解

kblack edited 7 年前

野鸡验题人评价：说好的 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}$ ， $s u m = \sum_{i = 1}^{n} c_{i}$ ，于是我们要做得事情，就是得到一个非空 $1, 2, \dots n$ 的真子集 $S$ ，使得 $1 \leq \sum_{i \in S} c_{i} \leq s u m - 1$ ， $1 \leq \sum_{i \notin S} c_{i} \leq s u m - 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 获得冠亚季军！

12 0

Master X

7 年前

提个建议吧，题目下面能不能加个Note，至少讲下示例是怎么获得的……
就比如说第三题和第四题，我感觉很多人都是不知道算什么东西，输出是什么。像第三题没加数据前根本不知道输出的是什么东西……

回复 2 0

kblack

7 年前

其实题目已经说得比较清楚了啊？如果第四题你看完题目还看不出要算什么，那很大可能本来就不知道如何解这类题。

第三题的描述可能的确略微简略了点，但验题人们并没有认为不够清楚，只提出样例比较弱（对调试意义不大），下次可以考虑增加一点解释。

回复 2 0

Master X

7 年前

第四题我倒是知道啊，在想每次要不要重新置0的问题。WA了就有点顾虑，毕竟题目描述感觉有点少，而且第三题的印象……（抱脸哭

回复 0 0

ultmaster

7 年前

某人的样例太 NB 了。

回复 0 0

GFZRZK

7 年前

大佬请问有地方下数据吗。。T4 test32line200多的地方错了好难受啊调不来–。。。

回复 0 0

kblack

7 年前

可以透露一下，这是第一组规模达到 6e4 的，之前都在 1e4 以下

回复 0 0

kblack

7 年前

线段树就是这样的啊，推荐好好检查标记下放，和各种地方取摸是否有遗漏吧，或者拿暴力对拍一下，做 bzoj 3064 的时候，我也是这么调过来的。

祝好(^_^)

回复 0 0

palayutm

7 年前

咋重交一次还减分了，还是我眼花了

回复 0 0

palayutm

7 年前

还是我眼花好了= =

回复 1 0

ultmaster

7 年前

欢迎检查代码：链接

回复 0 0

palayutm

7 年前

没，我是说standing页，好像又交了一次后分变少了，是不是按最后一次通过时间算分的

回复 0 0

kblack

7 年前

有两台评测机，其中一台稍快一点，时间在边界的时候可能会鬼畜

回复 0 0

A. 打工是不可能打工的

B. 蛇形矩阵

C. 劫持选举

D. 笋尖爆炸

E. 五彩地砖

Comments

服务

开源

关于我们