『2013 GDCPC』有为杯 广东ACM省赛小总结

0.00 avg. rating (0% score) - 0 votes
转载请注明: 吹水小镇 | reetsee.com
原文链接地址: http://blog.reetsee.com/archives/39

第一次参加省赛,心情万分激动,我不是大牛,但是在子畦大牛的带领下,刚好排到了校赛的第20名,晋级省赛。

广东的ACM省赛弄得非常好,无论是人员安排还是举办方对参赛队员的照顾,比赛时间是从上午的9点半一直打到下午2点半,持续5个小时,地点是华南农业大学。

我从来对由第三方提供的饮食没有什么信心,所以自己还买了个10大洋的三明治(美心的三明治做得很好……),但是等我看到提供给参赛选手的午餐后我才觉得那个三明治真弱啊。中午大概12点,每位选手会发一袋,对,是一袋午餐,里面有——大牛角包,香蕉(感觉是华农自己种的?因为这条香蕉的味道不太专业),一个三明治(普通面包店能买到的那种,不过量更足),一支华农酸奶,一条Kinder夹心巧克力。不错不错,当然矿泉水是一开始就有提供的。

比赛很好玩,从A~K一共11题,每题对应一个颜色的气球,最对的队伍就会有工作人员在桌子上竖一个气球。对于各题,拿到first blood的队伍还有额外的奖金羡慕

所以参加比赛的感觉就是很快乐,不过这次我们全队发挥失常,这是另外一个伤心的事。好了,还是直接上题目上总结吧,题目是全部英文的,不过我翻译成中文好了

——————————————题目——————————————

*A题:

(前面一大堆描述介绍temple run2这个游戏,然后重点来了)人物每次死后,可以消耗一定量的钻石来使用“Save Me”功能,在没有升级的情况下,同一局中多次使用Save Me将依次消耗1,2,4,8…..个钻石,每升级一次,每次消耗的钻石就减少1个,例如升级一次后,依次消耗1,1,3,7……最少消耗1个。问在升级了M次后,第N次使用Save Me会消耗多少钻石。

最水的题目,直接cout<<(pow(2,N-1)-M)<1?1:(pow(2,N-1)-M)<<endl; 就可以了

**B题:

(前面一堆描述……还画了图,十分具有误导作用,实际概括后就很简单)限定m*n大小的数列,给定K个数,然后对数列可以进行Insert(a),Remove(a),Find(a)操作,执行Insert如果超出数列容量,则把数列中最大的数丢弃,然后插入;Find操作则输出是否存在a即可。

这也是水题,可惜我们在这题上耗费了太多时间,哭大哭,为什么耗费了那么多时间呢,因为这题的数据结构是手敲的……实际直接使用STL的set就可以了,我是在比赛结束后突然间发现傻了。唉,STL啊STL,没想到每次大比赛最会这么败给STL一次。

?C题:

没有看……迟点有空我补上

***?D题:

不好意思……这题太蛋疼了,和编译原理有关,迟点有心情再看题补上

******E题:

有N元(1<=N<=10^18),可以兑换成1,2,5,100,5000,10000元,有多少种将N元完全兑换的方法?最后的结果对1000000007取模。

赛后CYL师兄讲题的时候说这是本次比赛最大的一个坑,因为其题目极其简短,题意极其简单,但是实际上是本次比赛的压轴题。具体的解体方法我来不及记,大概就是把N从大到小分解,然后可以发现一个什么东西,然后用矩阵求幂。下面的,我就不知道了……

***F题:

Alice和Bob的宠物小精灵互相对打,能力值高的精灵赢,每只小精灵只可以出场一次。Alice在每只小精灵赢,平手,输后,分别会获得X,Y元,或者损失Z元。现在给定Alice的先后出场的小精灵的能力值,然后再给出Bob的小精灵能力值(不按出场顺序),问Alice的期望收入是多少元。数据范围:每个人的小精灵数目N相同且范围是(0,100000],X,Y,Z的范围都是(0,1000)。

这题十分捶蛋,不知道为什么就是Wrong Answer,到最后结束也没检查出来,其实就是分别统计Alice每只小精灵的收入期望,然后再把Alice的所有小精灵的收入期望加起来。如果直接使用线性统计每只精灵的期望,那么复杂度将打到O(n^2),会超时,所以要先对Bob的精灵按照能力从小到大排序,复杂度是O(n*log(n)),然后对Alice的每只精灵,再Bob的精灵中用2分查找找到能力值一样的精灵,如果找不到那么也会找到分界点,这样可以快速统计多少只精灵是负于Alice当前的精灵,多少只平手,多少只胜出,然后直接计算即可,复杂度是O(n*log(n))。这样算法总的复杂度也降到了O(n*log(n)),这样就不会超时了。也是水题,可惜就是不知到哪里写错了

****G题:

N堆石子,每堆的数量至少为1,不超过10^18,Alice和Bob轮流取石子,有两种取的方法:1. 只取走1个石头 2. 在这堆石头有2个或以上时,可以取走一半(奇数时取走(N-1)/2,偶数时取走N/2)。给定有N堆石子,每堆的数量ni,问谁会赢。

这题本来是交给子畦做,但是因为没有沟通好,所以写完程序才发现题意理解错了。唉,悲催,时间啊。后来在赛后讲题时发现他们说若只有一堆时如果数目>=2则先手必胜??为什么呢??按照分析应该是找出不安全状态(可以搜索nim问题,或者可以看一下《编程之美》对于nim问题的解答),然后再递推。我今晚再问一下周生这题怎么做,到时再更新。

最新更新:这题问过周生后,周生告诉我查一下SG函数,看一下原论文,就知道了

****H题:

N*M的矩阵里面有若干老鼠,初始情况下每个格子最多1只老鼠,当铃响一次,老鼠就会随机挑一个相邻的格子并跳入其中,如果在同一个格子有x只公鼠,y只母鼠,那么它们会产下min(x,y)只小老鼠(看来是一夫一妻制……),这些小老鼠之后并不会交配产子,即可以把小老鼠当成是无性别的。问经过R次铃响后,小老鼠数量的期望值是多少?数据范围:N,M和R都是[1,10]

这题的数据范围小,不过我们并没有想过这题,也是等我问完周生怎么做,再更新吧。

***I题:

N个节点,M条边的有向无环图,问每个节点可以到达的节点数有多少个(包括自己)。数据范围:N是[1,10000],M是[1,100000]。

用STL的bitset容器

****J题:

给定N和K,整数序列S如果同时满足下面3个条件,那么就称之为沉闷序列:

1. 数列有N个整数

2. 每个整数要么是0,要么是1

3. 同样的数字连续出现K次以上(即K+1或以上次)

例如N=3,K=2,那么111和000都是沉闷序列。计算给定N和K在范围[1,1000]下的沉闷序列数量,最终结果对1007取模。

这题计算时要转换一下思路,首先计算非沉闷序列的数量,然后再用2^n减去非沉默系列的数量即可得到答案。计算非沉闷序列时,需要使用动态规划,后来子畦跟我说这题时,我的感觉就是——丫这动态规划的转移式太秒了,我肯定想不出来,怎么办?子畦语重心长地回答:“靠经验,靠积累吧。”

我们用f[i][j][0]表示到数列的第i个位置(从0开始)连续j个都是0(从(i-j+1)~i)的情况数,f[i][j][1]则是连续j个1,状态转移方程如下:

f[i][j][0] = f[i-1][j-1][0]

f[i][j][1] = f[i-1][j-1][1]

f[i][1][0] = f[i-1][k][1],其中k从1~K

f[i][1][1] = f[i-1][k][0],其中k从1~K

*K题:

给定一个字符集合(全部小写)如{a,e,f,f,g,i,r,q},然后再给定一些单词(全部小写),如:

abacus

deltoid

gaff

giraffe

microphone

reef

qar

要求找出一个单词,其字符全部由字符集合中的字符组成,并且对应的字符出现的次数不超过字符集中该字符出现的次数。如果有多个满足条件的单词,那么找最长的,如果长度一样,则找第一个出现的,这里符号条件的是“giraffe”

非常水的一道题……但是我们wrong answer了7次……算了,不说了。

————————题目完————————

这次比赛,虽然诸多不顺,但是总体来说是开了眼界,也发现了自己算法水平的不足,唯有努力追赶以缩小差距,其实比赛还是非常开心的,而且当你看到一些算法那么精妙的时候(不一定是巧妙),不忍啧啧称赞,哈哈,愿各位算法不太好的同学也多多加油。

发表评论

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