Codeforces Round #550 (Div. 3)

Posted by

A.Diverse Strings

简单的模拟,似乎有几个坑点。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <set>
#include <algorithm>
static const int MAXN=100050;
using namespace std;
string s;
set<char> ss;
int n,mm;
bool flag=true;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        s.clear();
        ss.clear();
        flag=false;
        cin>>s;
        sort(s.begin(),s.end());
        for(int i=0;i<s.length();i++) ss.insert(s[i]);
        if(s.length()==1){
            printf("Yes\n");
            continue;
        }
        if((int)ss.size()!=s.length()){
            printf("No\n");
            continue;
        }
        for(int i=0;i<s.length()-1;i++){
            if(s[i]-'a'+1!=s[i+1]-'a'){
                flag=true;
                break;
            }
        }
        !flag?printf("Yes\n"):printf("No\n");
    }
    return 0;
}

B.Parity Alternated Deletions

要消耗大的数才能保证最后剩的尽可能小,模拟即可。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int n,x,ans,yyy;
vector<int> v1,v2;
inline int read(){
    int x=0;
    bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        x=read();
        x&1?v1.push_back(x):v2.push_back(x);
    }
    sort(v1.begin(),v1.end());
    sort(v2.begin(),v2.end());
    if(v1.size()==0) for(int i=0;i<v2.size()-1;i++) ans+=v2[i];
    else if(v2.size()==0) for(int i=0;i<v1.size()-1;i++) ans+=v1[i];
    else if(v1.size()-1>v2.size()) for(int i=0;i<v1.size()-v2.size()-1;i++) ans+=v1[i];
    else if(v1.size()<v2.size()-1) for(int i=0;i<v2.size()-v1.size()-1;i++) ans+=v2[i];
    printf("%d\n",ans);
    return 0;
}

C.Two Shuffled Sequences

若一个数字出现超过2次,则就不能保证严格单调性,即不满足条件。

满足条件后把出现次数不唯一的数字放入单增和单减序列中即可。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
static const int MAXN=200070;
using namespace std;
int n,a[MAXN],num[MAXN];
vector<int>v1,v2;
bool vis[MAXN];
inline int read(){
    int x=0;
    bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        num[a[i]]++;
        if(num[a[i]]>2) return 0&printf("NO\n");
    }
    for(int i=1;i<=n;i++){
        if(vis[a[i]]) continue;
        if(num[a[i]]!=1) vis[a[i]]=true,v1.push_back(a[i]),v2.push_back(a[i]);
        else vis[a[i]]=true,v1.push_back(a[i]);
    }
    sort(v1.begin(),v1.end());
    sort(v2.begin(),v2.end());
    printf("YES\n");
    printf("%d\n",v1.size());
    if(!v1.size()) printf("\n");
    for(int i=0;i<v1.size();i++) printf("%d%c",v1[i],i==v1.size()-1?'\n':' ');
    printf("%d\n",v2.size());
    if(!v2.size()) printf("\n");
    for(int i=v2.size()-1;i>=0;i--) printf("%d%c",v2[i],i==0?'\n':' ');
    return 0;
}

D.Equalize Them All

由于是求最小次数,从而可以先找到出现次数最多的那个数字的位置pos,然后从1pos-1pos+1n处理即可。

判断一下大小从而确定操作即可。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
static const int MAXN=200050;
using namespace std;
int n,mmm,Max,pos,a[MAXN],num[MAXN];
set<int> s;
vector<pair<int,int> > Ans1,Ans2;
inline int read(){
    int x=0;
    bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        s.insert(a[i]);
        num[a[i]]++;
        if(num[a[i]]>Max){
            Max=num[a[i]];
            pos=i;
        }
    }
    if(s.size()==1) return 0&printf("0\n");
    for(int i=pos-1;i>=1;i--){
        if(a[i]==a[i+1]) continue;
        if(a[i]<a[i+1]) Ans1.push_back(make_pair(1,i));
        else Ans1.push_back(make_pair(2,i));
        a[i]=a[i+1];
    }
    for(int i=pos+1;i<=n;i++){
        if(a[i]==a[i-1]) continue;
        if(a[i-1]<a[i]) Ans2.push_back(make_pair(2,i));
        else Ans2.push_back(make_pair(1,i));
        a[i]=a[i-1];
    }
    printf("%d\n",Ans1.size()+Ans2.size());
    for(int i=0;i<Ans1.size();i++) printf("%d %d %d\n",Ans1[i].first,Ans1[i].second,Ans1[i].second+1);
    for(int i=0;i<Ans2.size();i++) printf("%d %d %d\n",Ans2[i].first,Ans2[i].second,Ans2[i].second-1);
    return 0;
}

 

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注