String和Irreducible Polynomial（2019牛客暑期多校训练营（第七场））

示例：

输入：

4
0
0001
0010
111011110

输出：

0
0001
001 0
111 01111 0

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

题解：先把每段按1结尾分开，然后暴力合并，合并的条件是每段字符串的字典序都不下降，这样可以保证是最小表示。
因为如果后面有一段字典序比前面合并的任意一段字典序小，那它放到这段合并的字符串最前面显然可以更小，因此不符合最小表示，这段不需要合并。

Code:

#include <bits/stdc++.h>

using namespace std;

char ss[];

int lens,r,l,j,k;

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%s",ss+);

        lens=strlen(ss+),r=;

        while(r<=lens)

        {

            j=l=r;

            k=r+;

            while(k<=lens&&ss[j]<=ss[k])

            {

                if(ss[j]<ss[k]) j=r;

                else j++;

                k++;

            }

            while(r<=j) r+=k-j;

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

                printf("%c",ss[i]);

            printf(" ");

        }

        printf("\n");

    }

    return ;

}

示例：

输入：

2
2
1 -2 1
2
1 0 1

输出：

No
Yes

题意：
给你一个n次n+1项式(An*X^n+A(n-1)*X^(n-1)...A*X+A0)，将系数An都给你，问你这个多项式是不是一个不可约多项式，可约多项式就是类型(x+1)*(x+2)=
x^2+3*x+2 这一种，它是不可约多项式就输出Yes，否则输出No

题解：
结论：当n>=3的时候，它一定不是不可约多项式；当n==2的时，b^2-4*a*c这个来判定就可以了，小于0就不可约，大于0就可约；当n<2的时候一定不可约。

Code:

#include <iostream>

#include <stdio.h>

using namespace std;

int a[];

int main()

{

    int n;

    int t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        for(int i=n; i>=; i--)

            scanf("%d",&a[i]);

        if(n<)

            cout<<"Yes"<<endl;

        else if(n==)

        {

            if((a[]*a[])>=*a[]*a[])

                cout<<"No"<<endl;

            else

                cout<<"Yes"<<endl;

        }

        else

            cout<<"No"<<endl;

    }

}

巴特西

String和Irreducible Polynomial（2019牛客暑期多校训练营（第七场））

最新文章

热门文章