2017 ACM女生专场比赛记录

大家好，这里是tiankonguse的公众号(tiankonguse-code)。
tiankonguse曾是一名ACMer，现在是鹅厂视频部门的后台开发。
这里主要记录算法，数学，计算机技术等好玩的东西。

这篇文章从公众号tiankonguse-code自动同步过来。
如果转载请加上署名：公众号tiankonguse-code，并附上公众号二维码，谢谢。

零、背景

今天看到群里说有个ACm比赛，还是女生专场，于是看了看题，记录一下思路。

一、1001 Automatic Judge

题意

告诉你一个规则，根据规则计算出两个答案；1.AC的数量题。2.队伍的罚时。

规则如下：

1. 第一次AC了才算过了。
2. 第一次AC一道题时，这道题的罚时为AC的时间。
3. 第一次AC一道题之前如果失败过，则没失败一次罚时20分钟。

思路

1. 扫描每道题
2. 对于每道题单独统计其是否AC，第一次AC的时间，第一次AC之前失败的次数。
3. 聚合计算：ans = sum(isAC * (firstACTime + 20 * beforAcTryTimes));

二、1002 Building Shops

题意

有一排教学楼，告诉你每个教学楼的位置，以及在这个教学楼建商店的话对应的成本。
对没有建造商店的教学楼，其成本是左边那个教学楼的成本。
求最优成本。

显然，最左边那个教学楼肯定需要建商店啦。

思路

假设题意没理解错误的话，显示是个DP问题。

定义状态：

1. F(i)代表第i个教学楼建造商店时前i个的最优解。
2. f(i)代表前i个教学楼的最优解。

状态转移公式

1. F(i) = val(i) + f(i-1)
2. f(i) = min(F(1) + (i-1)val(1), F(2) + (i-2)val(2), …, F(i-1) + val[i-1])

复杂度：O(n^2)

优化

由于最终每一个教学楼都会存在成本，不过有一个取左边商店最终成本的机会。
所以如果左边的成本更小的话，果断会选择左边的。这就满足单调性了。

从左扫描，如果成本更高，则取左边的。
如果成本变低，则建造成本更低的商店。

这样复杂度就是O(n)。

三 Coprime Sequence

题意

告诉你N个数，求删除一个数可以求得最大GCD。
N可能是100000。

思路

这道题其实很简单，但是想不到这点就很难。
简单的说就是先预处理，得到每个数字左边的GCD和右边的GCD.

1. befor(i)代表前i个数字的GCD, 复杂度O(n*log(n))
2. after(i)代表i之后的数字的GCD. 复杂度O(n*log(n))
3. ans = max(after(2), befor(1)+after(3), ..., befor(n-2)+after(n), befor(n-1));

四、Deleting Edges

题意

告诉你一个图，求最小根树的数量。
好吧，最小根树是我定义的词。
最小根树含义为每个节点到根的距离最短。

思路

和最小生成树数量算法差不多。

关键点如下图：

   0
  / \
 1   2
  \ /
   3

假设dis[0,3] = dis[0,1]+dis[1,3] = dis[0,2]+dis[2,3]
我们就是需要统计每个顶点这样的数量，然后根据乘法原理求出答案。

五、Easy Summation

题意

求ans=1^k + 2^k + ... + n^k得答案。
答案可能很大，需要取模10^9 + 7。

普通思路

由于k最大为5，直接暴力计算即可，复杂度O(n*log(k))。

公式

其实这个可以退出公式的，然后套入公式即可。

拉格朗日插值

几何大神杨晨雨在群里直接说复杂度和k有关,与n无关。
然后没人知道什么提示，然后大神补了一句拉格朗日插值。

拉格朗日插值是什么鬼？我大学数值分析课程挂科了。
我维基百科看了好久，发现原来使用这个东西可以自动算出公式来。
然后直接把n套入公式即可。

六、Forgiveness

题意

判断一个串是否是另一个串的子串时有KMP算法和KM算法。
这里允许一个子串有三个位置不同，我们称为为3位子串吧。
然后给你一个串S和m个操作。

操作1为对串S的l到r位置加k, 操作2为询问S[l,r]子串中有多少个T的3位子串。
S长度50000， 操作个数50000个。

思路

不会做。

七、Graph Theory

题意

有N个点，然后告诉你两个规则组成一个图。
判断图是否可以组成完全二分图。

完全二分图含义为挑一些边，边的顶点没有重复的，且恰好覆盖所有顶点。

规则1是i节点与左边所有节点没边。
规则2是i节点与左边所有节点没边。

思路

由于规则固定，所以图固定了。
但是由于节点可能太多，我们不能模拟算出图，然后使用对应算法是否是匹配的。

规则有个特点就特点就是是否和左边的所有节点有边。
所以这道题的突破口就在这里，我们从右逆着来推这道题。

1. 节点数为奇数，则不存在完全二分匹配。
2. 从右到左扫描。
3. 累计规则1的个数，遇到规则2则个数减一。
4. 不够减则不存在完全二分匹配。

八、Happy Necklace

题意

有一个带两个颜色的珠子串，在任意连续素数个子串中红珠的数目不小于蓝色的。
求满足这样的串数量。

思路

起初我把题意理解为珠子为多个素数子串之和，然后就没思路了。
看清题意后，发现就是一个普通的DP问题。

由于2和3就是素数，这两个素数就可以组成其他素数了。
由于这两个素数都，满足条件，所以组合也满足条件。
所以我们只需要考虑素数2和素数3即可。

素数2可以推出任意连续两个珠子必有一个红色珠子。
素数3可以推出任意连续三个珠子必有两个红色珠子。

于是我们可以定义状态和状态转移公式。

状态定义：f(n)代表长度为n的串的答案。

假设第n个位置为蓝色，则第n-1和n-2位置必须为红色。
假设第n个位置为红色，则前面的随意。

所以状态转移公式为：f(n) = f(n-3) + f(n-1)。
由于n比较大， 所以这个需要使用矩阵幂快速运算。

九、Innumerable Ancestors

题意

告诉你一个树，然后两个集合。
求在两个集合里分别取两个点，可以求出两个点的最近公共祖先(LCA).
这里需要求树高度最深的公共组件。

思路

基本思路是暴力计算。

1. 求出所有节点高度。
2. 求出A集合的所有点到根节点路径上的节点 O(n)
3. 求出B集合所有节点到根节点路径的节点 O(n)
4. 求交集，取高度max O(n)

当然这个方法需要O(n)的复杂度，可能会超时。

群里说可以使用树链刨分来做，这个我还不会，所以就不多说了。

十、Judicious Strategy

没看这道题。

十一、结语

好了，看到这里就记录完了。

对了现在开通了公众号和小密圈。
博客记录所有内容。
技术含量最高的文章放在公众号发布。
比较好玩的算法放在小密圈发布。
小密圈这周接受免费加入，欢迎大家加入看各种算法的思路。

长按图片关注公众号，接受最新文章消息。