前言
- 比赛链接。
这次好多外校的参加 \(60\) 多个人，反正至少没怎么挂分。
确切的说赛时我只能冲 T1、T2，T3 可撤销或可持久化并查集都不会，赛后现学的，T4 更抽象，可惜 T2 打假了。T3 最后五分钟才开始看，没想直接打暴力了。
但是 T3 数据太水了，加了捆绑还是水，赛后安排了重测。
T1 Permutations & Primes
- 同名原题。
一个区间合法必须有 \(1\)，所以把 \(1\) 放中间，然后将 \(2,3\) 放到两端即可，这样只要过 \(1\) 的区间除了原序列答案一定为 \(2\) 或 \(3\)，而原序列结果是无法更改的。
T2 树上游戏
-
原题：ARC116E Spread of Information，P3523 [POI2011] DYN-Dynamite……
弱化版：P3942 将军令，P2279 [HNOI2003] 消防局的设立（不用二分）……
-
部分分 \(10pts\)：爆搜。
-
部分分 \(29pts\)：当 \(k\ge \lfloor\dfrac{n}{2}\rfloor\) 时，答案为 \(1\)。
-
正解：
先来看 P3942 将军令 这道题，是一个树形 DP，要求每个点到关键点的距离不超过 \(k\)。
定义 \(f_{x,1}\) 为 \(x\) 到其子树中最远的一个没有被覆盖到的节点的距离，\(f_{x,0}\) 为 \(x\) 到其最近一个关键点的距离。
首先若 \(f_{x,1}+f_{x,0}\le k\) 说明改棵子树都被覆盖到了，\(f_{x,1}=-1\) 即可。
从贪心的角度，若 \(f_{x,1}=k\) 时，将 \(x\) 设为关键点，正确性是显然的，这样能在使其子树全部被覆盖的同时覆盖更多点，则此时 \(f_{x,1}=-1,f_{x,0}=0\) 即可。
最后发现根节点是处理不到的，特判其有没有被覆盖，没有就在根节点设立关键点。
发现本体存在单调性，二分答案其距离 \(k\) 即可。
点击查看代码
#include<bits/stdc++.h> #define ll long long #define endl '\n' #define sort stable_sort using namespace std; const int N=2e5+10,inf=1e9; template<typename Tp> inline void read(Tp&x) { x=0;register bool z=true; register char c=getchar(); for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0; for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48); x=(z?x:~x+1); } template<typename Tp> inline void wt(Tp x) {if(x>9)wt(x/10);putchar((x%10)+'0');} template<typename Tp> inline void write(Tp x) {if(x<0)putchar('-'),x=~x+1;wt(x);} int n,k,ans,f[N][2]; vector<int>e[N]; void dfs(int x,int fa,int mid) { f[x][0]=inf,f[x][1]=0; for(int y:e[x]) { if(y==fa) continue; dfs(y,x,mid); if(f[y][1]!=-1) f[x][1]=max(f[x][1],f[y][1]+1); f[x][0]=min(f[x][0],f[y][0]+1); } if(f[x][1]>=mid) { ans++; f[x][1]=-1; f[x][0]=0; } if(f[x][1]+f[x][0]<=mid) f[x][1]=-1; } signed main() { read(n),read(k); for(int i=1,x,y;i<=n-1;i++) { read(x),read(y); e[x].push_back(y); e[y].push_back(x); } int l=1,r=n-1,answ; while(l<=r) { int mid=(l+r)>>1; ans=0; memset(f,0,sizeof(f)); dfs(1,0,mid); if(f[1][1]!=-1) ans++; if(ans<=k) r=mid-1,answ=mid; else l=mid+1; } write(answ); }
T3 Ball Collector
-
同名原题。
-
部分分 \(20pts\)：爆搜即可。
-
正解：
经典的套路，将 \(a_i,b_i\) 进行连边，最后会出来很多连通块，其边数就是其可选的个数，每个块之间互不影响。
发现若连通块为一棵树，最多选 \(size-1\) 个点，否则可以取 \(size\) 个点。
考虑连边时的贡献，将两个块 \(x,y\) 连一条边，若其中存在至少一个是树的话，则其会变成图，贡献 \(+1\)，否则没有贡献。
可以使用可撤销并查集维护，这个玩意很好打，学一下就会了。
然后还学了一下可持久化并查集，就是用类似于主席树维护并查集即可。
点击查看代码
#include<bits/stdc++.h> #define ll long long #define endl '\n' #define sort stable_sort using namespace std; const int N=2e5+10; template<typename Tp> inline void read(Tp&x) { x=0;register bool z=true; register char c=getchar(); for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0; for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48); x=(z?x:~x+1); } template<typename Tp> inline void wt(Tp x) {if(x>9)wt(x/10);putchar((x%10)+'0');} template<typename Tp> inline void write(Tp x) {if(x<0)putchar('-'),x=~x+1;wt(x);} int n,f[N],sz[N],a[N],b[N],ans[N]; vector<int>e[N]; bool vis[N]; int find(int x) {return f[x]==x?x:find(f[x]);} void dfs(int x,int fa,int sum) { ans[x]=sum; for(int y:e[x]) { if(y==fa) continue; int fx=find(a[y]),fy=find(b[y]); if(sz[fx]<sz[fy]) swap(fx,fy); if(fx==fy) { if(!vis[fx]) { vis[fx]=1; dfs(y,x,sum+1); vis[fx]=0; } else dfs(y,x,sum); } else { int last=sz[fx]; bool vx=vis[fx],vy=vis[fy]; f[fy]=fx,sz[fx]+=sz[fy],vis[fx]|=vis[fy]; if(!vx||!vy) dfs(y,x,sum+1); else dfs(y,x,sum); f[fy]=fy,sz[fx]=last,vis[fx]=vx,vis[fy]=vy; } } } signed main() { read(n); for(int i=1;i<=n;i++) { read(a[i]),read(b[i]); f[i]=i,sz[i]=1; } for(int i=1,x,y;i<=n-1;i++) { read(x),read(y); e[x].push_back(y); e[y].push_back(x); } if(a[1]==b[1]) vis[a[1]]=1; else f[b[1]]=a[1],sz[a[1]]+=sz[b[1]]; dfs(1,0,1); for(int i=2;i<=n;i++) write(ans[i]),putchar(' '); }
T4 满穗
抽象玩意，溜了溜了。
官方题解
设 \(p_i\) 表示 \([1, i]\) 内所有正整数的和， \(q_i\) 表示 \([1, i]\) 内所有负整数的和。
如果 \(i < j\) 并且 \(s_i < s_j\) ，那么有 \(\tfrac{p_i}{P} - \tfrac{q_i}{Q} < \tfrac{p_j}{P} - \tfrac{q_j}{Q}\) 。
简单移项有 \(\tfrac{p_i - p_j}{P} < \tfrac{q_i - q_j}{Q}\) 。
有 \(\tfrac{Q}{P} < \tfrac{q_i - q_j}{p_i - p_j}\) 。
发现是斜率的形式，并且 \(p\) 单调递增， \(q\) 单调递减，可以维护一个上凸包在上面二分斜率。
由于存在修改操作，我们无法维护整个序列的凸包，但是容易发现如果修改的位置为 \(i\) ，对于 \(j > i\) 和 \(j < i\) 的位置，它们的图包只发生了平移操作，其斜率未发生变化，因此考虑使用分块维护。
具体的，对序列分块，每个块内建出对应的凸包，修改操作直接将其对应块的凸包重构，其他凸包平移，查询操作，扫描整个凸包，二分找到最优点后对所有凸包取 \(\max\) 即可。
总结
没学过的知识点还是好多啊，甚至都影响模拟赛了，但是天天模拟赛又很少有时间过知识点。
T2 没想出来有点可惜，感觉差一点吧，分数就比较平凡，反正没挂分就是好的。
附录
本场比赛 rk1 可以找 chino 领取穗。
T4 游戏背景写得不错，直接剧透了某款游戏，这是 T4 的图：
这是属于 rk1 的奖励（学长画的太好了）：
