CSU-ACM2019暑假集训（1）

雨点打透心脏的1/2处 2021-11-10 02:16 176阅读 0赞

原CF 1138A Sushi for Two  
![1678292-20190721193544252-1519367214.png][]

## 基本思路 ##

每个状态之和之前的一个连续状态有关，并且取下限即可，若状态发生改变，计数器置零

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int n;cin>>n;int num1=0,num2=0,sum=0;
        int pre=0;
        for(int i=0;i<n;i++)
        {
            int num;cin>>num;
            if(num==1)
            {
                if(pre==2)
                    num1=0;
                num1++;
            }
            if(num==2)
            {
                if(pre==1)
                    num2=0;
                num2++;
            }
            pre=num;
            sum=max(sum,min(num1,num2));
        }
        cout<<sum*2<<endl;
    }

原CF 1141C Polycarp Restores Permutation  
![1678292-20190721193812792-26630357.png][]

## 基本思路 ##

确定开头数字为最大，后面即可推导出来，然后原数列从1开始，因此减去最大和最小的差，最后用vector判断是否重复

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll n;ll q[200020],arr[200020];
    vector<ll>brr;
    int main()
    {
        cin>>n;
        for(int i=0;i<n-1;i++)
        {
            cin>>q[i];
        }
        arr[0]=n;ll maxn=n,minn=9999999;
        for(int i=1;i<n;i++)
        {
            arr[i]=arr[i-1]+q[i-1];
            maxn=max(maxn,arr[i]);
        }
        for(int i=0;i<n;i++)
        {
            arr[i]-=maxn-n;
            brr.push_back(arr[i]);
        }
        sort(brr.begin(),brr.end());
        for(int i=0;i<n-1;i++)
        {
            if(brr[i+1]-brr[i]!=1)
            {
                //cout<<i<<endl;
                cout<<-1<<endl;
                return 0;
            }
        }
        for(int i=0;i<n;i++)
        {
            cout<<arr[i]<<" ";
        }
        return 0;
    }

F题 原CF 1141E Superhero Battle  
![1678292-20190721194328924-348854446.png][]

## 基本思路 ##

减去第一次最小值，判断有无超过h，然后循环减，使用除法，最后一次使用步进

#include<bits/stdc++.h>
    typedef long long ll;
    using namespace std;
    ll h,n,arr[200020];
    int main()
    {
        cin>>h>>n;
        long long sum=0,time=0,minn=0,cnt=0;
        for(int i=1;i<=n;i++)
        {
            cin>>arr[i];
            sum+=arr[i];
            if(sum<minn)
            {
                minn=min(minn,sum);
                cnt=i;  
            }
            if(minn+h<=0)
            {
                cout<<i<<endl;
                return 0;
            }
        }
        //cout<<sum<<" "<<cnt<<endl;
        if(sum>=0&&minn<h)
        {
            cout<<-1<<endl;
            return 0;
        }
        h+=minn;
        time+=cnt;
        time+=(h/(-sum))*n;
        h=h%(-sum);
    //  cout<<h<<endl;
        ll i=cnt+1;
        while(h>0)
        {
            if(i%(n+1)==0)i++;
            h+=arr[(i++)%(n+1)];
            //cout<<h<<endl; 
            time++;
        }
        cout<<time;
        return 0;
    }

转载于:https://www.cnblogs.com/tldr/p/11222419.html

[1678292-20190721193544252-1519367214.png]: /images/20211109/286d2598956a4f55a2c24da828735deb.png
[1678292-20190721193812792-26630357.png]: /images/20211109/3846b1f26e3d427dbaf6ab72e3fbb380.png
[1678292-20190721194328924-348854446.png]: /images/20211109/1b598f2dc4ee4d6d88981638237af4e7.png