Codeforces Round #710 (Div. 3)

这就是签到场，小的n次方号打的，打的原因是被上周edu&div1&ARC&ABC四连杀来找找自信

ABC

阅读理解题，签到不解释

稍微需要脑子的签到。找众数就行，如果不超过n/2，始终拿它删当前出现次多的数，一直这样，发现答案是n%2；如果超过就是2*mx-n（拿这个数删其他数）

#include
using namespace std;
const int N=2e5+7;
int n,a[N];
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        int num=1,mx=1;
        for(int i=2;i<=n;i++)
        {
            if(a[i]==a[i-1])num++;else num=1;
            mx=max(mx,num);
        }
        if(mx<=n/2)printf("%d\n",n%2);
        else printf("%d\n",2*mx-n);
    }
}

每次a[i]变化时该位注定为a[i]，然后把(a[i-1],a[i])从小到大加入队列/栈，如果求最小字典序就是队列，最大字典序就是栈，然后遇到相同的时候从队头/栈顶弹出

#include
using namespace std;
const int N=2e5+7;
int n,top,a[N],st[N];
bool b[N];
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=0;
        int p=1;
        for(int i=1;i<=n;i++)
        if(a[i]!=a[i-1])b[a[i]]=1,printf("%d ",a[i]);
        else{
            while(b[p])++p;
            b[p]=1,printf("%d ",p);
        }
        puts("");
        top=0;
        for(int i=1;i<=n;i++)
        if(a[i]!=a[i-1])
        {
            printf("%d ",a[i]);
            for(int j=a[i-1]+1;jj;
        }
        else printf("%d ",st[top--]);
        puts("");
    }
}

挺有意思的规律题。发现原图就是形如梳子的连接方式，然后根据当前位边向左/右分类讨论，讨论其往左走了几步即可

#include
using namespace std;
const int N=2e5+7;
struct node{int r,c;}a[N];
int n,ans;
bool cmp(node a,node b){return a.r<b.r;}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",&a[i].r);
        for(int i=1;i<=n;i++)scanf("%d",&a[i].c);
        sort(a+1,a+n+1,cmp);
        ans=0;
        int nr=1,nc=1;
        for(int i=1;i<=n;i++)
        if(a[i].r!=nr)
        {
            int tp=(nr+nc&1);
            if(!tp)
            {
                if(a[i].r-nr==a[i].c-nc)ans+=a[i].r-nr;
                else ans+=(a[i].r-nr-a[i].c+nc)/2;
            }
            else ans+=(a[i].r-nr-a[i].c+nc+1)/2;
            nr=a[i].r,nc=a[i].c;
        }
        printf("%d\n",ans);
    }
}

发现字符串长度就是不同字母数，也就是说不超过26，也就是说可以从头开始枚举当前位置的字母，从大到小枚举依次判断是否符合条件，符合就停止判断搜下一位。判断方式是贪心，放该字母符合条件的最早出现位置，然后求其他未放置字母的最后一个位置的最小值是否在当前位置前面，若不在则符合条件。复杂度O(26Σn)

#include
using namespace std;
const int N=2e5+7;
int n,now,num,has[26];
char s[N];
vector<int>pos[26];
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s+1);
        n=strlen(s+1);
        for(int i=0;i<26;i++)has[i]=0,pos[i].clear();
        for(int i=1;i<=n;i++)pos[s[i]-'a'].push_back(i);
        num=now=0;
        for(int i=0;i<26;i++)if(pos[i].size())num++;else has[i]=1;
        for(int ca=1;ca<=num;++ca)
        for(int i=25;~i;--i)
        if(!has[i])
        {
            int pl=-1,mn=n+1;
            for(int j=0;jif(pos[i][j]>now){pl=pos[i][j];break;}
            if(pl==-1)continue;
            for(int j=0;j<26;++j)if(!has[j])mn=min(mn,pos[j][pos[j].size()-1]);
            if(mn>=pl){now=pl,printf("%c",'a'+i),has[i]=1;break;}
        }
        puts("");
    }
}

1hAK rank4 rating+=584

比赛记录

Codeforces Round #710 (Div. 3)

相关

标签