社区讨论

萌新求助 UB

wwukaichen888
P9074[WC/CTS2023] 比赛参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mkchl5un
此快照首次捕获于
2026/01/13 19:06
上个月
此快照最后确认于
2026/01/17 11:05
上个月
查看原帖
以下代码会 WA 44pts
CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=4005;
int T,n,m,maxx;
int mp[N][N],id[N],ans[N],res,tot1;
int col[N],val[N];
int check1(int x,int y,int z){
	if(mp[x][y]==0) return 1;
	if(mp[x][y]==mp[y][z]) return 0;
	return 1;}
int vis[N];
int check2(int x){
	return check1(ans[x],ans[(x+1>n)?(x+1-n):(x+1)],ans[(x+2>n)?(x+2-n):(x+2)]);}
mt19937 rnd(time(0));
inline int get(int l,int r){return ((rnd()&1073741823)%(r-l+1)+l);}
void work(){
	res=0;
	for(int i=1;i<=n;i++) res+=check2(i);
	for(int i=1;i<=n;i++) vis[i]=0;
	int x,y,las;
	while(res<n){
		x=get(1,n),y=get(1,n); while(x==y) x=get(1,n),y=get(1,n);
		
		for(int d=-2,p;d<=0;d++){
			p=((x+d-1)%n+n)%n+1; if(!vis[p]){vis[p]=1;res-=check2(p);}
			p=((y+d-1)%n+n)%n+1; if(!vis[p]){vis[p]=1;res-=check2(p);}}
		swap(ans[x],ans[y]);
		for(int d=-2,p;d<=0;d++){
			p=((x+d-1)%n+n)%n+1; if(vis[p]==1) vis[p]=0,res+=check2(p);
			p=((y+d-1)%n+n)%n+1; if(vis[p]==1) vis[p]=0,res+=check2(p);}
		
		if(res<las) res=las,swap(ans[x],ans[y]);
		else if(res==las) if(get(0,1)) swap(ans[x],ans[y]);
	}
	for(int i=1;i<=n;i++) printf("%d ",ans[i]); printf("\n");
}
bool cmp(int x,int y){
	if(val[x]!=val[y]) return val[x]>val[y];
	if(col[x]!=col[y]) return col[x]>col[y];
	return x>y;}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m); maxx=0;
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) mp[i][j]=0;
		for(int i=1;i<=n;i++) col[i]=val[i]=0;
		for(int i=1,siz;i<=m;i++){
			scanf("%d",&siz); maxx=max(maxx,siz);
			for(int j=1;j<=siz;j++) scanf("%d",&id[j]);
			for(int j=1,p;j<=siz;j++){
				p=id[j];
				if(siz>val[p]) col[p]=i,val[p]=siz;}
			for(int j=1;j<=siz;j++)
				for(int p=1;p<=siz;p++)
					mp[id[j]][id[p]]=mp[id[p]][id[j]]=i;}
		for(int i=1;i<=n;i++) id[i]=i;
		sort(id+1,id+n+1,cmp); tot1=0;
		for(int i=1;i<=n;i+=3) ans[i]=id[++tot1];
		for(int i=2;i<=n;i+=3) ans[i]=id[++tot1];
		for(int i=3;i<=n;i+=3) ans[i]=id[++tot1];
		if((maxx+1)/2<=n-maxx) work();
		else puts("-1");}
	return 0;}
修改以后可以得到 TLE 80pts
CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=4005;
int T,n,m,maxx;
int mp[N][N],id[N],ans[N],res,tot1;
int col[N],val[N];
int check1(int x,int y,int z){
	if(mp[x][y]==0) return 1;
	if(mp[x][y]==mp[y][z]) return 0;
	return 1;}
int vis[N];
int check2(int x){
	return check1(ans[x],ans[(x+1>n)?(x+1-n):(x+1)],ans[(x+2>n)?(x+2-n):(x+2)]);}
mt19937 rnd(time(0));
inline int get(int l,int r){return ((rnd()&1073741823)%(r-l+1)+l);}
void work(){
	res=0;
	for(int i=1;i<=n;i++) res+=check2(i);
	for(int i=1;i<=n;i++) vis[i]=0;
	int x,y,las;
	while(res<n){
		x=get(1,n),y=get(1,n); while(x==y) x=get(1,n),y=get(1,n);
		
		for(int d=-2,p;d<=0;d++){
			p=((x+d-1)%n+n)%n+1; if(!vis[p]){vis[p]=1;res-=check2(p);}
			p=((y+d-1)%n+n)%n+1; if(!vis[p]){vis[p]=1;res-=check2(p);}}
		swap(ans[x],ans[y]);
		for(int d=-2,p;d<=0;d++){
			p=((x+d-1)%n+n)%n+1; if(vis[p]) vis[p]=0,res+=check2(p);
			p=((y+d-1)%n+n)%n+1; if(vis[p]) vis[p]=0,res+=check2(p);}
		
		if(res<las) res=las,swap(ans[x],ans[y]);
		else if(res==las) if(get(0,1)) swap(ans[x],ans[y]);
	}
	for(int i=1;i<=n;i++) printf("%d ",ans[i]); printf("\n");
}
bool cmp(int x,int y){
	if(val[x]!=val[y]) return val[x]>val[y];
	if(col[x]!=col[y]) return col[x]>col[y];
	return x>y;}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m); maxx=0;
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) mp[i][j]=0;
		for(int i=1;i<=n;i++) col[i]=val[i]=0;
		for(int i=1,siz;i<=m;i++){
			scanf("%d",&siz); maxx=max(maxx,siz);
			for(int j=1;j<=siz;j++) scanf("%d",&id[j]);
			for(int j=1,p;j<=siz;j++){
				p=id[j];
				if(siz>val[p]) col[p]=i,val[p]=siz;}
			for(int j=1;j<=siz;j++)
				for(int p=1;p<=siz;p++)
					mp[id[j]][id[p]]=mp[id[p]][id[j]]=i;}
		for(int i=1;i<=n;i++) id[i]=i;
		sort(id+1,id+n+1,cmp); tot1=0;
		for(int i=1;i<=n;i+=3) ans[i]=id[++tot1];
		for(int i=2;i<=n;i+=3) ans[i]=id[++tot1];
		for(int i=3;i<=n;i+=3) ans[i]=id[++tot1];
		if((maxx+1)/2<=n-maxx) work();
		else puts("-1");}
	return 0;}
具体是将（WA）：
CPP
		for(int d=-2,p;d<=0;d++){
			p=((x+d-1)%n+n)%n+1; if(vis[p]==1) vis[p]=0,res+=check2(p);
			p=((y+d-1)%n+n)%n+1; if(vis[p]==1) vis[p]=0,res+=check2(p);}
改成（AC）：
CPP
		for(int d=-2,p;d<=0;d++){
			p=((x+d-1)%n+n)%n+1; if(vis[p]) vis[p]=0,res+=check2(p);
			p=((y+d-1)%n+n)%n+1; if(vis[p]) vis[p]=0,res+=check2(p);}
但是 vis 数组值域在 0∼10\sim1 啊，为啥结果不一样 /yun /yun /yun
感觉可能是 UB 但是我看不出来哪里有问题 /ll /ll /ll

回复

共 2 条回复，欢迎继续交流。

正在加载回复...