T1 Permutations & Primes
\(2,3\) 放两边，\(1\)，放中间，易证最优。
T2 树上游戏
原题 [ARC116E] Spread of Information
二分是明显的，关键在 check，发现每次选最深的叶子节点的 \(mid\) 级父亲一定不劣，因为它能够覆盖最多。然后每次找就行，实现比较麻烦。
设 \(f_i\) 表示 \(i\) 的子树内最远未被覆盖的点的距离，\(g_i\) 表示 \(i\) 的子树内最近是关键点的距离。初值 \(f\) 负无穷，表示被覆盖，\(g\) 正无穷，表示还没有关键点。然后分讨进行转移。
点击查看代码
#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
inline int read(){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;}
const int N=2e5+10;
int n,k,mid,res=0,f[N],g[N],dep[N];
std::vector<int> e[N];
bool vis[N];
inline void dfs(int u,int fa){
f[u]=-N,g[u]=N;
for(int v:e[u]){
if(v==fa)continue;
dfs(v,u);
f[u]=std::max(f[u],f[v]+1);
g[u]=std::min(g[u],g[v]+1);
}
if(f[u]+g[u]<=mid)f[u]=-N;
if(g[u]>mid){
f[u]=std::max(f[u],0);
}
if(f[u]==mid){
f[u]=-N,g[u]=0,++res;
}
}
signed main(){
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
n=read(),k=read();
for(int i=2;i<=n;++i){int u=read(),v=read();e[u].emplace_back(v);e[v].emplace_back(u);}
int l=1,r=n,ans=0;
r=n/k+1;
while(l<=r){
mid=l+r>>1;
res=0;
dfs(1,0);
res+=f[1]>=0;
if(res<=k)ans=mid,r=mid-1;
else l=mid+1;
}
std::cout<<ans<<'\n';
}
- \(f_i+g_i\le mid\) 表示这个点子树内的可以全覆盖，不需要进行覆盖。\(f_i=-inf\)
- \(g_i>mid\) 时，不呢覆盖当前节点，需要父亲来覆盖，\(f_i=\max(f_i,0)\)
- \(f_i=mid\) 是，这个点不得不覆盖了，\(f_i=-inf,g_i=0\)，答案加一。
对于最后的根节点，需要查看是否覆盖来增加答案。
T3 Ball Collector
原题 [ABC302Ex] Ball Collector
自然想到颜色连边，然后发现连成一棵树（\(n-1\) 条边，无自环）时可以拿到 \(n-1\) 种颜色，否则可以拿到 \(n\) 种颜色。
因为我们是按照边拿，对于树的话，从叶子开始拿最大，根节点拿不了，所以是 \(n-1\) 种颜色。
如果有环的话，就可以少贡献一条边，从而全拿。
知道这个之后就直接上可撤销并查集维护图的形态即可，因为要维护图的具体形态，所以不能路径压缩。
点击查看代码
#include<bits/stdc++.h>
#define int long long
typedef long long ll;
typedef unsigned long long ull;
inline int read(){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;}
const int N=4e5+10;
int n,a[N],b[N],dep[N],ANS[N],ans,num[N],size[N],tag[N],top,fa[N];
std::pair<int,int> st[N<<1];
std::vector<int> e[N];
inline int find(int x){return fa[x]==x?x:find(fa[x]);}
inline void add(int x,int y){
x=find(x);y=find(y);top++;
if(x==y){
if(num[x]==size[x]-1)ans++,tag[top]=1;
num[x]++,st[top]={-1,x};
}else{
if(size[x]>size[y])std::swap(x,y);
if(num[x]==size[x]-1||num[y]==size[y]-1)ans++,tag[top]=1;
size[y]+=size[x];fa[x]=y;st[top]={x,y};
num[y]+=num[x]+1;
}
}
inline void del(int id){
if(st[id].first==-1)num[st[id].second]--;
else{int x=st[id].first,y=st[id].second;fa[x]=x;size[y]-=size[x];num[y]-=num[x]+1;}
if(tag[id])ans--;
tag[id]=0;st[id]={0,0};
}
inline void dfs(int u,int fa){
int cur=top;
add(a[u],b[u]);
ANS[u]=ans;
for(int v:e[u])if(v!=fa)dfs(v,u);
while(top>cur)del(top--);
}
signed main(){
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
n=read();
for(int i=1;i<=n;++i)a[i]=read(),b[i]=read();
for(int i=2;i<=n;++i){
int u=read(),v=read();
e[u].emplace_back(v);e[v].emplace_back(u);
}
for(int i=1;i<=n;++i)size[i]=1,fa[i]=i;
dfs(1,0);
for(int i=2;i<=n;++i)std::cout<<ANS[i]<<' ';
}
T4 满穗
不会。
标签：std,ch,int,long,num,CSP,模拟,size From： https://www.cnblogs.com/Ishar-zdl/p/18327859