B3829 题解

wmrqwq · 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;
}