2024.12.24-2024.12.31 思维训练题解

【MX-S3-T2】「FeOI Round 1」Journey

见题解：P10886 【MX-S3-T2】「FeOI Round 1」Journey

[ARC186B] Typical Permutation Descriptor

题目大意：
给你一个长度为

N

的整数序列

(A_1,\dots,A_N)

。这个序列中的每个

i=1,\dots,N

都满足

0 \le A_i < i

。求以

998244353

为模数，满足以下条件的

(1,\dots,N)

的排列

(P_1,P_2,\dots,P_N)

的个数。

对于每个 $i=1,\dots,N$ $i = 1, \dots, N$ ：
- 对于所有满足 $A_i < j < i$ 的整数 $j$ ，都有 $P_j > P_i$ 。
- 如果 $A_i \neq 0$ ，则 $P_{A_i} < P_i$ 。

保证对于输入中给出的

(A_1, A_2, \dots, A_N)

序列，存在至少一个满足上述条件的排列。

考虑小的向大的连边，转化成一张 DAG 的拓扑序计数。

由于边数是

O(n^2)

的，所以无法直接建图。

发现一些边是没有用的，即拓扑排序的时候不会入队，用单调栈维护建边，只保留有用的边，最后出来的是一棵外向树，最终答案为

\frac{n!}{\prod_{i=1}^{n}sz_i}

【MX-X4-T3】「Jason-1」数对变换

题目大意：对一个数对

(a,b)

进行不超过

65

次操作，使得

(a,b)

变成

(c,d)

，不用最小化方案数。

先考虑这么变

(a,b) \to (1,a\times b) \to (c\times d,\lfloor \frac{a\times b}{c\times d}\rfloor) \to \dots \to (c\times d,1) \to (c,d)

想办法让

\lfloor \frac{a\times b}{c\times d} \rfloor=1

，令

n=\lfloor \frac{a\times b}{c\times d} \rfloor

将

n

除去

\lfloor \frac{n}{2} \rfloor+1

，这样把

n

变成

1

另外一边变成

\lfloor \frac{n}{2} \rfloor+1

这样做直到

n=1

即可，如果出现死循环直接算无解。

代码：

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll read(){
    ll x=0,f=1;char ch=getchar_unlocked();
    while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar_unlocked();}
    while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar_unlocked();}
    return f*x;
}

int T;
ll a,b,c,d,A,B,fl;
vector<pair<int,ll> >ans;

void solve(){
    a=read(),b=read(),c=read(),d=read();
    if(a*b<c*d)return puts("-1"),void();
    A=a*b,B=c*d;ans.clear();fl=1;
    if(a>1)ans.emplace_back(make_pair(1,a));
    while(A/2+1>B){
        ll tmp=A/2+1;
        if(A==tmp)return puts("-1"),void();
        fl=3-fl;if(tmp!=1)ans.emplace_back(make_pair(fl,tmp));
        A=tmp;
    }if(B>1)ans.emplace_back(make_pair(3-fl,B));
    if((fl==1?d:c)!=1)ans.emplace_back(make_pair(fl,fl==1?d:c));
    printf("%ld\n",ans.size());
    for(auto p:ans)printf("%d %lld\n",p.first,p.second);
}

int main(){
    T=read();while(T--)solve();
    return 0;
}

[ARC188A] ABC Symmetry

题目大意：、对于一个由字符 A,B,C 组成的非空字符串

T

，我们称其为一个好的字符串，当且仅当能够通过任意次数、任意顺序执行如下两种操作将其变为一个空字符串：

选择两个相同的字符，并将它们删除（当不存在两个及以上相同字符时，操作不能进行）。
选择一个 A，一个 B，以及一个 C，并将它们从字符串中删除（当 A,B,C 中某一者的个数不多于一时，操作不能进行）。

现在给定长度为

N

由 A,B,C,? 组成的字符串

S

。请计算：有多少种将每个 ? 替换为 A,B,C 的方案，使得得到的新字符串存在至少

K

个好的子串。
答对

998244353

取模。

注意到一个串是否是好串等价于

A\equiv B\equiv C (\bmod 2)

所以只要考虑奇偶性，只有

8

个状态。
由于互为反码的状态是等价的，所以只有

4

个状态。

记

f_{i,a,b,c,d,j}

为前

i

个每个状态分别又

a,b,c,d

种，前

i

个组合在一起状态是

j

，然后就直接分类讨论转移，发现空间会炸。

注意到

a+b+c+d=i+1

，所以可以节省掉

d

这一维。

i

这一维可以滚动数组，这样就是可以过的。

代码：

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll read(){
    ll x=0,f=1;char ch=getchar_unlocked();
    while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar_unlocked();}
    while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar_unlocked();}
    return f*x;
}

const int N = 55;
const ll mod = 998244353;
int n,m;
ll f[2][N][N][N][5],ans=0;
char s[N];

void fadd(ll &x,ll y){x+=y;if(x>=mod)x-=mod;}
ll sb(ll x){return (x-1)*x/2;}

int main(){
    n=read(),m=read();scanf("%s",s+1);
    f[0][1][0][0][0]=1;for(int i=1;i<=n;i++){
        memset(f[i&1],0,sizeof(f[i&1]));
        for(int a=0;a<=i;a++)for(int b=0;a+b<=i;b++)
        for(int c=0;a+b+c<=i;c++)for(int j=0;j<=3;j++)if(f[(i-1)&1][a][b][c][j]){
            for(char ch='A';ch<='C';ch++)if(ch==s[i]||s[i]=='?'){
                // fadd(f[i&1][a+1][b][c][0],f[(i-1)&1][a][b][c][j]);
                // fadd(f[i&1][a][b+1][c][1],f[(i-1)&1][a][b][c][j]);
                // fadd(f[i&1][a][b][c+1][2],f[(i-1)&1][a][b][c][j]);
                // fadd(f[i&1][a][b][c][  3],f[(i-1)&1][a][b][c][j]);
                if(ch=='A'&&j==0)fadd(f[i&1][a][b][c][  3],f[(i-1)&1][a][b][c][j]);
                if(ch=='A'&&j==1)fadd(f[i&1][a][b][c+1][2],f[(i-1)&1][a][b][c][j]);
                if(ch=='A'&&j==2)fadd(f[i&1][a][b+1][c][1],f[(i-1)&1][a][b][c][j]);
                if(ch=='A'&&j==3)fadd(f[i&1][a+1][b][c][0],f[(i-1)&1][a][b][c][j]);
                if(ch=='B'&&j==0)fadd(f[i&1][a][b][c+1][2],f[(i-1)&1][a][b][c][j]);
                if(ch=='B'&&j==1)fadd(f[i&1][a][b][c][  3],f[(i-1)&1][a][b][c][j]);
                if(ch=='B'&&j==2)fadd(f[i&1][a+1][b][c][0],f[(i-1)&1][a][b][c][j]);
                if(ch=='B'&&j==3)fadd(f[i&1][a][b+1][c][1],f[(i-1)&1][a][b][c][j]);
                if(ch=='C'&&j==0)fadd(f[i&1][a][b+1][c][1],f[(i-1)&1][a][b][c][j]);
                if(ch=='C'&&j==1)fadd(f[i&1][a+1][b][c][0],f[(i-1)&1][a][b][c][j]);
                if(ch=='C'&&j==2)fadd(f[i&1][a][b][c][  3],f[(i-1)&1][a][b][c][j]);
                if(ch=='C'&&j==3)fadd(f[i&1][a][b][c+1][2],f[(i-1)&1][a][b][c][j]);
            }
        }
    }
    for(int a=0;a<=n+1;a++)for(int b=0;a+b<=n+1;b++)for(int c=0;a+b+c<=n+1;c++)
    for(int j=0;j<=3;j++)if(f[n&1][a][b][c][j]&&sb(a)+sb(b)+sb(c)+sb(n+1-a-b-c)>=m){
        fadd(ans,f[n&1][a][b][c][j]);
    }printf("%lld",ans);
    return 0;
}

「Wdoi-5」建立与摧毁的结界

题目大意：
境界可以被抽象为由圆括号组成的括号序列。现做出如下定义：

定义 $D_i$ 为嵌套括号序列。其中 $D_0$ 为零阶嵌套括号序列，被定义为单组括号 $\verb!()!$ ；而 $D_k$ 则为 $k$ 阶嵌套括号序列（ $k \geq 1$ ）定义为 $\verb!(!D_{k-1}\verb!)!$ ，即在 $D_{k-1}$ 的外层增添了一层括号。
定义 $F_i$ 为平铺括号序列。其中 $F_0$ 为零阶平铺括号序列，被定义为单组括号 $\verb!()!$ ；而 $F_k$ 则为 $k$ 阶平铺括号序列（ $k \geq 1$ ），定义为 $\verb!()!F_{k-1}$ ，即在 $F_{k-1}$ 的左侧增添了一对括号。

例如，

\verb!((()))!

为

D_2

，

\verb!()()()()!

为

F_{3}

。

现在蓝给出了两个长度为

n

的合法括号序列

A

和

B

。橙可以用以下操作对序列

A

进行变换：

选择任意非负整数 $k$ ，选择括号序列的一个子串满足其为一个 $k$ 阶嵌套括号序列，然后将其变为 $k$ 阶平铺括号序列。
选择任意非负整数 $k$ ，选择括号序列的一个子串满足其为一个 $k$ 阶平铺括号序列，然后将其变为 $k$ 阶嵌套括号序列。

提示说明处有「合法括号序列」与「子串」的定义。
现在需要求出将序列

A

变换为序列

B

所需的最少操作数。可以证明，总存在一种操作方案能将序列

A

变换为序列

B

。

对于一个子区间

[l,r]

使得

a

和

b

中都是合法括号序列的话，这一段对答案的贡献是

\min\{D_{a,l,r}+D_{b,l,r},F_{a,l,r}+F_{b,l,r}\}

D

和

F

是可以用一个类似于区间 DP 的递归做。

代码：

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e6+5;
int n,p[N],q[N];
int stk[N],top=0;
char a[N],b[N];
bool L[N],R[N];
ll ans=0;

ll worka(int l, int r,bool flag){
    if(r-1==l)return 0;
    if(p[r-1]==l+1){
        return worka(l+1,r-1,1)+(!flag);
    }else{
        ll ans=0;
        for(int j=l+1;j!=r;j=p[j]+1)ans+=worka(j,p[j],0);
        return ans+(flag?1:2);
    }
}

ll workb(int l, int r,bool flag){
    if(r-1==l)return 0;
    if(q[r-1]==l+1){
        return workb(l+1,r-1,1)+(!flag);
    }else{
        ll ans=0;
        for(int j=l+1;j!=r;j=q[j]+1)ans+=workb(j,q[j],0);
        return ans+(flag?1:2);
    }
}

ll solve(int l, int r){
    if(r-1==l)return 0;ll ans=0;
    for(int j=l;j!=r+1;j=p[j]+1)L[j]=1;
    for(int j=l;j!=r+1;j=q[j]+1)R[j]=1;
    for(int j=l;j!=r+1;j=p[j]+1){
        L[j]=1;if(R[j]&&p[j]==q[j])ans+=solve(j+1,p[j]-1);
    }
    for(int j=l;j!=r+1;j=p[j]+1)if(p[j]!=q[j]||!R[j])ans+=worka(j,p[j],0);
    for(int j=l;j!=r+1;j=q[j]+1)if(p[j]!=q[j]||!L[j])ans+=workb(j,q[j],0);
    for(int j=l;j!=r+1;j=p[j]+1)L[j]=0;
    for(int j=l;j!=r+1;j=q[j]+1)R[j]=0;
    return ans;
}

int main(){
    scanf("%d%s%s",&n,a+1,b+1);
    for(int i=1;i<=n;i++){
        if(a[i]=='(')stk[++top]=i;
        else{p[i]=stk[top--];p[p[i]]=i;}
    }top=0;
    for(int i=1;i<=n;i++){
        if(b[i]=='(')stk[++top]=i;
        else{q[i]=stk[top--];q[q[i]]=i;}
    }
    printf("%lld",solve(1,n));
    return 0;
}

2024.12.24-2024.12.31 思维训练题解

文章操作

【MX-S3-T2】「FeOI Round 1」Journey

[ARC186B] Typical Permutation Descriptor

【MX-X4-T3】「Jason-1」数对变换

[ARC188A] ABC Symmetry

「Wdoi-5」建立与摧毁的结界

相关推荐

评论

2024.12.24-2024.12.31 思维训练题解