ZOJ Monthly, August 2010 比赛总结|解题报告
本次比赛由我、DTen和sssplk完成，一台机子进行。
这几天因为学校的一些事情回去了一趟，堕落了两天。一回学校发现离网赛只有1周了，必须再做两场比赛训练下。这几天有和其他学校的acmer交流，发现他们都很强，压力真心大啊。
言归正传，说下这场比赛。这场比赛做的效果总体来说不错，ac5道题，排名53/550.这场比赛虽然是我从头敲到尾敲5道题，但是队友还是帮了很多，比如F题也就是xxxxxxx题，我一拿到题目就有想法，然后说给DTen听，他比较适合这题，虽然最后还是我在敲，但是这个决策是对的，而且这道题没DTen中间提供的思路根本没办法ac。最后一道C题在离比赛17s的时候改了一个小错误提交返回AC,绝杀，也很漂亮。
然后就想说下敲题速度，一直在刷CF锻炼敲题速度，敲代码的速度是上去了，但思考问题的缜密程度仍有待提高，总是在敲完代码后七改八改，严重影响速度。关于这点，只能说继续CF以提高之。
到现在我们共A了6道题，因为开学晚上没怎么吸收题目，后面来补吧。现在说下这场比赛的题目（前面数字是题目在Zoj上的题号）：
Zoj 3373 Gensokyo Forbidden Words 看着像模拟题，其实就是模拟题，没想没写没ac。
Zoj 3374 ⑨ Adjacent Numbers 带环的DP，剪开环再进行转移。
Zoj 3375 Imperishable Night 状态压缩DP+贪心，好题！题目规定有三个变量，point，Iv,tv,让我们一个一个地选择n个地方种的某个地方，然后这个地方里面有两种宝物x,y可取，x宝物有xi个，可以让tv增加ai，y宝物有yi个，可以让lv增加bi。选择x,则point += lv，tv += ai，为了防止混乱带来思维复杂度地增加，我用xv代替lv，yv代替tv，这样就好看多了。那么选择x则point += xv，yv += ai，选择y，则point += yv，xv += bi;
这题初看上去很复杂，但其实想好几点就很简单了。1、由于后面point += yv或者point += xv,那么本次选择了某个城市，最后xv必定增加xi*bi，yv必定增加yi*ai，然后这两增加的量对后面的都会有影响，那么我们可以再前面就应该考虑后面。 2、选择城市是一步，选择好城市后里面的宝物如何选择才能让本次的point增加最后呢？这个贪心就好，我yy了一个结论，cnt = xi * yi,maxPoint = max(cntx * ai + cnty * bi)(cntx + cnty == cnt) .这个maxPoint是选择城市后增加的，对后面的不会有影响。可以认为选择城市和选择宝物是独立，那么我们可以预处理线算出每个点maxPoint。 3、选择城市可以用状态压缩来做，选择了某些特定的城市后，已经在后面的影响考虑在内，那么dp[i]就可以表示选择了城市编号压缩后为i的最大point。考虑好这三点之后就可以用类似于TSP的转移方法进行DP.
Zoj 3376 Safest Points 不会。
Zoj 3377 Ancient Duper 第一次鼓起勇气写博弈搜索，利用N点和P点的性质进行搜索。如果某个状态能走到一个P状态，那么当前状态就是N状态，如果都到不了，那么就是一个P状态。额，我有种错觉，是不是大部分博弈搜索都是这么写？请高人指点..
Zoj 3378 Attack the NEET Princess 题目让我们找起点到终点必须经过的边。如果题目中的边数很小，那么显然可以先枚举边然后判断是否能从起点到终点。但这题边数位10万，换种想法，先用Tarjan求出所有桥边。然后进行一次Dfs，找出哪些边在起点到终点的路上。最后还有一点需要注意，本题有重边，这个可以再一开始的时候标记重边，然后随意增加一条边，注意才不影响连通性。最后既是桥边又是起点到终点路上的边且没有重边的边。
Zoj 3379 Master Spark 几何题。
Zoj 3380 Patchouli's Spell Cards DP，但是没想没写没AC.
Zoj 3381 Osaisen Choudai! 线段树优化DP，我是敲完F发现暂时过不了再来敲这题的，果断增加了很多罚时。这题正着思考很复杂，应该逆着思考。由于第i天选择了之后，只有i + xi,i + yi - 1天能选，那么dp[i] = si + max(dp[j]) ( i + xi <= j <= i + yi - 1)，求max的过程可以用线段树来优化，单点更新成段查询。
Zoj 3382 Luna Dial 目测是神题。
Zoj 3383 Shiro? Kuro? 简单模拟题，两个trick，一个是整除，另一个：输入的是mxn,并不是nxm.
Zoj 3384 Yuyuko and Youmu 贪心，如果当前的ai小于bi，那么ansi = ai，否则就去前面ai-bi个，复杂度是O(n*n)，官方题解是O(n)，可以从后面往前贪心。
Zoj 3385 Hanami Party 贪心，没想没写没AC。
前面这些写得比较详细的，是我思考过的，我把它记录下来。Here是官方题解。
本文ZeroClock原创，但可以转载，因为我们是兄弟。