Codeforces Round #436 (Div. 2) A,B,D

A. Fair Game

题目链接：http://codeforces.com/contest/864/problem/A

水题

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<stack>

#include<map>

#include<vector>

#include<set>

using namespace std;

const int MAX=1e5+;

const double eps=1e-;

const double mod=1e9+;

#define INF 0x7fffffff

#define ll long long

#define edl putchar('\n')

#define useit  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define FOR(i,a,b) for(ll i=a;i<=b;i++)

#define ROF(i,a,b) for(ll i=a;i>=b;i--)

#define mst(a) memset(a,0,sizeof(a))

#define mstn(a,n) memset(a,n,sizeof(a))

#define lowbit(x) x&(-x)

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

//struct num{int v,i;}l[MAX],r[MAX];

//bool cmp(const num &x, const num &y){return x.v<y.v;}

int main()

{

    int n,a[MAX],b,t=,s1=,s2=;

    FOR(i,,)a[i]=;

    cin>>n;

    FOR(i,,n)

    {

        cin>>b;

        if(!a[b])

        t++;

        a[b]++;

    }

    if(t==)

    {

        FOR(i,,) if(a[i]){s1=i;break;}

        ROF(i,,) if(a[i]){s2=i;break;}

        if(a[s1]==a[s2]&&s1!=s2)

        cout<<"YES"<<endl<<s1<<" "<<s2<<endl;

        else

        cout<<"NO"<<endl;

    }

    else

    cout<<"NO"<<endl;

}

B. Polycarp and Letters

题目链接：http://codeforces.com/contest/864/problem/B

水题，写太急了，忘了考虑全是小写字母的情况，wa了两发血亏。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int inf = 1e9+;

const int M = 1e5+;

map<char,int>mp;

int main()

{

    int n,maxx;

    char s[];

    cin>>n;

    for(int i=;i<n;i++)

        cin>>s[i];

    maxx = -inf;

    int ans = ;

    for(char i = 'a';i<='z';i++){

                mp[i] = ;

            }

    for(int i=;i<n;i++){

        if(s[i]>='a'&&s[i]<='z'){

            if(mp[s[i]]==)

            {

                ans++;

                mp[s[i]]=;

            }

        }

        else{

            maxx = max(ans,maxx);

            ans = ;

            for(char i = 'a';i<='z';i++){

                mp[i] = ;

            }

        }

    }

    maxx = max(ans,maxx);

    cout<<maxx<<endl;

    return ;

}

D. Make a Permu！

题目链接：http://codeforces.com/contest/864/problem/D

题目有点水，直接暴力过了。。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int inf = 1e9+;

const int M = 2e5+;

map<int,int>mp;

int a[M],flag[M];

int main()

{

    int n,maxx,i,j;

    cin>>n;

    maxx = -inf;

    memset(flag,,sizeof(flag));

    int cnt = ;

    for(i=;i<n;i++){

        cin>>a[i];

        mp[a[i]]++;

        if(mp[a[i]]>)

        cnt++;

        maxx = max(a[i],maxx);

    }

    int l=;

    for(i=;i<n;i++){

        if(mp[a[i]]>){

            for(j=l+;j<=M;j++){

            if(mp[j]==){

                  mp[j]==;

                  l = j;break;

             }

           }

           //cout<<l<<endl;

            if(l<a[i]){

                   //cout<<mp[a[i]]<<endl;

                mp[a[i]]-=,a[i]=l;  //之前这里先替换再标记。搞得wa了一发，血亏。。还好学长出了发神样例查到了

                //cout<<mp[a[i]]<<endl;

            }

            else{

                if(flag[a[i]]==){

                    mp[a[i]]--,a[i]=l;

                }

                else{

                    mp[l]==;l--;

                    flag[a[i]] = ;

                }

            }

        }

    }

    cout<<cnt<<endl;

    for(i=;i<n;i++){

        cout<<a[i]<<" ";

    }

    cout<<endl;

    return ;

}