Codeforces Round #807 (Div 2.) A·B·C
本文最后更新于 729 天前,其中的信息可能已经有所发展或是发生改变。

A. Mark the Photographer


原题链接

Original Link


思想

  • 将所有人的身高存入数组 ,用sort排序
  • 利用双指针,以n为分界线,判断是否满足条件
  • n个人的身高+ x小于等于后n个人的身高

代码

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+3;

int a[N];

int main(){

    int t;

    scanf("%d",&t);

    while(t--){

        int n,x;
        scanf("%d%d",&n,&x);

        for(int i=0;i<n*2;i++) scanf("%d",&a[i]);

        sort(a,a+n*2);  //排序

        bool flag=1;
        for(int i=0,j=n;i<n;i++,j++){  //i从0~n-1  j从n~2*n-1
            if(a[j]-a[i]<x){
                flag=0;
                break;
            }
        }
        if(flag) printf("YES\n");
        else printf("NO\n");

    }

    return 0;

}

B. Mark the Dust Sweeper


原题链接

Origional Link


思想

  • 由题意可知当ij之间不存在$a_i=0$时,可以进行操作
  • 则对存入数组的数据进行遍历,直到从头遍历到$a_i=0$为止
  • 此时,后方的$a_i=0$的房间都可以通过$a_j\ne 0$的房间来填充一次,使得操作继续

代码

#include <bits/stdc++.h>
using namespace std;

int t;

const int N=1e6+3;

int a[N];

int main(){

    cin>>t;

    while(t--){

        int n;

        cin>>n;

        for(int i=0;i<n;i++) cin>>a[i];

        int p=0;

        while(p<n&&a[p]==0) p++;

        long long cnt=0;

        for(int i=p;i<n-1;i++){

            cnt+=a[i];
            if(a[i]==0) cnt++;

        }

        cout<<cnt<<endl;

    }

    return 0;

}

C. Mark and His Unfinished Essay


原题链接

Origional Link


思想

  • 由于数据范围暴大,想用string存下来是不可能的
  • 对于每次的copy操作,记录lr
  • 同时记录copy之后的lr的新位置,记为nlnr
  • 对于每次询问,要找到k所在的nlnr的区间
  • 即要找到进行第几次copy操作后,满足lr更新的区间nlnr,使得nl <= k <= nr
  • 找到后,将k更新为k' = k - (nl - l),使得k'lr所在的区间内,即l <= k' <= r
  • 不断重复上述步骤更新k,直到1 <= k <= n
  • 由于操作次数很少,在寻找对应区间时可以直接从大到小进行枚举

代码

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+3;

typedef long long LL;

LL l[N],r[N],nl[N],nr[N];
//l和r数组存储每次copy的l和r
//nl和nr数组存储copy之后,l和r的位置 

void solve(){

    LL n,m,q;

    cin>>n>>m>>q;

    string s;

    cin>>s;

    nl[0]=0,nr[0]=n;

    for(int i=1;i<=m;i++){

        cin>>l[i]>>r[i];
        nl[i]=nr[i-1]+1;  //更新nl 
        nr[i]=nl[i]+(r[i]-l[i]+1)-1;  //更新nr 

    }

    while(q--){

        LL k;
        cin>>k;

        for(int i=m;i>=1;i--){  //枚举区间
            if(nl[i]<=k&&k<=nr[i]) k-=nl[i]-l[i];
        }

        cout<<s[k-1]<<endl;

    }

}

int main(){

    LL t;

    cin>>t;

    while(t--){
        solve();
    }

    return 0;

}

后记

  • $A$题肥肠煎蛋,没有被hack也没什么感觉
  • $B$题比赛时写麻烦了,最后TLE了,补题才发现自己把自己绕晕了
  • $C$题实在是干到怀疑狗生了,前后搞了好几个小时才绕过来弯,希望自己以后不要这么笨了
  • 剩下的题实在是不行,毕竟还是个大弱鸡,交给未来吧,加油!!!
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇