第二场
A.扑克牌
这个是原题 着色方案
但是赛后我看别人的代码发现了其他的做法：
f[i][j]表示前i种数字，有j个地方是连着的方案。
然后我们枚举第i+1种颜色要拆成多少段，然后要放多少段在前i个连着的空里面。组合数搞一下。也是可以过的。
当然细节很多。
如果每种颜色的数量再多一点，前一种记忆化搜索的方法就不适用了，但是后面的方法还可以推广。
B.攻略城池
这题我刚开始想的是先把边去掉，然后考虑往上面加上m-k条边。
因为每个联通块需要的花费是该联通块内权值最小的点，所以我们从大到小尽可能的把权值打的点合并到权值小的点所在的联通块里。
这样就能不耗费大的权值。然后WA了。我想原因应该是大的权值连到其他的联通块内是由许多方案的，不同的方案可能对应着不同的ans。
而我们无法事先预知应该选择哪条边，所以这个贪心是有问题的QAQ。
然后膜拜了rausen大神的代码。发现这题可以这样来做。
我们把边全部加上去，此时的消费是所有联通块内的最小权值之和。然后把无用的边删掉，意思就是把每个联通块删成树状结构。这样我们在删这些边的时候不用额外的花费。然后如果还剩下边可以删，那么就把除去每个联通块内的最小权值的其他点按权值从小到大排序，取前k个砍掉。
砍掉很好做。只要断开它与当前联通块最小值连的那个方向的那条边即可。
Orz
C.八卦的小冰
这题我不会，但AC还是没有问题的
这题暴力是可过的。。。只要你敢写邻接表的暴力。。。还不知道正解QAQ求教！
第一场
A.彩色的树
这个题其实很简单，我们开n个map，分别表示每个点的儿子的每种颜色的个数。然后讨论一下，注意1的情况。
C.质数相关
神题，我根本想不到。
如果硬要说思路的话，我们在相关的两个点之间连边。那么题目要求就是求最大点独立集。
那么这张图要么是弦图，要么是二分图。（否则不是NP了么）
二分图的最大点独立集=点数-最大匹配
弦图的最大点独立集=完美消除序列从前往后能选就选
完美消除序列=最大势算法，每次选择与已标号的点连边最多的点从后往前进行染色（哎，我怎么都忘了QAQ）
那么令w[x]表示x这个数有多少个质数乘起来得到，那么根据w[x]的奇偶性这张图就成了一张二分图233
然后套用现成算法就可以了。
B.建造金字塔
好神啊 编程之美的题都。
我看的是这里的题解 链接君
关键在于因为是按左端点排序的，所以如果有dp[j]表示覆盖了j，不管前j个到底覆盖了多少，那么如果a[i].l<=j<=a[i].r,那么a[i].l到j的这一段一定是被覆盖了的！！！
因为是按左端点排序的！！！选择了某个那么到j的这一连续的一定都被选了！！！
然后DP什么的就可以自己脑补了。分j与a[i].l,a[i].r的先后关系DP即可。
这种题太神了，如果出在考试中，我能想到排序，并且注意到排序之后会有这样的性质吗？
评论 (0)
