CCPC2016 杭州站

A.ArcSoft’s Office Rearrangement

题目
题意:给n个数,每次可以选择相邻的两个数合并,或者把一个数拆成任意两部分,任务是把这n个数变成相等的k个数,问最小操作次数。

重组之后每个数的大小是x=sum/n,从左到右枚举每个数,如果比x大就一直分,直到比x小,将这一部分并到右边。

B.Bomb

题目
题意:n个炸弹,坐标(x_i, y_i) ,每个炸弹有一个爆炸半径和引爆花费,可以连锁爆,问引爆所有炸弹最小花费。

如果i能炸到j,就连一条i->j的边,然后tarjan缩点,缩点之后的权值为强联通分量里的点的最小花费,最后答案就是缩点之后的图中没有入度的点的权值和。

C.Car

题目
题意:一辆车从0开始沿x轴正方向走且速度不减。有n个检查点坐标为正整数,已知这辆车到达这n个检查点的时间都是整数,问到达第n个检查点时的最短时间。

贪心,第n-1个检查点到第n个检查点一定走了一秒,然后倒着往前考虑,v[i]表示i到i+1段的速度(注意速度不一定是整数),s[i]表示从i到i+1的路程,t[i]表示i到i+1的时间,如果s[i]%v[i+1]==0则t[i]=s[i]/v[i+1] ,否则t[i]= \lfloor s[i]/v[i+1] \rfloor+1 为避免精度误差用分数计算。

D.Difference

题目
题意:看上面链接。

最后答案最大差不多有10^10,因此先预处理前五位,然后枚举后五位。

E.Equation

题目
题意:形如a+b=c,a,b,c都是1-9的整数的等式一共有36个,给你1-9这9个数字用了多少次,问最多能从这36个等式中选几个。(1+2=3和2+1=3是不同的)。

总之就是各种奇怪姿势的剪枝。

F.Four Operations

题目
分成两部分,即(a+b)-(c*d/e)。枚举减号的位置,右边显然要e尽可能长,左边则是a只有一位或b只有一位,这两种取较大的。

I.Inequality

出题人题解
仍然搞不懂为什么只有一个全局极小值。

J.Just a Math Problem

题解

K.Kingdom of Obsession

首先,如果[1,n]和[s+1,s+n]有重叠部分([n+1,s]),那么[n+1,s]中的元素一定保持不动,然后去除重叠部分。此时如果区间内有两个或以上的质数则一定不满足,因为质数只能放在1的位置。而两个质数不会相隔太远,所以如果此时满足条件,则s一定不会太大,所以就可以直接算匹配了。

发表评论