【题解】南华大学第十五届ACM程序设计竞赛

A题

暴力呗，签到题啊。会写判质数就可以了。

B题

并查集，也没有什么别的东西。不过数据不是很强大。不用压缩路径好像也能过。统计一下一个集合有多少个元素减一就好了。时间复杂度:O(m)+O(n)?

C题

DP吧。

先可以把删除长度所的到的价值用O(n^2)预处理一下。得到删除长度所得到的最大价值。设x[i]为删除长度i所得到的最大价值，等于max(x[j]+x[i-j],x[i])(0<=j<=i)(虽然不这么做也可以得到答案)。

考虑题目所给的操作，我们从中删除一段，再把前后拼接起来，如何设置状态？

先看一个例子：11111011110000

然后我们删除0后变为1111111110000

答案等于单独的0加上{11111}11110000

这样我们可以设置一个前缀，这样我们就可以表示任何地方删除的状态了，答案不会变。

我们可以压缩一下相同的元素。（因为我们提前预处理过最大价值）

设dp[l][r][v]表示l+1到r加上前缀的v的最大答案。压缩后得到数组z。

我们来考虑一下状态的转移：

1、  我们直接删除前缀v，dp[l][r][v] = x[v] + dp[l+1][r][z[l+1]]，

2、  然后我们删中间任意一段，dp[l][r][v]= max ( dp[l][r][v] , dp[l+1][i][z[l+1]] + dp[i][r][v+z[i] ) (必须满足条件(l%2)==(i%2)因为只有这样删除才能把前缀合在一起。)

3、  如果(l%2)!=(i%2)，没必要删除。因为得到的答案可以在dp[l+1][A][b]中得到。

然后记忆化搜索一下就可以了。时间复杂度:O(n^4)?

(看不太懂可以自己模拟一下)

D题

由于每个点的度数≤3，由最大流最小割定理，最大流只会是0到3。

0:直接分别处理联通块；

1:同个联通块的不同边双；

2和3: 考虑依次删掉每一条边，再求边双，如果两个点不论删除哪一条边，都一直在同一个边双里，那么流量就为3，否则为2。

把每次边双的编号哈希就可以判断两个点是否一直在同一个边双里。

E题

关键词：最短路+枚举

对起点、终点分别求一遍最短路，分别用两个数组存储。

枚举每一个免费区间

每个免费区间a,b的价格是min(dis1[a]+dis2[b],dis1[b]+dis2[a]);（dis1数组存储起点到各点距离，dis2数组存储终点到各点距离）

F题

题目意思很明确，求一个三项式展开式中的系数是多少。

首先需要了解最基本的公式 没学过三项式展开怎么办 因为我们学过二项式展开公式，三项式自然就是多展开一次可以了，接下来就是求的问题了

由于此题数据量比较小，初略一看，直接暴力就可以写出，怎么暴力？求n的阶乘，放心循环就可以了（才1000的数据量），再做除法，取个模。这样写有个致命的错误，就是除法的取余的问题，除法不满足拆开分别取余，再相除后取余的，如果是对质数取余，可以考虑下费小马+快速幂 。

高级解法：杨辉三角，找找杨辉三角的层数和对应位置就知道， 正好与之对应，中间过程取余，因为递推是加法，所以不影响最终的结果。