有毒的粽子

公告

Codeforces Round #585 (Div. 2) CF1215A~C

CF1215A. Yellow Cards簡(jiǎn)單的模擬，給定了黃票張數(shù)，判斷最少和最多有多少人被罰下場(chǎng)。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,aa,bb,n,nnn;
    cin>>a>>b>>aa>>bb>>n;
    nnn=n;
    int t=(aa-1)*a+(bb-1)*b;
    int tt=0;
    if(aa<=bb)
    {
        if(n>=aa*a)
        {
            tt+=a;
            n-=aa*a;
        }
        else
        {
            tt+=n/aa;
            int o=n/aa;
            n-=o*aa;
        }
        if(n>=bb*b)
        {
            tt+=b;
            n-=bb*b;
        }
        else
        {
            tt+=n/bb;
            int o=n/bb;
            n-=o*bb;
        }
    }
    else
    {
        if(n>=bb*b)
        {
            tt+=b;
            n-=bb*b;
        }
        else
        {
            tt+=n/bb;
            int o=n/bb;
            n-=o*bb;
        }
        if(n>=aa*a)
        {
            tt+=a;
            n-=aa*a;
        }
        else
        {
            tt+=n/aa;
            int o=n/aa;
            n-=o*aa;
        }
    }
    if(t>=nnn)
    {
        cout<<"0 "<<tt<<endl;
    }
    else
    {
        cout<<min(nnn-t,a+b)<<" "<<tt<<endl;
    }
    return 0;
}

A. Yellow Cards

CF1215B. The Number of Products，我們以第一位數(shù)到最后一位數(shù)的乘積來分析，1-n的狀態(tài)數(shù)分別是n n-1 n-2……1。

觀察易得減少一個(gè)正數(shù)時(shí)，正數(shù)的狀態(tài)-1，減少一個(gè)負(fù)數(shù)時(shí)，負(fù)數(shù)的狀態(tài)數(shù)-1，并正負(fù)狀態(tài)交換，即可O(n)遞推求出答案

#include <bits/stdc++.h>
using namespace std;
int a[2000005];
typedef long long ll;
int main()
{
    int n;
    cin>>n;
    ll l=0,r=0;
    ll tt=1;
    for(int i=1;i<=n;++i)
    {
        ll t;
        cin>>t;
        if(t>0)
        {
            a[i]=1;
        }
        else
        {
            a[i]=-1;
        }
        tt*=a[i];
        if(tt>0)
        {
            l++;
        }
        else
        {
            r++;
        }
    }
    ll al=l,ar=r;
    for(int i=2;i<=n;++i)
    {
        if(a[i-1]>0)
        {
            l--;
        }
        else
        {
            r--;
            swap(l,r);
        }
        al+=l;
        ar+=r;
    }
    cout<<ar<<" "<<al;
    return 0;
}

B. The Number of Products

CF1215C. Swap Letters 首先只有ab和ba出現(xiàn)的次數(shù)為奇數(shù)不成立，其余時(shí)候ab\ba可和ab\ba一次配對(duì)，ab和ba需要兩次這里我用了vecotr來避免重復(fù)使用

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int>vt1;
vector<int>vt2;
int main()
{
    int n,aaa=0;
    cin>>n;
    string str1,str2;
    cin>>str1>>str2;
    int flag=0;
    for(int i=0;i<str1.size();++i)
    {
        if(str1[i]=='a'&&str2[i]=='a')
        {
            flag++;
        }
        if(str1[i]=='b'&&str2[i]=='b')
        {
            flag++;
        }
    }
    flag=n-flag;
    if(flag%2!=0)
    {
        cout<<-1;
        return 0;
    }
    for(int i=0;i<str1.size();++i)
    {
        if(str1[i]=='a'&&str2[i]=='b')
        {
            vt1.push_back(i);
        }
        if(str2[i]=='a'&&str1[i]=='b')
        {
            vt2.push_back(i);
        }
    }
    for(int i=vt1.size()-1;i>=0;i-=2)
    {
        int j=i-1;
        if(j>=0)
        {
            aaa++;
            vt1.pop_back();
            vt1.pop_back();
        }
    }
    for(int i=vt2.size()-1;i>=0;i-=2)
    {
        int j=i-1;
        if(j>=0)
        {
            aaa++;
            vt2.pop_back();
            vt2.pop_back();
        }
    }
    if(vt1.size())
    {
        int i=vt1.size()-1;
        int j=vt2.size()-1;
        aaa++;
        aaa++;
    }
    cout<<aaa<<endl;
    vt1.clear();
    vt2.clear();
    for(int i=0;i<str1.size();++i)
    {
        if(str1[i]=='a'&&str2[i]=='b')
        {
            vt1.push_back(i);
        }
        if(str2[i]=='a'&&str1[i]=='b')
        {
            vt2.push_back(i);
        }
    }
    for(int i=vt1.size()-1;i>=0;i-=2)
    {
        int j=i-1;
        if(j>=0)
        {
            cout<<vt1[j]+1<<" "<<vt1[i]+1<<endl;
            vt1.pop_back();
            vt1.pop_back();
        }
    }
    for(int i=vt2.size()-1;i>=0;i-=2)
    {
        int j=i-1;
        if(j>=0)
        {
            cout<<vt2[j]+1<<" "<<vt2[i]+1<<endl;
            vt2.pop_back();
            vt2.pop_back();
        }
    }
    if(vt1.size())
    {
        int i=vt1.size()-1;
        int j=vt2.size()-1;
        cout<<vt1[i]+1<<" "<<vt1[i]+1<<endl;
        cout<<vt1[i]+1<<" "<<vt2[j]+1<<endl;
    }
    return 0;
}

C. Swap Letters

posted on 2019-09-16 22:42 有毒的粽子閱讀(228) 評(píng)論(0) 收藏舉報(bào)

刷新頁面返回頂部