文章导读

Feb. 12th 总结 | 组合数学-Catalan 数 (Chpt.3)

DRheEheAM_Gary 2026-02-12 48

每日 Ad-hoc

P7915 [CSP-S 2021] 回文

我打算先贴代码（？

//hanser!!!!!!!
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=1e6+10;
int n,a[N];
char h,ans[N],er;
bool check (int u,int v) {
    return a[u]==a[v];
}
bool slove (int ll,int lr,int rl,int rr) {
    for (int t=1;t<n;t++) {
        if ((ll<lr)&&check(ll,lr)) {
            ans[t]='L';
            ans[2*n-t-1]='L';
            ll++;
            lr--;
        }
        else if ((ll<=lr)&&(rl<=rr)&&check(ll,rl)) {
            ans[t]='L';
            ans[2*n-t-1]='R';
            ll++;
            rl++;
        }
        else if ((ll<=lr)&&(rl<=rr)&&check(rr,lr)) {
            ans[t]='R';
            ans[2*n-t-1]='L';
            rr--;
            lr--;
        }
        else if ((rl<rr)&&check(rr,rl)) {
            ans[t]='R';
            ans[2*n-t-1]='R';
            rl++;
            rr--;
        }
        else return 0;
    }
    return 1;
}
signed main() {
    Cios;
    int T;
    cin>>T;
    while (T--) {
        cin>>n;
        for (int i=1;i<=2*n;i++) cin>>a[i];
        for (int i=1;i<=2*n+1;i++) ans[i]=0;
        int posl=-1,posr=-1;
        for (int i=1;i<=2*n;i++) {
            if (a[i]==a[1]&&i!=1) posl=i;
            if (a[i]==a[2*n]&&i!=2*n) posr=i;
        }
        if (slove(2,posl-1,posl+1,2*n)) cout<<"L"<<(ans+1)<<"L\n";
        else if (slove(1,posr-1,posr+1,2*n-1)) cout<<"R"<<(ans+1)<<"L\n";
        else cout<<"-1\n";
    }
    return 0;
}

//hanser!!!!!!!
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=1e6+10;
int n,a[N];
char h,ans[N],er;
bool check (int u,int v) {
    return a[u]==a[v];
}
bool slove (int ll,int lr,int rl,int rr) {
    for (int t=1;t<n;t++) {
        if ((ll<lr)&&check(ll,lr)) {
            ans[t]='L';
            ans[2*n-t-1]='L';
            ll++;
            lr--;
        }
        else if ((ll<=lr)&&(rl<=rr)&&check(ll,rl)) {
            ans[t]='L';
            ans[2*n-t-1]='R';
            ll++;
            rl++;
        }
        else if ((ll<=lr)&&(rl<=rr)&&check(rr,lr)) {
            ans[t]='R';
            ans[2*n-t-1]='L';
            rr--;
            lr--;
        }
        else if ((rl<rr)&&check(rr,rl)) {
            ans[t]='R';
            ans[2*n-t-1]='R';
            rl++;
            rr--;
        }
        else return 0;
    }
    return 1;
}
signed main() {
    Cios;
    int T;
    cin>>T;
    while (T--) {
        cin>>n;
        for (int i=1;i<=2*n;i++) cin>>a[i];
        for (int i=1;i<=2*n+1;i++) ans[i]=0;
        int posl=-1,posr=-1;
        for (int i=1;i<=2*n;i++) {
            if (a[i]==a[1]&&i!=1) posl=i;
            if (a[i]==a[2*n]&&i!=2*n) posr=i;
        }
        if (slove(2,posl-1,posl+1,2*n)) cout<<"L"<<(ans+1)<<"L\n";
        else if (slove(1,posr-1,posr+1,2*n-1)) cout<<"R"<<(ans+1)<<"L\n";
        else cout<<"-1\n";
    }
    return 0;
}

我们分析题面。

发现： $[1,n]$ 中的每个数都会出现且仅出现 $2$ 次。

所以我们分类讨论：
如果第一个操作为 L ，那么我们找到开头这个数第二次出现的位置，记作 $posl$ 。
可以发现，这个数只能最后出去，否则无解。

所以我们可以将 $posl$ 左右两边看做两个栈，栈顶分别为位置 $2$ 和 $2n$ 。

容易发现，当其中一个栈顶的数出现在了两个栈的任意一个栈底中，那么这个数就可以去掉，并且根据它所在的两个栈分别记录操作。
要求字典序最小，所以优先考虑左边的栈。
具体看代码中的 slove 函数。

发现第一个操作为 R 时同理。

要求字典序最小，优先考虑操作 L ，最后一个操作必定为 L。

组合数学-Catalan数

P14973 『GTOI – 2D』木棍

最开始嗑了一下没想出来。

看题解：？为什么有线段树
看标签：我去真有线段树

接下来我们分析题目…?

我们需要先推导 $V(S)$ 与 $f(S)$ 之间的关系。

我们记 $S$ 消掉 $d$ 对 01 串后变为长度为 $k$ 的 $f(S)$ ，记原序列 $S$ 长度为 $len$ ，则显然 $\large d=\frac{len-k}{2}$ 。

那么证明该式子：

\Large V(S)=C_{\ len}^{\ d}-C_{\ len}^{\ d+1}

可以考虑将 0->( ，将 1->) ，则转化为我们熟悉的括号序列配对问题，发现答案总数正好是 Catalan 数。

那么我们用线段树维护区间 0 和 1 在消去 01 串后的数量，以及取反后区间 0 和 1 在消去 01 串后的数量，以及区间翻转懒标记。
然后线段树节点合并需要注意一下，因为每个节点在消去 01 串后都为 $1…0…$ 的格式，所以两点合并时，左节点的 0 会和右节点的 1 尽可能多的合并，所以要进行一定的操作，具体见代码。

详细证明可以参考洛谷的这篇题解。

//hanser!!!!!!!
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=1e6+10,mod=998244353;
int n;
char s[N];
class segmentTree {
    #define lc(p) (p<<1)
    #define rc(p) (p<<1|1)
    struct node {
        int cnt0,cnt1,pcnt0,pcnt1;
        bool lz;
        void tag () {
            lz=!lz;
            swap(cnt0,pcnt0);
            swap(cnt1,pcnt1);
        }
        node ()=default;
    }tr[N<<2];
    void pushup (int p) {
        tr[p].cnt0=tr[lc(p)].cnt0+tr[rc(p)].cnt0;
        tr[p].cnt1=tr[lc(p)].cnt1+tr[rc(p)].cnt1;
        tr[p].pcnt0=tr[lc(p)].pcnt0+tr[rc(p)].pcnt0;
        tr[p].pcnt1=tr[lc(p)].pcnt1+tr[rc(p)].pcnt1;
        int deleted=min(tr[lc(p)].cnt0,tr[rc(p)].cnt1),pdeleted=min(tr[lc(p)].pcnt0,tr[rc(p)].pcnt1);
        tr[p].cnt0-=deleted;
        tr[p].cnt1-=deleted;
        tr[p].pcnt0-=pdeleted;
        tr[p].pcnt1-=pdeleted;
    }
    void pushdown (int p) {
        if (tr[p].lz) {
            tr[lc(p)].tag();
            tr[rc(p)].tag();
            tr[p].lz=0;
        }
    }
    public:
    void build (int p,int l,int r) {
        tr[p]=node();
        if (l==r) {
            if (s[l]=='0') {
                tr[p].cnt0++;
                tr[p].pcnt1++;
            }
            else {
                tr[p].cnt1++;
                tr[p].pcnt0++;
            }
            return;
        }
        int mid((l+r)>>1);
        build (lc(p),l,mid);
        build (rc(p),mid+1,r);
        pushup(p);
    } 
    void update (int p,int l,int r,int ql,int qr) {
        if (ql<=l&&r<=qr) {
            tr[p].tag();
            return;
        }
        int mid((l+r)>>1);
        pushdown(p);
        if (ql<=mid) update (lc(p),l,mid,ql,qr);
        if (qr >mid) update (rc(p),mid+1,r,ql,qr);
        pushup(p);
    }
    struct answer {
        int cnt0,cnt1;
        answer () =default;
        answer (int _cnt0,int _cnt1):cnt0(_cnt0),cnt1(_cnt1) {}
        answer (node p):cnt0(p.cnt0),cnt1(p.cnt1) {}
    };
    answer merge (answer p,answer q) {
        if (p.cnt0==0&&p.cnt1==0) return q;
        if (q.cnt0==0&&q.cnt1==0) return p;
        int deleted=min(p.cnt0,q.cnt1);
        answer ans=answer(p.cnt0+q.cnt0-deleted,p.cnt1+q.cnt1-deleted);
        return ans;
    }
    answer query (int p,int l,int r,int ql,int qr) {
        if (ql<=l&&r<=qr) return tr[p];
        int mid((l+r)>>1);
        pushdown(p);
        answer ansl=answer(),ansr=answer();
        if (ql<=mid) ansl=query(lc(p),l,mid,ql,qr);
        if (qr> mid) ansr=query(rc(p),mid+1,r,ql,qr);
        return merge(ansl,ansr);
    }
    #undef lc
    #undef rc
}st;
int f[N],invf[N];
int qpow (int a,int b) {
    int res=1;
    while (b) {
        if (b&1) res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
void init () {
    f[0]=f[1]=1;
    for (int i=2;i<N;i++) f[i]=(i*f[i-1])%mod;
    invf[N-1]=qpow(f[N-1],mod-2);
    for (int i=N-2;i>=0;i--) invf[i]=((i+1)*invf[i+1])%mod;
}
int C(int a,int b) {
    if (a<0||b<0||a<b) return 0;
    return ((f[a]*invf[b])%mod*invf[a-b])%mod;
}
int V(int len,int k) {
    if ((len-k)%2) return 0;
    int d=(len-k)/2;
    return ((C(len,d)-C(len,d-1))%mod+mod)%mod;
}
signed main() {
    Cios;
    init();
    cin>>n;
    cin>>(s+1);
    st.build(1,1,n);
    int q;
    cin>>q;
    while (q--) {
        int op,l,r;
        cin>>op>>l>>r;
        if (op==1) st.update(1,1,n,l,r);
        else if (op==2) {
            auto res=st.query(1,1,n,l,r);
            int k=res.cnt0+res.cnt1;
            cout<<V(r-l+1,k)<<"\n";
        }
    }
    return 0;
}

//hanser!!!!!!!
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=1e6+10,mod=998244353;
int n;
char s[N];
class segmentTree {
    #define lc(p) (p<<1)
    #define rc(p) (p<<1|1)
    struct node {
        int cnt0,cnt1,pcnt0,pcnt1;
        bool lz;
        void tag () {
            lz=!lz;
            swap(cnt0,pcnt0);
            swap(cnt1,pcnt1);
        }
        node ()=default;
    }tr[N<<2];
    void pushup (int p) {
        tr[p].cnt0=tr[lc(p)].cnt0+tr[rc(p)].cnt0;
        tr[p].cnt1=tr[lc(p)].cnt1+tr[rc(p)].cnt1;
        tr[p].pcnt0=tr[lc(p)].pcnt0+tr[rc(p)].pcnt0;
        tr[p].pcnt1=tr[lc(p)].pcnt1+tr[rc(p)].pcnt1;
        int deleted=min(tr[lc(p)].cnt0,tr[rc(p)].cnt1),pdeleted=min(tr[lc(p)].pcnt0,tr[rc(p)].pcnt1);
        tr[p].cnt0-=deleted;
        tr[p].cnt1-=deleted;
        tr[p].pcnt0-=pdeleted;
        tr[p].pcnt1-=pdeleted;
    }
    void pushdown (int p) {
        if (tr[p].lz) {
            tr[lc(p)].tag();
            tr[rc(p)].tag();
            tr[p].lz=0;
        }
    }
    public:
    void build (int p,int l,int r) {
        tr[p]=node();
        if (l==r) {
            if (s[l]=='0') {
                tr[p].cnt0++;
                tr[p].pcnt1++;
            }
            else {
                tr[p].cnt1++;
                tr[p].pcnt0++;
            }
            return;
        }
        int mid((l+r)>>1);
        build (lc(p),l,mid);
        build (rc(p),mid+1,r);
        pushup(p);
    } 
    void update (int p,int l,int r,int ql,int qr) {
        if (ql<=l&&r<=qr) {
            tr[p].tag();
            return;
        }
        int mid((l+r)>>1);
        pushdown(p);
        if (ql<=mid) update (lc(p),l,mid,ql,qr);
        if (qr >mid) update (rc(p),mid+1,r,ql,qr);
        pushup(p);
    }
    struct answer {
        int cnt0,cnt1;
        answer () =default;
        answer (int _cnt0,int _cnt1):cnt0(_cnt0),cnt1(_cnt1) {}
        answer (node p):cnt0(p.cnt0),cnt1(p.cnt1) {}
    };
    answer merge (answer p,answer q) {
        if (p.cnt0==0&&p.cnt1==0) return q;
        if (q.cnt0==0&&q.cnt1==0) return p;
        int deleted=min(p.cnt0,q.cnt1);
        answer ans=answer(p.cnt0+q.cnt0-deleted,p.cnt1+q.cnt1-deleted);
        return ans;
    }
    answer query (int p,int l,int r,int ql,int qr) {
        if (ql<=l&&r<=qr) return tr[p];
        int mid((l+r)>>1);
        pushdown(p);
        answer ansl=answer(),ansr=answer();
        if (ql<=mid) ansl=query(lc(p),l,mid,ql,qr);
        if (qr> mid) ansr=query(rc(p),mid+1,r,ql,qr);
        return merge(ansl,ansr);
    }
    #undef lc
    #undef rc
}st;
int f[N],invf[N];
int qpow (int a,int b) {
    int res=1;
    while (b) {
        if (b&1) res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
void init () {
    f[0]=f[1]=1;
    for (int i=2;i<N;i++) f[i]=(i*f[i-1])%mod;
    invf[N-1]=qpow(f[N-1],mod-2);
    for (int i=N-2;i>=0;i--) invf[i]=((i+1)*invf[i+1])%mod;
}
int C(int a,int b) {
    if (a<0||b<0||a<b) return 0;
    return ((f[a]*invf[b])%mod*invf[a-b])%mod;
}
int V(int len,int k) {
    if ((len-k)%2) return 0;
    int d=(len-k)/2;
    return ((C(len,d)-C(len,d-1))%mod+mod)%mod;
}
signed main() {
    Cios;
    init();
    cin>>n;
    cin>>(s+1);
    st.build(1,1,n);
    int q;
    cin>>q;
    while (q--) {
        int op,l,r;
        cin>>op>>l>>r;
        if (op==1) st.update(1,1,n,l,r);
        else if (op==2) {
            auto res=st.query(1,1,n,l,r);
            int k=res.cnt0+res.cnt1;
            cout<<V(r-l+1,k)<<"\n";
        }
    }
    return 0;
}

查看评论列表

暂无评论

发表评论取消回复

访客未填写邮箱

[填写昵称邮箱后可以评论]

Hello! 欢迎来到DRheEheAM的blog！

加载中

Feb. 12th 总结 | 组合数学-Catalan 数 (Chpt.3)

每日 Ad-hoc

P7915 [CSP-S 2021] 回文

组合数学-Catalan数

P14973 『GTOI – 2D』木棍

评论（0）

发表评论取消回复

插入代码

DRheEheAM_Gary Blog

Hello! 欢迎来到DRheEheAM的blog！

加载中

Feb. 12th 总结 | 组合数学-Catalan 数 (Chpt.3)

每日 Ad-hoc

P7915 [CSP-S 2021] 回文

组合数学-Catalan数

P14973 『GTOI – 2D』木棍

评论（0）

发表评论 取消回复

插入代码

DRheEheAM_Gary Blog

发表评论取消回复