CSU-ACM Home Page

湖南省第十三届大学生程序设计竞赛解题报告

Update Time: 2017-09-21 18:18:06     Recent Editor: Scanf     Create Time: 2017-09-11 22:14:06     Creator: 741852963    


A. Seating Arrangement

tag: 构造

任意两个相邻编号之差的绝对值都必须大于d,任意的意思实际上就是说行不行取决于最小的编号差,于是我们的目标就是要让最小的编号差最大。到目前为止目标就很明确了,至少有这样两种思路能够比较顺利的找到构造方法:

  1. 我们能够知道,对于任意一个编号而言,相邻的编号差是有一个上界的,两端编号(离1和n比较近的数)的上界比较大,中间的上界比较小,最小的上界就是中间的那一个或两个数了,那么我们会比较好奇这个上界能否达到呢?通过画一画是可以发现这个上界能够达到,那就ok了。

  2. 把3, 4, 5, 6, 7这些情况都画一画,估计就找到规律了。

B.Simplified Blackjack

tag: 枚举

枚举即可,注意Alice不是拿的牌越多越好。

C. Taking Photo

tag: 状态压缩dp

考虑bitmask dp,2^30状态有点多,但发现其实对于只有一个人的组,是可以不用放到状态里的,>=2个人的组<=15个,这样状态数就ok了。

D. Tian Ji's Horse Race Again

tag: 贪心,排序,单调性

首先,换马的策略是比较容易想到的,拿最小速度的马去换最大速度的马,但是这样的话每次换完再统计是O(n^2)。这里的话我们实际可以考虑每匹马对于查询的贡献,这个是存在一个单调性的,即在一匹一匹换的过程中,当一匹马现在可以赢的话,后面一定可以赢。再加上一些细节的考虑之后不难得到一个O(n)的算法,其实仔细想想是跟括号序列的问题很类似的。

E. Directed Chain Decomposition

tag: 树形dp, dp转移优化

这种树上的问题,规模又这么大,基本就是dp了(考虑到树分治其实也是为了dp,为了优化一部分复杂度)。

首先要想到,在一个边方向不改变的树上,怎么计算最少分解成几个链,发现是和sigma|in-out|(出度和入度差的绝对值之和)有关。接着考虑在改变边方向的基础上,最少链的下界,那么就是每个点的出度和入度之差都达到下界,0或者1。

dp的话状态比较容易想,一个是点肯定是状态的一部分,另外就是父边的方向,转移的时候乍一看是一个每个组二选一的分组背包,不过直接背包复杂度就高了,但其实根据前面的分析,这个背包还是比较特殊的,可以用贪心的方式排个序然后贪心选就可以了。

F.Forgot Password

tag: 数据结构,树链剖分,动态树

环基树(n个点n个边,带环的“树”),实际是森林,树链剖分和动态树都可以。直接暴力应该是会超时的。

G. Arithmetic Sequence

tag: 数学,计数,分治

考虑分治,要么在左边统计,要么在右边统计,要么跨区统计,那么只需要考虑跨区的。考虑等差数列的公差,跨区的结果里面公差一定是跨区临界两个元素差的约数,而约数的数量大概是log(n)级别的,所以枚举公差是可以接受的。枚举完公差之后,设计一个高效(因为最后结果可能是n^2级别的)的算法统计数量即可。

H. Finding Words

tag: 字符串,后缀自动机,AC自动机

考虑查询在*号位置断开首位拼接(中间加一个分隔符),字典里的单词也如此,可以转化成带限制长度的子串出现次数查询的问题。如果强制在线,可以上后缀自动机,离线的话AC自动机好搞一些。当然还有很多其他的思路,比如哈希等等,但可能复杂度上没有那么可靠。

I.Nearest Maintenance Point

tag: 最短路,Dijkstra

每次查询都跑一次最短路的代价有点高,要么就考虑优化每次做最短路的代价(确实有比较好想到的优化的余地,但也有可能不难想到针对的措施,或者真的优化的非常好也是可以的),要么就另辟蹊径。

发现可以直接从维修点一起开始跑最短路,这样一次跑完就能知道每个点距离维修点的最短距离了。对于输出结果的话,比较好写的是在Dijkstra状态转移的过程中直接用c++的bitset记录,或者跑完之后,每次查询dfs一下。

J.Monitoring Target

tag: 计算几何,直线/线段交

可以(p,0)和每个障碍物端点连线与路径求交点,这样路径变成了一段一段的,转而去求每一段能否被看到。一种方法是找到段的中点和(p,0)连线,看是否会经过障碍物。

K.Football Training Camp

tag: 贪心,枚举

这个题可以直接去找最大/最小是多少,也可以通过有策略的枚举,然后找到所有情况中的最优解。

最大/最小不难对应到,实际上就是3的场次的多少的问题,如果是最小,就是3的场次尽可能多,那么我们就把每个队都让他能赢尽可能多的场次,但是会发现有可能不行呀,最后的分总和得是偶数,但是这样还是不行,比如剩下2和0就不行,这对应到的一个问题就是不仅需要是偶数,还必须真的能拆成多个1+1。仔细想一下可以发现,如果能拆成多个1+1就必须要最大值<=总和的一半,只要满足这点一定可拆,只要不满足一定不可拆。那么我们就可以得到这样一个找最小的方法:把能减的3都减掉,然后往回加,每次加的时候把3分给当前还有3可以加的点,直到满足两个条件为止,一是和为偶数,二是最大值<=当前总和的一半。找最大类似,有策略的枚举的想法也类似。

下载:2017年湖南省大学生程序设计竞赛标程