快来估分！2020CCF NOIP部分题解

本周的NOIP联赛完满落下帷幕，以下是小编程家教研组老师们提供的前三题题解

T1－排水系统

【题目概要】

给定n个结点和di个单向管道，从接收口出发，排水口结束，每次经过结点将污水均分。

【解题思路】

在输入的时候先确定没有管道通向自身的是接收口，可以用数组标记求解。判断自身通向其他地方的管子数是0来确定是不是排水口。

采用bfs拓扑排序的思路

先用队列把接收口读入，用bfs 进行搜索，过程的时候注意如果前面还有管道要到达自身，就先不读入队列，当上面的水全部到达这一层时在入队，可以在输入时用数组计数判断自身到达的次数，

最后是水的求和部分，直接2个分数加起来 ，然后找最大公约数进行约分。

T2 字符串匹配

【题目概要】

题目是求 S = (AB)iC 的方案数，其中 F(A) ≤ F(C)，F(S ) 表示字符串 S中出现奇数次的字符的数量。

【解题思路】

先确定好C的可能，即末尾几位字符。然后再考虑划分(AB)i，需要找出(AB)i的最小重复子串，相关算法考虑KMP算法或者字符串哈希，再在该子串中划分A和B，产生方案。

需要注意的是AB不一定只能存在于最小的重复子串中。比如：

(AB)i = abababababab，最小重复是 ab，但重复的部分也可以是 abab，同样可以在abab中划分AB串，另外还有ababab以及整个(AB)i。分别是最小重复串的1、2、3、6倍，都是最大重复次数6的约数。

另外定好(AB)的范围后，划分AB时注意题目限制F(A) ≤ F(C)。

T3 移球游戏

1.40分部分分

我们可以用2*m次操作将两个球A,B交换，做法：记空柱子为C，假设A球上面的球的个数大于B的（否则交换AB），把A球的上面的球移动到空柱子C上，然后把B球上面的球移动到A上面，然后把A上面的球加上A球移动到B柱子）最后把空柱子C的球移动到A柱子。

我们把m*n个球通过这种交换操作归位，总次数2*m*m*n可以通过40%的数据

2.70分部分分

我们一个颜色一个颜色的处理，假如我们现在处理到颜色i，考虑一个柱子一个柱子的处理，假设颜色i的球是红球，不是颜色i的球是黑球，如果柱子A有红球（不一定在上面）我们可以通过如下操作使柱子A的红球全都移动到A柱子的上方：记辅助柱子为B，记空柱子为C，首先算一下柱子A有多少个红球，记为k个，把柱子B上方k个球移动到空柱子C上。对于A柱子，可以从顶部一个一个移动，如果是红球，移动到B柱子上，如果是黑球，移动到C上。这时候A空了，C上面都是A柱子上的黑球，下面k个是b柱子上面的球，而b柱子上面是k个红球。我们还原C柱子，我们把C上面的黑球移动到A，然后把B上面的k个红球移动到A最后把C柱子下面的k个球给B。这样我们就把A柱子上的红球移动到上方，而B柱子没有改变，这样一次要用m*2+k*2次操作。最后再把每个柱子上方的红球移动到某一个柱子上，然后移动黑球，留出一个空柱子，这样一个颜色就完成了。计算次数，因为k的总和是m，所以对于每个柱子做一遍要用n*(m*2)+m*2次，而对于每种颜色都做一次，要用(1+2+.......n)*(m*2)+m*n*2大约是n*n*m次操作，在n=50,m=300大概是75万次，可以拿到70分，而在m=400时需要100万次，不能通过本题。

3.100分做法                                        

我们可以发现，在70分部分分中，将柱子C还原是一个很消耗次数的操作，我们考虑为什么要还原，因为柱子C下面是原来B上方的k个球，里面可能有红球。考虑如果B是一个全黑球的柱子，在还原之前，C就是全黑球的柱子，而B上方是k个红球，A，B和C正好是还原之后的C，A和B柱子，这样我们就省下了还原的操作，操作顿时少了一半。最后只剩下一个问题，如何构造出一个全是黑球的柱子？考虑两个柱子，因为红球的个数一定小于等于m，所以黑球的个数一定大于等于m于是我们可以用70分部分分的操作把两个柱子的红球全移动到它们的上方，然后把两个柱子红球移动到空柱子，再把黑球移动到一个柱子上，最后把空柱子上的红球移动到另一个柱子上，这样就能用4*m次构造出一个全是黑球的柱子。计算次数，因为不用还原，所以复杂度瓶颈n*n*m次操作变成了n*n*m/2次操作，再加上一开始和最后的处理大概n*m*10次操作，总共约600000次操作，可以通过本题。std极限数据跑了66万次操作。

需要参考代码

可加陈老师微信咨询