题解归档 - cf2237I1

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2237I1
• 本地来源：problems/cf2237I1/idea.md
• 题目链接：https://codeforces.com/contest/2237/problem/I1

思路

pattern:
stable sorting / DP state decision model
claim:
For a fixed coloring, the traversal order equals sorting all vertices by the number of color-1 vertices on the root path, with DFS preorder as the stable tie-breaker.
why necessary:
Pushing a color-0 child to the deque front is a 0-cost move in lexicographic order of (number of 1-edges, DFS order); pushing a color-1 child to the back delays it by one layer.
why sufficient:
For the easy version every compressed adjacent layer boundary can be realized by changing the corresponding optional edge choices, while forced 0 edges stay in the same layer.
brute/check:
For n<=9 enumerate all 0/? colorings, simulate the deque traversal, and compare with the DP. The DP passed the official sample and random brute tests.
edge:
Chains have many colorings but only one traversal list; the DP removes a layer boundary unless some vertex of layer k+1 appears before a later vertex of layer k in DFS order.

DP:
Each partial DFS sequence state is (h, mask), where h is maximum layer and mask contains adjacent boundaries y whose layer y-1/y order is not yet distinguished inside the sequence. A boundary is good if there is a layer-y vertex before a later layer-(y-1) vertex.

When concatenating A then B, boundary y becomes good if it was already good in A, already good in B, or A contains level y and B contains level y-1. All levels in a valid component are contiguous, so the cross-good range is y in [shift+1, min(hA,hB+1)].

代码

来源：problems/cf2237I1/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1000000007;
const ll maxn=3005;
struct node{
    int h;
    string m;
    ll z;
};
vector<int>ss[maxn];
vector<node>dp[maxn];
char s[maxn];
int getl(const string &x,int i){
    return (unsigned char)x[i*4]+((unsigned char)x[i*4+1]<<8);
}
int getr(const string &x,int i){
    return (unsigned char)x[i*4+2]+((unsigned char)x[i*4+3]<<8);
}
void addint(vector<pair<int,int>>&v,int l,int r){
    if(r>=l) v.push_back({l,r});
}
void pushseg(string &x,int l,int r){
    if(r<l) return;
    if(!x.empty()){
        int p=x.size()/4-1;
        int L=getl(x,p),R=getr(x,p);
        if(l<=R+1){
            r=max(r,R);
            x.resize(x.size()-4);
            l=L;
        }
    }
    x.push_back((char)(l&255));
    x.push_back((char)(l>>8));
    x.push_back((char)(r&255));
    x.push_back((char)(r>>8));
}
string addtail(string x,int l,int r){
    pushseg(x,l,r);
    return x;
}
string enc(vector<pair<int,int>>v){
    int i,l,r;
    string x;
    if(v.empty()) return x;
    sort(v.begin(),v.end());
    l=v[0].first;
    r=v[0].second;
    for(i=1;i<(int)v.size();i++){
        if(v[i].first<=r+1) r=max(r,v[i].second);
        else{
            x.push_back((char)(l&255));
            x.push_back((char)(l>>8));
            x.push_back((char)(r&255));
            x.push_back((char)(r>>8));
            l=v[i].first;
            r=v[i].second;
        }
    }
    x.push_back((char)(l&255));
    x.push_back((char)(l>>8));
    x.push_back((char)(r&255));
    x.push_back((char)(r>>8));
    return x;
}
string shl1(string x){
    int i,n;
    vector<pair<int,int>>v;
    n=x.size()/4;
    for(i=0;i<n;i++){
        addint(v,getl(x,i)+1,getr(x,i)+1);
    }
    addint(v,1,1);
    return enc(v);
}
string getmask(const string &a,int ha,const string &b,int hb,int h,int d){
    int i,j,n,m,L,R,cl,cr,al,ar,bl,br;
    vector<pair<int,int>>q;
    string x,y,z;
    x=addtail(a,ha+1,h);
    y=addtail(b,hb+1,h);
    n=x.size()/4;
    m=y.size()/4;
    L=d+1;
    R=min(ha,hb+1);
    i=j=0;
    while(i<n and j<m){
        al=getl(x,i);
        ar=getr(x,i);
        bl=getl(y,j);
        br=getr(y,j);
        cl=max(al,bl);
        cr=min(ar,br);
        if(cr<L or cl>R) addint(q,cl,cr);
        else{
            addint(q,cl,L-1);
            addint(q,R+1,cr);
        }
        if(ar<br) i++;
        else j++;
    }
    return enc(q);
}
bool cmpnode(const node &a,const node &b){
    int i;
    if(a.h!=b.h) return a.h<b.h;
    if(a.m.size()!=b.m.size()) return a.m.size()<b.m.size();
    for(i=(int)a.m.size()-1;i>=0;i--){
        if((unsigned char)a.m[i]!=(unsigned char)b.m[i]) return (unsigned char)a.m[i]<(unsigned char)b.m[i];
    }
    return false;
}
void addvec(vector<node>&v,node x){
    v.push_back(x);
}
void norm(vector<node>&v){
    int i,j,n;
    vector<node>q;
    sort(v.begin(),v.end(),cmpnode);
    n=v.size();
    for(i=0;i<n;i=j){
        ll zc=0;
        for(j=i;j<n and v[j].h==v[i].h and v[j].m==v[i].m;j++) zc=(zc+v[j].z)%mod;
        q.push_back({v[i].h,v[i].m,zc});
    }
    v.swap(q);
}
vector<node> shiftvec(const vector<node>&v,int d){
    int i,n;
    vector<node>q;
    if(d==0) return v;
    n=v.size();
    q.reserve(n);
    for(i=0;i<n;i++){
        string x;
        x=shl1(v[i].m);
        q.push_back({v[i].h+1,x,v[i].z});
    }
    return q;
}
vector<node> mergevec(const vector<node>&a,const vector<node>&b,int d){
    int i,j,h;
    string m;
    vector<node>q;
    q.reserve(a.size()*b.size());
    for(i=0;i<(int)a.size();i++){
        for(j=0;j<(int)b.size();j++){
            h=max(a[i].h,b[j].h);
            m=getmask(a[i].m,a[i].h,b[j].m,b[j].h,h,d);
            q.push_back({h,m,a[i].z*b[j].z%mod});
        }
    }
    norm(q);
    return q;
}
void dfs(int u){
    int i,j,v,d;
    vector<node>cur,tmp,p;
    cur.push_back({0,"",1});
    for(i=0;i<(int)ss[u].size();i++){
        v=ss[u][i];
        dfs(v);
        tmp.clear();
        for(d=0;d<=1;d++){
            if(d==1 and s[v]!='?') continue;
            p=mergevec(cur,shiftvec(dp[v],d),d);
            for(j=0;j<(int)p.size();j++) tmp.push_back(p[j]);
        }
        norm(tmp);
        cur.swap(tmp);
    }
    dp[u].swap(cur);
}
int main(){
    int t,n,i,j,l,x;
    ll ans;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        scanf("%s",s+2);
        for(i=1;i<=n;i++){
            ss[i].clear();
            dp[i].clear();
        }
        for(i=1;i<=n;i++){
            scanf("%d",&l);
            for(j=1;j<=l;j++){
                scanf("%d",&x);
                ss[i].push_back(x);
            }
        }
        dfs(1);
        ans=0;
        for(i=0;i<(int)dp[1].size();i++){
            if(dp[1][i].m.empty()) ans=(ans+dp[1][i].z)%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}