题解：P15783 [JAG 2025 Summer Camp #3] Ants Collision

Tyih · 2026-10-21 19:14:18 · 题解

Solution

先考虑怎么算碰撞次数。

首先考虑从左往右加入一只蚂蚁，假设前面有 k 个 R，如果加入一只 L，那么会使最左边的蚂蚁和新加的蚂蚁碰撞次数加 1，中间部分加 2，且最左边的蚂蚁和新加的蚂蚁的方向改变，因此最左边的蚂蚁不会再被碰撞。

先从左往找到第一个 A_i 不为 0 的点，那么每次无法被碰撞的蚂蚁一定是连续的。可以枚举这个位置。

对于左边连续的位置，如果为奇数一定是 R，否则是 L，后面则相反。

最后模拟一遍，判断是否与给定的相同。

code

#include<bits/stdc++.h>
#define IOS cin.tie(0),cout.tie(0),ios::sync_with_stdio(0)
#define ll long long
#define db double
#define pb push_back
#define eb emplace_back
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define PLL pair<ll,ll>
#define PII pair<int,int>
#define Tp template<typename T>
#define Ts template<typename T,typename ...args>
#define lb(x) ((x)&(-x))
using namespace std;
const int N=3e5+20,M=1e5+20;
const ll INF=1ll<<60,mod=998244353;
namespace H_H_READ{
    char Buf[1<<23],*P1=Buf,*P2=Buf;
    #define gc() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
    Tp inline void read(T &o){
        bool f=0;o=0;int ch=gc();
        while(!isdigit(ch)) f=ch=='-',ch=gc();
        while(isdigit(ch)) o=(o<<1)+(o<<3)+(ch^48),ch=gc();
        if(f) o=-o;
    }
    Tp inline void Write(T o){
        if(o<0) putchar('-'),o=-o;
        if(o>9) Write(o/10);
        putchar(o%10+'0');
    }
    Tp inline void write(T o,char ch='\n'){Write(o);putchar(ch);}
    Ts inline void read(T &x,args&... y){read(x),read(y...);}
    Ts inline void write(T x,args... y){write(x,' '),write(y...);}  
}using H_H_READ::read;using H_H_READ::write;
namespace H_H{
    int n,a[N],ans[N],b[N];//0:L,1:R
    void solve(){
        read(n);
        int tot=0;
        for(int i=1;i<=n;i++) read(a[i]),tot+=(a[i]&1);
        a[n+1]=0;
        for(int i=0;i<=n;i++) b[i]=0;
        int l=1,r=n;
        while(l<=r && !a[r]) ans[r--]=1;
        while(l<=r && !a[l]) ans[l++]=0;
        if(l>r){
            for(int i=1;i<=n;i++) putchar(ans[i]?'R':'L');
            puts("");
            return ;
        }
        int pos=0,cnt=0;
        for(int i=l;i<=r;i++){
            tot-=a[i]&1;
            cnt+=(a[i]&1)^1;
            if(i-l+1==tot+cnt){
                pos=i;
                break;
            }
        }
        if(!pos) return puts("No"),void();
        for(int i=l;i<=pos;i++) ans[i]=a[i]&1;
        for(int i=pos+1;i<=r;i++) ans[i]=(a[i]&1)^1;       
        int num=0;
        for(int i=1;i<=n;i++){
            if(ans[i]) num++;
            else{
                if(num){
                    b[i-num]++;b[i-num+1]++;
                    b[i]--;b[i+1]--;
                }
            }
        }
        for(int i=1;i<=n;i++){
            b[i]+=b[i-1];
            if(b[i]^a[i]) return puts("No"),void();
        }
        for(int i=1;i<=n;i++) putchar(ans[i]?'R':'L');
        puts("");
    }
    int main(){
        int T=1;read(T);
        while(T--) solve();
        return 0;
    }
}
int main(){ 
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    // IOS;
    H_H::main();
    return 0;
}