求一组Hack数据
查看原帖
求一组Hack数据
1015002
Charles_with_wkc楼主2024/9/16 22:12

有没有一组Hack数据可以让这两份代码输出结果不同?(不考虑时间复杂度和空间复杂度

代码1:

#include<bits/stdc++.h>
using namespace std;
int n,side,m,sticks[25];
bool visit[25];
bool DFS(int sum,int number,int position){
	if(number==3){
		return true;
	}
	int sample=0;
	for(int i=position;i<m;++i){
		if(visit[i]||sum+sticks[i]>side||sticks[i]==sample) continue;
		visit[i]=true;
		if(sum+sticks[i]==side){
			if(DFS(0,number+1,0)) return true;
			else sample=sticks[i];
		}else{
			if(DFS(sum+sticks[i],number,i+1)) return true;
			else sample=sticks[i];
		}
		visit[i]=false;
	}
	return false;
}
bool cmp(int x,int y){ return x>y; }
int main(){
	scanf("%d",&n);
	while(n--){
		int length=0;
		scanf("%d",&m);
		for(int i=0;i<m;i++){
			scanf("%d",&sticks[i]);
			length+=sticks[i];
		}
		memset(visit,false,sizeof(visit));
		if(length%4!=0){
			printf("no\n");
			continue;
		}
		side=length/4;
		sort(sticks,sticks+m,cmp);
		if(sticks[0]>side){
			printf("no\n");
			continue;
		}
		if(DFS(0,0,0)) printf("yes\n");
		else printf("no\n");
	}
	return 0;
}

代码2:

#include<bits/stdc++.h>
using namespace std;
int n,side,m,sticks[25];
bool visit[25];
bool DFS(int sum,int number,int position){
	if(number==4){
		return true;
	}
	int sample=0;
	for(int i=position;i<m;++i){
		if(visit[i]||sum+sticks[i]>side||sticks[i]==sample) continue;
		visit[i]=true;
		if(sum+sticks[i]==side){
			if(DFS(0,number+1,0)) return true;
			else sample=sticks[i];
		}else{
			if(DFS(sum+sticks[i],number,i+1)) return true;
			else sample=sticks[i];
		}
		visit[i]=false;
	}
	return false;
}
bool cmp(int x,int y){ return x>y; }
int main(){
	scanf("%d",&n);
	while(n--){
		int length=0;
		scanf("%d",&m);
		for(int i=0;i<m;i++){
			scanf("%d",&sticks[i]);
			length+=sticks[i];
		}
		memset(visit,false,sizeof(visit));
		if(length%4!=0){
			printf("no\n");
			continue;
		}
		side=length/4;
		sort(sticks,sticks+m,cmp);
		if(sticks[0]>side){
			printf("no\n");
			continue;
		}
		if(DFS(0,0,0)) printf("yes\n");
		else printf("no\n");
	}
	return 0;
}
2024/9/16 22:12
加载中...