今天工信部的通信管理局终于发来ICP备案成功的消息（之前失败了一次。。。），时间是2011-6-8-17:25:18
以此为纪念，我宣布本Blog正式建立
NOI2008志愿者招募
题目解答
题目可以使用费用流建模 (费用流得实现细节就不说了 )，下面是一个常用的建模方式：首先按照天数从源到汇依次建立 S->1->2……N->N+1->T。也就是多加入一个点。他们的费用均为0，如图所示，第N天的流量就是 (MAX-第 N天的需求量 )。然后如果有一种雇员从 (x到 y)可以服务，那么连接 (x到 y+1),流量是 MAX,费用为雇佣花费。这样建模的大致思路大家应该已经明白：按照时间发展顺序，顺流而下。当我们选用一个雇员时，若覆盖 [x,y]天，那么自然就是连边 [x,y+1]只有这样才能保证当前的流量可以允许这些天都得到服务。那么为什么对呢？首先最大流一定是 MAX.因为这是最小割，而任何割集都不会小于这个割，所以就拿第一天来说，如果第一天最后求得的流量恰好是： (MAX-N[1])，一定有N[1] 的流量通过别的途径走了，而且对于第一天这个节点的最大流不可能超过 (MAX-N[1]),也就是说别的途径至少会有 N[1]个流量，而别的流量就是延伸出的包含费用的流，就是雇佣花费。也就符合了题目要求：第 1天的雇佣下限是 N[1].由此限制流量来满足题目要求。这样的方法利用的是补集的思想。
USACO 3.3.5 Game1
题目解答
首次遇到博弈问题，分析问题给定一个序列{num1,num2,num3……numN}两个人分别从左右以最佳策略取值，找到第一个人的可能最大值。那么我们把问题划分得小一点得知，当前的最佳策略相当于分别选择左右两边的数字加上剩下的决策序列中的最大的。因此具备最优子结构，可以拆分为小问题解决。又因为只有两个人所以知道了一个人的状态就一定知道另一个人的。用DP[i][j]表示区间 [i,j]第一个人的最佳策略。边界条件 DP[i][i]=num[i];状态转移方程:DP[i][j]=MAX{num[i]+sum[i+1][j]-DP[i+1][j],num[j]+sum[i][j-1]-DP[i][j-1]}; 根据分析不难理解本方程。不过需要从小的区间往大的区间计算。
关于原理：因为当第一个人选择最左边时从(左+1)向后它就作为后手了，而第二个人作为先手，因此从(左+1)向后第二个人是先手，他此时的决策相当于第一个人，根据方程的意义，第一个人在余下序列的最值就是从(左+1)向后的总合，减去第二个人作为先手的最优决策。(^o^)
USACO 4.3.2 Prime3
NOI2003木棒游戏
USACO 3.4.1 Fence
题目解答
第一个计算几何问题，计算几何问题必须要“踏踏实实”的来，但是也有优化。对于本题目，我使用的是2分法。(我只想到了这个方法，听说还有强大的类似线段树的方法)。首先第一问：使用叉积判断任意两条线段是否绝对相交，若有则输出“NOFENCE”并结束。重点是第二问。观察下图。我们可以很清楚的知道，如果一条线段可以被观察到，他的视野一定不为0，因此，我们只要先找到待观察线段的中点，并与观察点连线就能得到一条新的线段(中位线)。并用新的线段与其它所有线段进行绝对相交判断。同时还要考虑非绝对相交，被点挡住的情况。如果有中位线满足不与所有点相交，那么他一定可以被看到。否则2分。边界条件是两个端点挨在一起了，说明没有满足。这时就要考虑控制精度了。一旦精度过高就会超时。反之就会漏解。(0.005就不错(^o^))具体的实现请看程序。
提一句输出：我们按顺序2分，这样在输出序列里的就是有序的，只是当最后的结点坐标一样时要按输入文件的顺序输出。而只有当第(N-1)与第N个同时要输出时才会不满足(至于为什么不多作解释)。这时先输出N，再输出(N-1)
POJ2299树状数组
POJ3368区间最值-ST算法
题目解答
这是一道可以使用线段树轻松解决的问题，只要维护总最长区间，从左边开始和右边开始的最长区间三个域即可。
但是，还有更巧妙的RMQ解法，假如我们只要[1,n]的最长区间，很显然只要预处理一下，把连续的值的频率算出来，就可以很简单的RMQ了，但问题是：如果区间断开了，那么RMQ是否就失效了?对于断开的区间的整体来说必定是这样，但是其中的完整的子段依然保留着RMQ的最优性。
例如：-1 -1 1 1 1 1 3 10 10 10，预处理后：1 2 1 2 3 4 1 1 2 3，如果查询[5,10]直接ST会算出4，但是应该是3，再仔细观察，因为数列非递减，所以只有左边断开才会影响结果，因此我们只要特殊处理一下左边的连续值即可。然后对剩下的使用ST解决。