解题报告 jsc2019C 【Cell Inversion】

题目链接

比赛的时候根本没有思路，这种题就要多做，多写解题报告

首先，操作顺序不影响操作结果

区间问题可以考虑操作顺序对结果的影响

其次，操作[l_1,r_1] \to [l_2,r_2]与[l_1,r_2] \to [l_2,r_1]是等价的

所以一个点是哪个区间的左端点（右端点）是没有影响的，这样就可以单独考虑每个点是左端点还是右端点了

区间问题可以考虑左右端点交换（至上述结论）对结果的影响

一个点i是左端点，只会对i-1与i的相对关系有影响；是右端点，只会对i与i+1的相对关系有影响

点1只能是左端点

若s[i]=s[i-1]，这两个节点的左右就不能相等

发现一个点是左端点还是右端点是固定的

区间问题可以考虑一个点是左右端点是否固定

这样，问题就转化成，给定一个串，由“L”和“R”构成，判断匹配关系

这个问题当然就很简单了

在[1,i]中，t_i=\text{L的个数}-\text{R的个数}

易知，若t_i<0则无解，若点i是右端点，ans就乘以t_i+1(想一想，为什么)

然后特判s[1]和s[2n]是不是“B”就行了

#include<cstdio>
typedef long long ll;
const int MAXN = 1e5 + 5;
const ll mod = 1e9 + 7;

char s[MAXN*2];

int main(void)
{
    int n;
    scanf("%d%s",&n,s+1);

    if(s[1]=='W' || s[n<<1]=='W')
    {
        printf("0");
        return 0;
    }
    ll ans=1, t=1, last=1;
    for(int i=2; i<=(n*2); ++i)
    {   
        if(s[i]!=s[i-1])
        {
            if(last) ++t;
            else --t;
        }
        else
        {
            if(last) --t;
            else ++t;
            last=!last;
        }
        if(!last)
            ans = ans*(t+1) %mod;
        if(t<0)
        {
            printf("0");
            return 0;
        }
    }
    if(t)
    {
        printf("0");
        return 0;
    }

    for(int i=1; i<=n; ++i) ans = ans*i%mod;
    printf("%lld",ans);
    return 0;
}