模拟赛
疯狂补题解/改题中。。。
T1 [Permutations & Primes] (未找到)
构造一个 \(1-n\) 的序列，使所有区间中 \(mex\) 为质数的最多。
感觉题不是很好。结论是：\(1\) 放中间，\(2,3\) 放两边。
打标找规律，感性证明也挺显然的。
no code
T2 Spread of Information
首先看道典题：消防局的设立
题很水，但是思路一样，半径为 \(k\) 的最小覆盖问题就是跳 \(k\) 级祖先。
采用贪心的策略，每次找到没有被覆盖的最深的点，向上跳 \(k\) 级祖先，使当前没被覆盖的这个点刚好被覆盖。
但是这道题暴跳肯定不行，因为跳跃过程中要更新最小距离，倍增也不太好搞。
所以我们稍微变一下思路，还是跳祖先，跳到祖先直接 dfs 把能覆盖的点都标记。这样被标记的点一定不会再被跳。
虽然看着很暴力，但真的很快，而且卡不掉？
code
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n,k,a[N],dep[N],fa[N];
int head[N],tot;
struct E {int u,v;} e[N<<1];
inline void add(int u,int v) {e[++tot]={head[u],v}; head[u]=tot;}
inline int qr()
{
char ch=getchar();int x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
inline void dfs(int u,int f)
{
dep[u]=dep[f]+1; a[u]=u; fa[u]=f;
for(int i=head[u];i;i=e[i].u)
{
int v=e[i].v;
if(v==f) continue;
dfs(v,u);
}
}
inline bool cmp(int x,int y) {return dep[x]>dep[y];}
bool vs[N];
inline void fg(int u,int f,int d,int mid)
{
if(d>mid) return;
vs[u]=1;
for(int i=head[u];i;i=e[i].u)
{
int v=e[i].v;
if(v==f) continue;
fg(v,u,d+1,mid);
}
}
inline bool check(int mid)
{
int res=0;
for(int i=1;i<=n;i++) vs[i]=0;
for(int i=1;i<=n;i++) if(!vs[a[i]])
{
int u=a[i],jp=mid;
while(fa[u]&&jp) u=fa[u],jp--;
fg(u,0,0,mid);
res++;
if(res>k) return 0;
}
return 1;
}
int main()
{
n=qr(); k=qr();
for(int i=1;i<n;i++)
{
int x=qr(),y=qr();
add(x,y); add(y,x);
}
dfs(1,0);
sort(a+1,a+1+n,cmp);
int l=1,r=dep[a[1]],ans=r;
while(l<=r)
{
int mid=l+r>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
printf("%d\n",ans);
return 0;
}
还可以倍增优化一下暴跳，好像变慢了。
倍增code
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n,k,a[N],dep[N],fa[20][N],lg;
int head[N],tot;
struct E {int u,v;} e[N<<1];
inline void add(int u,int v) {e[++tot]={head[u],v}; head[u]=tot;}
inline int qr()
{
char ch=getchar();int x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
inline void dfs(int u,int f)
{
dep[u]=dep[f]+1; a[u]=u; fa[0][u]=f;
for(int i=1;i<=lg;i++) fa[i][u]=fa[i-1][fa[i-1][u]];
for(int i=head[u];i;i=e[i].u)
{
int v=e[i].v;
if(v==f) continue;
dfs(v,u);
}
}
inline bool cmp(int x,int y) {return dep[x]>dep[y];}
bool vs[N];
inline void fg(int u,int f,int d,int mid)
{
if(d>mid) return;
vs[u]=1;
for(int i=head[u];i;i=e[i].u)
{
int v=e[i].v;
if(v==f) continue;
fg(v,u,d+1,mid);
}
}
inline bool check(int mid)
{
int res=0;
for(int i=1;i<=n;i++) vs[i]=0;
for(int i=1;i<=n;i++) if(!vs[a[i]])
{
int u=a[i];
for(int j=lg;j>=0;j--) if(fa[j][u]&&dep[fa[j][u]]>=dep[a[i]]-mid) u=fa[j][u];
fg(u,0,0,mid);
res++;
if(res>k) return 0;
}
return 1;
}
int main()
{
// freopen("in.in","r",stdin);
n=qr(); k=qr(); lg=__lg(n);
for(int i=1;i<n;i++)
{
int x=qr(),y=qr();
add(x,y); add(y,x);
}
dfs(1,0);
sort(a+1,a+1+n,cmp);
int l=1,r=dep[a[1]],ans=r;
while(l<=r)
{
int mid=l+r>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
printf("%d\n",ans);
return 0;
}
T3 Ball Collector
一开始想二分图，树上遍历同时跑匈牙利。后来 GGrun 证明可以，HACK 之后 \({mathbb{MLE}}\)。
其实思路还是类似的，将同一个节点的两个颜色连边。
观察得性质，每选一个节点的颜色就相当于选一条边，如果边数大于颜色点数，那么一定可以选中所有颜色。否则有多少条边就能选多少种颜色。
因此对于我们以颜色为点建的图中，答案就是 \(\min(点数，边数)\) 。
然后考虑实时维护这个图。用到新科技：可撤销并查集。
其实原理很简单，就是在树上递归到一个点时记录这个状态，回溯时把它回归这个状态。
查询时不能路径压缩，合并时需要按秩合并（类似启发式合并，浅的合并到深的里，本题 \(sz\) 越大越深）。
好像挺简单的？
code
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n,ans[N],res,a[N],b[N],fa[N],sz[N],ed[N];
int head[N],tot;
struct E {int u,v;} e[N<<1];
inline void add(int u,int v) {e[++tot]={head[u],v}; head[u]=tot;}
int find(int x) {return fa[x]==x?x:find(fa[x]);}
struct A {int x,fa,sz,e;} g[N];
void merge(int u,int v,stack<A> &st,int &ans)
{
u=find(u); v=find(v);
st.push(A{u,fa[u],sz[u],ed[u]});
st.push(A{v,fa[v],sz[v],ed[v]});
if(u==v)
{
ed[u]++;
if(ed[u]==sz[u]) res++;
return;
}
if(sz[u]<sz[v]) swap(u,v);
ans-=min(sz[u],ed[u]); res-=min(sz[v],ed[v]);
fa[v]=u; sz[u]+=sz[v]; ed[u]+=ed[v]+1;
ans+=min(sz[u],ed[u]);
}
void dfs(int u,int f)
{
stack<A> st; int tmp=res;
merge(a[u],b[u],st,res);
ans[u]=res;
for(int i=head[u];i;i=e[i].u)
{
int v=e[i].v;
if(v==f) continue;
dfs(v,u);
}
while(!st.empty())
{
A pre=st.top(); st.pop();
fa[pre.x]=pre.fa;
sz[pre.x]=pre.sz;
ed[pre.x]=pre.e;
}
res=tmp;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
for(int i=1;i<n;i++)
{
int x,y; scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
for(int i=1;i<=n;i++) fa[i]=i,sz[i]=1,ed[i]=0;
dfs(1,0);
for(int i=2;i<=n;i++) printf("%d ",ans[i]);
return 0;
}
T4 Joker
先挂张图，咕咕咕。。。
