题意:给出长度为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("%d\n",query(y)); } return 0; }题意:n个结点的树,第i个结点权值为a[i].定义u的价值为gcd(u,fa[u]...rt). n,a[i]<=2e5.求第i个结点最大价值时,可以将某个结点的权值变为0一次.问i=1..n的最大价值? 求某个u的最大价值时, 2种情况. u变为0,res为pre[fa[u]] u不为0,res为pre[u],或者a[u]的某个因子.暴力记录当前路径中的因子出现频率.遍历完u子树后删除a[u]因子,复杂度为O(nsqrt(n)). #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; }
