2019牛客ACM暑期多校第七场

A-String

题目描述

A string is perfect if it has the smallest lexicographical ordering among its cyclic rotations.
For example: "0101" is perfect as it is the smallest string among ("0101", "1010", "0101", "1010").

Given a 01 string, you need to split it into the least parts and all parts are perfect.

输入描述:

The first line of the input gives the number of test cases, T (T≤300)T\ (T \leq 300)T (T≤300).  test cases follow.

For each test case, the only line contains one non-empty 01 string. The length of string is not exceed 200.

输出描述:

For each test case, output one string separated by a space.

示例1

输入

复制

4
0
0001
0010
111011110

输出

复制

0
0001
001 0
111 01111 0

给定一个字符串，将其划分成几部分，每部分都满足循环串字典序最小，如何划分使划分次数最少

枯了 暴力枚举子串终点，向后续延

#include <bits/stdc++.h>
using namespace std;
string s;
int len;
bool check(int l,int r)
{
    int len=r-l+1;
    string s1=s.substr(l,len);
    string s2=s1+s1;
    for(int i=0;i<len;i++)
    {
        if(s2.substr(i,len)<s1)
            return false;
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie();
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>s;
        len=s.size();
        int l=0,r;
        for(;l<len;l++)
        {
            r=len-1;
            while(!check(l,r))
                r--;
            string tmp=s.substr(l,r-l+1);
            cout<<tmp;
            if(r!=len-1)
                cout<<' ';
            l=r;
        }
        cout<<'\n';
    }
    return 0;
}

B-Irreducible Polynomial 

题目描述

In mathematics, a polynomial is an expression consisting of variables (also called indeterminate) and coefficients, that involves only the operations of addition, subtraction, multiplication, and non-negative integer exponents of variables. For example, x2+4x+7x^2 + 4x + 7x2+4x+7.

A polynomial is said to be irreducible if it cannot be factored into two or more non-trivial polynomials with real coefficients.
For example, x2+1x^2+1x2+1 is irreducible, but x2−2x+1x^2-2x+1x2−2x+1 is not (since x2−2x+1=(x−1)(x−1)x^2-2x+1=(x-1)(x-1)x2−2x+1=(x−1)(x−1)).

Given a polynomial of degree with integer coefficients: anxn+an−1xn−1+...+a1x+a0a_nx^n+a_{n-1}x^{n-1}+...+a_1x+a_0an​xn+an−1​xn−1+...+a1​x+a0​, you need to check whether it is irreducible or not.

输入描述:

The first line of the input gives the number of test cases, T (T≤100)T\ (T \leq 100)T (T≤100).  test cases follow.

For each test case, the first line contains one integers n (0≤n≤20)n\ (0 \leq n \leq 20)n (0≤n≤20). Next line contains n + 1n\ +\ 1n + 1 integer numbers:
an,an−1,...,a1,a0a_n, a_{n-1}, ..., a_1, a_0an​,an−1​,...,a1​,a0​

−109≤ai≤109-10^9 \leq a_i \leq 10^9−109≤ai​≤109

an≠0a_n \ne 0an​​=0

输出描述:

For each test case, output "Yes" if it is irreducible, otherwise "No".

示例1

输入

复制

2
2
1 -2 1
2
1 0 1

输出

复制

No
Yes

 询问一个多项式是否可拆分成单项式乘积的形式

我好菜啊太菜了

实数域不可拆分多项式只有两种：一次多项式和二次的(b^2<4ac)

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t,n,a[25];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n+1;i++)
            scanf("%d",&a[i]);
        if(n>2)
            cout<<"No"<<'\n';
        else if(n<2)
            cout<<"Yes"<<'\n';
        else
        {
            if(a[2]*a[2]-4*a[1]*a[3]>=0)
                cout<<"No"<<'\n';
            else
                cout<<"Yes"<<'\n';
        }
    }
    return 0;
}

D-Number

题目描述

I have a very simple problem for you. Given a positive integeter n (1≤n≤1000000)n\ (1 \leq n \leq 1000000)n (1≤n≤1000000) and a prime number p (2≤p≤1000000)p\ (2 \leq p \leq 1000000)p (2≤p≤1000000), your job is to output a positive number which is divisible by and has exactly digits. Please output "T_T" if you can not find such number.

输入描述:

The first line of the input file contains two integers n (1≤n≤1000000)n\ (1 \leq n \leq 1000000)n (1≤n≤1000000) and p (2≤p≤1000000)p\ (2 \leq p \leq 1000000)p (2≤p≤1000000). is a prime number.

输出描述:

Output one number (without leading zeros) or "T_T"

示例1

输入

复制

2 5

输出

复制

10

示例2

输入

复制

1 11

输出

复制

T_T

示例3

输入

复制

5 2

输出

复制

10000

给定一个素数p，输出一个n位的p的倍数

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int p,n;
    while(scanf("%d%d",&n,&p)!=EOF)
    {
        int cnt=0;
        int tmp=p;
        while(p>0)
        {
            cnt++;
            p/=10;
        }
        if(cnt>n)
            cout<<"T_T"<<'\n';
        else
        {
            cout<<tmp;
            n-=cnt;
            while(n--)
                cout<<0;
            cout<<'\n';
        }
    }
    return 0;
}

J-A+B problem

题目描述

Reversed number is a number written in arabic numerals but the order of digits is reversed. The first digit becomes last and vice versa. And all the leading zeros are omitted.
For example: the reversed number of 1234 is 4321. The reversed number of 1000 is 1.

We define reversed number of as . Given you two positive integers and , you need to calculate the reversed sum: .

输入描述:

The first line of the input gives the number of test cases, T (T≤300)T\ (T \leq 300)T (T≤300).  test cases follow.

For each test case, the only line contains two positive integers: and . (1≤A,B≤231−11 \leq A, B \leq 2^{31}-11≤A,B≤231−1)

输出描述:

For each test case, output a single line indicates the reversed sum.

示例1

输入

复制

3
12 1
101 9
991 1

输出

复制

22
11
2

A的反转加B的反转再反转

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long a,b,ans,tmp;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld",&a,&b);
        long long c=0,d=0;
        while(a)
        {
            c*=10;
            c+=a%10;
            a/=10;
        }
        while(b)
        {
            d*=10;
            d+=b%10;
            b/=10;
        }
        tmp=c+d;
        ans=0;
        while(tmp)
        {
            ans*=10;
            ans+=tmp%10;
            tmp/=10;
        }
        cout<<ans<<'\n';
    }
    return 0;
}