题解：CF2232E Snaking Arrangement

ssy666666 · 2026-11-11 14:33:30 · 题解

我说这题真挺牛的。

有一个比较显然的观察是他应该是一个对称的图形。我们只用看左上部分即可。至于为什么得等后面再证。

这样的话我们就相当于要在一个上三角里塞长度为 1 到 n 的蛇。你发现一条蛇开头的位置应该是斜着的一行，比如说 n=5，长度为 3 的蛇的蛇头只能在这些位置：

这启发我们把矩阵转四十五度，然后斜着一行行考虑。

你发现一个很优秀的性质，如果上一行已经确定了，那么此时如果我们确定这一行的蛇头，方案是唯一的。比如这是我们原来的方案：

此时我们钦定下一行的蛇头（蓝色的位置），那么方案一定只能是：

并且，所有在这个新蛇头“左边”的位置会向原矩阵下走，在新蛇头“右边”的位置会向右走。

那其实你发现这个关系应该是对应的。换句话说，我们强制原来一条蛇向右走，这一行对应的蛇头就应该在这条蛇的“左边”，反之同理。

因此，转置矩阵的一行上，只有一个区间能够放蛇头。

然后你直接乘法原理即可。

AC Code

#include<bits/stdc++.h>
#define int long long
using namespace std ;
const int MAXN = 1e4 + 7 ;
const int MOD = 1e9 + 7 ;
int L[MAXN] , R[MAXN] ;
char p[MAXN] ;
void solve() {
    int n , k ;
    cin >> n >> k ;

    for (int i = 1 ; i <= n ; i ++) {
        L[i] = 1 ;
        R[i] = i ;
    }

    for (int i = 1 ; i <= k ; i ++) {
        int s ;
        cin >> s ;

        int r , c ;
        cin >> r >> c ;

        if (s > 1)  cin >> p ;

        int g = r + c - 1 ;
        if (L[g] > r or R[g] < r) {
            cout << 0 << "\n" ;
            return ;
        }

        L[g] = R[g] = r ;

        g ++ ;
        for (int j = 0 ; j < s / 2 ; j ++ , g ++) {
            if (p[j] == 'R') {
                L[g] = max(L[g] , r + 1) ;
                c ++ ;
            }
            else {
                R[g] = min(R[g] , r) ;
                r ++ ;
            }

            if (L[g] > R[g]) {
                cout << 0 << "\n" ;
                return ;
            }
        }
    }

    int ans = 1 ;
    for (int i = 1 ; i <= n ; i ++) {
        ans = ans * (R[i] - L[i] + 1) % MOD ;
    }

    cout << ans << "\n" ;
}

signed main() {
    ios::sync_with_stdio(0) ;
    cin.tie(0) ;
    cout.tie(0) ;

    int t ;
    cin >> t ;
    while (t--) {
        solve() ;
    }

    return 0 ;
}