CCPC2016 杭州解题报告

Posted on By 二价氢

A. ArcSoft’s Office Rearrangement

Tag: 贪心

给定一列数,要把它分成K个大小相等的堆,每次可以

  1. 合并两个相邻的堆
  2. 将一个堆拆成两个,大小自定

解法

Code

贪心,从第一个开始,如果这堆的大小跟目标的大小相等,则跳过

如果它的大小大于目标大小,则将它拆成两堆

如果它的大小小于目标大小,则将它并到下一堆里

B. Bomb

Tag: 图论

平面上有1000个炸弹,需要被全部引爆,引爆第i个炸弹需要的代价,同时会引爆半径以内的所有炸弹。

问引爆所有炸弹需要多少代价

解法

Code

强联通分量缩点后变成DAG,显然此时选择所有入度为0的炸弹最优

C. Car

Tag: 贪心

一条线段上分成了n个区间,通过每个区间的时间为整数,同时通过前面的区间的速度不大于通过后面区间的速度。求通过整个线段的最短时间。

解法

Code

显然,通过最后一个区间的时间为1个单位

通过第个区间的最短时间为

其中,表示第i个区间的长度

D. Difference

Tag: 折半查找

设函数的各位数的次方的和,设,给定,求满足的x的个数,其中

解法

注意到,所以猜想x的范围不会超过,将x拆成两部分,预处理后枚举前面一半就可以确定后面一半

复杂度

Code

E. Equation

Tag: 搜索

给定个数字,和无数的加号与等号,求可以组成的9以内的不同的加减法的个数,加数有序

解法

手头枚举一下,不难发现,答案绝对不会超过36,考虑搜索+剪枝

实际上,搜索+剪枝可以恰好在时限以内通过此题,大约在950毫秒左右,这样的复杂度不超过,如果是在比赛时,这样没有问题

考虑优化复杂度,我们可以归类,注意到是不一样的,但是它们用的数字完全相同,所以可以将其合并,复杂度变为,其中,大概就变成了前者的1/50左右,对于此题是完全没有问题的

本题的作者给出的做法是在此基础上,将这样的等式再提出来,放在最后贪心处理,这的等式有8个,这样复杂度就变成了,其中,这样之后,即使全部枚举,也只需要不超过150万次,完全没有问题

在实际测试中,枚举+剪枝比出题人的方法快一些

Code

F. Four Operations

Tag: 贪心

给定一个长度不超过20的,仅包含1-9的字符串,要求在其中按顺序添加+-*/四个符号,使得表达式的结果最大。

解法

考虑到四个符号的优先级,最后的A*B/C的结果是越小越好,那么AB显然是一位数

然后枚举加号、减号和除号的位置就好,这个复杂度是的,但是常数小,所以没有被卡掉。

正解是在这个基础上,如果最后的表达式为A+B-C*D/E的话,AB必有一个是一位数,E最多是两位数,这样答案就只有4种,复杂度大概在20^2这个数量级上

代码

(待写题解)

G. Game of Eliminate

(待写题解)

H. Hazy String

(待写题解)

I. Inequality

(待写题解)

J. Just a Math Problem

(待写题解)

K. Kingdom of Obsession

给定,求一个的双射,且满足,只需要回答该映射是否存在。

解法

首先,一个最显然的结论是,直接映射到就好。

第二个显然的结论是,如果在之间有两个质数,那么显然答案不存在。

因而,注意下面这个式子:

通过这个式子,推出结论:如果一个连续区间内只有一个质数,那么这个区间不会太长,即不太大。

综合以上三点,当比较大的时候,直接输出不可能即可

否则,将直接映射到之后,对剩下的数暴力匹配就好。

本题的关键在于,通过能够得出“如果一个连续区间内只有一个质数,那么这个区间不会太长,即不太大”这一重要结论。

Code