题解：P10349 [PA2024] Mrówki

we_are_the_chuibing · 2024-04-17 19:32:19 · 题解

思想

想起来了 P1007，有一个重要思想：

由于两只蚂蚁速度不变，所以这两只蚂蚁碰撞反弹时，可以看做两只蚂蚁互相穿过并且交换灵魂。

但由于这题要求每个蚂蚁的碰撞次数，所以并不能这样做。

但是思想还是可以借鉴一下的。

思路

因为对于每个蚂蚁求碰撞次数时，别的蚂蚁的碰撞不需要计算，所以我们可以看成只有需要计算次数的这只蚂蚁和其他蚂蚁碰撞会造成反弹。

现在将这只蚂蚁左边和右边分成两个区域左部分和右部分。

很明显，在左部分且朝向左边的蚂蚁和在右部分且朝向右边的蚂蚁不会和需要计算次数的蚂蚁永远碰撞不上，舍去。

接下来设在左部分且朝向右边的蚂蚁个数为 x，在右部分且朝向左边的蚂蚁个数为 y。

由于需要计算次数的蚂蚁肯定是在这些蚂蚁之间来回碰撞，且被碰撞到的蚂蚁就永远不会再次被碰撞，当一个部分的蚂蚁被碰完时，需要计算次数的蚂蚁就再也不会碰到这个部分的蚂蚁，同时只能进行一次碰撞了。所以我们可以得出以下结论：

• 当 x=y 时，答案为 x+y。
• 当 x<y 时：
  • 如果需要计算次数的蚂蚁面向左边，那么答案为 2x。
  • 如果需要计算次数的蚂蚁面向右边，那么答案为 2x+1。
• 当 x>y 时：
  • 如果需要计算次数的蚂蚁面向右边，那么答案为 2y。
  • 如果需要计算次数的蚂蚁面向左边，那么答案为 2y+1。

然后将所有的 x 和 y 预处理即可。

#include<iostream>
using namespace std;
int n,lans,rans,l[300001],r[300001];
char c[300001];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>c[i];
    for(int i=1;i<=n;i++){
        l[i]=lans;
        if(c[i]=='P')lans++;
    }
    for(int i=n;i>=1;i--){
        r[i]=rans;
        if(c[i]=='L')rans++;
    }
    for(int i=1;i<=n;i++){
        if(l[i]==r[i])cout<<l[i]+r[i];
        else if(l[i]<r[i]){
            if(c[i]=='L')cout<<l[i]*2;
            else cout<<l[i]*2+1;
        }
        else{
            if(c[i]=='P')cout<<r[i]*2;
            else cout<<r[i]*2+1;
        }
        cout<<" ";
    }
    return 0;
}

如果各位有什么不懂的地方，欢迎私信询问。