作者存档：edward_mj

NOIP2010提高组解题报告——Prison

【题目大意】

给定一个无向图。

我们用三个值来描述一条边：Edge.w(该边的权值),Edge.x,Edge.y(该边所相连的两个顶点)。

现需要把该图里的点分在两个集合A,B中。

令Weight_A=Max(Edge.w | Edge.x∈A，Edge.y∈A)

令Weight_B=Max(Edge.w | Edge.x∈B, Edge.y∈B)

则Answer=Max(Weight_A,Weight_B)

问Answer最小能是多少？

【算法分析】

本题有两种思路。

【算法一】

先二分答案，然后单独地判定可行性。

注意到二分答案Limit以后，使用所有Edge.w>Limit的边构成一个新图。然后这个可行性问题可以转化为：判定该新图是否一个二分图。

对于这个问题，我们可以通过对每个点黑白染色来判定。

染色过程如下：

使用广度优先搜索或者深度优先搜索遍历全图，对于一个连通分量，先对其中一个点染上白色。然后再将与它相邻的点都染成和该点相反的颜色。如此下去，不同连通分量分别处理，最后得到一个所有顶点都经过染色的图。然后检测是否存在一条边所连接的两个顶点颜色相同，若是，则不可行，否则可行。

【时间复杂度】O(V lg 10^9+E lg 10^9)

【空间复杂度】O(V+E)

【算法二】

注意到答案一定是某条边的权值，那么我们把边按权值从大到小排序，然后枚举答案，并考虑答案的改变，情况会发生什么变化。

答案每次减少一点，就会加入几条边，我们现在要在线判定新加边以后，该图是否还是二分图。那么我们用并查集维护每个连通分量，利用该点到并查集中根的距离判定染白色还是黑色。然后如果新加入一条边，连接同一连通块的两点并且他们到根的奇偶性相同，那么出现矛盾，不可行。否则，合并两个集合。

【时间复杂度】O(E lg E + V α(V))

【空间复杂度】O(V+E)

NOIP2010提高组解题报告——Tortoise

【题目大意】

给定N(1<=N<=350)个排在一行的格子，每个格子上都有一个权值。同时给出M(1<=M<=120)张卡片，每张卡片上有[1,4]中的一个数字。一开始游戏者站在第一个格子处，每使用一张写着数字x的卡片，那么向后跳x步，并得到该格子上的权值。卡片不可重复使用。数据保证每种卡片的数量不超过40，并且所有卡片上的数字之和与N-1相等。

【算法分析】

本题很容易使用动态规划解决，而且可以通过所有数据的状态定义也有很多种。由于转移都比较简单，并且几乎都一样思路，所以转移方程在此略去。

【算法一】

F[i][j][k][l]表示写着数字1、2、3、4的卡片分别剩下i、j、k、l张时的最大得分。

(可以使用n-(i*1+j*2+k*3+l*4)来得知当前到达哪一个格子)

【时间复杂度】

O(41^4+N+M)

【空间复杂度】

O(41^4+N+M)

【算法二】

F[i][j][k][l]表示跳到了第i个格子，写着数字2、3、4的卡片分别剩下j、k、l张时的最大得分。

(可以使用n-i-j*2-k*3-l*4来得知1号牌剩下多少张)

【时间复杂度】

O(N*41^3+N+M)

【空间复杂度】

O(N*41^3+N+M)

【算法三】

F[i][j][k][l]表示剩下i张牌可用，写着数字2、3、4的卡片分别剩下j、k、l张时的最大得分。

(可以使用i-j-k-l得知1号牌剩下多少张)

【时间复杂度】

O(M*41^3+N+M)

【空间复杂度】

O(M*41^3+N+M)

NOIP2010提高组解题报告——Translate

【题目大意】

给定一个有M(0

【算法分析】

由于数据范围很小，做法很多，这里只介绍一种较优秀的算法。

首先建立一个哈希表和一个队列。

哈希表用来判断该元素是否存在于储存器中。

而队列的先进先出的性质与题目要求刚好相符合。

对于每次输入，先在哈希表中查找，如果存在，那么什么也不用做，否则插入队列，如果队列超过了规定的长度，那么把队头元素出队即可。

【时间复杂度】

O(M+N+Max(a[i]))

【空间复杂度】

O(M+N+Max(a[i]))

各种模拟赛之后有感

这段时间做了很多NOIP模拟赛。。。
某些题目描述都不清的。
甚至搞到一半，题目都换了+_=。
我觉得，一份题目，首先第一要点就是题目要清楚，如果必须看答疑帖才能让大部分懂的话，那么还是先别放出来吧，找多几个人验证一下再说
由此所见，我的那份题目还是出的不错的。。。汗