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