CF 842D Vitya and Strange Lesson 01Trie(mex)

题意:给出长度为n的序列a,m次操作,第i次操作将序列中每个元素与x[i]异或.求出此时序列的mex值.
n,m,a[i]<=3e5.

第i次操作后 序列中的第i个元素为 a[i]^x[1]^x[2]..x[i]=a[i]^(x[1]^x[2]..x[i])=a[i]^y[i].
问题相当于将A中每个元素与y[i]异或后求出此时的mex.

a[i]<=3e5,令全集V={0,1,2,...2*3e5},B=V-A.
mex(A)=min(V-A)=min(B)
A'=A^y[i], mex(A')=min(V-A')=min(B')=min(B^x). 
取任意一个b[i]^x 都属于B'.
proof:若存在b[i]^x属于V-B'=A' 即b[i]^x=a[j]^x 即b[i]=a[j] 与A,B交集为空集矛盾.

问题转换问求min(B^y[i]) 初始B插入Trie中 找到B^y[i]最小值就好了.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
const int N=3e5+20,inf=0x3f3f3f3f,M=3e5;
int vis[N*2];
int ch[N*32][2],num[N*32],sz;
void init()
{
memset(ch[0],0,sizeof(ch[0]));
memset(num,0,sizeof(num));
sz=1;
}
void insert(int x)
{
int u=0;
for(int i=20;i>=0;i--)
{
int c=(x>>i)&1;
if(!ch[u][c])
{
memset(ch[sz],0,sizeof(ch[sz]));
ch[u][c]=sz++;
}
u=ch[u][c];
}
num[u]=x;
}
int query(int x)
{
int res=0,u=0;
for(int i=20;i>=0;i--)
{
int c=(x>>i)&1;
if(ch[u][c])
u=ch[u][c];
else
u=ch[u][c^1],res|=(1<<i);
}
return num[u]^x;
}
int main()
{
init();
int n,m,x;
cin>>n>>m;
for(int i=1;i<=n;i++)
scanf("%d",&x),vis[x]=1;
for(int i=0;i<=M*2;i++)
if(!vis[i])
insert(i);
int y=0;
while(m--)
{
scanf("%d",&x);
y^=x;
printf("%dn",query(y));
}
return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
const int N=4e5+20,inf=0x3f3f3f3f;
int n,a[N],pre[N],cnt[N];
vector<int> e[N];
int dp[N];
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
void update(int x,int val)
{
for(int i=1;i*i<=x;i++)
{
if(x%i==0)
{
cnt[i]+=val;
if(i*i!=x)
cnt[x/i]+=val;
}
}
}
void dfs(int u,int fa,int dep)
{
update(a[u],1);
if(fa==0)
{
pre[u]=a[u];
dp[u]=a[u];
}
else
{
pre[u]=gcd(a[u],pre[fa]);
int mx=1;
for(int i=1;i*i<=a[u];i++)
{
if(a[u]%i==0)
{
if(cnt[i]>=dep-1)
mx=max(mx,i);
if(cnt[a[u]/i]>=dep-1)
mx=max(mx,a[u]/i);
}
}
dp[u]=max(mx,pre[fa]);
}
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i];
if(v==fa)	continue;
dfs(v,u,dep+1);
}
update(a[u],-1);
}
int main()
{
int n,u,v;
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n-1;i++)
{
scanf("%d%d",&u,&v);
e[u].push_back(v),e[v].push_back(u);
}
dfs(1,0,1);
for(int i=1;i<=n;i++)
{
int res=max(pre[i],dp[i]);
printf("%d%c",res,i==n?'n':' ');
}
return 0;
}

最后

以上就是糊涂鸵鸟最近收集整理的关于CF 842D Vitya and Strange Lesson 01Trie(mex)的全部内容，更多相关CF内容请搜索靠谱客的其他文章。