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 的格子,從 M
到 T
,有些格子中有初始狀態指向東西南北的攝像頭,每 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