Problem C. A Sequence Problem
Brief description:
… 略）
Analysis:
其实这题是我们通化区域邀请赛的C题提取出的一个子问题，这次把他当做一个比较简单的题目来出。
分析：
a[i]>=k;
a[i+1]>=k-1;
…
a[i+k-2]>=2;
a[i+k-1]>=1;我们可以从后往前倒推。假设以当前位置为起点(不妨假设为位置i)最大符合题意的连续子串长度为len，
即表示a[i]>=len,a[i+1]>=len-1,…a[i+len-1]>=1 (假设)刚开始len = 0。1.如果当前项a[i]>len，根据假设，可以把a[i]直接加到连续子串的第一位，len++
2.如果当前项a[i]<=len，根据假设，后面的数我们可以发现是不用考虑了的，这时只需要把a[i]放进 子串的第一位，因为需要满足a[i]>=a[i]，(a[i+1]>=a[i]-1…a[i+a[i-1]-1]>=1)这显然满足，
所以把a[i]放进来的时候，len = a[i]。每一步更新答案。
————————（by yejinru）
Problem G. GSM
Brief description:
… 给定一个 V 图，问一条线段经过了多少晶胞（cells）。
Tags: 几何，Voronoi 图，二分
Analysis:
… 给定一个点集，Voronoi 图是指将平面划分到距离其最近的点的几何结构。完整的构造出 Voronoi 图是困难的。。。单就这个题目来说。。更为科学的方法是对所查询的线段执行二分。。因为如果一个线段的两端同属于一个晶胞。。那么该线段的任何一个部分一定都属于一个晶胞。。。
。用这个来作为一个终止条件。。每次暴力检查两个端点分属哪个集合即可。。复杂度 O(n*每次二分)。
类似的搞法在计算几何中很常见。。。
参见。Usaco Section 3.4 Closed Fences (fence4)
参考程序
Problem H. To The Moon 2
Brief description:
。。维护一个序列。支持区间加减。区间求和。。以及返回到之前的一个操作之前。
Tags: 线段树、树状数组、可持久化数据结构、离线、事件树、DFS()
Analysis:
。。首先。。区间加减。区间求和这个线段树的基本操作。。（也可以用树状数组巧妙实现）。。
。。不是这题的重点。。不会的可以翻看。。【完全版】线段树 by hh。。。
。。主席树（可持久化线段树）因为可以查询到任何一个历史状态中去。。所以用到这题当然随便做。。
。。当然离线的话有更为方便的做法。。将操作看成事件。。那么事件之间会呈现出一棵树形关系。。
。。从根开始。DFS() 一遍这颗 “事件树” 。进入子节点时执行操作。。返回时撤销这个操作。。
。。。就可以得到所有询问的答案。。。
External link:
https://www.shuizilong.com/house/archives/spoj-11470-to-the-moon/
Problem I. ????…
Brief description:
… 经典的 MAWC （minimum-average-weight-circle）问题
Analysis:
方法一：
设 dp[k][i][j] 表示当前长度为 k, i 到 j 的最短路。。于是可以 O(n4) 动态规划（倍增第一维可以优化到 O(n3logn)。
类似的方法还可以做 MAWP （均值最短路径）
（minimum-average-weight-path）
。。。。但是我验题的时候这个方法一直 WA。。。。/w\。。。
方法二：
。。二分答案判定。假设存在平均值小于 x 的环，那么将整副图中的边权全部减 x。
。。一定存在一个负权环。… 二分答案判定。。
。。对每条边 -x。。spfa 判断是否存在负权环。
。。如果有一个点进入队列 n 次。。。则表明存在负权环。
External link:
http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=34650
