Codeforces Round #710 (Div. 3)

D、Epic Transformation

题意：选择数组中不同的两个数消去，求消去后数组最少有多少个数。

思路：
出现次数最多的数，如果出现次数小于等于n，最优策略是先排出现次数少的数，然后按出现次数降序插入，最后不可能有两个及以上的数没有配对成功，那么顶多有个数找不到配对；如果出现次数大于n，那么最优的策略是把其它的数分别插到这些数中间，那么最多只有个数没有配对。

MyCode1：

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+7,maxm=1e6+7,mod=1e9+7;
typedef long long int ll;
typedef unsigned long long ull;
int a[maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T,n;
    cin>>T;
    while(T--) {
        cin>>n;
        int cnt(0),pos(0);
        for(int i=1;i<=n;++i) {
            cin>>a[i];
            if(a[i]==pos) cnt+=1;
            else if(!cnt) cnt=1,pos=a[i];
            else cnt-=1;
        }
        cnt=0;
        for(int i=1;i<=n;++i) cnt+=(pos==a[i]);
        if(cnt<=n/2)
            cout<<(n&1)<<'\n';
        else cout<<(cnt*2-n)<<'\n';
    }
    return 0;
}

MyCode2：

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+7,maxm=1e6+7,mod=1e9+7;
typedef long long int ll;
typedef unsigned long long ull;
int a[maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T,n;
    cin>>T;
    while(T--) {
        cin>>n;
        for(int i=1;i<=n;++i) cin>>a[i];
        sort(a+1,a+1+n);
        vector<int>b;    a[n+1]=0;
        for(int i=1,now;i<=n;++i) {
            now=1;
            while(a[i]==a[i+1]) {
                i+=1;
                now+=1;
            }
            b.emplace_back(now);
        }
        sort(b.begin(),b.end());
        int m=b.size()-1,ans=b[0],sum=0;
        for(int i=1;i<=m;++i) {
            sum+=b[i-1];
            if(b[i]>sum) {
                ans=b[i]-sum;
            }
            else if(ans>b[i]) ans-=b[i];
            else if((b[i]+sum)&1) ans=1;
            else ans=0;
        }
        cout<<ans<<'\n';
    }
    return 0;
}

E、Restoring the Permutation

题意：，给出q数组，输出p数组(p数组是的一个全排列)所有可能的组合中字典序最小的和最大的。

思路：
q数组中第一次出现的数，在p数组中也在同样的位置，一开始位置就确定的数肯定是递增的。它后面的空位只能填比它小的数。
讨论字典序最小，每次把可以填在确定的数后面的数存入队列，队列内的数一定是递增的，在需要填数的时候从小到大取，既不破坏q数组的性质()又保证字典序最小。
讨论字典序最大，每次把可以填在确定的数后面的数存入队列，队列内的数一定是递增的，在需要填数的时候从大到小取，既不破坏q数组的性质()又保证字典序最大。

MyCode：

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+7,maxm=1e6+7,mod=1e9+7;
typedef long long int ll;
typedef unsigned long long ull;
int a[maxn],q[maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T,n,l,r,tot;
    cin>>T;
    while(T--) {
        cin>>n;
        for(int i=1;i<=n;++i) cin>>a[i];
        l=0,r=0,tot=0;
        for(int i=1;i<=n;++i) {
            if(a[i]!=a[i-1]) {
                cout<<a[i]<<' ';
                for(int k=tot+1;k<a[i];++k) q[r++]=k;
                tot=a[i];
            }
            else cout<<q[l++]<<' ';
        }
        cout<<'\n';
        l=0,r=0,tot=0;
        for(int i=1;i<=n;++i) {
            if(a[i]!=a[i-1]) {
                cout<<a[i]<<' ';
                for(int k=tot+1;k<a[i];++k) q[r++]=k;
                tot=a[i];
            }
            else cout<<q[--r]<<' ';
        }
        cout<<'\n';
    }
    return 0;
}

F、Triangular Paths

题意：，左边表示第几层，右边表示在该层第几个，为奇数就向右下连有向边，为偶数就向左边连有向边。将向左连的边变为向右需要1个代价，反之同理。题目给出n个点，求从(1,1)开始走完所有的点需要多少贡献，保证没有相同的点且一定能走完所有的点。

思路：
保证从(1,1)开始能走完所有的点也就是说每一层顶多给一个点。
一个规律，从为奇数的点出发，只能走直线，而偶数值的点则只能走向左边相邻直线上的点(比如)。

如果出发点和目的地是同一直线上的点，则不需要代价
如果出发点是直线相连的值为偶数的点，目的地如果是左边相邻直线上的点也不需要代价，目的地如果是和出发点共连一条直线，那么需要的代价是

如果不满足上述条件，那么可以通过不断往左下，然后沿着直线往下走到上然后往左下到达目的地，中间的贡献等于跨越的直线数量。

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+7,maxm=1e6+7,mod=1e9+7;
typedef long long int ll;
typedef unsigned long long ull;
typedef pair<int,int> pai;
int r[maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T,n;
    cin>>T;
    while(T--) {
        cin>>n;
        vector<pai >a;
        for(int i=1;i<=n;++i) cin>>r[i];
        for(int i=1,c;i<=n;++i) {
            cin>>c;
            a.emplace_back(pai{r[i],c});
        }
        sort(a.begin(),a.end());
        int l=1,pos=1,ans(0),now;
        for(int i=0,x,y;i<n;++i) {
            x=a[i].first,y=a[i].second;
            now=(x-y+2)>>1;
            ans+=now-pos;
            if(!((x+y)&1)&&pos==now) ans+=x-l;
            pos=now,l=x;

        }
        cout<<ans<<'\n';
    }
    return 0;
}

G、Maximize the Remaining String

题意：删除多余的字母，使得处理后的单词每个字母只出现一次且字典序最大。

最优策略：
类似单调栈的思路，栈顶比当前字母字典序小且能删除(进栈再出栈就是一个删除的过程)则依次出栈,如果该字母没有进栈则进栈，保证了字典序最大且每个字母只出现一次。

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10,mod=1e9+7;
typedef long long int ll;
int cnt[27],n,tot;
char s[maxn],ans[maxn];
bool vis[27];
inline void solve() {
    scanf("%s",s+1);
    n=strlen(s+1),tot=0;
    for(int i=0;i<26;++i)
        cnt[i]=vis[i]=0;
    for(int i=1;s[i];++i) cnt[s[i]-'a']+=1;
    for(int i=1;s[i];++i) {
        while(tot&&s[i]>ans[tot-1]&&!vis[s[i]-'a']&&cnt[ans[tot-1]-'a']) {
            vis[ans[tot-1]-'a']=false;
            tot-=1;
        }
        cnt[s[i]-'a']-=1;
        if(!vis[s[i]-'a']) {
            ans[tot++]=s[i];
            vis[s[i]-'a']=true;
        }
    }
    ans[tot]='\0';
    puts(ans); 
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    scanf("%d",&T);
    while(T--) solve();
}
/*
1
cmjnmooljolejjg
*/