csps-模拟7778lrd两试

2024-02-21 11:37:52

题面：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然后赋值

csps-模拟7778lrd两试
 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 }
View Code

连连看：我咕了

串串香：

正解是kmp，被hash完美过掉

csps-模拟7778lrd两试
 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 }
View Code

糊涂图：除了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;
}

 

 

 

上一篇：【题解】最大公约数


下一篇：Max Sum Plus Plus HDU - 1024滚动数组