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
