2015 ACM Amman Collegiate Programming Contest 做题记录


fls说我暑假需要给学弟们找点简单gym做,于是决定锻炼一下自己的代码能力,单挑了一场非常水的gym,然后做的时候各种心累,感觉真是写不完的感觉,主要是卡到了一道全场题,然后找李大爷当小黄鸭才发现了一个傻逼bug,最后也因此没有打成AK目标。不过最后那个题目不给我多点时间我肯定也是想不出来的。。。于是这个post就按照我做题的顺序记录吧。因为题目较短只写做法不写题意了。

A.Who Is The Winner

直接把数据读入,在这个过程中维护答案即可。时间复杂度:\(O(n)\)

 

B. Rock-Paper-Scissors

n的范围很小,考虑暴力枚举。因为出手的情况是三段,所以我们预处理出来每个位置处”剪刀石头布“这三种情况的得分前缀和,然后枚举断点即可。注意断点需要考虑没有某一种操作的情况。时间复杂度:\(O(n^{2})\)

C. Street Lamps

简单贪心,先把所有已知灯能影响到的格子全部标上’*’,那么接下来就贪心即可,出现一个’.’如果它后面紧跟着是’.’方格,那么就选择染后面的那个,因为这样会更优。记录染的次数即可。时间复杂度:\(O(n)\)

D. Alternating Strings

这个题和L一样,但是数据范围不一样。本题中n较小,可以暴力dp。\(dp[i]\)表示前i个数被分成的最小段数。然后根据限制条件转移即可。时间复杂度:\(O(n^{2})\)。

E. Epic Professor

限制加分后不能超过100,所以我们找到一个加分前最大分数即可确定加分,然后扫一遍即可。时间复杂度:\(O(n)\)

F. Travelling Salesman

寻找一棵生成树,使得其最大边最小就是最小瓶颈生成树,也就是最小生成树。时间复杂度可以认为是:\(O(mlogm+n)\)

K. Runtime Error

把数组排序后,把数字和位置组成一个pair插入到一个set里面,然后扫的过程中即可判断是否存在这个数。时间复杂度:\(O(nlogn)\)

J. Candy

确定顺序后贪心选择即可,当同等级的糖果小于当前等级学生时候舍去,否则分配即可。时间复杂度:\(O(nlogn)\)

G. Heavy Coins

状压一下暴力枚举删钱情况进行判断。时间复杂度:\(O(2^{n}*n)\)

H. Bridges

我们需要先求出所有的桥边,显然当一个连通的无向图我们把边双连通分量全部缩成点后,得到了一棵树,这棵树的边都是桥。那么加的那条边一定是直径的两个端点才最优。所以bfs几下就可以了。时间复杂度:\(O(n+m)\)

I. Bahosain and Digits

从大到小枚举操作长度\(K\)和最终结果,然后从左到右进行check即可。时间复杂度:\(O(k*n^{2})\)

L. Alternating Strings II

对于每个字符\(i\)都可以预处理出来一个位置\(len[i]\)表示从这个位置往后均为01交替串直到位置\(i\)。而且转移返程一直需要的都是前面的最大的那个dp值,所以维护一个单调递减的队列即可,状态数\(O(n)\),转移优化到\(O(1)\)。时间复杂度:\(O(n)\)。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注