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

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之间不存在ai=0a_i=0时,可以进行操作
  • 则对存入数组的数据进行遍历,直到从头遍历到ai=0a_i=0为止
  • 此时,后方的ai=0a_i=0的房间都可以通过aj0a_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;
}

后记

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

发送评论 编辑评论


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