为什么有四个点TLE了
查看原帖
为什么有四个点TLE了
1594374
zhanganheng2024楼主2025/1/30 18:22
#include<iostream>
using namespace std;
#include<string>
#include<map>
#include<algorithm>
#include<cstring>
int n, vis[1005], tot, sum, flag;
map<char, int>m1, m2;
string a[1005], ans[1005];
void dfs(int x)
{
	if (flag) return;
	if (sum == n)
	{
		flag = 1;
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if (vis[i])
		{
			continue;
		}
		if (a[x][a[x].length() - 1] == a[i][0])
		{
			//cout << a[i] << '
			// ';
			sum++;
			ans[++tot] = a[i];
			vis[i] = 1;
			dfs(i);
			if (flag) return;
			sum--;
			tot--;
			vis[i] = 0;
		}
	}
}
int main()
{
	cin >> n;
	for (char i = 1; i <= n; i++)
	{
		cin >> a[i];
		m1[a[i][0]]++;
		m2[a[i][a[i].length() - 1]]++;
	}
	sort(a + 1, a + 1 + n);
	//for (int i = 1; i <= n; i++) cout << a[i] << ' ';
	char s = '*', t = '*';
	for (char i = 'a'; i <= 'z'; i++)
	{
		//cout << m1[i] << ' ';
		if (m1[i] - m2[i] == 1)
		{
			s = i;
		}
		if (m2[i] - m1[i] == 1)
		{
			t = i;
		}
	}
	int cnt = m2[t];
	//cout << s << t;
	if (s == '*' && t == '*')
	{
		for (int i = 1; i <= n; i++)
		{
			memset(vis, 0, sizeof(vis));
			sum = 1;
			flag = 0;
			tot = 0;
			ans[0] = a[i];
			vis[i] = 1;
			dfs(i);
			if (sum == n)
			{
				for (int i = 0; i < n - 1; i++)
				{
					cout << ans[i] << '.';
				}
				cout << ans[n - 1];
				return 0;
			}
		}
	}
	else
	{
		for (int i = 1; i <= n; i++)
		{
			if (a[i][0] == s && (a[i][a[i].length() - 1] != t || cnt != 1))
			{
				memset(vis, 0, sizeof(vis));
				sum = 1;
				flag = 0;
				tot = 0;
				vis[i] = 1;
				dfs(i);
				ans[0] = a[i];
				if (sum == n)
				{
					for (int i = 0; i < n - 1; i++)
					{
						cout << ans[i] << '.';
					}
					cout << ans[n - 1];
					return 0;
				}
			}
		}
	}
	cout << "***";
	return 0;
}
2025/1/30 18:22
加载中...