自动搬运

查看原文

来自洛谷，原作者为

	wmrqwq 会登顶的。

搬运于2025-08-24 21:15:20，当前版本为作者最后更新于2023-09-15 22:03:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题链接

B3829 [NICA #2] 字符串入门题

题目简述

现在有一个字符串 $s$，你需要将字符串 $s$ 拆分成至少 $k$ 段子串，并需要满足每一个子串都为拆分后字符串的第一个子串的子串，并依次输出拆分成的字段数量和这些子串，若无法满足条件，则输出 $-1$。

解题思路

首先，因为拆分后所有的子串都需要为拆分后字符串的第一个子串的子串，所以我们就需要让拆分后的第一个字符串尽量的长，因为这样就能让第一个字符串的字符变多，进而可以让后面的子串成为第一个字符串的子串的可能性更大。

然后我们就得出了结论：需要尽可能的增加拆分后第一个字符串的长度。

接着我们再来推一下这个结论的逆定理，因为我们要尽可能增加第一个字符串的长度，所以我们就要使得后面的字符串的长度尽量的短，因为要最短，所以后面的字符串的长度就需要为 $1$，因为这样我们就能尽可能增加第一个字符串的长度了，因此，我们只需要从后面依次拆分每个字符即可。

而题目中要求我们至少要拆分 $k$ 个子串，因为我们要让第一个字符串最长，所以只需要拆分为正好 $k$ 个子串即可。

推出了结论，我们就可以用程序解决问题了。

我们只需要开一个桶，存储每一个字符的数量，不过需要注意，不用存储后 $k-1$ 个字符，因为这些字符我们是必然需要拆分的，因此只需要判断后 $k-1$ 个字符有没有在前面出现过即可，若没有，则直接输出 $-1$。否则我们直接依次输出这 $k$ 个子串即可。

参考代码

#include<bits/stdc++.h>
using namespace std;
#define QwQ return 0;
long long pd[1010],n,m;
string s;
int main(){

	cin>>n>>m>>s;
	for(int i=0;i<n-m+1;i++) 
		pd[s[i]]=1;//先把前 n-k+1 个字符装桶里存储
	for(int i=n-m+1;i<n;i++)
		if(!pd[s[i]])//如果前面没有后面 k-1 个字符，则直接输出 -1
		{
			cout<<-1;
			QwQ;
		}
	cout<<m<<endl;	//否则直接依次输出这 k 个子串即可。
	for(int i=0;i<n-m+1;i++) 
		cout<<s[i];
	cout<<endl;
	for(int i=n-m+1;i<n;i++) 
		cout<<s[i]<<endl;
	QwQ;
}