[ABC302C] Almost Equal

题面翻译

题目描述

给定 $ N $ 个长度为 $ M $ 的仅包含小写英文字母的字符串 $ S_1, S_2, \cdots, S_N $。保证 $ S_i $ 互不相同。

判断是否可以通过对这些字符串重新排序，得到一个新的字符串序列 $ T_1, T_2, \cdots, T_N $，使得：

  • 对于任意 $ i $ 使得 $ 1 \le i \le N - 1 $，均满足 $ T_i $ 在改变恰好一个字母后可以等于 $ T_{i + 1} $。

数据范围

  • $ 2 \le N \le 8 $
  • $ 1 \le M \le 5 $
  • 保证 $ S_i $ 长度为 $ M $，且仅由小写英文字母组成。$ (1 \le i \le N) $
  • 保证 $ S_i $ 互不相同。

样例一解释

安排顺序如下：abcd，abed，bbed，fbed。满足条件。

样例二解释

无论如何对这两个字符串排序，均不可能满足条件。

题目描述

英小文字からなる長さ $ M $ の文字列 $ N $ 個 $ S_1,S_2,\dots,S_N $ が与えられます。ここで、$ S_i $ は互いに異なります。

これらを並び替えた文字列の列 $ T_1,T_2,\dots,T_N $ であって、以下の条件を満たすものが存在するか判定してください。

  • $ 1\ \le\ i\ \le\ N-1 $ を満たす全ての整数 $ i $ に対して、$ T_i $ を $ 1 $ 文字だけ別の英小文字に変えて $ T_{i+1} $ にすることが出来る。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ M $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_N $

输出格式

問題文の条件を満たす列が存在するならば Yes を、そうでないならば No を出力せよ。

样例 #1

样例输入 #1

1
2
3
4
5
4 4
bbed
abcd
abed
fbed

样例输出 #1

1
Yes

样例 #2

样例输入 #2

1
2
3
2 5
abcde
abced

样例输出 #2

1
No

样例 #3

样例输入 #3

1
2
3
4
5
6
7
8
9
8 4
fast
face
cast
race
fact
rice
nice
case

样例输出 #3

1
Yes

提示

制約

  • $ 2\ \le\ N\ \le\ 8 $
  • $ 1\ \le\ M\ \le\ 5 $
  • $ S_i $ は英小文字からなる長さ $ M $ の文字列である。$ (1\ \le\ i\ \le\ N) $
  • $ S_i $ は互いに異なる。

Sample Explanation 1

abcd , abed , bbed , fbed の順に並び替えると条件を満たします。

Sample Explanation 2

どのように並び替えても条件を満たすことは出来ません。

题解

题目解析

一道考全排列的题,我一开始用的dfs,结果越写越不对劲…然后我突然想起jiangly做了这道题,我就翻了翻他BB空间.然后找到了他的写法.一看,码风简介易懂.这道题他用了next_permutation()函数.就是暴力嘛,数据不是挺大.

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
	int N,M;
	cin >> N >> M;
	vector<string> S(N);
	for(int i=0;i<N;i++){
		 cin >> S[i];
	}
	sort(S.begin(), S.end());//使用next_permutation()之前必须要sort.
	do{
		bool ok = true;
		for(int i=0;i<N-1;i++){
			int cunt = 0;
			for(int j=0;j<M;j++){
				cunt += S[i][j] != S[i+1][j];
			}
			if(cunt != 1){
				ok = false;
			}
		}
		if(ok){
			cout << "Yes" << endl;
			return 0;
		}
	} while (next_permutation(S.begin(), S.end()));
	cout << "No" << endl;
	return 0;
}

Remark

  • 使用next_permutaion()前必须sort(),要不然排列会不完全.
  • vector<T> V(n)表示开n个空间的向量.
  • 使用next_permutaion()时可以搭配do-while使用.