期望得分： (0+30+30 = 60)
实际得分：(0+40+36=76)
数据水了点，暴力分多拿了点，但还是一道题都不会做。
T1 折纸游戏
题意描述
有一张纸平放在桌面上，划分为 (n imes m) 个格子，它们构成了 (n) 行 (m) 列的网格，每个格子大小相同。第 (i) 行第 (j) 列的格子的颜色为 (c_{i,j}) 。
每次折叠操作可以描述为：
- 将当前的纸沿着一条平行于边界且不穿过任何一个格子的线划分为 (A,B) 两个部分，且 (S_Aleq S_B) （(S_A) 为 (A) 的面积，这样 (A) 折叠后不会覆盖到当前纸的外面）。
- 将 (A) 沿着这条线折叠并覆盖到 (B) 的关于这条线的对称位置上，并保持 (B) 的位置不变。
- 必须保证折叠后 (A,B) 重合在一起的格子颜色相同。
- 折叠之后原来的 (B) 即看成新的一张纸。
你可以进行任意多次这个操作。
你需要求出有多少个子矩形满足它固定在桌面上不动时，可以将其余部分全部折到它上面。
数据范围： (n,mleq 3000,n imes mleq 10^6)
solution
不会做，咕咕咕。
T2 爬上山顶
题意描述
给出一些山顶的坐标 ((x_i,y_i)) ，我们认为山是这些山顶构成的一段折线 (l)，其中每条线段连接 ((x_i,y_i)) 和 ((x_{i+1},y_{i+1})) ((1leq ileq n))（保证 (x_i) 单调递增）。
每到一个山顶以后，你会左右张望找到能看到的最高的山顶 (P)（一个山顶 (P) 能被他们看到当且仅当连接你与 (P) 的线段与 (l) 只在你和 (P) 上相交），并向到目前为止你看到过的最高的山顶那个方向继续前进（爬到左边相邻的一个山顶或右边相邻的一个山顶）。
爬到最高的山顶后你会停下来。
对于每个山顶，求出若你选择此处作为爬山起点的话，你会爬过几个山顶（重复经过算多次，不同的询问相互独立）。
注意：(y) 坐标相同情况下选取 (x) 坐标最大的为最高山顶。
数据范围：(1leq nleq 5 imes 10^5,x_i,y_ileq 10^6)
solution
首先，我们可以求出 (l_i,r_i) 分别表示 从 ((x_i,y_i)) 向左右两边能看到的最高的山顶。
不难发现 (l_i) 为前 (i) 个点构成的上凸壳中的倒数第二个点， (r_i) 为后 (i) 个点构成的上凸壳中第二个点。
有了 (l_i,r_i) 我们很容易求出 (to_i) 表示从 ((x_i,y_i)) 能看到的最高的山峰。
我们是往看到过的最高的山顶方向前进，也就是说当前在 (i) 点的前进方向可能不是 (to_i) 。
假设当前看到的最高的山顶为 (h = y_{to_i}) ，找到一个 (j) 满足 (y_{to_j} > h) ，那么到 (j) 之前我们的方向是不会改变的。
记 (pre[i]) 为 (i) 左边满足 (y_{to_i} < y_{to_j}) 的最大的 (j) （(y_i) 相等的情况下，就比较横坐标的大小），如果不存在则 (pre[i] = to[i])。
记 (suf[i]) 为 (i) 右边满足 (y_{to_i} < y_{to_j}) 的最小的 (j) （(y_i) 相等的情况下，就比较横坐标的大小），如果不存在则 (suf[i] = to[i])。
(pre[i]) 和 (suf[i]) 维护一个单调栈就可以得到。
容易发现，当 (i > to[i]) 的时候，从 (i) 走到 (pre[i]) 的时候，方向是不会改变的，且到 (pre[i]) 的时候，可以看到更高的山峰或者达到最高的山峰，此时我们的方向就会发生改变。
同理当 (i<to[i]) 的时候，从 (i) 走到 (suf [i]) 的时候，方向是不会改变的，且到 (pre[i]) 的时候，可以看到更高的山峰或者达到最高的山峰，此时我们的方向就会发生改变。
因此，如果 (i>to[i]) 我们就从 (i) 向 (max(to[i], pre[i])) 连一条边权为 (i-max(to[i],pre[i])) 的边。
若 (i<to[i]) 就从 (i) 向 (min(to[i],suf[i])) 连一条边权为 (min(to[i],suf[i])) 的边。
不难发现，这样建图会构成一棵树。
(i) 号点的答案则为 (i) 到根节点的距离。
复杂度：(O(n))
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 5e5+10;
int n,st,top,tot;
int ls[N],rs[N],pre[N],net[N],dis[N],sta[N],head[N],to[N],x[N],y[N],k[N];
struct node
{
int to,net,w;
}e[10000010];
void add(int x,int y,int w)
{
e[++tot].to = y;
e[tot].w = w;
e[tot].net = head[x];
head[x] = tot;
}
int pmax(int i,int j)
{
if(y[i] == y[j]) return x[i] > x[j] ? i : j;
else return y[i] > y[j] ? i : j;
}
double slope(int i,int j)
{
return 1.0*(y[j]-y[i])/(x[j]-x[i]);
}
bool pd(int i,int j)
{
if(y[to[i]] == y[to[j]]) return x[to[i]] > x[to[j]];
return y[to[i]] > y[to[j]];
}
void dfs(int x,int fa)
{
for(int i = head[x]; i; i = e[i].net)
{
int to = e[i].to;
if(to == fa) continue;
dis[to] = dis[x] + e[i].w;
dfs(to,x);
}
}
signed main()
{
freopen("mountain.in","r",stdin);
freopen("mountain.out","w",stdout);
scanf("%d",&n);
for(int i = 1; i <= n; i++)
{
scanf("%d%d",&x[i],&y[i]);
if(y[i] >= y[st]) st = i;
}
sta[++top] = 1; sta[++top] = 2; ls[1] = 1; ls[2] = 1;
for(int i = 3; i <= n; i++)
{
while(top > 1 && slope(sta[top],sta[top-1]) < slope(i,sta[top-1])) top--;
ls[i] = sta[top]; sta[++top] = i;
}
top = 0; sta[++top] = n; sta[++top] = n-1; rs[n] = n; rs[n-1] = n;
for(int i = n-2; i >= 1; i--)
{
while(top > 1 && slope(sta[top],sta[top-1]) > slope(i,sta[top-1])) top--;
rs[i] = sta[top]; sta[++top] = i;
}
for(int i = 1; i <= n; i++) to[i] = pmax(ls[i],rs[i]);
top = 0;
for(int i = 1; i <= n; i++)
{
while(top && pd(i,sta[top])) top--;
if(top) pre[i] = sta[top];
else pre[i] = to[i];
sta[++top] = i;
}
top = 0;
for(int i = n; i >= 1; i--)
{
while(top && pd(i,sta[top])) top--;
if(top) net[i] = sta[top];
else net[i] = to[i];
sta[++top] = i;
}
for(int i = 1; i <= n; i++)
{
if(i == st) continue;
if(i > to[i]) add(max(to[i],pre[i]),i,i-max(pre[i],to[i]));
if(i < to[i]) add(min(to[i],net[i]),i,min(to[i],net[i])-i);
}
dfs(st,0);
for(int i = 1; i <= n; i++) printf("%d
",dis[i]);
fclose(stdin); fclose(stdout);
return 0;
}
T3 鸽子饲养
题目描述
小 K 养了 (n) 只鸽子，这 (n) 只鸽子可以看成平面直角坐标系内的 (n) 个固定的整点。
同时，为了看住这些格子，小 K 可以在 (m) 个给定的点上选择其中的若干个点安装监视器。
对于一只鸽子，它被监视当且仅当下面三个条件之一成立：
- 这只鸽子的位置恰好和某个监视器重合。
- 这只鸽子在其中两个位置不同的监视器连接形成的线段上。
- 这只鸽子在三个不共线的监视器所构成的三角形内。
现在小 K 要让所有鸽子都被监视，请问他最少需要选择多少个给定的位置设置监视器。
数据范围：(nleq 10^5,mleq 500)
solution
简化题意：求一个最小的凸多边形，满足凸多边形的顶点为 (m) 个节点之一，且包含给定的 (n) 个点。
先把给定的 (m) 个点，按极角排序。
新建一个图，对于点 (i,j) 如果满足给定的 (n) 个点都在直线 (l_{i,j}) 的左侧，则 (i) 向 (j) 连一条边。
不难发现，求的最小凸多边形等价于新图中的最小环。
最小环可以用 (Floyed) 求出来。
现在问题转化为怎么判断 (n) 个点都在直线 (l_{i,j}) 的左侧。
暴力做的复杂度是 (O(nm^2)) 。
但实际上我们只需要判断离 直线 (l_{i,j}) 最远的两个点是否在 (l_{i,j}) 的左侧。
显然离直线 (l_{i,j}) 最远的点肯定在 (n) 个点构成的凸包上。
把凸包分为上下两个凸壳，然后在凸壳上二分即可。
横坐标最大/小的两个点要拿出来特判一下。
复杂度：(O(nlogn+m^2logn+m^3))
Code
//太难写了，咕咕咕