全排列暴力40分,还有救吗?
查看原帖
全排列暴力40分,还有救吗?
261262
WaltVBAlston楼主2021/7/14 10:29

RT,这么暴力的程序,还有优化空间吗?其他全部TLE,跑了一个21的点,跑了大概半小时吧都没跑完。

向中科院申请使用天河一号(

#include<bits/stdc++.h>
using namespace std;
int ans[26],n;
string in1,in2,out;
int a[26],b[26],c[26];
int nowa[26],nowb[26],nowc[26];
int main(){
	cin>>n;
	cin>>in1;
	cin>>in2;
	cin>>out;
	for(int i=n;i>=1;i--){
		a[i]=in1[i-1]-65+1;
		b[i]=in2[i-1]-65+1;
		c[i]=out[i-1]-65+1;
	}
	for(int i=1;i<=n;i++)
		ans[i]=i-1;
	while(1){
		for(int i=1;i<=n;i++){
			nowa[i]=ans[a[i]];
			nowb[i]=ans[b[i]];
			nowc[i]=ans[c[i]];
			cout<<ans[i]<<" ";
		}
		cout<<endl;
		int up=0;
		bool flag=true;
		for(int i=n;i>=1;i--){
			if((nowa[i]+nowb[i]+up)%n!=nowc[i]){
				next_permutation(ans+1,ans+n+1);
				flag=false;
				break;
			}
			int temp=nowa[i]+nowb[i]+up;
			up=temp/n;
		}
		if(flag==true)
			break;
	}
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<" ";
	return 0;
}
2021/7/14 10:29
加载中...