2014 ACM/ICPC Asia Regional Beijing Online
A.Always Cook Mushroom
给定一个1000x1000的点阵，m组询问，每次询问一个由(0,0)、(x,0)点一以及从原点出发的方向向量(a,b)构成的直角三角形包围的点的权值和。
预处理出这1e6个点的极角关系序，离线，将询问也按(a,b)的极角排序。然后只需想象一根表针在逆时针的扫，把扫过的点的权值加到树状数组中，对于每一个询问也仅仅是一个前缀和。
- 这题其实还是挺简单的啊……前期读错题了到后面也没来得及看。
- 叉姐说存在一个枚举1000x1000个点极角序的方法，就免去了排序的过程。(法雷序列)
B.Building
平面上有n个建筑，每个建筑由$(x_i,h_i)$表示，m组询问在某一个点能看到天空的视角范围大小。
离线。可以看出对于每个询问视角的左半边和右半边是独立的，可以分开做。每一边都是寻找一个点最远能看到哪个点，就是一个求凸包的过程。
C.Cowboy
（坑）
D.Delivery
n个柜台每个柜台服务的时间都满足指数分布$t=p(k)$，求$min(p(k)+t)$的期望…… 枚举哪一个柜台是最小的，计算出对应概率和期望。 最后再将期望按概率加权平均。 然后就能推出来答案为$\frac{n+1}{\sum{k_i}}$ 指数分布一个有趣的特性是没有后效性，所以可以猜猜$c_i$是没有用的。
- 给猜出答案的队伍跪了。
E.Explosion
n个房间每个房间里面有一把或多把钥匙可以打开其他的门。如果手上没有钥匙可以选择等概率随机选择一个门炸开，求用炸弹数的期望。
每个房间期望都是可加的。 单独考虑一个房间，如果有k个房间被炸开都会导致这个房间被打开。那么炸一次这个房间被打开的概率即为$\frac{k}{n}$。也就意味着为了把这个房间打开的期望炸的次数为$\frac{n}{k}$。全部加起来后除以n即可。
至于怎么求每个房间的k。暴力是$O(n^3)$的，但想到可以使用bitset这样的黑科技，复杂度就大概是$O(\frac{n^3}{64})$了。
F.Frog
有只青蛙踩石子过河，河宽m，有n个石子坐标已知。青蛙每次最多跳L。现在可以在河中再放一些石子，使得青蛙过河跳的次数最多。
青蛙的策略肯定是尽可能往远的跳。如果它现在在cur位置跳不动了，且它上一次所在位置为pre。那么God肯定要把新石子放在$max(cur,pre+L)+1$的位置。这样可以保证每次青蛙能前进的长度最短。
肯定不能暴力直接做，但可以发现没有石子着陆时青蛙都是每两步跳L+1的距离，就能利用周期优化暴力的过程。
G.Grade
签到题
H.Hilarity
给定一棵树，边权为0/1。m个操作支持翻转一条边的权值或者询问树上有多少条路径的边权和为奇数。
因为只在乎奇偶性，可以看做求有多少条路径的xor值为1。 随便找个根dfs出根到每个节点路径的xor值d[x]，那么很明显路径的xor值就是两个端点的d[]的xor值。 这样这个问题就比较喜闻乐见了，而修改仅仅是翻转在dfs序上的一个区间，线段树就可以做了。
- 这题就是数据范围有点奇怪，带偏了整个队的想法……
I.Instrusive
题意不是很清楚的题。 总之只有人要以隐身状态的情况下移动时代价为3，其余都为1。
J.Just A Challenge
（坑）