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
*/