Codeforces Round #113 (Div. 2)
B. Polygons
题意
- 给一个(N(N le 10^5))个点的凸包
- (M(M le 2 cdot 10^4))次询问，每次给一个点判断该点是否在凸包内。
思路
- 按(y)坐标将凸包分成两部分。
- 在左右两边二分找出夹住该点的(y)值区间，判断叉积正负。
代码
D. Shoe Store
题意
- 有(N le 10^5)双鞋，每双鞋价格为(c_i le 10^9),大小为(s_i le 10^9)，保证任意两双鞋的大小均不相同。
- 有(M le 10^5)个顾客，每个人有钱(d_i le 10^9)，以及脚的大小(l_i)。当(c_j le d_i)且(s_j = l_i or s_j-1=l_i)时，这位顾客就会买相应的鞋。每个人最多买一双鞋。
- 求最大收益。
思路
- 每个人只关心(l_i)和(l_i+1)的大小的鞋，并且每种大小的鞋只有一双，所以按(l)从小到大排序，考虑每个人买鞋状态。
- 用(f(i, st))表示到第(i)个人时，((l_i+1,l_i))是否被买的状态(st)的最大收益：
- (st)需要根据(l_i)和(l_{i-1})的大小转移。
代码
E. Tetrahedron
题意
- 一只蚂蚁从(D)点出发，每次会边走到邻近的一个顶点上，求蚂蚁走(n le 10^7)后回到(D)的方案数，modulo 1000000007。
思路
- 矩阵+快速幂
代码