ACM-ICPC2018江苏邀请赛总结

虽然是没人权的邀请赛,不过也算是完成了第一次ICPC的比赛了吧(现在回忆起来第一次ACM比赛应该归宿到中学某次OI的夏令营,当时还是和CJR和CH组的队,甚至机房的裁判还是中学机房的学长,时间一晃过去了好多年了)这次在徐州的邀请赛我和wgy和zmy一起组成「老年吃饭党」的一只老年队,和另一组17级的学弟出来比赛了。之前我们仨曾一起去福州打过CCSP(突然想起来学校的奖金还没到,雾)我和w也想通过这次邀请赛体验一下与dalao们的差距


邀请赛的分割线

A题签到题,B题是求A的子串中有多少是B的前缀子串,my用后缀自动机直接A了,赛后发现直接用扩展KMP也可以做的。C题是求边界和最大的自边界的值,乍一看n<=1000很吓人,但是题目有一个很强的条件就是非0的个数至多为100,那么我们就可以枚举行列的位置,然后预处理求出四条边的前缀和,时间复杂度是O(100^4)。邀请赛结束之后,my也和我说了O(100^3)做法,比如说当左右的两列的位置确定的时候,此时我们来选择移动上下的两行时,这个答案是具有单调性的,即不管上面的一行在哪,总可以确定住下面的最优的一行在哪(画图显然可得),然后我们就只要扫两次就行了。D题是一道物理题,基尔霍夫定律模板题。当时我和w写了一个比较大的例子,试了这个例子好像不太对,但还是交了没想到1A了(哭笑不得) 然后就开始日常测环境准备溜了。邀请赛我们打得不错,估计在前五的位置。也为第二天的小翻车做好了铺垫


正式赛的分割线

[latexpage]

D题很easy,就是一个组合数求模的乘积。预处理阶乘和其逆元就好。

A题本身是签到题。题意是二维矩阵上有k(<=10)个起点,每次向周围扩散一格,求哪 个格子最后被扩展到。当时我们一致认为,这个不就是bfs一遍嘛?然后我们队就疯狂T。以为是vector慢,又以为是pair慢各种等等,然后看到榜过了一大半,my索性直接每个点来个判断,咦过了?5发T后你给我看的就是这个。局部性原理这么牛逼的吗(赛后我们认为最内层的k比较小,因此cache命中率很高,因此时效会好,这一点比卡常数会有效的多)一上来就遭遇此等变故,一开始着实有点怕。

K题,求一颗生成树,使得每个点到原点的最短距离不变,求方 案数。据说和去年女生赛D题的题很像,我看了下确实几乎一样,思路都是找可以替代的上一个节点个数然后乘起来。这个题呢,主需要先计算出每个点到原点的最短距离。然后对于任意一个非原点,考虑给其选择一个父亲,使得父亲到原点
的距离+两点距离=自己到原点距离。每个点的可能的父亲数量的 乘积就是答案。

J题答案就是(n+1)!-1,高精度就好了。

B题的题目是问你1~n的所有排列中有多少种排列拥有k对逆序数。我们考虑f[i][j]代表长度为i的排列有j对逆序数的方案数。然后如果前i-1个数已经填好,那么如果此时j放在最右边,那么不会产生新的逆序数;如果放在最左边,则会产生i-1的逆序数。所以状态转移方程为:

$$f[i][j] = \sum_{x=0}^{i-1} f[i-1][j-x] $$

另外由于出题人对于PC^2的新操作,使得空间限制在64M内,不能开5000*5000的long long(我们因此MLE了一发)。所以需要把询问离线下来,然后用滚动数组求解同时离线答案。

I题的递推关系式就是计算dp[i][j]=max(dp[i-1][k]+f[k][j])。然后由于n很大(数据范围是2 ≤ N≤ 100000, 1 ≤ M≤ 100),所以我们不能直接用O(n^2)的做法。回忆一下矩阵快速幂的操作,在这里如果我们把max想象成矩阵的+,+想象成矩阵的乘。(满足矩阵乘法的原因是因为max和加满足结合率的)所以直接就是读入的矩阵的n次方,其中乘法被我们重载了一下。

G题的题意是有一个长度为n的序列,长度为m的划窗,计算每次划窗内 的乘积的求和。关于滑动窗的这篇博客讲得不错。在我看来核心就是要抓住充分利用之前的信息并在合适的时间弹出之后不需要的信息。在这个题里面我们遇到的麻烦是除法遇到取模且不是质数比较麻烦。我们这样看这个问题,每个长度m的段的乘积都相当于前面一段的末尾乘上当前在更新的。比如我们举m=3为例,我们每到m的倍数就计算之前的一段m的后缀乘积。那么对于i=6,直接用1suffix[6];计算i=7,用a[7]suffix[5];计算i=8,用a[8]a[7]suffix[4]。以此类推。因为每一个数最多被一段后缀所计算到,所以时间复杂度是O(n)。当时还出了一个状况就是题目有个非常sb的地方就是中间的每一步要取模但是最后一步没说取模,我们被坑了很久、各种对拍都是一样的,还好最终发现了。不知道这个题目最终全场只有5个人过是不是也有人卡在了这里。

F题是我们这场比赛的失败点。在我们片名前的队伍都过了。题意是给一棵(片)森林,求有多少三元组(x,y,z)满足f[y]>f[x]且 f[y]>f[z]且x是y的祖先,y是z的祖先。很显然的是也就是求每个点有多少它的祖先的值比它小,有多少子孙的值比它小。看到这个题我最初的想法就是直接构造树状数组统计个数。但是怎么处理第二问当时没想出来(这个时候已经下午了,感觉思维很乱)w说用平衡树应该可以搞,我也没继续想树状数组的细节(又是自己的败笔)之后看到榜前面刷刷刷的过F,我们的做法相对要调试的比较多而且遇到了C::B过度优化的坑,总之最后一直卡在卡在这里也没交。比赛完后看到群里说到做法就是树状数组,然后发现第二问也不难求。我们只要先把dfs序记录一下然后再按照这个dfs序来增删就能求了。标程的做法可能更为简单一小点。就说一下子孙节点小的吧。这个充分利用在当前dfs的时候,我们可以在执行它的子孙之前先求一波,然后执行后再求一波,用两者的值相减就可以了。

E题的题意是二维矩阵,从左上角走到右下角,求两条路径不相交的方案数。第一反应是DP,但是不满足最优子结构,推不出状态转移方程。当时在现场也有想到只要考虑起点是往右还是往下,终点是从上还是左来的,但是还是没有想到标解。标解是这样的:考虑从A1(1,2)走到B1(n-1,m)和从A2(2,1)走到B2(n,m-1), S(x,y)为x到y的方案数,由容斥可得答案为 S(A1,B1)S(A2,B2)-S(A1,B2)S(A2,B1)。这个是怎么一回事呢,我们想一下什么样的情况是我们所排除的。如下图,图1是我们从A1(1,2)走到B2(n, m-1)的一条路径和A2->B1的两条路径,这个是不符合题意的,因为它们显然是相交的了。那么我们怎么剔除掉这种情况呢?我们把从两条路径相交交点后的路径交换一下行程图2。这是从A1->B1和A2->B2的路径。发现端倪了吗?我们只需要把两者相减就可以求出所有的情况。知道了答案的式子后,题目就迎刃而解了。从(1,1)到(n,m)的方案数是 $C_{n+m}^{m}$ 所以就可以直接求出来了。由于阶乘可以预处理,所以时间复杂度O(n).

《ACM-ICPC2018江苏邀请赛总结》

一种路径相交的例子

《ACM-ICPC2018江苏邀请赛总结》

转化后的例子

剩下的H题(数学题)据说是近年来的一个ICPC CAMP的板子题?C是可持久化线段树。现在暂时还没复现就不讨论了。


最终的榜单:http://ctec.cumt.edu.cn/acmboard2018/

由于在封榜后一直没过题,所以还是有点担心跌掉银首的情况的。不过当算了一下名次去除了打星队后正好卡在了金尾(18/195)的时候,还是有点庆幸的。结果还算ok,只是过程不那么顺利了。


接下来是总结(说学逗唱)环节

  • 会模板≠掌握了算法,就像F题我知道dfs序也知道树状数组仍然懵逼就是一种没有真正理解LCA算法的体现
  • 不管哪个方面,要学习的还有很多。永远记得比你强的人比你还努力的多
  • 徐州的地锅鸡真的好吃,也完成了在湖(云龙湖)上打牌的夙愿(雾)
  • 学弟推荐的打牌双抠真的复杂,打这个比写大模拟还复杂的多差点为第二天双双银写下铺垫
  • 没顺路回家有点遗憾,不过徐州菜的风味真的是非常合我意了

贴几张图纪念一下

《ACM-ICPC2018江苏邀请赛总结》
《ACM-ICPC2018江苏邀请赛总结》

点赞
  1. Lucien说道:

    好厉害啊!致敬。

    1. ohazyi说道:

      感觉自己很菜啊 还得学习一个 感受到和大佬们的差距太大了

发表评论

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