HCPC 2013 Spring Onsite Contest 解题报告

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:

http://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