dp转移

记录方案

P6454

本题有dp的 \(O(n)\) 解法。设已经用完 \(1\) 到 \(i\) 的麻将，有 \(j\) 组从 \(i-2\) 开始的顺子，\(k\) 组从 \(i-1\) 开始的顺子，是否已经确定雀头，没有加入任何牌的麻将组合是否能和为 \(g[i][j][k][0/1]\)，对于已经加入一张牌的记为 \(f[i][j][k][0/1]\)。转移难处在于，从 \(g\) 到 \(f\) 转移时，没法记录加入了那张牌。 所以把所有 \(g\) 到 \(f\) 的转移变成建边(第一种边)，所有 \(f\) 到 \(f\) 的转移变成第二种边(因为只有能够通过第二种边到达终点状态的第一种边是可行解)。最后从 \(f(n,0,0,1)\)代表的点，通过第二种边进行dfs，每次到一个点枚举第一种边，对 \(v\) 标记为可行解。

#include<iostream>
#include<vector>
using namespace std;
const int N=5e3+10,M=2e5+10;
int g[N][3][3][2];
inline int id(int i,int j,int k,int p){
    return i*18+j*6+k*2+p;
}
int n,m,tmp;
int a[N],cnt[2],lst[2],ans[N],vis[M],res[N];
vector<int> G[M],E[M];
void dfs(int u){
    vis[u]=1;
    for(int i=0;i<E[u].size();++i){
        int v=E[u][i];
        ans[v]=1;
    }
    for(int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if(!vis[v]) dfs(v);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i) scanf("%d",&tmp),a[tmp]++;
    for(int i=1;i<=n;++i) cnt[a[i]%2]++,lst[a[i]%2]=i;
    g[0][0][0][0]=1;
    for(int i=0;i<n;++i){
        for(int j=0;j<3;++j){
            for(int k=0;k<3;++k){
                for(int p=0;p<2;++p){
                    if(!g[i][j][k][p]) continue;
                    if(a[i+1]>=j+k) g[i+1][k][(a[i+1]-j-k)%3][p]=g[i][j][k][p];
                    if(!p && a[i+1]>=j+k+2) g[i+1][k][(a[i+1]-j-k-2)%3][1]=g[i][j][k][p];
                }
            }
        }
        for(int j=0;j<3;++j){
            for(int k=0;k<3;++k){
                for(int p=0;p<2;++p){
                    //if(!f[i][j][k][p]) continue;
                    int t=id(i,j,k,p);
                    if(a[i+1]>=j+k) G[id(i+1,k,(a[i+1]-j-k)%3,p)].push_back(t);
                    if(!p && a[i+1]>=j+k+2) G[id(i+1,k,(a[i+1]-j-k-2)%3,1)].push_back(t);
                }
            }
        }
        ++a[i+1];
        for(int j=0;j<3;++j){
            for(int k=0;k<3;++k){
                for(int p=0;p<2;++p){
                    if(!g[i][j][k][p]) continue;
                    if(a[i+1]>=j+k) E[id(i+1,k,(a[i+1]-j-k)%3,p)].push_back(i+1);
                    if(!p && a[i+1]>=j+k+2) E[id(i+1,k,(a[i+1]-j-k-2)%3,1)].push_back(i+1);
                }
            }
        }
    }
    dfs(id(n,0,0,1));
    if(cnt[1]==1) ans[lst[1]]=1;
    int tot=0;
    for(int i=1;i<=n;++i){
        if(ans[i]) res[++tot]=i;
    }
    printf("%d\n",tot);
    for(int i=1;i<=tot;++i) printf("%d ",res[i]);
    return 0;
}