分类存档：默认分类

NOIP2010提高组解题报告——Translate

【题目大意】

给定一个有M(0

【算法分析】

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

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

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

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

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

【时间复杂度】

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

【空间复杂度】

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

各种模拟赛之后有感

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

【[NOIP模拟赛]东方幻想乡系列模拟赛 Stage.3】小结

【题目链接】http://imnettle.net/contest/problemlist.asp?stage=3
里面Download里有完整的包~~
这套题目感觉上出的还是比较好的。
然后我自己做得了300分。。。
原因是第三题mokou。。。样例的边权是整数。。。然后没看清，直接就用了int存。。。但是实际上，是实数，于是爆0
然后下面写个简单的题解：
1、tenshi。二分答案然后由于每个1都要被覆盖，所以验证时，每次找第一个未被覆盖的1，然后把连续的长度为答案的1都删掉。如果覆盖次数<=k。那么可行。
2、reisen。这题一看就是动态规划。。。F[i][j][k]表示第i个时间，这一步走到j，走到j之前在k上的概率，然后加法原理一下就能解决。
3、mokou。就是最小生成树以后在树里统计。设d[x]表示以x为根的子树的所有边权之和。然后枚举切割点。然后向下的边每个分出一个区域，如果x不为根，那么x向父亲那边也构成一个区域。而这个区域的边权则为树中所有边权和-d[x]。最后模拟求方差即可。
时间复杂度O(m lg m+n)
另外纠正出题人题解一个错误，n比较大不是不能用prim，用堆或线段树优化以后还是可以的。
4、akyuu。先建图，图中的边表示第i组和第j组相斥。那么问题变为求任意图的最大独立集。
这个有几种做法：
一、若二、爆搜+调搜索顺序+最优化剪枝+Dancing Link。(我写的就是这种。。。)
三、这个解法来自WJBZBMR，名曰“分二乱搜”。。。实则就是把20个点分出来。
然后用二进制表示这20个点的某种取舍情况下，最大独立集是多少。然后在搜剩下的点。对于另一一边搜到的一个独立集，到这20个点里面把有边相连的点去掉，剩下的点全部取，接着就可以利用前面那个二进制得这种情况的最优解。
实际上第三种解法可以与前两种结合，理论上能使一个方法搜多20左右。
我再讲讲我的优化策略吧。
首先，我把所有点按在图中的度从大到小排序，然后从前往后进行选与不选的搜索。这样做的根据是如果我选取了这个点，那么就可以排除最大量的点，减少搜索量。
接下来，我有两个参数，cnt和rest。cnt表示现在已经取了多少个点。rest表示除了已经选的和排除的以后，有多少个点。于是如果cnt+rest<=ans，那么可以退出了。
最后，我用了Dancing_Link。每次调用dfs，都直接跳到下一个没选的地方。
最终所有数据都是0.01s过掉了。（没有加上WJMZBMR的方法）
【CODE】
[tenshi]http://xiudaima.appspot.com/code/detail/3117006
[reisen]http://xiudaima.appspot.com/code/detail/3226001
[mokou]http://xiudaima.appspot.com/code/detail/3122006
[akyuu]http://xiudaima.appspot.com/code/detail/3201003

记录一下失误

今天上午Tyvj的比赛下面交只有320分。
原因有两个：
一是第一题多组数据没有memset。
二是还是第一题里面。。。原来scanf("n")和Pascal的readln是不同的。。。跳不过那个很疼的输入。。。
后来是写了个函数
void Cross{
char ch=getchar();
while (ch!=’n’) ch=getchar();
}
来解决的。。。求其他解决方法。。。