1.金币

1.1 100分算法

对于$100\%$的数据,有:$K \le 10000$,直接模拟即可。
复杂度:$O(K)$

1.2 总结

签到题,主要考察选手是否会编写程序。

2.扫雷游戏

2.1 100分算法

对于$100\%$的数据,有:$n\le100,m\le100$,直接模拟即可。
复杂度:$O(nm)$

2.2 总结

签到题,主要考察选手是否会熟练地编写程序。

3.求和

3.1 20分算法

对于$20\%$的数据,有:$1\le n\le100,1\le m\le5$,我们可以通过三个循环来枚举每个三元组$(x,y,z)$,然后计算其对答案做出的贡献。
复杂度:$O(n^3)$

3.2 40分算法

通过仔细分析题目我们可以发现,三元组$(x,y,z)$中的$y$是否会对答案造成影响,显然不会,那么限制1 $(x<y<z,\ y-x=y-z )$则变为了$x<z\ ,\ (z-x)\ mod\ 2 =0$。
对于$40\%$的数据,有:$1\le n\le3000,1\le m\le100$,我们可以枚举每个二元组$(x,z)$,然后计算其对答案做出的贡献。
复杂度:$O(n^2)$

3.3 60分算法

对于第5,6组数据,有:$1\le n\le100000,1\le m\le100000$,并保证每种颜色出现次数小于20次。
通过仔细分析题目我们可以发现,不同种的颜色对答案不做出贡献,则我们可以一种颜色一种颜色的考虑。对于每种颜色,我们枚举其二元组,然后计算其对答案做出的贡献。
复杂度:上界$O(20^2n)$,下界$O(n)$

3.4 100分算法

对于$100\%$的数据,有:$1\le n\le100000,1\le m\le100000$。
对于每一个可以对答案做出贡献的二元组$(x,z)$,其贡献为$(x+z)\times(num_x+num_z)$,我们可以对这个式子进行变形,为$x\times num_x+x\times num_z+z\times num_x+z\times num_z$。
我们依然一种颜色一种颜色地考虑该问题,则对于某一个方格x,在x后面并且颜色与x相同的方格会对方格x造成贡献,则贡献为:
$$\sum^{n}_{z>x,(z-x)mod\ 2=0}(x+z)\times(num_x+num_z)$$
$$\sum(x\times num_x+x\times num_z+z\times num_x+z\times num_z)$$
$$\sum(x\times num_x)+x\times \sum num_z+num_x\times \sum z+\sum (z\times num_z)$$
显然,我们可通过前缀和来优化这个式子的转移。
复杂度:$O(n)$

3.5 总结

对于求和公式,我们一般通过展开$\sum$式子来获取某些前缀和或其他性质的优化,从而解决问题。仔细分析题目所给的条件,剔除冗余条件,一步步简化问题。

4.推销员

4.1 20分算法

对于$20\%$的数据,有:$1\le n\le20$,我们可以对于每个$X$,直接暴力枚举大小为$X$的子集,计算答案。
复杂度:$O(\sum^{n/2}_{i=1}C^i_n)$

4.2 40分算法

对于$40\%$的数据,有:$1\le n\le100$,并不会。。。

4.3 60分算法

对于$60\%$的数据,有:$1\le n\le1000$,我们可以使用动态规划解决。
设$dp[i,j]$表示最远的距离至第i户人家,共拜访了j户人家的最大消耗体力值。
则$dp[i,j] = max\{dp[k,j-1],\ \forall k\in [1,i-1]\}+2\times (S[i]-S[k])+A[i]$。
利用前缀和优化转移,再利用滚动数组优化空间(其实没必要了)。
复杂度:$O(n^2)$

4.4 100分算法

对于$100\%$的数据,有:$1\le n\le100000$,我们可以使用贪心解决。
我们将这条胡同想象成一张图,而我们要做的就是找一颗最大生成树,对于当前我们选择的点集$S1$,我们要将其扩展至$S2$,使收益最大,显然这是一个类似与prim或dijkstra的算法。
利用数据结构(线段树,堆,平衡树)优化转移。
复杂度:$O(nlogn)$

4.5 总结

通过阅读题面,深入挖掘出题目中所包含的隐晦条件,以及一些不那么显而易见的性质,想到使用贪心策略。

5.总结

NOIP2015普及组复赛试题题风良好,十分符合“普及”的性质,又不失有蕴含着巧妙的转化思想,并且适度考验了选手的代码能力,是很不错的一套题。
如需参考本人代码:百度云盘:https://pan.baidu.com/s/1bQA17C