求助,为什么TLE9了
查看原帖
求助,为什么TLE9了
261335
_Daota_楼主2020/10/14 22:20
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 30;
int n;
char str[3][N];
int ans[N], vis[N], add[N];

bool jz()
{
	if ((ans[str[0][n] - 'A'] != -1 && ans[str[1][n] - 'A'] != -1) && (ans[str[0][n] - 'A'] + ans[str[1][n] - 'A']) / n) return true;
	for (int i = 1; i <= n; i++)
	{
		int a = ans[str[0][i] - 'A'], b = ans[str[1][i] - 'A'], c = ans[str[2][i] - 'A'];
		if (a == -1 || b == -1 || c == -1) continue;
        if ((a + b) % n - c && (a + b + 1) % n - c) return true;
	}
	return false;
}

bool check()
{
	int x = 0;
	for (int i = 1; i <= n; i++)
	{
		int a = ans[str[0][i] - 'A'], b = ans[str[1][i] - 'A'], c = ans[str[2][i] - 'A'];
		if (a == -1 || b == -1 || c == -1) return false;
		if ((a + b + x) % n - c) return false;
		x = (a + b + x) / n;
	}
	return true;
}

bool dfs(int now)
{
	if (jz()) return false;

	if (now == n + 1)
	{
		if (check()) return true;
		else return false;
	}

	if (ans[str[0][now] - 'A'] == -1)
	{
		for (int i = 0; i < n; i++)
			if (!vis[i])
			{
				ans[str[0][now] - 'A'] = i;
				vis[i] = 1;
				if (dfs(now)) return true;
				ans[str[0][now] - 'A'] = -1;
				vis[i] = 0;
			}
	}
	else if (ans[str[1][now] - 'A'] == -1)
	{
		for (int i = 0; i < n; i++)
			if (!vis[i])
			{
				ans[str[1][now] - 'A'] = i;
				vis[i] = 1;
				if (dfs(now)) return true;
				ans[str[1][now] - 'A'] = -1;
				vis[i] = 0;
			}
	}
	else if (ans[str[2][now] - 'A'] == -1)
	{
		for (int i = 0; i < n; i++)
			if (!vis[i])
			{
				ans[str[2][now] - 'A'] = i;
				vis[i] = 1;
				if (dfs(now)) return true;
				ans[str[2][now] - 'A'] = -1;
				vis[i] = 0;
			}
	}

	int a = ans[str[0][now] - 'A'], b = ans[str[1][now] - 'A'], c = ans[str[2][now] - 'A'];
	if ((a + b + add[now]) % n != c) return false;
	add[now + 1] = (a + b + add[now]) / n;
	if (dfs(now + 1)) return true;
	add[now + 1] = 0;
	return false;
}

int main()
{
	memset(ans, -1, sizeof ans);
	cin >> n;
	for (int i = 0; i < 3; i++)
	{
		scanf("%s", str[i] + 1);
		reverse(str[i] + 1, str[i] + 1 + n);
	}
	dfs(1);
	for (int i = 0; i < n; i++)
		printf("%d ", ans[i]);
	return 0;
}
2020/10/14 22:20
加载中...