2018.3 月赛题解

kblack edited 2 年,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$,$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

Master X

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

kblack

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

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

Master X

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

ultmaster

某人的样例太 NB 了。

palayutm

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

palayutm

还是我眼花好了= =

ultmaster

欢迎检查代码:链接

palayutm

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

kblack

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

GFZRZK

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

kblack

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

kblack

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

祝好(^_^)

你当前正在回复 博客/题目
存在问题!