省选模拟20

A. 定位系统

只会 \(O(n^2)\) 的暴力 \(dp\)

不难发现每个节点的子树,至多有一个不放

发现当根的度数大于等于 \(3\) 时,答案就是也是如此

于是以度数大于等于 \(3\) 的为根来 \(dp\)

Code
#include<bits/stdc++.h>
//#define int long long//OVERFLOW !!! MEMORY LIMIT !!!
#define rint signed
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
int n,q,rt;
set<int>S[5010],mx;
int f[5010],deg[5010];
inline void ins(int x,int y){S[x].insert(y);S[y].insert(x);deg[x]++,deg[y]++;}
inline void del(int x,int y){S[x].erase(y);S[y].erase(x);deg[x]--,deg[y]--;}
void dfs(int x,int fa){
	int prod=1,sum=0;
	for(auto y:S[x]) if(y!=fa) dfs(y,x),sum+=max(f[y],1),prod*=f[y];
	f[x]=sum-(prod==0);
}
inline int solve(){
	memset(f,0,sizeof(f));
	rt=0;for(int i=1;i<=n;i++) if(deg[i]>=3) rt=i;if(!rt) return 1;
	dfs(rt,0);return f[rt];
}
signed main(){
#ifdef LOCAL
	freopen("in","r",stdin);
	freopen("out","w",stdout);
#endif
	freopen("location.in","r",stdin);
	freopen("location.out","w",stdout);
	n=read();if(n==1) puts("0"),exit(0);
	for(int i=1,x,y;i<n;i++){x=read(),y=read();ins(x,y);}
	printf("%d\n",solve());
	q=read();
	for(int i=1,x,y;i<=q;i++){
		x=read(),y=read();del(x,y);
		x=read(),y=read();ins(x,y);
		printf("%d\n",solve());
	}
	return 0;
}

B. 签到题

部分分可以最小割树来做

分治求出最小割树,两点之间最小的边权就是两点的最小割

发现度数都小于等于 \(3\)

那么答案只有 \(0,1,2,3\) 这几种情况

\(0\) 的不用考虑, \(1\) 可以用 \(tarjan\) 求出割边算

那么考虑对每个边双维护答案

根据最小割树理论,若 \(mincut(a,b)=3,mincut(b,c)=3,mincut(a,c)=2\)

则 \(a,c\) 划分开时, \(b\) 必然被分进一个集合,所以不可能出现上述情况

于是可以考虑划分等价类,每个类里的元素互相之间的最小割都是 \(3\)

然后对边双建出 \(dfs\) 树

考虑割两条边把这个图割开的情况,可以根据这个来划分等价类

一共两种情况

树边和树边,非树边和树边

非树边和非树边不可能,因为是棵树

于是对每个非树边赋上一个随机权值,树边的权值为所有跨过他的非树边的权值异或和

对于第一种情况,只能是他被一条非树边跨过时可以把树割开

第二种情况,只能是被完全相同的非树边跨过时可以把树割开

对于划分等价类,可以对每个等价类异或上一个随机权值,最后随机权值相同的就是一个等价类

Code
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define int long long
#define uint unsigned long long
#define rint signed
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using namespace __gnu_pbds;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
int n,m,A,ctt,ans;
int fa[1000010],siz[1000010];
int dep[1000010];
int dfn[1000010],low[1000010],clo,id[1000010],col;
int stk[1000010],vis[1000010],p,now;
int head[1000010],ver[3000010],to[3000010],tot;
int ndep[1000010];
uint c[1000010],v[1000010],t;
bool del[3000010],in[1000010];
mt19937_64 rd(std::chrono::steady_clock::now().time_since_epoch().count());
gp_hash_table<uint,bool>mp;
gp_hash_table<uint,int>idep,ct;
inline void add(int x,int y){ver[++tot]=y;to[tot]=head[x];head[x]=tot;}
int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
inline void merge(int x,int y){x=getfa(x),y=getfa(y);if(x==y) return ;fa[x]=y;}
void tarjan(int x,int fa){
	dfn[x]=low[x]=++clo;
	stk[++p]=x;vis[x]=1;
	for(int i=head[x];i;i=to[i]){
		int y=ver[i];if(y==fa) continue;
		if(!dfn[y]){tarjan(y,x);low[x]=min(low[x],low[y]);}
		else if(vis[y]) low[x]=min(low[x],dfn[y]);
	}
	if(dfn[x]==low[x]){
		int k;col++;ctt=0;
		do{ctt++;k=stk[p--];id[k]=col;vis[k]=0;}while(k!=x);
		ans+=siz[getfa(x)]*ctt;siz[getfa(x)]+=ctt;
	}
}
void dfs1(int x,int fa){
	vis[x]=now;dep[x]=dep[fa]+1;
	for(int i=head[x];i;i=to[i]) if(!del[i]){
		int y=ver[i];if(y==fa) continue;
		if(vis[y]!=now) dfs1(y,x);
		else if(dep[y]<dep[x]){mp[t=rd()]=1;c[y]^=t,c[x]^=t;}
	}
}
void dfs2(int x,int fa){
	vis[x]=now;
	for(int i=head[x];i;i=to[i]) if(!del[i]){
		int y=ver[i];if(y==fa) continue;
		if(vis[y]!=now){
			dfs2(y,x);c[x]^=c[y];
			if(mp.find(c[y])!=mp.end()) v[y]^=rd();
		}
	}
}
void dfs3(int x,int fa,int dep){
	vis[x]=now;if(fa) idep[c[x]]=dep,ndep[dep]=x;
	for(int i=head[x];i;i=to[i]) if(!del[i]){
		int y=ver[i];if(y==fa) continue;
		if(vis[y]!=now){
			if(idep.find(c[y])!=idep.end()){t=rd();v[ndep[idep[c[y]]]]^=t;v[y]^=t;}
			dfs3(y,x,dep+1);
		}
	}
}
void dfs4(int x,int fa,uint val){
	val^=v[x];vis[x]=now;ct[val]++;
	for(int i=head[x];i;i=to[i]) if(!del[i]){
		int y=ver[i];if(y==fa) continue;
		if(vis[y]!=now) dfs4(y,x,val);
	}
}
signed main(){
#ifdef LOCAL
	freopen("in","r",stdin);
	freopen("out","w",stdout);
#endif
	freopen("juice.in","r",stdin);
	freopen("juice.out","w",stdout);
	n=read(),m=read();now=1;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1,x,y;i<=m;i++){x=read(),y=read();add(x,y),add(y,x);merge(x,y);}
	for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);
	for(int x=1;x<=n;x++) for(int i=head[x];i;i=to[i]){int y=ver[i];if(id[x]!=id[y]) del[i]=1;}
	for(int i=1;i<=n;i++) if(!in[id[i]]){
		in[id[i]]=1;mp.clear(),ct.clear(),idep.clear();
		now++;dfs1(i,0);
		now++;dfs2(i,0);
		now++;dfs3(i,0,1);
		now++;dfs4(i,0,0);A=0;
		for(auto L:ct){
			ans+=3*L.second*(L.second-1)/2;
			ans+=L.second*A*2;A+=L.second;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

C. 卷王

分类讨论即可,构造方案都比较呆,使劲造菊花就完事了

Code
#include<bits/stdc++.h>
//#define int long long//OVERFLOW !!! MEMORY LIMIT !!!
#define rint signed
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
int n,x,y,lst,cnt,cx,cy,l1;
int v[1000010];
int p[1000010];
set<int>S;
signed main(){
#ifdef LOCAL
	freopen("in","r",stdin);
	freopen("out","w",stdout);
#endif
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	n=read();for(int i=1;i<=n;i++) S.insert(p[i]=read());
	if(S.size()>=4) puts("Impossible"),exit(0);
	if(S.size()==1){
		if((*S.begin())!=-1){
			if(n==1) puts("Possible"),exit(0);
			else puts("Impossible"),exit(0);
		}
		if(n==1) puts("Impossible"),exit(0);
		if(n==2) puts("Impossible"),exit(0);
		if(n==3) puts("Impossible"),exit(0);
		puts("Possible");for(int i=2;i<=n;i++) printf("1 %d\n",i);exit(0);
	}
	if(S.size()==2){
		if(*S.begin()==-1){
			x=lst=*(++S.begin());if(p[x]!=-1) puts("Impossible"),exit(0);
			for(int i=1;i<=n;i++){
				if(p[i]==-1) cnt++;
				if(p[i]==x) cx++;
			}
			if(cnt<=1||cx<=2) puts("Impossible"),exit(0);
			puts("Possible");cnt=0;
			for(int i=1;i<=n;i++){
				if(p[i]==-1&&i!=x){printf("%d %d\n",i,lst);lst=i;cnt++;}
				if(cnt==2) break;
			}
			int xxx=0;
			for(int i=1;i<=n;i++) if(p[i]==-1&&i!=x&&i>lst) printf("%d %d\n",lst,i);
			for(int i=1;i<=n;i++) if(p[i]==x){printf("%d %d\n",i,lst);xxx=i;break;}
			for(int i=1;i<=n;i++) if(p[i]==x&&i!=xxx) printf("%d %d\n",i,xxx);
			exit(0);
		}else{
			x=*S.begin(),y=*(++S.begin());if(p[x]!=y||p[y]!=x) puts("Impossible"),exit(0);
			if(n==2){puts("Possible");printf("%d %d\n",x,y);exit(0);}
			if(n==3) puts("Impossible"),exit(0);
			if(n==4){
				for(int i=1;i<=n;i++) if(p[i]==x) cnt++;
				if(cnt!=2) puts("Impossible"),exit(0);
				puts("Possible");lst=x;
				for(int i=1;i<=n;i++) if(p[i]==y&&i!=x) printf("%d %d\n",i,x),lst=i;
				for(int i=1;i<=n;i++) if(p[i]==x&&i!=y){printf("%d %d\n",i,y);printf("%d %d\n",i,lst);}
				exit(0);
			}
			for(int i=1;i<=n;i++){if(p[i]==x) cx++;if(p[i]==y) cy++;}
			if(cx<3||cy<3) puts("Impossible"),exit(0);
			puts("Possible");
			lst=x;cnt=0;
			for(int i=1;i<=n;i++){
				if(p[i]==y&&i!=x){printf("%d %d\n",lst,i);cnt++;lst=i;}
				if(cnt==2) break;
			}
			for(int i=1;i<=n;i++) if(p[i]==y&&i!=x&&i>lst) printf("%d %d\n",lst,i);l1=lst;
			lst=y;cnt=0;
			for(int i=1;i<=n;i++){
				if(p[i]==x&&i!=y){printf("%d %d\n",i,lst);cnt++;lst=i;}
				if(cnt==2) break;
			}
			printf("%d %d\n",lst,l1);
			for(int i=1;i<=n;i++) if(p[i]==x&&i!=y&&i>lst) printf("%d %d\n",lst,i);
			exit(0);
		}
	}
	if(S.size()==3){
		if(*S.begin()!=-1) puts("Impossible"),exit(0);
		auto iter=++S.begin();x=*iter;iter++;y=*iter;if(p[x]!=y||p[y]!=x) puts("Impossible"),exit(0);
		if(n==3){
			int xxx=0;for(int i=1;i<=n;i++) if(p[i]==-1) xxx=i;
			puts("Possible");
			printf("%d %d\n",xxx,x);
			printf("%d %d\n",xxx,y);
			exit(0);
		}
		for(int i=1;i<=n;i++){if(p[i]==x) cx++;if(p[i]==y) cy++;}
		if(cx==2&&cy==2){
			puts("Possible");
			int xxx=0;for(int i=1;i<=n;i++) if(p[i]==-1) xxx=i;
			for(int i=1;i<=n;i++) if(p[i]==y&&i!=x){printf("%d %d\n",i,xxx);printf("%d %d\n",i,x);}
			for(int i=1;i<=n;i++) if(p[i]==x&&i!=y){printf("%d %d\n",i,xxx);printf("%d %d\n",i,y);}
			for(int i=1;i<=n;i++) if(p[i]==-1&&i!=xxx) printf("%d %d\n",i,xxx); 
			exit(0);
		}
		if(cx<3||cy<3) puts("Impossible"),exit(0);
		int xxx=0;for(int i=1;i<=n;i++) if(p[i]==-1) xxx=i;
		puts("Possible");
		for(int i=1;i<=n;i++) if(p[i]==-1&&i!=xxx) printf("%d %d\n",i,xxx);
		lst=x;cnt=0;
		for(int i=1;i<=n;i++){
			if(p[i]==y&&i!=x){printf("%d %d\n",lst,i);cnt++;lst=i;}
			if(cnt==2) break;
		}
		for(int i=1;i<=n;i++) if(p[i]==y&&i!=x&&i>lst) printf("%d %d\n",lst,i);
		printf("%d %d\n",xxx,lst);
		lst=y;cnt=0;
		for(int i=1;i<=n;i++){
			if(p[i]==x&&i!=y){printf("%d %d\n",i,lst);cnt++;lst=i;}
			if(cnt==2) break;
		}
		for(int i=1;i<=n;i++) if(p[i]==x&&i!=y&&i>lst) printf("%d %d\n",lst,i);
		printf("%d %d\n",xxx,lst);
		exit(0);
	}
	return 0;
}
上一篇:vue安装node-sass失败


下一篇:20 公式求解