73分 1,7,8wa点
  • 板块P1127 词链
  • 楼主ananran998
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/1/17 23:34
  • 上次更新2023/10/24 03:47:05
查看原帖
73分 1,7,8wa点
660776
ananran998楼主2023/1/17 23:34
#include <bits/stdc++.h>
using namespace std;
struct node {
	int y;
	string s;
	bool operator < (const node &A) const {
		return s < A.s;
	}
};

string ans[1001];
int m, n, l, id[27], od[27], f[27], c[1002];
vector<node> v[27];

inline void dfs(int x) {
	while (f[x] < od[x]) {
		node temp = v[x][f[x]];
		++f[x];
		int y = temp.y;
		dfs(y);
		c[++l] = y;
		ans[l] = temp.s;
	}
}

inline void euler() {
	int x = 0, y = 0, z = 0;
	for (int i = 0; i < n; i++)	{
		if (id[i] + 1 == od[i])
			x = i, ++y;
		if (od[i] != id[i])
			++z;
	}
	if (!(!z || (z == 2 && y == 1))) {
		printf("***\n");
		return;
	}
	for (int i = 1; i <= n; i++)
		if (od[i]) {
			x = i;
			break;
		}
	l = 0;
	memset(f, 0, sizeof(f));
	dfs(x);
	c[++l] = x;
	if (l != m + 1)
		printf("***\n");
	else {
		for (int i = l - 1; i; i--) {
			if (i != l - 1)
				printf(".");
			printf("%s", ans[i].c_str());
		}
	}
}

int main() {
	n = 26;
	scanf("%d", &m);
	for (int i = 1; i <= m; i++) {
		char str[22];
		scanf("%s", str);
		int x = str[0] - 'a' + 1;
		int y = str[strlen(str) - 1] - 'a' + 1;
		++od[x], ++id[y];
		node temp;
		temp.y = y, temp.s = str;
		v[x].push_back(temp);
	}
	for (int i = 1; i <= n; i++)
		sort(v[i].begin(), v[i].end());
	euler();
	return 0;
}
2023/1/17 23:34
加载中...