6.6 NOI 模拟

\(T1\)括号序列

——那是，朝思夜想也未尝得到的自由

一个比较常见的转化，考虑如何判断前一段和后一段能够拼成一个合法的括号序列

充要条件：

前半部分，‘（’看为\(1\)， ‘）’看为\(-1\)，前缀和一直\(\geq 0\)

后半部分，‘）’看为\(1\)， '（'看做\(-1\)，后缀和一直\(\geq 0\)

并且前缀和等于后缀和

然后，依照这个结论可以使用暴力拿到\(70pts\)，\(100pts\)需要写的很麻烦，所以换一种写法

\(70pts\)：

暴力统计每个位置满足条件的就好了

#include<cstdio>

using namespace std;

int n,q,l,r,cn[8010];

char s[8010];

int main()

{

    scanf("%d%d%s",&n,&q,s+1);

    for(int i=1;i<=q;i++)

    {

        scanf("%d%d",&l,&r);

        long long res=0;

        int li=l-1,lt=0;

        while(li<r&&lt>=0)

        {

            cn[lt]++;

            if(s[++li]=='(')lt++;

            else lt--;

        }

        int ri=r+1,rt=0;

        while(ri>l&&rt>=0)

        {

            if(li==ri)

            {

                if(s[li--]=='(')lt--;

                else lt++;

                cn[lt]--;

            }

            res+=cn[rt];

            if(s[--ri]==')')rt++;

            else rt--;

        }

        while(li>=l)

        {

            if(s[li--]=='(')lt--;

            else lt++;

            cn[lt]--;

        }

        printf("%lld\n",res);

    }

    return 0;

设\(f[l][r]\)表示区间\([l,r]\)的方案数

考虑类似\(S[l,r]\)形如\((...)\)的询问，\(l'\)为\(s[l]\)匹配右括号的位置，\(r'\)为\(s[r]\)匹配左括号的位置，我们对删去\(L,R\)位置进行讨论

\(Sit_1:L>l'\)或\(R<r'\)

\(Case_1:L>l'\)且\(R<r'\) \(f[l][r]+=f[l'+1][r'-1]\)比较显然，可以和外面的合法括号序列接上

\(Case_2:R<r',f[l][r]+=f[l][r'-1]\)，同上

\(Case_3:L>l' ,f[l][r]+=f[l'+1][r]\)，同上

\(Sit_2:L\leq l',R\geq r'\)

\(f[l][r]+=f[l+1][r-1]\)

至于不是形如这样的询问，直接把\(l'=n,r'=1\)即可

正确性的话，这样的话转移的时候不合法的就直接变成\(0\)了，就是包含最左最右不合法部分的

#include<bits/stdc++.h>

#define MAXN 8010

using namespace std;

int n,q,in1,in2,pre[MAXN],nxt[MAXN],dp[MAXN][MAXN];

vector<int>sta;

char s[MAXN];

int main()

{

    scanf("%d%d",&n,&q);

    scanf("%s",s+1);

    for(int i=1;i<=n;i++)

    {

        pre[i]=1;//r'

        nxt[i]=n;//l'

    }

    for(int i=1;i<=n;i++)

    {

        if(s[i]=='(')

        {

            sta.push_back(i);

        }

        else

        {

            if(!sta.empty())

            {

                nxt[sta.back()]=i;

                sta.pop_back();

            }

        }

    }

    sta.clear();

    for(int i=n;i;i--)

    {

        if(s[i]==')')

        {

            sta.push_back(i);

        }

        else

        {

            if(!sta.empty())

            {

                pre[sta.back()]=i;

                sta.pop_back();

            }

        }

    }

    sta.clear();

    for(int i=1;i<=n;i++)dp[i][i]=1;

    for(int i=1;i<n;i++)

    {

        for(int j=1;j+i<=n;j++)

        {

            dp[j][j+i]=dp[nxt[j]+1][j+i]+dp[j][pre[j+i]-1]-dp[nxt[j]+1][pre[j+i]-1]+1;

//            cout<<"zy: "<<nxt[j]+1<<" "<<j+i<<"\n";

//            cout<<"zy: "<<j<<" "<<pre[j+i]-1<<"\n";

//            cout<<"zy: "<<nxt[j]+1<<" "<<pre[j+i]-1<<"\n";

            if(s[j]=='('&&s[j+i]==')')

            {

                dp[j][j+i]+=dp[j+1][j+i-1];

            }

        }

    }

    for(int i=1,l,r;i<=q;i++)

    {

    	scanf("%d%d",&l,&r);

        cout<<dp[l][r]<<"\n";

    }

    return 0;

}

\(T2\)泽连斯基

——那是，至今为止都不曾体会的懵懂

\(l_i\le r_i\)的部分分比较简单，考虑维护一个单点最大值就好了，因为必然有一个位置被所有线段包含

正解：

考虑枚举一个圆弧，钦定为答案中最短的圆弧为\(x\)

可以把其余圆弧分成\(7\)类

\(Case_1:\)和\(x\)相同，必然需要加入答案

\(Case_2:\)被\(x\)包含，钦定\(x\)最小，必然不选

\(Case_3:\)包含\(x\)，由于\(x\)和其他有交，那么包含\(x\)必然也有交，必然加入答案

\(Case_4:\)和\(x\)无交，必然不选

\(Case_5:\)包含\(x\)左端点，称为\(L\)，下面讨论

\(Case_6:\)包含\(x\)右端点，称为\(R\)，下面讨论

\(Case_7:\)包含左右\(x\)端点，但不包含\(x\)，称为\(U\)，\(U\)必然与\(L/R\)相交，\(U\)必选

我们只需考虑\(L,R\)最多可以选出几个，\(L,R\)内部必然两两相交

所以我们二维数点！

圆弧看成平面上一个点\((x,y)\)，\(L\)为黑点，\(R\)为白点，转化成

平面上选出最多的点使得不存在一个黑点\((x_1,y_1)\)和一个白点\((x_2,y_2)\)满足\(x_1<y_1\land x_2<y_2\)

然后考虑\(dp\)，\(f[x][y]\)表示横坐标\(\leq x\)的所有点，黑点纵坐标最小值为\(y\)最多能选多少个，由于最大值我们直接选一个最大值转移就好了，这就变成了一个线段树优化\(DP\)

#include <bits/stdc++.h>

//#define int long long

#define ll long long

#define db double

#define fi first

#define se second

#define pii pair<int,int>

#define vi vector<int>

using namespace std;

const int maxn=6e3;

struct node {

    int l,r;

} a[maxn+5];

int n,L[maxn+5],R[maxn+5],key[maxn*2+5],cnt,cnt2; 

int ID[maxn+5],len[maxn+5];

int in(int l,int r,int x) {

    if (l<=r) return l<=x && x<=r;

    return ((l<=x && x<=cnt) || (1<=x && x<=r));

}

struct point {

    int x,y,o;

    point() {

        x=y=o=0;

    }

    point(int a,int b,int c) {

        x=a,y=b,o=c;

    }

    bool operator < (const point &t) const {

        return x==t.x?(o>t.o):x<t.x;

    }

} b[maxn+5];

int num; 

int mx[maxn*8+5],tag[maxn*8+5];

void seta(int p,int d) {

    tag[p]+=d;

    mx[p]+=d;

}

void upd(int p) {

    mx[p]=max(mx[p+p],mx[p+p+1]);

}

void push(int p) {

    if (!tag[p]) return ;

    seta(p+p,tag[p]);

    seta(p+p+1,tag[p]);

    tag[p]=0;

}

void build(int p,int l,int r) {

    mx[p]=-1e9;

    tag[p]=0;

    if (l==r) {

        if (l==cnt2) mx[p]=0;

        return ;

    }

    int mid=(l+r)>>1;

    build(p+p,l,mid);

    build(p+p+1,mid+1,r);

    upd(p);

}

void modify(int p,int l,int r,int ql,int qr,int d) {

    if (ql>qr) return ;

    if (l==ql&&r==qr) {

        seta(p,d);

        return ;

    }

    int mid=(l+r)>>1;

    push(p);

    if (qr<=mid) modify(p+p,l,mid,ql,qr,d);

    else if (mid<ql) modify(p+p+1,mid+1,r,ql,qr,d);

    else modify(p+p,l,mid,ql,mid,d),modify(p+p+1,mid+1,r,mid+1,qr,d);

    upd(p);

}

void cover(int p,int l,int r,int pos,int d) {

    if (l==r){

        mx[p]=max(mx[p],d);

        return ;

    }

    push(p);

    int mid=(l+r)>>1;

    if (pos<=mid) cover(p+p,l,mid,pos,d);

    else cover(p+p+1,mid+1,r,pos,d);

    upd(p);

}

int query(int p,int l,int r,int ql,int qr) {

    if (ql>qr) return -1e9;

    if (l==ql&&r==qr) return mx[p];

    int mid=(l+r)>>1;

    push(p);

    if (qr<=mid) return query(p+p,l,mid,ql,qr);

    else if (mid<ql) return query(p+p+1,mid+1,r,ql,qr);

    else return max(query(p+p,l,mid,ql,mid),query(p+p+1,mid+1,r,mid+1,qr));

}

void solve() {

    cin>>n;

    cnt=0;

    for (int i=1;i<=n;i++) {

        cin>>L[i]>>R[i];

        key[++cnt]=L[i],key[++cnt]=R[i];

    }

    sort(key+1,key+cnt+1);

    cnt=unique(key+1,key+cnt+1)-key-1;

    for (int i=1;i<=n;i++) {

        L[i]=lower_bound(key+1,key+cnt+1,L[i])-key;

        R[i]=lower_bound(key+1,key+cnt+1,R[i])-key;

        len[i]=(R[i]-L[i]+cnt)%cnt;

    }

    for (int i=1;i<=cnt;i++) ID[i]=0;

    int ans=0;

    for (int i=1;i<=n;i++) {

        num=cnt2=0;

        int nl=L[i],nr=R[i];

        int p=nl;

        while (1) {

            ID[p]=i;

            if (p==nr) break ;

            p=p%cnt+1;

        }

        int cursum=0;

        for (int j=1;j<=n;j++) {

            if (i==j) continue ;

            if (len[j]<len[i]) {

                continue ;

            }

            int inl=in(L[j],R[j],L[i]);

            int inr=in(L[j],R[j],R[i]);

            if (!inl && !inr) continue ;

            if (inl && inr) cursum++;

            else {

                int x=L[j],y=R[j];

                if (ID[x]!=i) swap(x,y);

                x=(x-L[i]+cnt)%cnt;

                y=(L[i]-y+cnt)%cnt;

                x++,y++;

                if (inl) {

                    b[++num]=point(x,y,0);

                    key[++cnt2]=y;

                }

                else {

                    b[++num]=point(x,y,1);

                    key[++cnt2]=y;

                }

            }

        }

        if (!num) {

            ans=max(ans,cursum+1);

            continue;

        }

        sort(key+1,key+cnt2+1);

        cnt2=unique(key+1,key+cnt2+1)-key-1;

        for (int j=1;j<=num;j++) {

            b[j].y=lower_bound(key+1,key+cnt2+1,b[j].y)-key;

        }

        build(1,1,cnt2);

        sort(b+1,b+num+1);

        for (int j=1;j<=num;j++) {

            if (b[j].o==0) {

                modify(1,1,cnt2,1,b[j].y-1,1);

                int mx=query(1,1,cnt2,b[j].y,cnt2);

                cover(1,1,cnt2,b[j].y,mx+1);

            }

            else {

                modify(1,1,cnt2,b[j].y,cnt2,1);

            }

        }

        ans=max(ans,cursum+mx[1]+1);

    }

    cout<<ans<<'\n';

}

int main() {

    int T;

    cin>>T;

    while (T--) solve();

    return 0;

}

\(T3\)

——那是，将我们三色交织在一起的绘卷

不会

讲题人：这道题太奇怪了，咱们不讲了吧

魔怔出题人的题解

巴特西

6.6 NOI 模拟

最新文章

热门文章