题解：P14448 [ICPC 2025 Xi'an R] Beautiful Dangos

· · 题解

真没招了，重现赛最后二十分钟快写完了结果被同学关电脑了，痛失场切。所以这篇题解没有完整代码。

如果想看如何判断是否能使一个区间排序后满足要求，那还是去看官方题解吧。本人数学不行。

题意

给你一个序列，让你求差最小的 l 和 r，使对下标 l 到 r 重排后可以使这个序列相同的数不相邻。特别的，这个序列中只有至多三种数。

做法

考虑用双指针来扫。先求出左边往右边的第一个有相邻并相同的数的位置 L，再求出从右往左第一个有相邻并相同的数的位置 R。取指针 l 为 1，r 为 R。此时 l 到 r 包含了所有相邻且相同的数。如果无法对此区间进行排序使这段区间与旁边两侧的数（各只用考虑一个，因为更远的已经满足要求）合并起来符合要求，那么把 r 往右移直到满足要求。再在满足要求的情况下将 l 右移直到不满足要求的前一个，更新答案。接着把 l 右移一个。一直扫到 l 扫到 L 时或 r 扫到 n 并且不满足要求时结束。

计算是否符合要求可以用前缀和来维护，算出三种数各有多少个，再考虑左右两个数，就是组合问题了。另外开头需要先计算一下整个序列是否可以变成满足条件的序列，和是否原来就满足条件。

最后输出可以把 ansl 往左和 ansr 往右都按原序列打印出来，中间的用前缀和求一下每个数的数量，组合咋算的咋输出就可以了。

中间输出再说一句，要注意记录上一个颜色是什么，然后尽可能的先输出与其不相同的剩余更多的颜色。相同数量就看看 ansr 右边那个是什么，优先输出。注意判 ansl 为 1 的情况第一个颜色应该输出什么。

其实可以把前缀和省掉，边扫变更新，更省空间。

给出部分关键代码。

l=1,r=R-1;     //双指针
ansl=0,ansr=n+1;
while(l<=L+1){
    while(r<=n&&!query(l,r))r++;
    if(r>n)break;
    while((l<L+1)&&query(l+1,r))l++;
    if((ansr-ansl)>(r-l)){
        ansr=r,ansl=l;
    }
    if(l==L+1)break;
    l++;
}

还有丑陋的判断是否符合要求（不要嘲笑我可以吗）。

inline bool query(int l,int r){
    int x1=s1[r]-s1[l-1],x2=s2[r]-s2[l-1],x3=s3[r]-s3[l-1];
    int y=(r-l+1);
    int g;
    if(y%2==1){
        if(x1>(y/2+1)||x2>(y/2+1)||x3>(y/2+1)){
            return false;
        }
    }
    else {
        if(x1>y/2||x2>y/2||x3>y/2){
            return false;
        }
    }
    if(l==1&&r==n){
        return true;
    }
    if(l==1||r==n){
        int g;
        if(l==1)g=a[r+1];
        else g=a[l-1];
        if(y%2==0)return true;
        if(g==1){
            if(x1==(y/2+1))return false;
        }
        if(g==2){
            if(x2==(y/2+1))return false;
        }
        if(g==3){
            if(x3==(y/2+1))return false;
        }
        return true;
    }
    if(a[l-1]==a[r+1]){
        g=a[l-1];
        if(y%2==0){
            if(g==1){
                if(x1==(y/2))return false;
            }
            if(g==2){
                if(x2==(y/2))return false;
            }
            if(g==3){
                if(x3==(y/2))return false;
            }
            return true;
        }
        if(y%2==1){
            if(g==1){
                if(x1==(y/2+1))return false;
            }
            if(g==2){
                if(x2==(y/2)+1)return false;
            }
            if(g==3){
                if(x3==(y/2)+1)return false;
            }
            return true;
        }
    }
    int g1=a[l-1],g2=a[r+1];
    if(y%2==0)return true;
    if(g1==1||g2==1){
        if(x1==(y/2+1))return false;
    }
    if(g1==2||g2==2){
        if(x2==(y/2+1))return false;
    }
    if(g1==3||g2==3){
        if(x3==(y/2+1))return false;
    }
    return true;
}