S组 T1 wa了一个点 求hack或调
  • 板块学术版
  • 楼主70CentsApple
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/10/22 09:31
  • 上次更新2023/11/2 12:01:04
查看原帖
S组 T1 wa了一个点 求hack或调
901717
70CentsApple楼主2023/10/22 09:31
#include<iostream>
#include<cstdio>
#include<cstring>
//#define debug(x) std::cerr<<"[L "<<__LINE__<<"] debugging "<<#x<<" = "<<x<<'\n';
//using namespace std;

int d[10][10];
const short nxt[] = {1,2,3,4,5,6,7,8,9,0};
bool vis[100000];
int now[10];
long long ans = 0;
int t;

int get_different(int k,int expect){ // returns diff == expect
	int tot = 0;
	for(int i=1;i<=5;i++){
		if(d[k][i] != now[i]) tot++;
		if(tot>expect) return false;
	}
	return tot == expect;
}

#define val (now[1]*10000+now[2]*1000+now[3]*100+now[4]*10+now[5])
bool judge(){
	const int num = now[1]*10000+now[2]*1000+now[3]*100+now[4]*10+now[5];
	if(vis[num]) return false;
	// 如果当前数到所有输入的数组的距离都为1 
	bool all_diff_1_flag = true;
	for(int i=1;i<=t;i++) {
		if(!get_different(i,1)){
			all_diff_1_flag = false;
			break;
		}
	}
	if(all_diff_1_flag) return true;
			
	// 试图移动i和i+1
	for(int i=1;i<5;i++){
		int cnt = 0;
		for(int j=1;j<=10;j++){
			now[i] = nxt[now[i]]; // roll 1 step
			now[i+1] = nxt[now[i+1]]; // roll 1 step
			if(vis[val]) cnt++;
		}
		for(int kk=1;kk<=t;kk++){
			if(!vis[val] && get_different(kk,1))cnt++;
		}
		if(cnt == t) return true;
	}
	return false;
}

void dfs1(int k){
	if(k>=6) return;
	for(int i=0;i<=9;i++){
		now[k] = i;
		if(k==5){
			if(judge()){
				ans++;
//				debug(now[1]*10000+now[2]*1000+now[3]*100+now[4]*10+now[5]);
			}
		} else {
			dfs1(k+1);
		}
	}
}

signed int main(){
	std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr);
	std::cin>>t;
	if(t == 1) return std::cout<<81, 0;
	
	memset(vis,0,sizeof vis);
	for(int i=1;i<=t;i++){
		std::cin>>d[i][1]>>d[i][2]>>d[i][3]>>d[i][4]>>d[i][5];
		const int num = d[i][1] * 10000 + d[i][2] * 1000 + d[i][3] * 100 + d[i][4] * 10 + d[i][5];
		vis[num] = true;
	}
//	now[1]=2; now[2]=8; now[3]=3; now[4]=1; now[5]=1;
//	debug(judge());
//	system("pause");
	dfs1(1);
	
	std::cout<<ans;
	return 0x0;
}
/*
2
2 8 3 5 5
2 8 3 5 1

*/
2023/10/22 09:31
加载中...