CCPC 2016 杭州站

CCPC2016杭州赛区推出了大中学生对抗赛,于是全场比赛主要看点一是clj封榜前能不能AK,另一个就是看清华学长PK清华学弟。

1001 ArcSoft’s Office Rearrangement

题意

给定a[1..N],可以合并相邻两项或者将一项拆开成两项,问是否能够得到b[1..K]b中每项都相等。

思路

我的错误代码
代码

1002 Bomb

题意

平面上给了n个炸弹,引爆其中的炸弹i需要代价ci,一个炸弹爆炸会使得它半径ri内的炸弹爆炸,以此类推。求使得所有炸弹爆炸需要的最小代价。

思路

强连通缩点,然后找入度为0的所有的联通块,然后在联通块内找一个花费最小的即可。
找联通快和寻找花费最小代价的点可以在tarjan的弹栈操作完成。
特别地,寻找入度为0的所有连通块是通过遍历所有的边然后比较(u,v)是否属于同一联通块实现的实现的。
此外注意引爆具有有向性。
代码

1003 Car

题意

一辆车保持不减速运动(速度为实数),时间从0开始,在某些整数时刻记录下车的位置(整数递增),求最少需要多长时间达到最后一个记录点

思路

这道题目的坑主要是卡精度,求ceil得时候要减去eps=1e-7。或者直接用分数类也能过。
代码

1006 Four Operations

题意

在一个最多20位的整数里面按顺序插入+-*/(整除)四个运算符,要求结果最大。

思路

要注意整数有20位,使用long long
代码