Educational Codeforces Round 62 E 局部dp + 定义状态取消后效性

https://codeforces.com/contest/1140/problem/E
局部dp + 定义状态取消后效性

题意

给你一个某些位置可以改变的字符串,假如字符串存在回文子串,那么这个字符串就是坏的,问有多少好的串(n<=2e5)

题解

• 首先发现只需要保证\(s[i-2]!=s[i]\)(局部保证),就可以保证不存在回文子串
  • 直接计算有多少个好的串(即不存在回文子串的情况)
  • 分奇偶位考虑,因为假如奇偶位都合理,那么就不存在1,2,3,2,1这种情况,这个序列考虑奇数位是1,3,1,考虑偶数位是2,2,奇数位序列合理,但是偶数位序列不合理
• 将奇偶分别数位抽出来,那我们就得到一段一段\([A,-1,-1,...,-1,-1,B]\),A,B可能不存在,因为所有段符合乘法性质,所以我们可以在每一段上dp,最后乘起来就是答案
• 假设定义dp[i]为到第i位一共有多少种情况,那么转移就是dp[i]=dp[i-1]*(k-1),但是这样到最后一个-1的时候,不能保证和B的关系(有后效性,且只和B有关)

• 那么我们就定义状态为dp[i][0/1],分别表示当前这位和B[不同/相同]

  • \(dp[i][0]=dp[i-1][0]*(k-2)+dp[i-1][1]*(k-1)\)
  • \(dp[i][1]=dp[i-1][0]\)

• 分开讨论[A,-1,-1],[-1,-1,A]两种情况

处理

• 模拟[A,-1,-1,-1,A]的区间

for(int l=0;i<r;l=r+1){
    r=l;
    //用r扫
}

代码

#include<bits/stdc++.h>
#define MOD 998244353
using namespace std;
int n,i,x;
vector<int>A,B;
long long ans,dp[200005][2],k;

void chk(vector<int> A){
    for(int i=1;i<A.size();i++){
        if(A[i]==A[i-1]&&A[i]!=-1){cout<<0;exit(0);}
    }
}
void sol(vector<int> A){
    for(int l=0,r;l<A.size();l=r+1){
        r=l;
        if(A[r]!=-1)continue;
        while(r<A.size()&&A[r]==-1)r++;
        if(r==A.size()){
            r--;
            if(l==0)dp[l][0]=k;
            else dp[l][0]=k-1;
            for(int i=l+1;i<=r;i++)dp[i][0]=dp[i-1][0]*(k-1)%MOD;
        }else{
            if(l==0){
                dp[l][0]=k-1;dp[l][1]=1;
            }else{
                int a=A[l-1],b=A[r];
                if(a==b){
                    dp[l][0]=k-1;
                    dp[l][1]=0;
                }else{
                    dp[l][0]=k-2;
                    dp[l][1]=1;
                }
            }
            r--;
            for(int i=l+1;i<=r;i++){
                dp[i][0]=(dp[i-1][0]*(k-2)%MOD+dp[i-1][1]*(k-1)%MOD)%MOD;
                dp[i][1]=dp[i-1][0]%MOD;
            }
        }
        ans=ans*dp[r][0]%MOD;
    }
}
int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++){
        scanf("%d",&x);
        if(i&1)A.push_back(x);
        else B.push_back(x);
    }
    ans=1;
    chk(A);chk(B);
    sol(A);sol(B);
    cout<<ans;
}

Educational Codeforces Round 62 E 局部dp + 定义状态取消后效性

原文：https://www.cnblogs.com/VIrtu0s0/p/10585902.html