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
