第一年参加省赛，也是我接触acm半年多的第一个正式省级赛事，这半年来我为acm付出的可能很多，但经历过这次省赛后，给我唯一的感觉就是，还不够多。
& & &直接分析题目吧，开始拿到试题后我读的是A题，然后我的队友好像是开始读BC，我读完A题就确定这是一道水题，然后没多加分析就开始写了，中间过程有很多的差错，导致我们差不多30多分钟才2A了这道水题，之前的一次WA是因为少输出了一个#号……。总而言之还是不太习惯这种大赛场面，由于被各种高校包围，所以我们全场基本都是在吵杂的讨论声度过的，导致读题及其难以专心。在这也要提到的是一个英语的问题，其实在我们队可能英语我可能要负担的更多，但这次比赛之前由于我做的英语题题目数量还是远远不够多，所以导致我在比赛过程读题极其不顺利，耽搁了很多做题的时间。然后xh0告诉我B题是一个简单的搜索，也清楚的告诉了我题意，让我去写。但我写着写着，发现这道题并没有那么简单，再看下榜，发现一个A的都没有，赶紧放下题目，看榜发现有人A了G,E,L，然后我就去攻读L，把E留给xh，把G留给hx。后来hx也不负众望地在87分钟成功通过了G题。这时候我们其实心态是有点浮躁的，因为看了下周围，发现大部分都是2-3题，所以就有点飘了，导致我看L题看了大概半个多小时都看不懂它究竟要干什么，而我的队友也跟我一样没有太大的进展。之后我不断地去看用例和深挖L题的一些字眼，终于大概蒙出了题意（而赛后证明我蒙错了一个点，英语一定要好好复习啊！！！），然后把题意告诉了hx，让他去打，然后我继续看一道AC人数较多的J题。而xh还在执着那道B题，其实我告诉他这道没人A的可以放一下，但是他还是坚持他可以。大概过了差不多1个多小时，华农的举办方每人发了一份快餐，吃饱喝足后（经教练提醒后，比赛是千万不能吃东西的！！！！！！！，而且进入做题状态也不应该吃多西，这次算是一个大失误），因为L题hx用了自己不熟悉的c++，导致整个程序一直出错却找不到错误，而我也一直在纠结J的题意，xh也放弃了B转向E，其实E我看了下是可以做的，只是数据规模太大导致这道题难度上升了好多好多。到了比赛结束前一个小时，我基本摸清了J题题意，发现有点麻烦，就选择放弃了，然后xh一直在纠结E题，hx用C把原来C++的代码重新改回来了，但依然不能顺利地运行。剩下的时间我们就基本是把希望寄托在L题上了，因为看了下榜3题就能有铜，但很遗憾地是到最后还是不能A（原因是代码没实现好，其实最根本的原因是我弄错了题意的一个点），但我坚信如果我们能做快点这题是完全可以后期debug然后A掉的。其实我们参赛就没想过奖，但是这次还是让我们触摸到了那种拿奖的喜悦与兴奋，但同时也暴露出了很多很多我们队的缺点和问题，下面我总结一下吧。
&&&&&&&& 1.英语能力还不足以顺利阅读题目，导致我们很多时候卡读题很久，日后必定要多做英文题目，多积累生词，这是程序设计竞赛，英语不能成为绊脚石。
&&&&&&&& 2.对于坐在我们隔壁华农的一支队，他们应该是16的，他们其实A,G题A的比我们还慢，但是最后他们顺利A出了L而我们却失败了。其实对于同样是16的接触acm半年的其他高校新生，我们是有信心能平起平坐的，但是这场比赛却拉开了差距，据我观察主要是他们团队协作的更好，更多地交流和分工，其实我觉得最好的团队合作模式，应该是一人打题，另外两人读题和讨论，但是在我们现在这个阶段其实很难做到，希望以后能通过各种各样的模拟赛来做到这一点。
&&&&&&&& 3.比赛环境对我们自身其实不应该有这么大的影响，无论别人做了多少，拿了多少气球，都不是自己的。而且只要更加专心地看题，就不会被周围的环境影响。比赛结束后的那一晚，我整整看了一晚题，其实专心地那种状态看题是更加容易了，我在反思为什么自己比赛进入不了那种状态，还是一个抗干扰能力需要锻炼的问题。
&&&&&&&& 4.平时的锻炼还不够拼，对于一个ZQU的学生，我认为是可以有更多地时间放在ACM上的，我回来看完题后发现我们做的实在是太慢了，虽有读题的问题，但是打题也是很慢很慢，所以我坚定要加大训练的决心，我们觉得在暑假之前，可以把部分刘汝佳紫书的题目刷完，然后在平时的星期三下午可以刷CF加强一下团队合作的训练，暑假是一个跃升的机会，但暑假之前的这段时间也是稳步上升的契机。趁热打铁，有了这次省赛的经验和投入，我觉得集训队在训练上会做得越来越好！
& & & 虽然这次省赛目标不是奖，但以后比赛的追求必将越来越高，如果说这次是一次遗憾，那么我希望下次能拼个无怨无悔。对于acm，只有怀着持续长久的热情，我觉得才有机会坚持下去，对于没有这种体验的人，其实离开也不一定是坏事。再附上CLJ的一句话，成功的路并不拥挤，因为大部分人都在颓?。
阅读(...) 评论()2017 ACM女生专场比赛记录 - 推酷
2017 ACM女生专场比赛记录
作者: tiankonguse | 更新日期:
今天看到群里说有个比赛，于是看了看题，记录一下思路。
大家好，这里是tiankonguse的公众号(tiankonguse-code)。
tiankonguse曾是一名ACMer，现在是鹅厂视频部门的后台开发。
这里主要记录算法，数学，计算机技术等好玩的东西。
这篇文章从公众号
自动同步过来。
如果转载请加上署名：公众号tiankonguse-code，并附上公众号二维码，谢谢。
今天看到群里说有个ACm比赛，还是女生专场，于是看了看题，记录一下思路。
一、1001 Automatic Judge
告诉你一个规则，根据规则计算出两个答案；1.AC的数量题。2.队伍的罚时。
规则如下：
第一次AC了才算过了。
第一次AC一道题时，这道题的罚时为AC的时间。
第一次AC一道题之前如果失败过，则没失败一次罚时20分钟。
扫描每道题
对于每道题单独统计其是否AC，第一次AC的时间，第一次AC之前失败的次数。
聚合计算：ans = sum(isAC * (firstACTime + 20 * beforAcTryTimes));
二、1002 Building Shops
有一排教学楼，告诉你每个教学楼的位置，以及在这个教学楼建商店的话对应的成本。
对没有建造商店的教学楼，其成本是左边那个教学楼的成本。
求最优成本。
显然，最左边那个教学楼肯定需要建商店啦。
假设题意没理解错误的话，显示是个DP问题。
定义状态：
F(i)代表第i个教学楼建造商店时前i个的最优解。
f(i)代表前i个教学楼的最优解。
状态转移公式
F(i) = val(i) + f(i-1)
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.
befor(i)代表前i个数字的GCD, 复杂度 O(n*log(n))
after(i)代表i之后的数字的GCD. 复杂度 O(n*log(n))
ans = max(after(2), befor(1)+after(3), ..., befor(n-2)+after(n), befor(n-1)) ;
四、Deleting Edges
告诉你一个图，求最小根树的数量。
好吧，最小根树是我定义的词。
最小根树含义为每个节点到根的距离最短。
和最小生成树数量算法差不多。
关键点如下图：
假设 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则个数减一。
不够减则不存在完全二分匹配。
八、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).
这里需要求树高度最深的公共组件。
基本思路是暴力计算。
求出所有节点高度。
求出A集合的所有点到根节点路径上的节点 O(n)
求出B集合所有节点到根节点路径的节点 O(n)
求交集，取高度max O(n)
当然这个方法需要 O(n) 的复杂度，可能会超时。
群里说可以使用树链刨分来做，这个我还不会，所以就不多说了。
十、Judicious Strategy
没看这道题。
十一、结语
好了，看到这里就记录完了。
对了现在开通了公众号和小密圈。
博客记录所有内容。
技术含量最高的文章放在公众号发布。
比较好玩的算法放在
小密圈这周接受免费加入，欢迎大家加入看各种算法的思路。
长按图片关注公众号，接受最新文章消息。
已发表评论数()
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见
正文不准确
标题不准确
排版有问题
主题不准确
没有分页内容
图片无法显示
视频无法显示
与原文不一致你正在使用的浏览器版本过低，将不能正常浏览和使用知乎。