本文最后更新于 887 天前，其中的信息可能已经有所发展或是发生改变。
A. Mark the Photographer
原题链接
思想
- 将所有人的身高存入数组 ，用
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
原题链接
思想
- 由题意可知当
i与j之间不存在$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
原题链接
思想
- 由于数据范围暴大，想用
string存下来是不可能的 - 对于每次的
copy操作，记录l和r - 同时记录
copy之后的l和r的新位置，记为nl和nr - 对于每次询问，要找到
k所在的nl和nr的区间 - 即要找到进行第几次
copy操作后，满足l和r更新的区间nl和nr，使得nl <= k <= nr - 找到后，将
k更新为k' = k - (nl - l)，使得k'在l和r所在的区间内，即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$题实在是干到怀疑狗生了，前后搞了好几个小时才绕过来弯，希望自己以后不要这么笨了
- 剩下的题实在是不行，毕竟还是个大弱鸡，交给未来吧，加油！！！