这次的结果应该就是“情理之外意料之中”吧。意料之中是因为看到我放在HDOJ上的练习题有多少人做、多少人AK就能大致估计出这次不会有太多新手做出题来。但我也没降低题目的难度，因为我们的要求是不会降低的。落后于我们的要求可以努力可以追赶，但如果到了4月依然落后那就是真的被淘汰了。去年我们是在11月和12月讲图论的算法，而寒假完全放养。后来反馈的情况是普遍寒假不怎么做题然后12月的时候听人讲算法也听不明白。于是改为现在的形式。不知道到底有多少人在看，但可以肯定的是看的人没看明白，不然不会出现最小生成树模板题也不会做的情况。至于为什么没看明白ppt/书还没在bbs/QQ群问别人，我就不知道了。
这次7题，3题王子一出的，3题我出的，1题是卫欣找的数学题然后我改描述出数据。先原文照搬王子一的题解。
B Adventure of Dragon’s Mystery:
简单DFS，用used数组标记使用过的技能即可。
D ziyi’s plan:
0-1背包,题目要求的是至少一次交易成功的的最大概率,换个角度求都不成功的最小概率即可,状态转移方程:f[j]=min(f[j],f[j-v[i]]*w[i]);其中,w[i]表示不成功的概率,(1-f[j])为花费j元交易成功的最大概率。
F Bloody X:
最多只有10个DNA片段，有2^10=1024种出现的可能，所以在AC自动机上做状态压缩dp,字符串结尾状态更新用或运算实现，d[i][j][k]分别表示当前长度i，字符串结尾状态j，二进制压缩状态k。如果d[i][j][k]=1，那么d[next][chd[j][k]][z|word[chd[j][k]]] = 1;最后从d[l]的所有状态中找出最大值，最大值小于0就Bloody Monday！（AC自动机模板采用HDU胡浩大神的模板）
我插一句……有个问题需要注意，那就是给出的序列如果都是负，不一定就必死，你可以构造一个不出现那些序列的DNA串，结果就是0.
然后从头说。
A题的原型是什么第四届百度杯决赛，不知道百度杯跟百度之星啥关系，总之不少OJ有这套题。不过时间范围给的比较宽松，标程大约300ms，按照一般OJ的时间给了3秒，于是某HDU大牛好像用dijksra在2750ms过去了……严格说来这应该是一道1秒或两秒的题。
这题如果不考率每个点上的污染值，那么就是个很简单的floyd。而且我们知道，floyd的三层循环k-i-j含义为：以0-k中的若干个点作为中间点，i到j的最短距离。因此实际上相当于三维的空间，而f[i][j][k]只跟f[i][k][k-1]和f[k][j][k-1]有关，因此用滚动数组将第三维省略节省空间。而在此题，因为每条路径最大污染值不确定，而查询的忍受值又有很多种，因此需要保留这一维。
当然，只保存中间的结果不能获得全局最优，因此需要将这些点按照污染值从小到大排序，因为不要求起点和终点的污染值在承受的范围内，只要保证中间点的最大值小于要求，再在这些可能中寻找最短即可。因此f[i][j][k]的含义为，以前k小的污染点(为方便可以让k从1到n)为中间点，从i到j的最短路径。这样其最大污染值一定是第k个点的污染值。这样查询u到v只需要枚举n个排序后的点，假设第x个点是满足承受范围的点中污染值最大的，那么f[u][v][x]就是所求。
C题真的很简单……USACO3.2左右那个给奶牛吃黄油的题……很明显是很稀疏的图，所以用floyd的属于自杀行为。实际上单源最短路径用N次效果跟floyd是一样的，因此只要用那种复杂度主要跟边数有关的最短路模板用N次就能过，我是用吉大那个STL的dijkstra模板过的，当然需要手动修改模板让其运行n次。理论上用SPFA或者bellman-ford效果应该更好。
E题不解释了……赤裸裸的最小生成树，随便套模板，跟比上个月赛题还省事（不给坐标自己求图而是直接给图）。唯一需要注意的是这题存在重边和自环。
G属于典型的会了不难的题。我个人感觉解法最好的是这里的这个。
总之这套题不算很难。如果再多两道大水题或者模拟题再多一道中等以上的题就跟省赛难度差不多了。但是我们不能以做出省赛水题为目标，那样连非985非211的都干不过。因此平时的比赛没必要为了区分出谁排第20谁排第30而出一个比谁水得快的题，能留到明年暑假的加上老人也就是9-12人而已。明年5月的省赛还有3个月的时间，如果这半个月没学到什么东西，如何能肯定自己在未来的6个半个月里学到东西呢？开学之后肯定不会讲这些东西，一定是比这些还难又很难自学的。而自学这些东西不应成为问题。简单的图论就是套模板，以至于亚洲赛今年为了避免出模板题很多都不出图论，嫌水。只要好好看书/ppt，理解基本概念，理解题型，会套模板就够了。当然知道模板算法的原理最好，不然是不可能做出A题那样的题的。
本次比赛冠军是一个不认识的杭电的同学……而且他拿了4题的FB。第二好像是川大的妹子？第三是东大的罗耀燊，拿C题的FB，第四是上次第一HIT卢大牛，第五是东大的李科。以上做出5题。第六宁硕同学拿了D题的FB。恭喜以上各位，希望后面的再接再厉。新一期NEUACM积分榜随后放出。
发表回复