第六届山东省ACM总结

拖了好久才写这份总结,中间考试,聚会,等等都推迟了这事儿。写的过程中一度想要不写了,可能是觉得结果有些不尽人意吧。

赛程

早上6点多起床,然后吃了个早饭,大概7点钟出发,路上前面的两位都在听歌,我因为耳机找不到,也没有下电影,思想神游了4个小时,也是挺佩服自己的 — 或者是刷微博?

到了以后大体上逛了下山科的校园,挺大,环境也不错,但是明显能够感觉出年轻,没有岁月的味道,心情一直是比较平静的。下午热身赛,没有特别出彩,已经不记得当时在个什么名次上 — 反正也不是很重要= =

然后就是正式比赛,拿了铜牌。

不想空洞的描述这场比赛,还是随意一点,然后再简单整理一下吧。

比赛之前的晚上发现自己博弈部分没有掌握好,图论部分也是没有完全看完重点,但是因为第五届的比赛的原因,觉得无妨,图论题目应该出了也做不出来(的确,没做出来,笑),博弈因为去年有一个(后来想到可能是记错了),所以也是没有很在意,觉得应该不至于不幸的一次就搞到我不擅长的地方吧!

结果正式比赛正好考到博弈和图论,博弈费了好些力才推理出来,图论一开始搞错了题目的意思,最后分析题目计算时间复杂度的时候就已经发现可能超时间,但是没有找出合理的办法 — 其实在当时看看,也的确应该是去试试,因为感觉可能比较简单,AC的人并不少。

当然赛后发现如果有那个知识,那么这道题目还是比较简单的,哈哈。

GH题目就是比较简单的质因子分解+哈希,但是糟糕的是当时虽然想到质因子分解,但是没有具体的细想,去探究,深度不够。 — 也是因为受了之前比赛的影响,很多时候因为我自己想得太深方向还不对结果浪费了时间。

总结

ACM – 浙江省赛F – 图论

  • 浙江省赛题目,分析后直接暴力即可,奈何场上脑子里全是floyd,WA无数次。

  • 做题一定要先分析时间复杂问题,采取暴力方法,然后再考虑复杂问题解决方法。

  • 此外今天开始使用赛用vimrc才发现出现不少问题,还好提前使用了。

ACM – Uva10047 – 图论

隐式图搜索,多个状态然后减枝。。没看懂李大大所说可以承受是个啥意思。。

做起来实在太累了。。减枝的部分看了别人的代码,发现着实麻烦,不如用优先队列来的痛快=- =还有用优先队列做的= =

主要是$vis[x][y][p][c]$这组状态比较难搞,但是给了优先级(时间短的先出队),事情就好办了。

ACM – Uva10054 – 欧拉回路

问能不能拼接一条项链,条件是首尾相同构成环。

这个题的坑在:

  1. 虽然保证连通,但是不一定每个颜色都有,所以单纯的暴力euler(1)是很愚蠢的。

  2. 题目本身是要求顺序输出的,也就是dfs不能回溯,如果回溯,为了保证准确性,需要交换uv的位置来保证。

  3. 通过统计出度入度判断是否满足欧拉回路。

灭火

火会蔓延,人被火追着跑,能否跑出边界的问题。

bfs火之后bfs人,或火和人放在一个队列里面bfs

坑是没有火的情况,如果从0更新火势图而不是inf开始,那么可能造成没火不能跑的情况。

ACM – Uva10294 – 置换

项链和手镯。

项链的问题在于不可以翻转,因此少了一种置换,而手镯则可以反转。然后我们计算旋转的置换。

旋转的步长可以是0,i,2i…然后我们可以得出循环一共有n/gcd(i,n)个元素,因此,我们可以计算出一共有gcd(i,n)个循环。则不定点的个数为

$a = \Sigma t^{gcd(i,n)}$。

翻转。翻转奇数情况和偶数情况是不一样的,因为奇数情况会多一个不定点,这个不定点就是在轴上的点。剩余的不定点的个数就是$n/2$,总共不定点的个数就是$nt^{(n+1)/2}$。偶数的情况下,如果正好切在两个珠子上,那么循环长度为2的点有$n/2-1$个,长度为1的循环有2个,所以总共$n/2+1$个。如果没有切在珠子上,不定点的个数为$n/2$,和为$b = n/2*(t^{n/2+1} + t^{n/2})$。

然后我们可以计算出项链的个数$a/n$,手镯的个数$(a+b)/2n$

列出式子以后代码就方便了。记得求pow的时候可以顺手打表

ACM – 置换

终于搞明白置换了,可喜可贺。建议不要看屈的离散数学,看白书即可,通俗易懂。

我在这里简单阐述一下,当然也是依据李大大的书。

置换

置换就是把n个元素全排列,置换可以定义乘法。

循环就是置换的移位。例如:

1 2 3 4 5
3 5 1 4 2

即为(1 3)(2 5)(4)

其中,(1 3)通过这个置换发现形成一个循环,(2 5)通过这个置换形成一个循环,(4)本身构成一个循环。

不动点

对于一个置换f,若一个着色方案s经过置换后不变,则称s为f的不动点,将f的不动点记录为C(f),则可证明等价类数目为所有C(f)的平均值,成为Burnside引理。

Polya定理

一般的,如果f分解成m(f)个循环的乘积,那么每个循环的所有格子的颜色必须相同。(因为这样才是一个不动点)。

假设涂k种颜色,则有

$$C(f) = k^{m(f)}$$

(乘法原理。循环内相同,循环间可以不同)。

代入Burnside引理之后得到Polya定理:等价类的个数等于所有置换f的$k^{m(f)}$的平均数。

ACM – UVa10023 – 开平方

本题目计算开根号数字,给出Y求X。X = sqrt(Y),主要问题在Y的超大数据。

时间限制是3s。我使用的大数模板中没有一个大数除大数的算法,因此直接借用Java来搞一搞。

利用公式$$(5/x+x)/2 = x$$递归逼近求解。这个公式比较好推,移项即可。

参考他人代码,不需要用set,直接判断是否和前一个相等即可= =。

再一个就是模拟手算。手算法有些麻烦。。注意第二个除数开始余数*20即可。

ACM – Uva10105 – 组合数

基本上是组合数裸题。。

给出$(x_1+x_2+x_3….x_k)^n$,要求计算$x_1^{n_1}x_2^{n_2}…x_k^{n_k}$的系数。

思想就是从一个算式中取出$n_k$,即$C_n^{n_k}$,然后减去$n_k$,如果直接相乘则会重复。

ACM – UVA10308 – 无根树转有根树

比较莫名奇妙的题目,明明是搜索题目居然放在了数学分类,完全找不到数学的影子。。

利用vector,遍历树,找出最大的子树路径,然后与次大的子树路径相加即为答案。

因为图表示这方面太渣,基本上抄袭了别人的代码= =