CF544A Set of Strings 题解

Content

有一个长为 \(n\) 的字符串 \(q\)，试问能否将其划分为 \(k\) 个子串，使得每个子串的首字母都不相等，可以的话输出 \(\texttt{YES}\) 并输出任意一个方案，否则输出 \(\texttt{NO}\)。

数据范围：\(1\leqslant n\leqslant 100,1\leqslant k\leqslant 26\)。

Solution

我们可以考虑这样的一个流程：

输入字符串后，一个一个去扫。
如果有一个之前没有出现过的字母，就立刻建立新的一个空子串。之后，将当前字符加入到当前子串里面（有可能是之前已经有字母在里面的子串，而不是新的子串）。

看不懂的话可以参照下面这个数据：

10

whenthereisawillthereisaway

下面是模拟过程——

从第一个字符 \(\texttt{w}\) 开始。
建立第一个空子串。将第一个字符加入到这个子串里面，这时，第一个子串是 \(\texttt{w}\)。
扫到第二个字符 \(\texttt{h}\)，前面没有出现过，则建立第二个空子串，并将第二个字符加入到这个子串里面，这时，第二个子串是 \(\texttt{h}\)。
扫到第三个字符 \(\texttt{e}\)，前面没有出现过，则建立第三个空子串，并将第三个字符加入到这个子串里面，这时，第三个子串是 \(\texttt{e}\)。
扫到第四个字符 \(\texttt{n}\)，前面没有出现过，则建立第四个空子串，并将第四个字符加入到这个子串里面，这时，第四个子串是 \(\texttt{n}\)。
扫到第五个字符 \(\texttt{t}\)，前面没有出现过，则建立第五个空子串，并将第五个字符加入到这个子串里面，这时，第五个子串是 \(\texttt{t}\)。
扫到第六个字符 \(\texttt{h}\)，前面出现过，则将第六个字符加入到第五个子串里面，这时，第五个子串是 \(\texttt{th}\)。

以此类推，这样，最后的十个子串分别是 \(\texttt{w}\)、\(\texttt{h}\)、\(\texttt{e}\)、\(\texttt{n}\)、\(\texttt{the}\)、\(\texttt{re}\)、\(\texttt{i}\)、\(\texttt{s}\)、\(\texttt{awi}\)、\(\texttt{llthereisaway}\)。

你也可以试试 \(k=17\) 的情况，此时应该输出 \(\texttt{NO}\)，具体请读者自行模拟。

Code

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <string>

#include <iostream>

#include <cmath>

#include <map>

using namespace std;

int k, num;

string s, spre[107];

map<char, int> vis;

int main() {

	scanf("%d", &k);

	cin >> s;

	num = 1;

	spre[num] += s[0];

	vis[s[0]] = 1;

	for(int i = 1; i < s.size(); ++i) {

		if(!vis[s[i]]) {

			num++;

			if(num > k) {

				for(int j = i; j < s.size(); ++j)

					spre[num - 1] += s[j];

				break;

			}

			vis[s[i]] = 1;

		}

		spre[num] += s[i];

	}

	if(num < k)	return printf("NO"), 0;

	else {

		puts("YES");

		for(int i = 1; i <= num; ++i)

			cout << spre[i] << endl;

	}

}

巴特西

CF544A Set of Strings 题解

Content

Solution

Code

最新文章

热门文章