APIO2021 简要题解
command_block
2021-07-12 15:10:31
# T1 [六边形领域](https://www.luogu.com.cn/problem/P7598)
阴间题，当不存在。
有好哥哥教我做吗 /kel
# T2 [雨林跳跃](https://www.luogu.com.cn/problem/P7599)
**题意** : 给出一个长度为 $n$ 的排列 $A$ 。
当玩家在位置 $u$ ，当且仅当满足下列两个条件之一，能一步移动到 $v$。
- $A_v$ 是 $A_u$ 左侧第一个大于 $A_u$ 的。
- $A_v$ 是 $A_u$ 右侧第一个大于 $A_u$ 的。
记 $dis(u,v)$ 表示从 $u$ 出发到达 $v$ 所需的最小步数。若不能办到，则定义为 $+\infty$。
每次询问给出 $l_1,r_1,l_2,r_2$ ，求 $\min_{u\in[l_1,r_1],v\in[l_2,r_2]}dis(u,v)$。
$n\leq 2\times 10^5,q\leq 10^5,\ l_1\leq r_1<l_2\leq r_2$ ，时限$\texttt{3s}$。
------------
先用单调栈求出每个位置的两条出边。
- 求单个 $dis(u,v)$
途中的权值必然单调增加，若到达 $A_p>A_v$ 则不再能到达 $A_v$。
若 $\max A_{[u,v)}>A_v$ 则 $u$ 必不能到达 $v$ ，反之则必然存在到达 $v$ 的方案，证明略。
每一步只有两种决策，若目的地 $>A_v$ 则排除。
若两种决策都可选，则贪心地选择更大的一个。
- **证明** ： 对于 $u$ 左右两侧的目的地 $l,r$ ，它们的后继都不可能经过区间 $[l,r]$ ，于是可以缩成一个点考虑。
命题等价于，在同一个位置 $u$ ，将 $A_u$ 在不超过 $A_v$ 的前提下尽量增大，是否更优。答案是肯定的。
观察我们的决策，先会不断选择两侧更大的一个，然后会不断向右跳。
用倍增加速求解即可。
- $u\in[l_1,r_1]$ 时
若 $[l_1,r_1]$ 中的某个 $u$ 走起一步却仍然在 $[l_1,r_1]$ 内，必不优。
于是也可以将 $[l_1,r_1]$ 缩成一个点考虑。取有解（满足 $\max A_{u\sim l_2-1}<A_v$ ）的最大的起点即可。
可以 ST 表加二分求解出最长合法后缀，再取出其中的最大值。
- $v\in[l_2,r_2]$ 时
有解的条件是 $\max A_{[l_2,r_2]}>\max A_{[r_1,l_2)}$。
仍然用上一部分的方法确定 $u$ 。
讨论结束的最后一步 $p\rightarrow v$。
若 $p\in(r_1,l_2)$ ，则必然是 ${\rm arg}\max A_{(r_1,l_2)}$ 。
若 $p\in[l_1,r_1]$ ，则答案为 $1$ ，判据为 $A_u>\max A_{(r_1,l_2)}$。
若 $p\in[1,l_1)$ ，则必然是 $A_{[1,l_1)}$ 有解的最大值，同样二分求出。
复杂度 $O((n+q)\log n)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#define MaxN 200500
using namespace std;
const int INF=1000000000;
#define Pr pair<int,int>
#define fir first
#define sec second
#define mp make_pair
struct ST{
Pr t[20][MaxN];
int lg2[MaxN];
Pr qry(int l,int r){
int k=lg2[r-l+1];
return max(t[k][l],t[k][r-(1<<k)+1]);
}
void Init(int n,int *x)
{
for (int i=1;i<=n;i++)t[0][i]=mp(x[i],i);
for (int i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1;
for (int j=1;(1<<j)<=n;j++)
for (int i=1;i+(1<<j)-1<=n;i++)
t[j][i]=max(t[j-1][i],t[j-1][i+(1<<j-1)]);
}
}T;
int h[MaxN],stk[MaxN],tl[MaxN],tr[MaxN]
,f[20][MaxN],fr[20][MaxN],fl[20][MaxN];
void init(int n, std::vector<int> _H)
{
for (int i=1;i<=n;i++)h[i]=_H[i-1];
T.Init(n,h);
h[0]=INF;
for (int i=1,top=0;i<=n;i++){
while(top&&h[i]>h[stk[top]])top--;
tl[i]=stk[top];stk[++top]=i;
}
for (int i=n,top=0;i;i--){
while(top&&h[i]>h[stk[top]])top--;
tr[i]=stk[top];stk[++top]=i;
}
for (int i=1;i<=n;i++){
f[0][i]=(h[tl[i]]>h[tr[i]]) ? tl[i] : tr[i];
fr[0][i]=tr[i];fl[0][i]=tl[i];
}
for (int j=1;j<=17;j++)
for (int i=1;i<=n;i++){
f[j][i]=f[j-1][f[j-1][i]];
fr[j][i]=fr[j-1][fr[j-1][i]];
fl[j][i]=fl[j-1][fl[j-1][i]];
}
}
int minimum_jumps2(int u, int v)
{
int ans=0;
for (int k=17;k>=0;k--)
if (h[f[k][u]]<=h[v])
{u=f[k][u];ans+=(1<<k);}
for (int k=17;k>=0;k--)
if (h[fr[k][u]]<=h[v])
{u=fr[k][u];ans+=(1<<k);}
return ans;
}
int minimum_jumps3(int u, int v)
{
int ans=0;
for (int k=17;k>=0;k--)
if (h[f[k][u]]<=h[v])
{u=f[k][u];ans+=(1<<k);}
for (int k=17;k>=0;k--)
if (h[fl[k][u]]<=h[v])
{u=fl[k][u];ans+=(1<<k);}
return ans;
}
int minimum_jumps(int l1, int r1, int l2, int r2)
{
l1++;r1++;l2++;r2++;
int lim=T.qry(l2,r2).fir;
if (T.qry(r1,l2-1).fir>lim)return -1;
int l=l1,r=r1,mid;
while(l<r){
mid=(l+r)>>1;
if (T.qry(mid,l2-1).fir<lim)r=mid;
else l=mid+1;
}
int u=T.qry(r,r1).sec,ans=INF;
if (h[u]>=T.qry(r1,l2-1).fir)return 1;
ans=min(ans,minimum_jumps2(u,T.qry(r1,l2-1).sec)+1);
if (1<l1){
int l=1,r=l1-1,mid,lim2=T.qry(l1,l2-1).fir;
while(l<r){
mid=(l+r+1)>>1;
if (T.qry(mid,l1-1).fir>lim2)l=mid;
else r=mid-1;
}
int v=T.qry(l,l1-1).sec;
if (lim2<h[v]&&h[v]<lim)
ans=min(ans,minimum_jumps3(u,v)+1);
}return ans;
}
```
# T3 [封闭道路](https://www.luogu.com.cn/problem/P7600)
- 重题 ： [CF1119F Niyaz and Small Degrees](https://www.luogu.com.cn/problem/CF1119F)
**题意** : 给出一棵 $n$ 个点的树，边有边权。
对于每个 $k=1\sim n$ ，要求选出一个边的集合，使得每个点连接的未选择的道路的个数 $\leq k$ ，且这个边集的边权和最小。
$n\leq 10^5$ ，时限$\texttt{1s}$。
------------
> 树的性质如此特殊，不要先入为主大搞模拟费用流，即使搞了，也应该即使止损，更不能由此支配对难度的判断。
最小化删去的边权和，等同于最大化保留的边权和。
考虑对于单个 $k$ 如何求解。
进行 DP ，记 $f_{u,0/1}$ 表示在 $u$ 的子树内， $u$ 与父亲之间的边“保留/不保留”，所选的最大边权和。
在处理 $u$ 点时，对于直接儿子 $v$ ，若选择边 $(u,v)$ 则贡献为 $f_{v,1}+w_{(u,v)}$ ，否则为 $f_{v,0}$。
对于 $f_{v,1}+w_{(u,v)}\leq f_{v,0}$ 的 $v$ ，显然选择后者。
对于其余的 $v$ ，若不足 $k$ 个，则全选前者。否则选增益较大的前 $k$ 个。（用排序处理）
对于 $f_{u,1}$ ，则相当于预支了一个度数，选前 $k-1$ 个即可。
接下来对所有 $k$ 进行求解。
当 $k$ 较大时限制会很松，具体地，对于度数 $\leq k$ 的点，可以看做没有限制。
我们将度数 $\leq k$ 的点称为小点，度数 $>k$ 的点称为大点。
我们只对大点进行 DP 来决策。DP 所涉及的总点数是 $O(\sum_{u}\sum_{i=1}^n[d_i>i])=O(\sum d_i)=O(n)$ ，可以保证。
对于小点，内部的边全部选择。“边界”上的边则加入度数 $>k$ 的点的 DS（用以维护排序）中。
将 $k$ 从小大处理，对于某条边，先为小点内部的边，然后一头小一头大（插入 DS 中），最后为大点内部的边（从 DS 中删除，等到 DP 时再加入）。
我们需要一个如下的数据结构 ：
- 插入删除
- 求前 $k$ 大的和。其中 $k$ 单调增加。
这可以用动态开点权值线段树来完成。时空复杂度为 $O(n\log n)$。
```cpp
```