「SFMOI」Round I Strange Train Game 题解

· · 个人记录

来篇贪心题解

知乎观看更佳

首先标粗的 “从小到大依次”没有影响，先排除掉顺序影响。

我们发现对于任意 i 使得 a_i=b_i 而言，任何操作对其都不会产生影响，所以先将其剔除掉。

对于剩下的点而言，我们的每个操作其实就等价于对其进行区间异或，不妨先设所有操作的左端点互不相同，考虑将所有操作根据左端点进行排序，从左到右依次考虑添加，若有当前操作的左端点的值为 0 ，因为所有操作的左端点互不相同，所以位于右侧的操作一定不会影响到当前位置，那么使用此操作肯定会让答案变得更优。

接下来考虑有重复左端点的情况，类比于异或操作，如下图，我们有 a_1,a_2,a_3 等价于 b_1,b_2,b_3 。

所以对于左端点相等的点，将其从小到大排序并将两两相邻的拆解，由于拆解后依旧可能被继续拆解，所以将拆解得到的区间加入其左端点对应的区间内，从左到右尝试拆解，于是乎我们就得到了若干个两两左端点互不相同的操作，套用上边的算法即可 然后就做完啦~

对于区间异或操作，直接上差分即可，没必要这么麻烦，具体看代码。

码丑，勿喷

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define db double
using namespace std;
const int Max=2e5+5,Mod=998244353;

int n,m,a[Max],b[Max];
int x[Max],tot;
int pre[Max],nxt[Max];
int getc()
{
    char c=getchar();
    while(!isdigit(c))
        c=getchar();
    return c-'0';
}

struct qur{
    int l,r;
    qur()
    {
        l=r=0;
    }
    qur(int L,int R)
    {
        l=L;r=R;
    }
    friend bool operator < (qur A,qur B)
    {
        if(A.l==B.l)
            return A.r>B.r;
        return A.l>B.l;
    }
}p[Max];
int rk[Max];
priority_queue<qur> qs[Max],qs2[Max];
int tmp[Max];
signed main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        a[i]=getc();
    for(int i=1;i<=n;i++)
        b[i]=getc();
    for(int i=1;i<=n;i++)
    {
        pre[i]=pre[i-1];
        if(a[i]!=b[i])
        {
            pre[i]=i;
            x[++tot]=i;
            rk[i]=tot;
        }
    }
    nxt[n+1]=Max;
    for(int i=n;i>=1;i--)
    {
        nxt[i]=nxt[i+1];
        if(a[i]!=b[i])
            nxt[i]=i;
    }
    int l,r;
    int ms=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&l,&r);
        if(pre[r]<nxt[l] or nxt[l]==Max or pre[r]==0)
            continue;
        p[++ms].l=rk[nxt[l]];
        p[ms].r=rk[pre[r]];
    }
    m=ms;
    for(int i=1;i<=m;i++)
        qs[p[i].l].push(p[i]);
    for(int i=1;i<=tot;i++)
    {
        while(!qs[i].empty())
        {
            qur now=qs[i].top();
            qs2[i].push(now);
            qs[i].pop();
            while(!qs[i].empty())
            {
                qur nt=qs[i].top();
                if(now.r!=nt.r)
                    qs[now.r+1].push(qur(now.r+1,nt.r));
                now=qs[i].top();
                qs[i].pop();
            }
        }
    }
    for(int i=1;i<=tot;i++)
    {
        tmp[i]=tmp[i-1]+tmp[i];
        if(!qs2[i].empty())
        {
            if(!(a[x[i]]^(tmp[i]%2)))
            {
                tmp[i]++;
                tmp[qs2[i].top().r+1]--;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(a[i]!=b[i])
        {
            if(tmp[rk[i]]%2)
                printf("%d",a[i]^1);
            else
                printf("%d",a[i]);
        }
        else
            printf("%d",a[i]);
    }
}