题解：P17528 [JAG 2026 Summer Camp #1] Neighbour or Opposite

· · 题解

菜就多练神秘题。

由于匹配方式为 i 和 i+1 或 i 和 i+n，那么完全可以把圆分成两半：从 1 到 n（上点）和从 n+1 到 2n（下点），并把 (i,\ i+n) 看成第 i 列。这样匹配就变成了上下（相对）和左右（相邻），讨论对象从圆变成了链。

这样分割后，仍然有两条边特殊：1 和 2n 与 n 和 n+1，它们把链首尾交叉连成环。暴力枚举这两对是否匹配就好，共 4 种情况。

对于每一列，我对这一列的匹配操作只关心它的两个点是否被占用。于是设计 dp 状态，用一个两位二进制数 l 表示：第 0 位表示上点是否被左侧占用，第 1 位表示下点是否被左侧占用。每列枚举三种决策：是否选本列的竖直边、是否选向右的上水平边、是否选向右的下水平边，以此计算匹配数。

需要特判 n=1 的情况。

时间复杂度 O(n)。

::::success[参考实现]

#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define rep2(i,x,y) for (int i=(x);i<(y);i++)
#define rec(i,x,y) for(int i = (x);i;i = (y))
#define dow(i,x,y) for (int i=(x);i>=(y);i--)
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define mt empty
#define siz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define fil(a,b) memset((a),(b),sizeof(a))
#define int long long
#define ull unsigned long long
#define N 1005
#define inf 0x3f3f3f3f3f3f3f3f
#define mod 998244353
#define ciallo return 0;
int n, ans1, ans2;
string s;
pair<int, int> solve(int n, string s, int s1, int s2) {
    if (s1 && (s[1] == 'x' || s[2 * n] == 'x')) return {-inf, 0};
    if (s2 && (s[n] == 'x' || s[n + 1] == 'x')) return {-inf, 0};
    vector<int> f(4, -inf), g(4, -inf), cnt(4, 0), cnt2(4, 0);
    cnt[0] = 1,f[0] =0;
    rep(i, 1, n) {
        int A = (s[i] == 'o'), B = (s[n + i] == 'o');
        if (i == 1) {if (s1)A = 0;if (s2)B = 0;}
        if (i == n) {if (s1)B = 0;if (s2)A = 0;}
        int nxtA = 0, nxtB = 0;
        if (i < n) {
            nxtA = (s[i + 1] == 'o'), nxtB=(s[n + i + 1] == 'o');
            if (i + 1 == n) {if (s1)nxtB = 0;if (s2)nxtA = 0;}
        }
        rep(j, 0, 3) { g[j] = -inf; cnt2[j] = 0; }
        rep(l, 0, 3) {
            if ((l & 1) && !A) continue;
            if ((l & 2) && !B) continue;
            rep(t,0,1){
                if (t && ((l & 1) || (l & 2) || !A || !B)) continue;
                rep(rA,0,1) {
                    if (rA && (!A ||(l & 1) || t|| i == n || !nxtA)) continue;
                    for (int rB = 0; rB <= 1; rB++) {
                        if (rB && (!B || (l & 2) || t || i == n || !nxtB)) continue;
                        int add = t + rA + rB,nm = (rA ? 1 : 0) | (rB ? 2 : 0);
                        if (f[l] + add > g[nm]) {
                            g[nm] = (f[l] + add) %mod;
                            cnt2[nm] = cnt[l];
                        } else if (f[l] + add == g[nm])
                            cnt2[nm] = (cnt2[nm] + cnt[l]) %mod;

                    }
                }
            }
        }
        rep(j,0,3){f[j] = g[j];cnt[j] = cnt2[j];}

    }
    return {s1+s2+f[0],cnt[0]};
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;cin >> s;s = " " + s;
    if(n==1) {
        if (s[1] == 'o' && s[2] == 'o')cout << 1 << ' ' << 1 << endl;
        else cout << 0 << ' ' << 1 << endl;
        ciallo}
    rep(s1, 0, 1) {
        rep(s2, 0, 1) {
            auto r = solve(n, s, s1, s2);
            int a1=r.fi,a2=r.se;
            if(ans1 < a1){ans1 = a1;ans2 = a2;}
            else if (ans1 == a1) {ans2 = (ans2+a2)%mod;}
        }
    }
    cout << ans1 <<" "<< ans2;
    ciallo
}

::::