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

· · 题解

求最多能组成多少对，这个比较容易，好像直接贪就行，但是如果在这上面计数就比较难了。

如果直接 DP 的话不好处理环的性质和相对的状态处理。

处理相对，我们让 1\sim n 为一排，n+1\sim 2n 为一排，将两排一起考虑，就不用东西来记相对是否使用了。

处理环，我们考虑直接断开，在对端点分讨，只用处理 4 种情况。

考虑 DP 怎么设计，我们需要统计方案书和组成了几对，还需要记两位二进制数来表达这一位是否使用，之后的转移好推，因为转移式太长就不写在这了，已经加了注释。

具体实现还要特判，因为分讨可能判到自己，然后就没了，代码：

#include<bits/stdc++.h>
// #define int long long
using namespace std;
/*
#pragma region 哈基米
*/
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c>'9'||c<'0') {if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return x*f;
}
inline string reads(){
    string s=" ";char c=getchar();
    while(c!=EOF&&(c=='\n'||c=='\0'||c=='\r')) c=getchar();
    while(c!=EOF&&c!='\n'&&c!='\0'&&c!='\r') s+=c,c=getchar();
    return s;
}
const int N=1e6+5,inf=1e9,mod=998244353;
int n;string s;
struct stu{//我这里直接用结构体来存DP值了
    int c,w;
    stu add(int x){return (stu){c+x,w};}
    stu operator+(const stu &t){
        if(c>t.c) return (stu){c,w};
        if(c==t.c) return (stu){c,(w+t.w)%mod};
        return t;
    }
}f[2][2][2],em,ans;//i,上,下
void solve(){//求解这一次的答案
    for(int i=0;i<2;i++) for(int o=0;o<2;o++) for(int p=0;p<2;p++) f[i][o][p]=em;
    f[0][1][1]=(stu){0,1};
    for(int i=1;i<=n;i++) {
        const int now=i&1,l=now^1;
        f[now][0][0]=f[now][1][0]=f[now][0][1]=f[now][1][1]=em;//清空
        if(s[i]=='o'&&s[i+n]=='o') {
            f[now][1][1]=f[l][0][0].add((s[i-1]=='o'&&s[i-1+n]=='o'&&i>1)?2:1)+//填两个或一个，需要判断上一列能否使用
            f[l][1][0].add(1)+f[l][0][1].add(1)+f[l][1][1].add(1);//填一对在i,i+n
        }
        if(s[i]=='o'&&s[i-1]=='o'&&i>1) f[now][1][0]=f[l][0][0].add(1)+f[l][0][1].add(1);//填一对在i,i-1
        if(s[i+n]=='o'&&s[i-1+n]=='o'&&i>1) f[now][0][1]=f[l][0][0].add(1)+f[l][1][0].add(1);//填一对在i+n,i-1+n
        f[now][0][0]=f[l][0][0]+f[l][1][0]+f[l][0][1]+f[l][1][1];//不填
    }
}
signed main(){
    // freopen("1.in" ,"r",stdin );
    n=read();s=reads();em.c=-inf,em.w=0;ans=em;
    solve();//不连
    ans=ans+f[n&1][0][0]+f[n&1][1][0]+f[n&1][0][1]+f[n&1][1][1];
    if(n==1) {printf("%d %d\n",ans.c,ans.w);return 0;}//直接输出，后面的分讨在n=1时相当于滚木
    if(s[1]=='o'&&s[2*n]=='o') {//1和2n连
        s[1]='x',s[2*n]='x';//需要把这个位置改成不可用
        solve();
        ans=ans+f[n&1][0][0].add(1)+f[n&1][1][0].add(1)+f[n&1][0][1].add(1)+f[n&1][1][1].add(1);//补上数量
        s[1]='o',s[2*n]='o';
    }
    if(s[n]=='o'&&s[n+1]=='o') {//n和n+1连
        s[n]='x',s[n+1]='x';
        solve();
        ans=ans+f[n&1][0][0].add(1)+f[n&1][1][0].add(1)+f[n&1][0][1].add(1)+f[n&1][1][1].add(1);
        s[n]='o',s[n+1]='o';
    }
    if(s[n]=='o'&&s[n+1]=='o'&&s[1]=='o'&&s[2*n]=='o') {//1和2n连且n和n+1连
        s[n]='x',s[n+1]='x';s[1]='x',s[2*n]='x';
        solve();
        ans=ans+f[n&1][0][0].add(2)+f[n&1][1][0].add(2)+f[n&1][0][1].add(2)+f[n&1][1][1].add(2);
        s[n]='o',s[n+1]='o';s[1]='o',s[2*n]='o';
    }
    printf("%d %d\n",ans.c,ans.w);
    return 0;
}