CF - 782D. Innokenty and a Football League - 模拟+思维+贪心+dfs插入

1.题目描述：

D. Innokenty and a Football League time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

Innokenty is a president of a new football league in Byteland. The first task he should do is to assign short names to all clubs to be shown on TV next to the score. Of course, the short names should be distinct, and Innokenty wants that all short names consist of three letters.

Each club's full name consist of two words: the team's name and the hometown's name, for example, "DINAMO BYTECITY". Innokenty doesn't want to assign strange short names, so he wants to choose such short names for each club that:

the short name is the same as three first letters of the team's name, for example, for the mentioned club it is "DIN", or, the first two letters of the short name should be the same as the first two letters of the team's name, while the third letter is the same as the first letter in the hometown's name. For the mentioned club it is "DIB".

Apart from this, there is a rule that if for some club x the second option of short name is chosen, then there should be no club, for which the first option is chosen which is the same as the first option for the club x. For example, if the above mentioned club has short name "DIB", then no club for which the first option is chosen can have short name equal to "DIN". However, it is possible that some club have short name "DIN", where "DI" are the first two letters of the team's name, and "N" is the first letter of hometown's name. Of course, no two teams can have the same short name.

Help Innokenty to choose a short name for each of the teams. If this is impossible, report that. If there are multiple answer, any of them will suit Innokenty. If for some team the two options of short name are equal, then Innokenty will formally think that only one of these options is chosen.

Input

The first line contains a single integer n (1 ≤ n ≤ 1000) — the number of clubs in the league.

Each of the next n lines contains two words — the team's name and the hometown's name for some club. Both team's name and hometown's name consist of uppercase English letters and have length at least 3 and at most 20.

Output

It it is not possible to choose short names and satisfy all constraints, print a single line "NO".

Otherwise, in the first line print "YES". Then print n lines, in each line print the chosen short name for the corresponding club. Print the clubs in the same order as they appeared in input.

If there are multiple answers, print any of them.

Examples input 2 DINAMO BYTECITY FOOTBALL MOSCOW output YES DIN FOO input 2 DINAMO BYTECITY DINAMO BITECITY output NO input 3 PLAYFOOTBALL MOSCOW PLAYVOLLEYBALL SPB GOGO TECHNOCUP output YES PLM PLS GOG input 3 ABC DEF ABC EFG ABD OOO output YES ABD ABE ABO Note

In the first sample Innokenty can choose first option for both clubs.

In the second example it is not possible to choose short names, because it is not possible that one club has first option, and the other has second option if the first options are equal for both clubs.

In the third example Innokenty can choose the second options for the first two clubs, and the first option for the third club.

In the fourth example note that it is possible that the chosen short name for some club x is the same as the first option of another club y if the first options of x and y are different.

2.题意概述：

某人需要给若干球队选择队名缩写。已知每个球队的名字必然是<team name><hometown neme>的形式。取队名缩写的规则是固定的，只有两种：选择 team name 的前三个字母作为队名缩写或选择 team name 的前两个字母与 hometown name 的首字母组成队名缩写。每个队的队名缩写都可以从两种中任选一种，问能够使得每个队最终的队名缩写均不同。如果 x 的第一类队名缩写为 x.fi，第二类队名缩写为 x.se，并且x.fi== y.fi，若 x 选择了 x.se作为最终的队名缩写，并且如果 x 的第一类队名缩写为 x.fi，第二类队名缩写为 x.se，那么其他队伍均不能以 y.fi 作为最终的队名缩写。如果是 y.se==x.fi的话，则不触发这一禁制规则。

3.解题思路：

注意红色字，虽然不触发禁制，但是如果按照这个规则，可能出现最终队名相同的，所以还需要处理，比赛时候我就是因为没认真读题一直Wrong answer on test 16

好，言归正传，对于每个队伍，如果选择第二个名称，肯定是会导致它的第一个名称以后都不能使用，那么我们肯定希望尽可能少的出现这种情况，因此先对所有可以的队伍贪心地选取第一个名称选择，如果出现矛盾，这些人必须全换成第二选择。如果新的第二选择和另一个人的第一选择冲突的话那个人必须也换成第二选择，如果那个人也是第二选择那就无解了。 实现就是通过的dfs，没想到15MS这么效率orz

貌似网上题解还有个2-SAT版本，具体实现以后学了再说ORZ

4.AC代码：

#include <bits/stdc++.h> #define INF 0x3f3f3f3f #define maxn 100100 #define N 1111 #define eps 1e-6 #define pi acos(-1.0) #define e exp(1.0) using namespace std; const int mod = 1e9 + 7; typedef long long ll; typedef unsigned long long ull; map<string, int> mp; string fst[N], snd[N], str1, str2; int ans[N], flag; void dfs(int id) { if (!mp.count(snd[id])) mp[snd[id]] = id; else { int pos = mp[snd[id]]; if (pos == -1) mp[snd[id]] = id; else if (ans[pos] == 2) flag = 0; else { ans[pos] = 2; dfs(pos); } } } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); long _begin_time = clock(); #endif int n; while (~scanf("%d", &n)) { mp.clear(); for (int i = 1; i <= n; i++) { cin >> str1 >> str2; fst[i] = str1.substr(0, 3); snd[i] = str1.substr(0, 2) + str2[0]; } flag = 1; for (int i = 1; i <= n && flag; i++) { if (!mp.count(fst[i])) { mp[fst[i]] = i; ans[i] = 1; } else { ans[i] = 2; dfs(i); int pos = mp[fst[i]]; if (pos != -1 && ans[pos] == 1) { mp[fst[i]] = -1; ans[pos] = 2; dfs(pos); } } } if (flag) { puts("YES"); for (int i = 1; i <= n; i++) if (ans[i] == 1) cout << fst[i] << endl; else cout << snd[i] << endl; } else puts("NO"); } #ifndef ONLINE_JUDGE long _end_time = clock(); printf("time = %ld ms.", _end_time - _begin_time); #endif return 0; }