P15847 [NOISG 2026 Finals] 猴子 / Monkeys 题解

· · 题解

水篇题解。

感觉已经好久好久没写过黄题题解了吧。

日常看错题之当我以为一个猴子在点 x 时要以 d_x 的方向移动然后思考许久无果看了眼样例发现：哦我又看错题了。

上一次看错题，被某个巨佬扯出来搞到一个紫题，吓哭了。

感觉是比较一眼的题目。当然这建立在你题看对了的情况下。

一个点只会朝着一个方向永远移动，所以相遇只有两种情况：

  1. 相向而行的相遇：

    • 这要求两点中，最初位于左侧的点是往右走，最初位于右侧的点是往左走。
    • 且两点之间的间隔 y-x 为偶数（奇数的话会擦边而过，但无法在整点上相遇），还要求 y-x \le 2k（否则在 k 时间内也无法相遇）。

  2. 同向而行的相遇：

    • 正常来讲，同向而行能相遇是因为一个快一个慢。
    • 但是这道题中，所有点的移动速度都是 1，这也就不存在“追及”情况了，也就是说，两个同向而行的点能相遇，当且仅当其初始点位置相同。也就是两个本质一样的点。

那么就可以做了，维护三个数组 R,L_0,L_1，分别存储：

对这三个序列升序排序之后，就很好做了。

相向而行的，枚举 R 中的点 x，在对应的 L 数组（根据 x 的奇偶性判断是 L_0 还是 L_1）内二分到对应区间 [x,x+2k] 所含有的点数，累加答案即可。

同向而行的，只需要分往左还是往右，对下标开两个桶记录一下，贡献 \sum \frac{cnt(cnt-1)}{2}。

整个还是非常好做的。

代码里有一些辅助理解的注释喵。

::::success[code && submission]

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 2e5+5;
LL n,k,p[N],Ans;//不开 LL 见祖宗 
vector<LL> L[2],R;//其实应该开数组的但是实在不想写三个长度变量
map<LL,LL> t[2];//充当桶解决重复点的问题 
int read(){
    int su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
int main(){
    n=read(),k=read();
    for(int i=1;i<=n;i++)p[i]=read();
    //注意 vector 的下标从 0 开始！！ 
    for(int i=1;i<=n;i++){
        char opt;cin>>opt;
        if(opt=='R')R.pb(p[i]);
        else L[p[i]&1].pb(p[i]);
        //按点位的奇偶性分类
        //因为中间间隔路程只能是偶数（两只猴子都在移动） 
        t[(opt=='L'?0:1)][p[i]]++;//塞进桶 
    }
    sort(R.begin(),R.end());
    sort(L[0].begin(),L[0].end());
    sort(L[1].begin(),L[1].end());
    for(LL x:R){
        //以往右走的为指定物，找右侧奇偶性匹配且距离不长的猴子 
        int o=(x&1);//奇偶性判定
        int l=lower_bound(L[o].begin(),L[o].end(),x)-L[o].begin();
        int r=upper_bound(L[o].begin(),L[o].end(),x+2*k)-L[o].begin()-1;
        //找到能相遇的猴子的左右端点
        //注意右端点要用 upper_bound 最后 -1 因为可能有重复！ 
        Ans+=r-l+1;//累加答案 
    }
    for(int o=0;o<2;o++)//左右方向 
        for(auto [x,y]:t[o])Ans+=y*(y-1)/2;//累加答案
    cout<<Ans<<"\n"; 
    return 0;
}

::::

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！