题解：CF2144F Bracket Groups

Sgt_Dante · 2025-12-04 19:15:37 · 题解

看见这个 k\leq 50 咱就先打了个表，发现长度为 50 的合法括号序列只有 43422380 个。

然后咱发现这个该组内的任意一个串都不是这个串的子串的限制非常弱。

考虑极端一点的情况，假设咱有两个串分别为()()()()...和(((((...(())...)))))，那么他们共同拥有的字串就只有()。而咱要给出的括号串必须要合法，所以不可能不包含()，所以含有()的情况一定无解。

那么咱已经有了一个组数为 2 的构造方案，接下来就只用考虑组数为 1 的就可以了。而长度为 50 的合法括号序列只有 43422380 个，咱可以暴搜搜出所有的长度为 k 的合法括号串，再花费 O(k) 的代价在ACAM上判断是否合法即可。

时间复杂度 O(k\times S)~~~(S=43422380)。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2505,M=55;

int n,k;
struct node{int son[26],fal,tag;}tr[N];
char ans[N];int tot;
vector<int> G[N],ans1,ans2;

void insert(string &s)
{
    int u=0;
    for(char c:s)
    {
        int p=c-'(';
        if(!tr[u].son[p]) 
            tr[u].son[p]=++tot;
        tr[tr[u].son[p]].tag|=tr[u].tag;
        u=tr[u].son[p];
    }
    tr[u].tag=1;
}

void build()
{
    queue<int> q;
    for(int i=0;i<26;i++) 
        if(tr[0].son[i]) 
            q.push(tr[0].son[i]),
            G[0].push_back(tr[0].son[i]),
            tr[tr[0].son[i]].fal=0;
    while(q.size())
    {
        int u=q.front();q.pop();
        for(int i=0;i<26;i++)
        {
            int to=tr[u].fal,v=tr[u].son[i];
            if(v)
            {
                tr[v].fal=tr[to].son[i];
                G[tr[v].fal].push_back(v);
                q.push(v);
            }
            else tr[u].son[i]=tr[to].son[i];
        }
    }
}

void init(int u)
{
    for(int v:G[u]) 
        tr[v].tag|=tr[u].tag,init(v);
}

bool dfs(int u,int l,int s,int op)
{
    ans[k-l]=op+'(';
//  cout<<u<<" "<<l<<" "<<s<<" "<<op<<"\n";
//  for(int i=1;i<=k-l;i++) cout<<ans[i];cout<<'\n'<<tr[u].tag<<'\n';
    if(tr[u].tag) return 0;
    else if(!l) return 1;
    else if(!s) return dfs(tr[u].son[0],l-1,s+1,0);
    else if(s==l) return dfs(tr[u].son[1],l-1,s-1,1);
    else if(s>l) return 0;
    else if(!dfs(tr[u].son[0],l-1,s+1,0)) 
        return dfs(tr[u].son[1],l-1,s-1,1);
    else return 1;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        string s;cin>>s;
        if(s=="()") return cout<<-1,0;
        int cnt=0,pos=-1;
        for(int i=0;i+1<s.size();i++)
            if(s[i]!=s[i+1]) pos=i,cnt++;
        if(cnt>1) ans1.push_back(i);
        else if(cnt==1&&s[pos]=='(') ans2.push_back(i);
        else if(cnt==1) ans1.push_back(i);
        else ans2.push_back(i);
        insert(s);
    }
    build();
    init(0);
    if(dfs(0,k,0,0))
    {
        cout<<1<<'\n';
        for(int i=1;i<=k;i++) cout<<ans[i];
        cout<<'\n'<<n<<'\n';
        for(int i=1;i<=n;i++) cout<<i<<" ";
        return 0;
    }
    cout<<2<<'\n';
    for(int i=1;i<=k/2;i++) cout<<'(';
    for(int i=1;i<=k/2;i++) cout<<')';
    cout<<'\n';
    cout<<ans1.size()<<'\n';
    for(int p:ans1) cout<<p<<" ";cout<<'\n';
    for(int i=1;i<=k/2;i++) cout<<"()";
    cout<<'\n';
    cout<<ans2.size()<<'\n';
    for(int p:ans2) cout<<p<<" ";cout<<'\n';
    return 0;
}