期望得分： \(0+30+30 = 60\)
实际得分：\(0+40+36=76\)
数据水了点，暴力分多拿了点，但还是一道题都不会做。
T1 折纸游戏
题意描述
有一张纸平放在桌面上，划分为 \(n\times m\) 个格子，它们构成了 \(n\) 行 \(m\) 列的网格，每个格子大小相同。第 \(i\) 行第 \(j\) 列的格子的颜色为 \(c_{i,j}\) 。
每次折叠操作可以描述为：
- 将当前的纸沿着一条平行于边界且不穿过任何一个格子的线划分为 \(A,B\) 两个部分，且 \(S_A\leq S_B\) （\(S_A\) 为 \(A\) 的面积，这样 \(A\) 折叠后不会覆盖到当前纸的外面）。
- 将 \(A\) 沿着这条线折叠并覆盖到 \(B\) 的关于这条线的对称位置上，并保持 \(B\) 的位置不变。
- 必须保证折叠后 \(A,B\) 重合在一起的格子颜色相同。
- 折叠之后原来的 \(B\) 即看成新的一张纸。
你可以进行任意多次这个操作。
你需要求出有多少个子矩形满足它固定在桌面上不动时，可以将其余部分全部折到它上面。
数据范围： \(n,m\leq 3000,n\times m\leq 10^6\)
solution
不会做，咕咕咕。
T2 爬上山顶
题意描述
给出一些山顶的坐标 \((x_i,y_i)\) ，我们认为山是这些山顶构成的一段折线 \(l\)，其中每条线段连接 \((x_i,y_i)\) 和 \((x_{i+1},y_{i+1})\) \((1\leq i\leq n)\)（保证 \(x_i\) 单调递增）。
每到一个山顶以后，你会左右张望找到能看到的最高的山顶 \(P\)（一个山顶 \(P\) 能被他们看到当且仅当连接你与 \(P\) 的线段与 \(l\) 只在你和 \(P\) 上相交），并向到目前为止你看到过的最高的山顶那个方向继续前进（爬到左边相邻的一个山顶或右边相邻的一个山顶）。
爬到最高的山顶后你会停下来。
对于每个山顶，求出若你选择此处作为爬山起点的话，你会爬过几个山顶（重复经过算多次，不同的询问相互独立）。
注意：\(y\) 坐标相同情况下选取 \(x\) 坐标最大的为最高山顶。
数据范围：\(1\leq n\leq 5\times 10^5,x_i,y_i\leq 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\n",dis[i]);
fclose(stdin); fclose(stdout);
return 0;
}
T3 鸽子饲养
题目描述
小 K 养了 \(n\) 只鸽子，这 \(n\) 只鸽子可以看成平面直角坐标系内的 \(n\) 个固定的整点。
同时，为了看住这些格子，小 K 可以在 \(m\) 个给定的点上选择其中的若干个点安装监视器。
对于一只鸽子，它被监视当且仅当下面三个条件之一成立：
- 这只鸽子的位置恰好和某个监视器重合。
- 这只鸽子在其中两个位置不同的监视器连接形成的线段上。
- 这只鸽子在三个不共线的监视器所构成的三角形内。
现在小 K 要让所有鸽子都被监视，请问他最少需要选择多少个给定的位置设置监视器。
数据范围：\(n\leq 10^5,m\leq 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
//太难写了，咕咕咕