2019牛客暑期多校训练营（第七场）

题目描述

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\$

输出描述:

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

示例1

输入

输出

0
0001
001 0
111 01111 0

题意：给一个01构成的字符串，要把该字符串切分成最少的份数，使得每一个字符串都是循环移位字典序最小的字符串。

#include <bits/stdc++.h>

using namespace std;
string s;
int len,ans;
int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        cin>>s;
        len=s.length();
        for (int i=0; i<len; i++)
        {
            ans=i;
            for (int j=len-1; j>=i; j--)
            {
                vector<string>V;
                for (int k=i; k<=j; k++)
                {
                    V.push_back(s.substr(k,j-k+1)+s.substr(i,k-i));
                }
                sort(V.begin(),V.end());
                if (V[0]==s.substr(i,j-i+1))
                {
                    ans=j;
                    break;
                }
            }
            cout<<s.substr(i,ans-i+1);
            if (ans==len-1)
            {
                printf("
");
            }
            else
            {
                printf(" ");
            }
            i=ans;
        }
    }
}

题意：给一个n次多项式，判断该多项式能不能在实数域拆分

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

#include<bits/stdc++.h>
int a[1000];
using namespace std;
int main()
{
    int T,n;
    double b;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d",&n);
        for (int i=n; i>=0; i--)
        {
            scanf("%d",&a[i]);
        }
        if (n==0||n==1)
        {
            printf("Yes
");
            continue;
        }
        if (n==2)
        {
            if (a[1]*a[1]-4*a[2]*a[0]>=0)
            {
                printf("No
");
            }
            else
            {
                printf("Yes
");
            }
            continue;
        }
        if (n>=3)
        {
            printf("No
");
        }
    }
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f(ll a){
    ll res=0;
    while (a){
        res=res*10+a%10;
        a=a/10;
    }
    return res;
}
ll a,b;
int main(){
    int T;
    scanf("%d",&T);
    while (T--){
        scanf("%lld%lld",&a,&b);
        printf("%lld
",f(f(a)+f(b)));
    }
}

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e6+10;

int n;
char s[maxn];

int main()
{
    scanf("%d",&n);
    scanf("%s",s);
    int len=strlen(s);
    if (n<len)
    {
        printf("T_T
");
        return 0;
    }
    printf("%s",s);
    for (int i=0; i<n-len; i++)
    {
        printf("0");
    }
    printf("
");
}

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+100;
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3f;
struct node
{
    ll p,c,h;
} a[maxn];
ll ans;
ll pre[maxn],suf[maxn],num[maxn];
bool cmp(node a,node b)
{
    return a.h<=b.h;
}

int main()
{
    int T,n;
    while (~scanf("%d",&n))
    {
        map<ll,ll>m;
        memset(num,0,sizeof(num));
        for (int i=1; i<=n; i++)
        {
            scanf("%lld%lld%lld",&a[i].h,&a[i].c,&a[i].p);
            m[a[i].h]+=a[i].p;
        }
        sort(a+1,a+n+1,cmp);
        for (int i=1;i<=n;i++){
            pre[i]=pre[i-1]+a[i].c*a[i].p;
        }
        for (int i=n; i>=1; i--)
        {
            suf[i]=suf[i+1]+a[i].p*a[i].c;
        }
        ans=inf;
        for (int i=1; i<=n; i++)
        {
            ll re=0;
            ll all=m[a[i].h]-1;
            for (int j=200; j>=1; j--)
            {
                if (num[j]<all)
                {
                    re+=num[j]*j;
                    all-=num[j];
                }
                else
                {
                    re+=all*j;
                    all=0;
                    break;
                }
            }
            num[a[i].c]+=a[i].p;
            int pos=i+1;
            while (a[pos].h==a[i].h)
            {
                pos++;
            }
            ans=min(ans,pre[i-1]-re+suf[pos]);
        }
        printf("%lld
",ans);
    }
}

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+10;
typedef long long ll;
ll ans,res,tall,tot;
struct node
{
    int h,c,p,pos;
} a[maxn];

bool cmp2(node a,node b)
{
    return a.h<b.h;
}

bool cmp1(node a,node b)
{
    return a.c<b.c;
}

struct node1
{
    int l,r;
    ll num,sum;
} tree[maxn*4];

void build(int rt,int l,int r)
{
    tree[rt].l=l;
    tree[rt].r=r;
    tree[rt].num=0;
    tree[rt].sum=0;
    if (l==r)
    {
        return;
    }
    int mid=(l+r)>>1;
    build (rt<<1,l,mid);
    build (rt<<1|1,mid+1,r);
}

void pushup(int rt)
{
    if (tree[rt].l==tree[rt].r)
    {
        return;
    }
    tree[rt].num=tree[rt<<1].num+tree[rt<<1|1].num;
    tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;
}

void add(int rt,int pos,ll c,ll p)
{
    if (tree[rt].l==tree[rt].r)
    {
        tree[rt].num+=p;
        tree[rt].sum+=p*c;
        return;
    }
    int mid=(tree[rt].l+tree[rt].r)>>1;
    if (pos<=mid) add(rt<<1,pos,c,p);
    else add(rt<<1|1,pos,c,p);
    pushup(rt);
}

ll query(int rt,ll num)
{
    if (num<=0)
    {
        return 0;
    }
    if (num>=tree[rt].num) return tree[rt].sum;
    if (tree[rt].l==tree[rt].r)
    {
        return tree[rt].sum/tree[rt].num*num;
    }
    return query(rt<<1,num)+query(rt<<1|1,num-tree[rt<<1].num);
}

int main()
{
    int n,j;
    while (~scanf("%d",&n))
    {
        ans=0;
        for (int i=1; i<=n; i++)
        {
            scanf("%lld%lld%lld",&a[i].h,&a[i].c,&a[i].p);
            ans+=a[i].c*a[i].p;
        }
        sort(a+1,a+n+1,cmp1);
        for (int i=1; i<=n; i++)
        {
            a[i].pos=i;
        }
        j=tot=0;
        build (1,1,n);
        sort(a+1,a+n+1,cmp2);
        res=ans-a[1].p*a[1].c;
        tall=a[1].p;
        for (int i=2; i<=n+1; i++)
        {
            if (i==n+1||a[i].h!=a[i-1].h)
            {
                ans=min(ans,query(1,tot-(tall-1))+res);
                tall=a[i].p;
                if (i<=n)
                {
                    while (j<i)
                    {
                        add(1,a[j].pos,a[j].c,a[j].p);
                        tot+=a[j].p;
                        j++;
                    }
                }
            }
            else
            {
                tall+=a[i].p;
            }
            if (i<=n) res-=a[i].p*a[i].c;
        }
        printf("%lld
",ans);
    }
    return 0;
}