2018 ACM-ICPC Asia Nanjing Regional Contest
Replay
oxx1108:
- 垃圾比赛，毁我青春。
- 全场副作用，贡献了6发罚时。
- 唯一欣慰的是可以嘲笑对面要吊打咖啡鸡的队伍。
dreamcloud:
Xiejiadong:
- 热身赛受到对面南大队伍碾压。听说他们少过了一题，正式赛能多过一题？那我们正式赛一定能多过两题，比他们多一题（flag）。
- flag立住了（他们应该看不到这个吧，怂）。
- 开场开题，博弈题，数学题...挂机预定。
- 感觉B题很可做啊。搞了至少两个小时的$N^2$的优化，躺在地上看队友各种过题，差点零贡献领奖。
- 打印差评，送的慢，甚至中间有一段连打三份一份都不送，导致占着电脑debug，强制减少oxx上机时间。
- 比赛结束后，背后一生大吼，东南一队好强啊，随机seed用某人生日把K过去了。
- 冠军是dls，xls，小火车梦之队，心服口服。不过冠军没有奖杯，那这场冠军真是亏了。
- M题差评，由于原题，金牌题强行变成银牌题。K题差评，场上过的绝大部分都是随机。
- 比赛最后二十分钟，划水观看oxx提交了127发E题随机代码，比赛结束20min才得到了全部WA的feedback，差点以为要Au了。
Problem A
Solved by oxx1108.
题意：1～n，每次可以取走连续至多k个数，两个人博弈问谁必胜。
题解：sg函数打表找规律，sg函数敲错wa了两发。
Problem B
Unsolved.
IOI2016原题。
还是有一些区别的。
Problem C
Unsolved.
Problem D
Solved by Redbook.
题意：三维求最小球覆盖。
题解：红书原题，甚至数据范围小了很多。
Problem E
Unsolved.
Problem F
Unsolved.
Problem G
Solved by oxx1108.
题意：给一个正三角形的金字塔，求其中有多少个正三角形（包括斜的）
题解：看n层到n+1层，固定底边上一个点，枚举另一个点即可列出递推式，然后再求和公式既可以写出公式。
当然最简单做法直接打表找规律。
Problem H
Unsolved.
Problem I
Solved by dreamcloud.
题意：$n$个人，$m$个怪兽，每个人能打一只怪兽，给$k$个人超能力，使得他们能打两只怪兽。最多能消灭多少怪兽。
题解：网络流，首先对于人和怪兽建边，起点到每个人都建流量为1的边。再额外建个节点，它到每个人建一条流量为1 的边，起点到它建流量为k的边。
Problem J
Solved by dreamcloud.
题意：给你一个数组，算每个区间中有多少质数的总和。
题解：预处理出来每个数，含哪些质数，即可。
Problem K
Unsolved.
Problem L
Unsolved.
Problem M
Solved by Xiejiadong && dreamcloud.
题意：给出两个字符串$s$，$t$，求有多少的数对$(i,j,k)$满足$s_i,\cdots ,s_j,t_1,\cdots ,t_k$是回文串，且$j-i+1>k$。
题解：可以把$s$串倒转成$s$'，然后我们拿$t$在$s$'上匹配，假设$t_1,\cdots ,t_k=s$'$_i,\cdots ,s$'$_j(j-i+1=k)$，这种情况下的方案个数就是以$s$‘$_{i-1}$为结尾的回文串个数。
首先用Manacher算法处理一下以每个位置$i$为结尾的回文串个数$ans_i$，就是在当前位置和最远位置分别打上tag，然后扫一遍，统计一下。
接着我们需要$s$‘的每一位最多与$t$匹配了多少位，这个可以用拓展KMP来处理每个位置$i$与最多$t$匹配成功的位数$a_i$，那么答案就是$\sum_{i=1}^{|s|}ans_{i-1}*a_i$。