只有1 3过了,2 dfs超时了,其他全wa
查看原帖
只有1 3过了,2 dfs超时了,其他全wa
1035989
Camelliail楼主2024/3/4 15:19
#include<bits/stdc++.h>
using namespace std;

/*P1088 [NOIP2004 普及组] 火星人*/
int n, r;
int b[10005], a[10005];//a存整数总和
int mark, pd[10005], used[10005], ans = 0;
void dfs(int m) {
	if (m == n) {
		ans++;//表示每个数代表的小整数
		for (int j = 1; j <= n; j++) {
			a[ans] += used[j] * pow(10, n - j);//a下标值为每个大整数的小整数
		}
		return;
	}

	for (int i = 1; i <= n; i++) {
		if (pd[i] == 0) {//如果该数没被用过
			pd[i] = 1;
			used[m + 1] = i;//m从0层开始
			dfs(m + 1);
			pd[i] = 0;//回溯
		}
		
	}
}
int main() {
	cin >> n;
	cin >> r;
	for (int i = 1; i <= n; i++) cin >> b[i];
	dfs(0);
	
	int sum = 0;
	for (int j = 1; j <= n; j++) {
		sum += b[j] * pow(10, n - j);//a下标值为每个大整数的小整数
	}
	//找到火星人给的对应的小整数,sum为大整数
	for (int i = 1; i <= ans; i++) {
		if (sum == a[i]) {
			mark = i;//火星人给的对应的小整数mark
			break;
		}
	}
	int flag = 1;
	for (int i = 1; i <= n; i++) {
		flag = a[mark + r] / pow(10, n - i);
		cout << flag << " ";
		a[mark + r] -= flag * pow(10, n - i);
	}
	return 0;
}
2024/3/4 15:19
加载中...