首页

Codeforces Round 913 (Div. 3)A~F

比赛链接

A. Rook

题目大意

给出国际棋盘中车的位置，求该车一步能走到的位置（车可以横向或纵向移动任意步数）

思路

模拟

代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=9;
int awa[maxn][maxn];
signed main()
{
    int t=read();
    while(t-->0)
    {
        string awa;cin>>awa;
        for(int i=1;i<=8;i++)
        {
            if(awa[1]-'0'!=i) cout<<awa[0]<<i<<endl;
        }
        for(char i='a';i<='h';i++)
        {
            if(awa[0]!=i) cout<<i<<awa[1]<<endl;
        }
    }
    return _123hh2;
}

B. YetnotherrokenKeoard

题目大意

给出一个字符串，模拟输入操作，当遇到 $B$ 时删除先前最后输入的大写字母，遇到 $b$ 时删除先前最后输入的小写字母，若没有则视为不操作，求最后的字符串

思路

模拟，先将这个字符串的每个位置状态记为 $1$ ，对于需要删除的大小写字母，我们可以用两个数组分别记录，碰到 $B,b$ 时将最后进入数组的大小写字母状态置为 $0$ ，最后再扫描一下这个字符串即可

代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=1e6+11;
int x[maxn],d[maxn];
bool judge[maxn];
void init(int q)
{
    for(int i=0;i<=q;i++) x[i]=0,d[i]=0,judge[i]=1;
}
signed main()
{
    int t=read();
    while(t-->0)
    {
        string awa;cin>>awa;
        init(awa.length());
        int cntx=0,cntd=0;
        for(int i=0;i<awa.length();i++)
        {
            if(awa[i]>='a'&&awa[i]<='z'&&awa[i]!='b') x[++cntx]=i;
            if(awa[i]>='A'&&awa[i]<='Z'&&awa[i]!='B') d[++cntd]=i;
            if(awa[i]=='B'&&cntd) judge[d[cntd]]=0,cntd--;
            if(awa[i]=='b'&&cntx) judge[x[cntx]]=0,cntx--;
        }
        for(int i=0;i<awa.length();i++)
        {
            if(judge[i]&&awa[i]!='B'&&awa[i]!='b') cout<<awa[i];
        }
        cout<<endl;
    }
    return _123hh2;
}

C. Removal of Unattractive Pairs

题目大意

给你一个长度为 $n$ 的字符串，你可以将这个字符串任意两个不相同的字母从这个字符串中删除，求这个字符串可能的最小长度

思路

贪心

字符串最后不能删除的情况有三种

  • 字符串为空
  • 字符串只剩一个字母
  • 字符串剩余的字母都是相同的

所以我们可以找出该字符串中出现次数最多的那个字母，尽可能将这个字母先删除完即可

代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=27;
int tong[maxn];
void init() {for(int i=0;i<26;i++) tong[i]=0;}
signed main()
{
    int t=read();
    while(t-->0)
    {
        int n=read();init();string awa;cin>>awa;
        for(int i=0;i<awa.length();i++) tong[awa[i]-'a']++;
        int maxx=0;
        for(int i=0;i<26;i++) maxx=max(maxx,tong[i]);
        if(n%2==0)
        {
            if(n-maxx>=maxx) puts("0");
            else write(2*maxx-n),puts("");
        }
        else
        {
            if(n-maxx>=maxx) puts("1");
            else write(2*maxx-n),puts("");
        }
    }
    return _123hh2;
}

D. Jumping Through Segments

题目大意

给出 $n$ 条线段，每个线段都在数轴上，左右端点为 $l_i,r_i$ ，现有一玩家从坐标 $0$ 出发，每次都能移动不超过 $k$ 的距离，且第 $i$ 次移动过后必须落在第 $i$ 个线段上，求 $k$ 可能的最小值

思路

二分

不难发现 $k$ 的取值满足二分答案的性质，所以我们可以对 $k$ 进行二分

如何判断一个 $k$ 是否合法？

我们可以维护两个值 $nowl,nowr$ 表示当前所能到达的最左和左右位置，再模拟每次移动更新两个值即可

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=2e5+1;
struct A {int l,r;}awa[maxn];
bool judge(int k,int n)
{
    int nowl=0,nowr=0;
    for(int i=1;i<=n;i++)
    {
        if(awa[i].l>nowr+k||awa[i].r<nowl-k) return 0;
        if(awa[i].l>=nowl-k&&awa[i].r<=nowr+k) {nowl=awa[i].l,nowr=awa[i].r;continue;}
        if(awa[i].l<=nowl-k&&awa[i].r>=nowr+k) {nowl-=k,nowr+=k;continue;}
        if(awa[i].r>=nowl-k&&awa[i].r<=nowr+k) {nowl-=k,nowr=awa[i].r;continue;}
        if(awa[i].l>=nowl-k&&awa[i].l<=nowr+k) {nowl=awa[i].l,nowr+=k;continue;}
    }
    return 1;
}
signed main()
{
    int t=read();
    while(t-->0)
    {
        int n=read();
        for(int i=1;i<=n;i++) awa[i].l=read(),awa[i].r=read();
        int l=0,r=1e9;
        while(l!=r)
        {
            int mid=(l+r)/2;
            if(judge(mid,n)) r=mid;
            else l=mid+1;
        }
        write(l),puts("");
    }
    return _123hh2;
}

E. Good Triples

题目大意

给出一个数 $n$ ，求有多少个 $(a,b,c)$ 满足

  • $a+b+c=n$
  • $digsum(a)+digsum(b)+digsum(c)=digsum(n)$

其中 $digsum(x)$ 的值为数 $x$ 每位的数之和

思路

将 $n$ 按位进行拆分，令 $a,b,c$ 的对应位之和等于 $n$ 的对应位

这样可以保证上述两条规则成立，不难发现每位都是互相独立的，所以最终答案就是每位的方案数之乘

对于每位数的方案数，相当于 $n$ 个球放入三个编号不同的盒子，允许盒子为空的方案数

代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
int num[10]={1,3,6,10,15,21,28,36,45,55};
int div(int x)
{
    int sum=1;
    while(x)
    {
        sum*=num[x%10];x/=10;
    }
    return sum;
}
signed main()
{
    int t=read();
    while(t-->0)
    {
        int n=read();
        write(div(n)),puts("");
    }
    return _123hh2;
}

F. Shift and Reverse

题目大意

给出一个长度为 $n$ 的数组，现有两种操作

  • 移位：将数组的最后一个元素移到首位，并将所有其他元素向右移动
  • 反转：将整个数组反转

求将该数组变成非递减排序的最小操作次数，否则输出 $-1$

思路

贪心+模拟

我们发现，将数组看成首尾衔接的环，对于两个操作来说是不会改变环上每个元素的位置的

所以判断是否有解可以看从某个位置出发顺序访问的值是否递增/递减即可

代码

#include<bits/stdc++.h>
#define int long long
#define in inline
#define ri register
#define _123hh2 0
using namespace std;
in int read()
{
    int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
}
in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
const int maxn=1e5+1;
int awa[maxn<<1];
signed main()
{
    int t=read();
    while(t-->0)
    {
        int n=read(),ans=1e9;
        for(int i=1;i<=n;i++) awa[i]=read(),awa[i+n]=awa[i];
        for(int i=1;i<=n;i++)
        {
            int now=i,cnt=1;
            while(awa[i]>=awa[i+1]&&i<2*n) i++,cnt++;
            if(cnt>=n) ans=min(now,n-now+2);
        }
        for(int i=1;i<=n;i++)
        {
            int now=i,cnt=1;
            while(awa[i]<=awa[i+1]&&i<2*n) i++,cnt++;
            if(cnt>=n) ans=min(min(ans,now+1),n-now+1);
            if(cnt>=n&&now==1) ans=0;
        }
        if(ans!=1e9) write(ans),puts("");
        else puts("-1");
    }
    return _123hh2;
}
更新于

请我喝[茶]~(￣▽￣)~*

123hh2 微信支付

微信支付

123hh2 支付宝

支付宝

123hh2 贝宝

贝宝