Codeforces Round #545 (Div. 2)

悠悠 2023-06-03 13:52 22阅读 0赞

A. Sushi for Two

求连续最长的1，2子序列，要求1和2的数量相等；

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    using namespace std;
    const int maxn=1e5+10;
    typedef long long ll;
    int a[maxn];
    int ans[maxn];
    int main(){
        int n;
        cin>>n;
        int cnt1=0,cnt2=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        int tot=0;
        for(int i=2;i<=n;i++){
            if(a[i]==1&&a[i-1]==1){
                cnt1++;
            }
            else if(a[i]==1&&a[i-1]!=1){
                ans[tot++]=cnt2+1;
                cnt2=0;
            }
            if(a[i]==2&&a[i-1]==2){
                cnt2++;
            }
            else if(a[i]==2&&a[i-1]!=2){
                ans[tot++]=cnt1+1;
                cnt1=0;
            }
        }
        ans[tot]=cnt1+cnt2+1;
        int res=1;
        for(int i=0;i<tot;i++){
            res=max(res,min(ans[i],ans[i+1]));
        }
        cout<<res*2<<endl;
     
     
     
     
     
        return 0;
    }

B. Circus

求第一排选择1的数量等于第二排选择1的数量，输出第一排选择的位置；

对（0，0）（1，0）（0，1）（1，1）进行记录，先将（0，1）（1，1）都安排给第二个演出，然后枚举（1，0）（1，1）的个数，

找到满足的每个可能的数量，输出即可，找不到就-1；

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+10;
    vector<int>a,b,c,d;
    int n;
    char s[maxn],t[maxn];
    int main(){
        scanf("%d%s%s",&n,s+1,t+1);
        for(int i=1;i<=n;i++){
            if(s[i]=='0'&&t[i]=='0')a.push_back(i);
            else if(s[i]=='1'&&t[i]=='0')b.push_back(i);
            else if(s[i]=='0'&&t[i]=='1')c.push_back(i);
            else if(s[i]=='1'&&t[i]=='1')d.push_back(i);
        }
        for(int i=0;i<=b.size();i++){
            for(int j=0;j<=d.size();j++){
                int res=d.size()+c.size()-i-2*j;
                if(res>=0&&res<=c.size()){
                    int sum=i+j+res;
                    int k=n/2-sum;
                    if(k>=0&&k<=a.size()){
                        //cout<<k<<' '<<i<<' '<<sum<<' '<<j<<endl;
                        for(int z=0;z<k;z++)printf("%d ",a[z]);
                        for(int z=0;z<i;z++)printf("%d ",b[z]);
                        for(int z=0;z<res;z++)printf("%d ",c[z]);
                        for(int z=0;z<j;z++)printf("%d ",d[z]);
                        return 0;
                    }
                }
            }
        }
        printf("-1");
     
     
        return 0;
    }

C. Skyscrapers

看不懂。……待补

这场整体挺难的》》还是自己太弱

转载于:https://www.cnblogs.com/lin1874/p/11350550.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/331938d3234647138283dad851fc79e8.png