2024.12.24-2024.12.31 思维训练题解

_sin_ · 2024-12-31 11:58:02 · 个人记录

【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：
  • 对于所有满足 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 即可，如果出现死循环直接算无解。

代码：

#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 这一维可以滚动数组，这样就是可以过的。

代码：

#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}\}