题面：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;
}