2014 ACM/ICPC Asia Regional Beijing Online

Problem 1001. Always Cook Mushroom

Brief description:

給定一個 [1, 1000] x [1, 1000] 的點陣,每個點陣中的點有一個權值。
n 組詢問,每次詢問一個由 (0,0)、(x,0) 點一以及從原點出發的方向向量 (a,b) 構成的直角三角形包圍的點的權值和。

Analysis:

離線,極角排序,樹狀數組。
http://vjudge.net/vjudge/problem/viewSource.action?id=2788351

Problem 1002. Building

Brief description:

x-軸上分布著 n 個位置為 xi,高度為 hi 的建築物,問位置在 qi 的某個人,左右的視角有多少。人的高度為 0,並且不與建築物重疊。

Analysis:

棧維護下凸殼。

http://vjudge.net/vjudge/problem/viewSource.action?id=2773898

(參見... SPOJ 13031. Vision Field/a>
Tsinsen A1377. 樓房重建

Problem 1005. Explosion

Brief description:

給定一個有向圖,每個結點打開後,可以自動打開它的傳遞閉包。
問期望要暴力打開多少結點,可以打開所有結點。

Analysis:

http://codeforces.ru/problemset/problem/280/C
做法同這個題。根據期望的線性性,統計每個結點對期望的貢獻為 1 的概率即可。
強連通縮點,後轉換成 DAG,那麼每個結點要麼自己打開要麼被一個能夠到達它的結點打開。

http://vjudge.net/vjudge/problem/viewSource.action?id=2773890

Problem 1006. Frog

Brief description:

青蛙踩石子過河,河寬 [0, m],有 n 個石子坐標已知。青蛙每次最多跳 L,初始在 0。
現在可以在河中再放一些石子,要求在保證青蛙可以跳到 m 的情況下,使得青蛙在跳的步數最少的情況下次數最多。

Analysis:

好題!
。。。對已經存在的石子排序。從前往後一次處理。。。如果這一步可以一步跳過去,要討論是否青蛙上一步就已經可以跳過去了。(相當於雙方在博弈,到這裡主要是知道需要保存上一步跳的距離 ll)。。如果一步跳不過去,那麼可以知道每 (l+1) 長度至多需要跳兩步。設這兩步分別是aa,bb:

ll + aa = l+1
aa + bb = l+1

可知不會影響 ll,那麼對直接用距離對 (l+1) 取模,可以規約到前面的情況。

//}/* .................................................................................................................................. */

const int N = int(1e5) + 9;
int n;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    Rush{
        int n, m, l; RD(n, m, l); int x = 0, ll = l, c = 0;
        VI I; REP(i, n) I.PB(RD()); I.PB(m); UNQ(I); ECH(i, I){

            int d = *i - x; x = *i; if (d >= (l+1)){
                c += d / (l+1) * 2;
                d %= (l+1);
            }

            if (d + ll <= l){
                ll += d;
            }
            else{
                ll = d;
                ++c;
            }
        }
        OT(c);
    }
}

http://vjudge.net/vjudge/problem/viewSource.action?id=2788406

Problem 1008. Hilarity

Brief description:

給定一棵邊權為 0/1 的樹,要求支持兩類操作:
1. 詢問有多少條路徑 xor 和為 1。
2. 修改一條邊的權值。

Analysis:

。。(u, v) 路徑的 xor 和。。。等價於 (1, u) xor (1, v)。。
。。於是用線段樹維護所以從 (1, x) 的路徑就可以了。。
。。修改操作等價於區間取反。

http://vjudge.net/vjudge/problem/viewSource.action?id=2773880

Problem 1009. Instrusive

Brief description:

給定一個 N*N 的格子,從 MT ,有些格子中有初始狀態指向東西南北的攝像頭,每 1s 順時針轉動 90 度,監控範圍為攝像頭所在的格子和它指向的一個格子。如果當前格子和下一個格子出發時刻都沒被監,則移動的代價是 1s,否則移動需要 3s。可以等待不動,無論當前時刻是否被監控,等待的代價都是 1s。求最少的時間。

Analysis:

Dijkstra,題意不是很清楚,幾乎無法一遍 AC。。。

題意
但從A格子走到B格子,其實時刻Ax,到達B的時刻Ax+1,如果在Ax時刻AB格子均不被照且AB格子均不是照相機,但是Ax+1時刻B被照,那麼這個代價是1還是3?
team0227 北京航空航天大學 at 2014-09-21 16:25:40

RE:題意
1
admin at 2014-09-21 16:27:16                 

http://vjudge.net/vjudge/problem/viewSource.action?id=2784472