题面:https://www.cnblogs.com/Juve/articles/11707775.html
位运算:
大力分类讨论
第一次发现若a^b=c,则c^b=a,c^a=b
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define int long long #define re register using namespace std; inline int read(){ re int x=0,f=1;re char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } int t,a,o,x; inline int q_pow(re int a,re int b){ re int res=1; while(b){ if(b&1) res=res*a; a=a*a; b>>=1; } return res; } inline int calc(re int x){ re int res=0; while(x){ if(x&1) ++res; x>>=1; } return res; } signed main(){ t=read(); while(t--){ a=read(),o=read(),x=read(); if(a!=-1&&o==-1&&x==-1){//only have and puts("inf"); continue; } if(a==-1&&o!=-1&&x==-1){//only have or printf("%lld\n",q_pow(3,calc(o))); continue; } if(a==-1&&o==-1&&x!=-1){//only have xor puts("inf"); continue; } if(a==-1&&o!=-1&&x!=-1){//no and re int t=o^x; if((t|o)!=o) puts("0"); else printf("%lld\n",q_pow(2,calc(x))); continue; } if(a!=-1&&o==-1&&x!=-1){//no or re int t=x^a; if((a|t)!=t) puts("0"); else printf("%lld\n",q_pow(2,calc(x))); continue; } if(a!=-1&&o!=-1&&x==-1){//no xor if((a|o)!=o) puts("0"); else printf("%lld\n",q_pow(2,calc(a^o))); continue; } if(a!=-1&&o!=-1&&x!=-1){//have all if((a|o)!=o||(a^o)!=x) puts("0"); else printf("%lld\n",q_pow(2,calc(x))); continue; } } return 0; }
集合论:
好像我打的不是正解
大力set模拟集合,在集合外加一个bas懒标记,表示集合中的数被增加了多少,查询x是否在集合中出现在set中查x-bas,插入插x-bas,
保证在加完bas后得到x
本题卡常,unordered_map也会T,只要把清空set改成新建一个空set然后赋值
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<unordered_set> 6 #define re register 7 using namespace std; 8 const int MAXN=3e6+5; 9 char xch,xB[1<<15],*xS=xB,*xTT=xB; 10 #define getc() (xS==xTT&&(xTT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xTT)?0:*xS++) 11 inline int read(){ 12 re int x=0,f=1;re char ch=getc(); 13 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();} 14 while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getc();} 15 return x*f; 16 } 17 int m,bas=0,sta[MAXN],top=0; 18 unordered_set<int>s; 19 long long ans=0ll; 20 signed main(){ 21 m=read(); 22 for(re int i=1,opt,sum;i<=m;++i){ 23 opt=read(); 24 if(opt==3){ 25 if(s.size()) ++bas; 26 } 27 if(opt==4){ 28 if(s.size()) --bas; 29 } 30 if(opt==1){ 31 sum=read(); 32 for(re int j=1,x;j<=sum;++j){ 33 x=read(); 34 if(s.find(x-bas)==s.end()){ 35 s.insert(x-bas); 36 ans+=(x-bas); 37 } 38 } 39 } 40 if(opt==2){ 41 sum=read(); 42 top=ans=0; 43 for(re int j=1,x;j<=sum;++j){ 44 x=read(); 45 if(s.find(x-bas)!=s.end()){ 46 sta[++top]=x-bas; 47 ans+=(x-bas); 48 } 49 } 50 unordered_set<int>t; 51 swap(t,s); 52 while(top) s.insert(sta[top--]); 53 } 54 printf("%lld\n",ans+(long long)bas*s.size()); 55 } 56 return 0; 57 }
连连看:我咕了
串串香:
正解是kmp,被hash完美过掉
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define int long long 6 #define ull unsigned long long 7 using namespace std; 8 const int MAXN=1e6+5; 9 const int mod=13331; 10 int t,n,m,ans; 11 ull pre[MAXN<<1],h[MAXN<<1]; 12 char ch[MAXN]; 13 signed main(){ 14 pre[0]=1; 15 for(int i=1;i<=2*MAXN-3;++i){ 16 pre[i]=pre[i-1]*mod; 17 } 18 scanf("%lld",&t); 19 while(t--){ 20 scanf("%lld%lld",&n,&m); 21 scanf("%s",ch+1); 22 for(int i=1;i<=m;++i){ 23 h[i]=h[i-1]*mod+ch[i]-'A'+1; 24 } 25 ans=0; 26 if(n==1){ 27 for(int i=m-1;i>=1;--i){ 28 if(h[i]==h[m]-h[m-i]*pre[i]){ 29 ans=i; 30 break; 31 } 32 } 33 if(ans==0) ans=-1; 34 printf("%lld\n",ans); 35 continue; 36 } 37 for(int i=1;i<=m;++i){ 38 h[i+m]=h[i+m-1]*mod+ch[i]-'A'+1; 39 } 40 for(int i=2*m-1;i>=1;--i){ 41 if(h[i]==h[2*m]-h[2*m-i]*pre[i]){ 42 ans=2*m-i; 43 break; 44 } 45 } 46 printf("%lld\n",n*m-ans); 47 } 48 return 0; 49 }
糊涂图:除了qj啥都不会
木叶下:
如果u,v相等,那么答案就是树的直径
如果u,v不想等,那么u,v,lca会构成一个环,环上的点会被保护起来,那么答案就是u,v路径上的点向下延伸的最长长度和lca处不走lca子树的最长长度
先求出对于每个点x,x的子树中的前三长的链的长度和对应的儿子
然后dfs求出每一个x,不走x的子树能走的最长长度,再求出每一个x,他的父亲不走x的最大长度,这个可以倍增,且可以用前三长链求出
然后倍增solve答案,注意在lca处是由两条路径走到的,所以要求前三大的链,保证有一条链既不过u,也不过v
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int MAXN=200005; int n,m,du[MAXN],ans=1; int to[MAXN<<1],nxt[MAXN<<1],pre[MAXN],cnt=0; void add(int u,int v){ ++cnt,to[cnt]=v,nxt[cnt]=pre[u],pre[u]=cnt; } queue<int>q; int fa[MAXN][23],deep[MAXN]; bool flag=0; int tot=0; void DFS(int x,int f){ for(int i=pre[x];i;i=nxt[i]){ int y=to[i]; if(y==f) continue; DFS(y,x); } } pair<int,int>mxx[MAXN][3]; void dfs(int x,int f){ deep[x]=deep[f]+1; fa[x][0]=f; for(int i=pre[x];i;i=nxt[i]){ int y=to[i]; if(y==f) continue; dfs(y,x); int k=mxx[y][0].first+1; if(k>mxx[x][2].first){ mxx[x][2].first=k; mxx[x][2].second=y; } if(mxx[x][2].first>mxx[x][1].first){ swap(mxx[x][2],mxx[x][1]); } if(mxx[x][1].first>mxx[x][0].first){ swap(mxx[x][0],mxx[x][1]); } } } int get(int x){ int f=fa[x][0]; for(int i=0;i<=2;++i){ if(mxx[f][i].second!=x) return mxx[f][i].first; } return 0; } int gett(int x,int y){ int f=fa[x][0]; for(int i=0;i<=3;++i){ if(mxx[f][i].second!=x&&mxx[f][i].second!=y) return mxx[f][i].first; } return 0; } int w[MAXN],ww[MAXN][23]; void dfs(int x){ ww[x][0]=get(x); w[x]=max(w[fa[x][0]],ww[x][0])+1; for(int i=pre[x];i;i=nxt[i]){ int y=to[i]; if(y==fa[x][0]) continue; dfs(y); } } int solve(int x,int y){ if(deep[x]>deep[y]) swap(x,y); int k=deep[y]-deep[x],res=mxx[y][0].first; for(int i=0;i<=20;++i) if((1<<i)&k){ res=max(res,ww[y][i]); y=fa[y][i]; } if(x==y){ res=max(res,w[x]); return res; } res=max(res,mxx[x][0].first); for(int i=20;i>=0;--i) if(fa[x][i]!=fa[y][i]){ res=max(res,max(ww[x][i],ww[y][i])); x=fa[x][i],y=fa[y][i]; } res=max(res,max(gett(x,y),w[fa[x][0]])); return res; } int main(){ scanf("%d",&n); for(int i=1,u,v;i<n;++i){ scanf("%d%d",&u,&v); add(u,v),add(v,u); ++du[u],++du[v]; if(abs(u-v)!=1) flag=1; } if(!flag){ scanf("%d",&m); while(m--){ int u,v; scanf("%d%d",&u,&v); if(u==v) printf("%d\n",n/2); else{ if(v<u) swap(u,v); printf("%d\n",max(n-v,u-1)); } } return 0; } for(int i=1;i<=n;++i){ if(du[i]<=1){ q.push(i); deep[i]=1; du[i]=-1; } } while(!q.empty()){ int x=q.front(); q.pop(); for(int i=pre[x];i;i=nxt[i]){ int y=to[i]; if(du[y]==-1) continue; --du[y]; if(du[y]<=1){ deep[y]=deep[x]+1; ans=max(ans,deep[y]); q.push(y); du[y]=-1; } } } memset(deep,0,sizeof(deep)); dfs(1,0);dfs(1); w[1]=0; for(int i=1;i<=20;++i){ for(int j=1;j<=n;++j){ fa[j][i]=fa[fa[j][i-1]][i-1]; ww[j][i]=max(ww[j][i-1],ww[fa[j][i-1]][i-1]); } } scanf("%d",&m); while(m--){ int u,v; scanf("%d%d",&u,&v); if(u==v) printf("%d\n",ans); else printf("%d\n",solve(u,v)); } return 0; }