A. Beautiful String

解题思路

?可以修改成a,b,c三种字符，我们考虑其修改之后的影响，其只会对周围两个字符产生影响，所以我们只要替换成合法的字符即可。将所有的?替换完之后判断其是否是合格的即可。
参考代码

B. Beautiful Numbers

/**
  *@filename:A
  *@author: pursuit
  *@created: 2021-08-09 17:19
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 1e5 + 10;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int t;
string s;
void solve(){
    char pre = '.';
    bool flag = false;
    int len = s.size();
    for(int i = 0; i < len; ++ i){
        if(s[i] == '?'){
            for(int j = 0; j < 3; ++ j){
                //枚举修改。
                s[i] = 'a' + j;
                if(i == 0 && s[i] != s[i + 1]){
                    break;
                }
                else if(i == len - 1 && s[i] != s[i - 1]){
                    break;
                }
                else if(s[i] != s[i - 1] && s[i] != s[i + 1]){
                    break;
                }
            }
        }
    }
    for(int i = 0; i < len - 1; ++ i){
        if(s[i] == s[i + 1]){
            flag = true;
        }
    }
    if(flag){
        cout << -1 << endl;
    }
    else{
        cout << s << endl;
    }
}
int main(){
    cin >> t;
    while(t -- ){
        cin >> s;
        solve();
    }	
    return 0;
}

解题思路

求 $\forall m \in [1,n], [1,m]$ 的排列是否存在。我们只需要记录 $[1, m]$ 的最左端下标和最右端下标，如果 $其差值 = m$ ，就说明都在里面。简单解释：因为最左端和最右端限定了 $[1, m]$ ?都在这个里面。
参考代码

/**
  *@filename:B
  *@author: pursuit
  *@created: 2021-08-09 17:28
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 2e5 + 10;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int t,n,a[N],pos[N];
void solve(){
    int r = 0,l = n + 1;
    for(int i = 1; i <= n; ++ i){
        r = max(r,pos[i]);
        l = min(l,pos[i]);
        printf("%d", r - l + 1 == i);
    }
    puts("");
}
int main(){	
    scanf("%d", &t);
    while(t -- ){
        scanf("%d", &n);
        for(int i = 1; i <= n; ++ i){
            scanf("%d", &a[i]);
            pos[a[i]] = i;//记录下标。
        }
        solve();
    }
    return 0;
}

C. Beautiful Regional Contest

解题思路

我们知道，奖牌等级的分割是根据解题数量的不同而来的，所以必然是相邻解题数不同处产生金牌。由于金牌数严格小于银牌和铜牌数。即 $s\ and \ g < b$ 。所以我们要让金牌越少越好。而对于银牌，我们也可以让它越少越好,不过必须满足 $g < s$ ?。然后让铜牌数量不断增多即可。最后判断合法性。
参考代码

/**
  *@filename:C
  *@author: pursuit
  *@created: 2021-08-09 17:30
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 4e5 + 10;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int t,n,a[N];
void solve(){
    vector<int> pos;
    for(int i = 2; i <= n; ++ i){
        if(a[i] != a[i - 1]){
            pos.push_back(i);
        }
    }
    if(pos.size() < 3){
        puts("0 0 0");
        return;
    }
    int g,s = n,b = n;
    g = pos[0] - 1;
    int idx = 0;
    for(int i = idx + 1; i < pos.size(); ++ i){
        //根据间隔获取银牌数量。
        int temp = pos[i] - pos[idx];
        if(g < temp){
            s = temp;
            idx = i;
            break;
        }
    }
    for(int i = idx + 1; i < pos.size(); ++ i){
        //根据间隔获取铜牌数量。
        int temp = pos[i] - pos[idx];
        if(g + s + temp > n / 2){
            break;
        }
        else{
            b = temp;
        }
    }
    //cout << g << " " << s << " " << b << endl;
    //判断是否符合题目要求。
    if(g >= s || g >= b || g + s + b > n / 2){
        puts("0 0 0");
    }
    else{
        printf("%d %d %d\n", g, s, b);
    }
}
int main(){
    scanf("%d", &t);
    while(t -- ){
        scanf("%d", &n);
        for(int i = 1; i <= n; ++ i){
            scanf("%d", &a[i]);
        }
        solve();
    }	
    return 0;
}

D. Beautiful Sequence

解题思路

因为 $101210$ ?等价于 $121010$ ????，即如果我们贪心的去使用这些字符，那么如果答案可行这解必然存在。而起始位置的数字会影响字符的使用，所以我们可以枚举起始字符然后去贪心即可，最后判断能不能使用完这些。
参考代码

/**
  *@filename:D
  *@author: pursuit
  *@created: 2021-08-09 18:01
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 1e5 + 10;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int num[4],cnt,temp[4];
void solve(){
    //枚举出发点。
    vector<int> ans(cnt);
    for(int st = 0; st < 4; ++ st){
        if(num[st]){
            bool flag = true;
            int last = st,idx = 1;
            ans[0] = st;
            for(int i = 0; i < 4; ++ i)temp[i] = num[i];
            temp[st] --;
            for(int i = 0; i < cnt - 1; ++ i){
                if(last + 1 < 4 && temp[last + 1]){
                    temp[++last] --;
                    ans[idx++] = last;
                }
                else if(last - 1 >= 0 && temp[last - 1]){
                    temp[--last] --;
                    ans[idx++] = last;
                }
                else{
                    flag = false;
                    break;
                }
            }
            if(flag){
                cout << "YES" << endl;
                for(int i = 0; i < cnt; ++ i){
                    cout << ans[i] << " ";
                }
                cout << endl;
                return;
            }
        }
    }
    cout << "NO" << endl;
}
int main(){
    for(int i = 0; i < 4; ++ i){
        cin >> num[i];
        cnt += num[i];
    }	
    solve();
    return 0;
}

E. Beautiful Mirrors

解题思路

用 $d p [i]$ 来表示询问到第 $i$ ??个镜子的期望天数。

第 $i$ ???个镜子都会有概率 $\frac{p_i}{100}$ ???让其开心。则第 $i ? 1$ ???天若开心， $\frac{p_{i-1}}{100}$ ???，而若不开心，则需要重新回到 $1$ ???，然后再开始 $d p [i]$ ???到达第 $i$ ???个镜子，这样就会消耗 $d p [i] + 1$ 天，则 $dp[i]=(1+dp[i])\times (1-\frac{p_{i-1}}{100})$ ???。故方程可得： $+\frac{p_{i-1}}{100}+(1+dp[i])\times (1-\frac{p_{i-1}}{100})$ ???，化简成 $d p [i] = f (d p [i ? 1])$ ???的递推关系得：

$=\frac{100\times(dp[i-1]+1)}{p_i}$ ，则?可递推得到，注意由于涉及取模，故需要使用费马小定理将除法取模转化为乘法。
参考代码

/**
  *@filename:E
  *@author: pursuit
  *@created: 2021-08-09 19:01
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 2e5 + 10;
const int P = 998244353;
const int INF = 0x3f3f3f3f;

int n,dp[N],p[N];
int qsm(int n,int q = P - 2){
    int ans = 1;
    while(q){
        if(q & 1){
            ans = 1LL * ans * n % P;
        }
        n = 1LL * n * n % P;
        q >>= 1;
    }
    return ans;
}
void solve(){
    for(int i = 1; i <= n; ++ i){
        dp[i] = 1LL * 100 * (dp[i - 1] + 1) % P * qsm(p[i]) % P;
    }
    printf("%d\n", dp[n]);
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i){
        scanf("%d", &p[i]);
    }
    solve();
    return 0;
}

F. Beautiful Bracket Sequence (easy version)

题意

给你一个长度为 $n$ 的字符串 $s$ ，其中由(,),?三种字符组成，?可以替换成(,)。问将这些?全部替换之后的方案的最大深度之和。其中深度含义为： $()$ 这样就有一层深度，贡献为 $1$ ， $(())$ 这样就有两层，贡献为 $2$ ，但 $() ()$ 这样也只有一层，贡献也为 $1$ ?。?
解题思路

由于直接考虑整个问题特别复杂，不利于处理，而对于较小的子问题我们是可知的，即 $s [i], s [i + 1]$ ??，所以我们可以将问题分解得到局部问题的最优解再将其整合即可，这正是区间DP的思想。即我们可以用 $d p [i] [j]$ ??表示字符串 $[i, j]$ ??的最大深度：

我们只需考虑左右两端，我们发现如果 $s [i]! =$ (，说明其对区间 $[i, j]$ 没有贡献，无法配对，那么这个可以直接忽略，状态转移为 $d p [i] [j] = d p [i + 1] [j]$ ，如果 $s [j]! =$ )，说明其对区间 $[i, j]$ 没有贡献，无法配对，状态转移为 $d p [i] [j] + = d p [i] [j ? 1]$ ，如果 $s [i]! =$ ( $\ and\ s[j]!=$ ),即说明我们重复计算了一遍覆盖的区间 $d p [i + 1] [j ? 1]$ （这里注意理解），所以 $d p [i] [j] ? = d p [i + 1] [j ? 1]$ ，对于 $s [i]! =$ ) $\ and\ s[j]!=$ ??????(,则说明我们可以组成贡献，直接由 $d p [i + 1] [j ? 1]$ ?转移，而这个点同时需要考虑到内部问号的替换，因为外围的两个决定了其可以替换配对，即 $dp[i][j]+=dp[i+1][j-1]+2^k$ ， $k$ 为区间 $[i + 1] [j ? 1]$ 的数量。

考虑完所有情况后我们枚举区间合并问题的最优解即可。最后的答案即是 $d p [1] [n]$ 。
参考代码

/**
  *@filename:F
  *@author: pursuit
  *@created: 2021-08-09 19:30
**/
#include <bits/stdc++.h>
#define debug(a) cout << "debug : " << (#a)<< " = " << a << endl

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
const int N = 2e3 + 10;
const int P = 998244353;
const int INF = 0x3f3f3f3f;

int n,dp[N][N],f[N];
char s[N];
int qsm(int n,int q = P - 2){
    int ans = 1;
    while(q){
        if(q & 1){
            ans = 1LL * ans * n % P;
        }
        n = 1LL * n * n % P;
        q >>= 1;
    }
    return ans;
}
void solve(){
    n = strlen(s);
    //初始化f数组。
    for(int i = 0; i < n; ++ i){
        f[i + 1] = f[i] + (s[i] == '?');
    }
    //枚举区间长度。
    for(int len = 2; len <= n; ++ len){
        //枚举区间左端点。
        for(int i = 0; i + len - 1 < n; ++ i){
            int j = i + len - 1;
            if(s[i] != '('){
                dp[i][j] = (dp[i][j] + dp[i + 1][j]) % P;
            }
            if(s[j] != ')'){
                dp[i][j] = (dp[i][j] + dp[i][j - 1]) % P;
            }
            if(s[i] != '(' && s[j] != ')'){
                dp[i][j] = (1LL * dp[i][j] - dp[i + 1][j - 1] + P) % P;
            }
            if(s[i] != ')' && s[j] != '('){
                dp[i][j] = (1LL * dp[i][j] + dp[i + 1][j - 1] + qsm(2,f[j] - f[i + 1])) % P;
            }
            //cout << i << " " << j << " " << dp[i][j] << endl;
        }
    }
    printf("%d\n", dp[0][n - 1]);
}
int main(){
    scanf("%s", s);	
    solve();
    return 0;
}