2019牛客暑期多校训练营（第七场）A.String【最小表示法】

传送门：https://ac.nowcoder.com/acm/contest/887/A

题意：大意就是给你一个只含有0和1的字符串，找出一种分割方法，使得每个分割出的字符串都是在该字符串自循环节中最小

思路：

一：

最小表示法的模板题了，数据范围比较小。每次枚举字符串的最长长度，用最小表示法进行判断即可。

最小表示法的介绍：https://oi-wiki.org/string/minimal-string/

代码：

#include<bits/stdc++.h>

using namespace std;

char s[205];

char t[205];

//最小表示法进行判断

bool solve(int l, int r)

{

    int len = 0;

    for(int i = l; i <= r; i++)

        t[len++] = s[i];

    int i = 0, j = 1, k = 0;

    while(i < len && j < len && k < len)

    {

        int num = t[(i + k) % len] - t[(j + k) % len];

        if(!num)

            k++;

        else

        {

            if(num > 0)

            {

                i += k + 1;

            }

            else

            {

                j += k + 1;

            }

            if(i == j)

                j++;

            k = 0;

        }

    }

    if(min(i, j) == 0)

        return true;

    else

        return false;

}

void print(int l, int r)

{

    for(int i = l; i <= r; i++)

        cout << s[i];

    cout << " ";

}

int main()

{

    int T;

    scanf("%d", &T);

    getchar();

    while(T--)

    {

        scanf("%s", s);

        int n = strlen(s);

        for(int i = 0; i < n; )

        {

            for(int j = n - 1; j >= i; j--)//每次从后面枚举，即是使得长度尽可能的长

            {

                if(i == j || solve(i, j))

                {

                    print(i, j);

                    i = j + 1;

                }

            }

        }

        cout << endl;

    }

}

二：

看的别人的写法。

首先看一下数据范围，题目中的保证每个01字符串的长度都不会超过200，所以可以去暴力枚举，在枚举的时候要注意，由于需要保证分割次数最少，所以每个字符串要尽可能的长，所以枚举时就要从最长的开始，找好起点之后，首次枚举都从起点到字符串末尾，然后慢慢缩小范围，然后找到合适的范围后（即该字符串时自循环中的最小值）再更新起点即可，直至枚举完整个字符串。重点说一下，如何判断枚举出的字符串是不是自循环字符串中的最小值。
我们知道，对于一串数来说，无论什么进制，最高位数字或权值越大的位上（越靠前的位上）的数字越大，那么这串数字本身就越大，比如199和201，201最高位数字为2，大于199最高位数字1，所以201>199,（果两个数字位数不同，就前边补0，补成相同的，再比如2020和2019，在前两位相同的情况下，第三位数字2>1,所以2020>2019。就用这个思路来判断该字符串是不是自循环字符串中最小值。
对于自循环来说，我们还可以认为，自循环就是依次让每个数字都做一次最高位，所以对于长度为len的字符串，自循环就有len中方式，也就产生了len个数字，所以我们利用当前字符串的每一位去和自循环产生的字符串的每一位去作比较，如何当前字符串与自循环产生的字符串的相同位上，当前字符串大，那么直接否决，如果小，直接让当前字符串去和下一个自循环字符串去比较（从高位开始比，高位小，总体一定小）

代码：

#include<bits/stdc++.h>

using namespace std;

bool check(string str){

    int len=str.length();

    for(int i=0;i<len;i++){

        for(int j=0;j<len;j++){

            if(str[j]>str[(i+j)%len])

                return false;

            if(str[j]<str[(i+j)%len])

                break;

        }

    }

    return true;

}

int main(){

    int n;

    cin>>n;

    while(n--){

        string t;

        cin>>t;

        int len=t.length();

        int head=0;

        while(head<len){

            for(int j=len-head;j>0;j--){

                if(check(t.substr(head,j))){

                    cout<<t.substr(head,j);

                    head+=j;

                    if(head<len)

                        cout<<" ";

                    break;

                }

            }

        }

        cout<<endl;

    }

    return 0;

}

巴特西

2019牛客暑期多校训练营（第七场）A.String【最小表示法】

最新文章

热门文章