NOIP2023模拟19联测40
异或连通
类似于线段树分治，但是可以在 \(trie\) 树上做。首先根据询问建一棵 \(trie\) 树，然后现在考虑将边插到树上。设插入的边权为 \(c_i\)，因为 \(c_i^x<K\)，所以我们压着上界走，考虑每一位 \(i\)，如果 \(K\) 在第 \(i\) 位上位 \(1\)，那么假如 \(c_i\) 在这位上位 \(1\)，那么在 \(1\) 的儿子上可以压入这条边，而且这个点下面的值异或起来都不会大于 \(K\)。然后再用一个可撤销并查集就可以了。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,m,q,k;
struct asd{
int x,y,c;
}a[N];
int Q[N];
int tr[N*100][2],idx=0;
unordered_map<int,int> rk;
void insert(int x,int p){
int u=0;
for(int i=32;i>=0;i--){
int ch=((x>>i)&1);
if(!tr[u][ch]) tr[u][ch]=++idx;
u=tr[u][ch];
}
rk[p]=u;
}
vector<int> s[N*100];
void updata(int x){
int w=a[x].c;
int u=0;
for(int i=32;i>=0;i--){
int p=((k>>i)&1);
int ch=(((k^w)>>i)&1);
if(p==1 && tr[u][(w>>i)&1]) s[tr[u][(w>>i)&1]].push_back(x);
u=tr[u][ch];
if(!u) break;
}
}
struct qwe{
int x,fx,siz;
}b[N*10];
int top=0;
int fa[N],siz[N];
int get_fa(int x){
if(fa[x]==x) return x;
else return get_fa(fa[x]);
}
int ans=0;
unordered_map<int,int> anss;
void dfs(int x){
int lim=top;
for(int p=0;p<s[x].size();p++){
int i=s[x][p];
int fx=get_fa(a[i].x),fy=get_fa(a[i].y);
if(fx==fy) continue;
if(siz[fx]>siz[fy]){
b[++top]={fy,fx,siz[fx]};
ans=ans-(siz[fx]-1)*siz[fx]/2;
ans=ans-(siz[fy]-1)*siz[fy]/2;
fa[fy]=fx;
siz[fx]+=siz[fy];
ans=ans+(siz[fx]-1)*siz[fx]/2;
}
else{
b[++top]={fx,fy,siz[fy]};
ans=ans-(siz[fx]-1)*siz[fx]/2;
ans=ans-(siz[fy]-1)*siz[fy]/2;
fa[fx]=fy;
siz[fy]+=siz[fx];
ans=ans+(siz[fy]-1)*siz[fy]/2;
}
}
anss[x]=ans;
if(tr[x][0]) dfs(tr[x][0]);
if(tr[x][1]) dfs(tr[x][1]);
while(top>lim){
fa[b[top].x]=b[top].x;
ans-=(siz[b[top].fx]-1)*siz[b[top].fx]/2;
siz[b[top].fx]=b[top].siz;
ans+=(siz[b[top].fx]-1)*siz[b[top].fx]/2+(siz[b[top].x]-1)*siz[b[top].x]/2;
top--;
}
}
signed main(){
// freopen("data.in","r",stdin);
// freopen("cnt.out","w",stdout);
freopen("xor.in","r",stdin);
freopen("xor.out","w",stdout);
scanf("%lld%lld%lld%lld",&n,&m,&q,&k);
for(int i=1;i<=m;i++) scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].c);
for(int i=1;i<=q;i++){
scanf("%lld",&Q[i]);
insert(Q[i],i);
}
for(int i=1;i<=m;i++){
if(a[i].x==a[i].y) continue;
updata(i);
}
for(int i=1;i<=n;i++){
fa[i]=i,siz[i]=1;
}
dfs(1);
for(int i=1;i<=q;i++){
printf("%lld\n",anss[rk[i]]);
}
}
民主投票
设 \(dp_{i,u}\) 表示当前子树为 \(i\)，且子树内每个点票数不大于 \(u\)，此时这个子树需要向祖先贡献的票数，显然当 \(dp_{1,u}=0\) 时，\(u\) 是成立的。
那么我们可以二分一个 \(u\)，然后找到一个最小的 \(u\)，然后进行讨论。
如果一个点的子树（排除自己）大小大于 \(u\)，那么这个点可以获胜，如果一个点子树大小小于 \(u\)，那么这个点不可能获胜，因为需要严格大于，所以思考等于的情况。
我们可以求一个 \(u-1\) 时的 \(dp\) 状态，然后考虑一个子树为 \(u\) 的点 \(x\)，那么这个点 \(dp\) 肯定为 \(0/1\)，现在我们要让这个点票数为 \(u\)，相当于贡献减少 \(1\)，然后要通过一系列操作让 \(dp_1\) 边为 \(0\)。那么肯定 \(dp_x=0\) 肯定无解，那么考虑向上传递，没会会让到根路径上的点 \(dp\) 减一，然后发现如果为 \(0\)，那么就传递不动，也就无法影响根，所以无解。还要保证根的 \(dp\) 为 \(1\)，因为只能减少 \(1\) 的贡献使之变为 \(0\)。
标签：fy,NOIP,int,siz,top,36,fx,ans,模拟 From： https://www.cnblogs.com/jinjiaqioi/p/17837396.html