基础算法

WoodReal12 · 2023-12-27 20:31:23 · 算法·理论

前言

本文为chenweizhen所作。未经许可禁止转载。

若有疑问或描述不清之处，欢迎在评论区提出。

以下是目录（点击可跳转）

\large\color{black}\text{1. 枚举与模拟}

• \small\color{black}\text{1.1 卡片}

• \small\color{black}\text{1.2 回文日期}

• \small\color{black}\text{1.3 赢球票}

• \small\color{black}\text{1.4 既约分数}

• \small\color{black}\text{1.5 数的分解}

\large\color{black}\text{2. 搜索与查找}

• \small\color{black}\text{2.1 九宫幻方}

• \small\color{black}\text{2.2 穿越雷区}

• \small\color{black}\text{2.3 小朋友崇拜圈}

• \small\color{black}\text{2.4 迷宫与陷阱}

• \small\color{black}\text{2.5 扫地机器人}

• \small\color{black}\text{2.6 123}

\large\color{black}\text{3. 思维与贪心}

• \small\color{black}\text{3.1 重复字符串}

• \small\color{black}\text{3.2 翻硬币}

• \small\color{black}\text{3.3 乘积最大}

• \small\color{black}\text{3.4 巧克力}

• \small\color{black}\text{3.5 答疑}

• \small\color{black}\text{3.6 皮亚诺曲线}

\large\color{black}\text{4. 简单数论}

• \small\color{black}\text{4.1 阶乘约数}

• \small\color{black}\text{4.2 求值}

• \small\color{black}\text{4.3 循环小数}

• \small\color{black}\text{4.4 等差数列}

• \small\color{black}\text{4.5 最大比例}

\large\color{black}\text{5. 字符串算法}

• \small\color{black}\text{5.1 单词分析}

• \small\color{black}\text{5.2 人物相关性分析}

• \small\color{black}\text{5.3 子串分值和}

• \small\color{black}\text{5.4 字串排序}

\large\color{black}\text{6. 动态规划}

• \small\color{black}\text{6.1 数字三角形}

• \small\color{black}\text{6.2 砝码称重}

• \small\color{black}\text{6.3 括号序列}

• \small\color{black}\text{6.4 异或三角}

• \small\color{black}\text{6.5 组合数问题}

\large\color{black}\text{7. 数据结构}

• \small\color{black}\text{7.1 修改数组}

• \small\color{black}\text{7.2 翻转括号序列}

• \small\color{black}\text{7.3 双向排序}

• \small\color{black}\text{7.4 冰山}

1.枚举与模拟

1.1卡片

1.1.1

#include<bits/stdc++.h>
using namespace std;
int cnt[10];
bool check(int x){  // x 表示当前枚举的数
    while(x){
        int b = x % 10; // 获取 10 进制下的每个数位
        if(b == 1) {
            if(cnt[1] == 0) return false;
            cnt[1] -- ;
        }
        x /= 10; // 将十位变为个位
    }
    return true;
}
signed main(){
    for(int i = 0 ; i <= 9 ; i ++) cnt[i] = 2021;
    for(int i = 1 ; ; i ++){
        if(!check(i)) return cout << i - 1 << '\n' , 0;
    }
    return 0;
}

1.2回文日期

1.2.1

#include<bits/stdc++.h>
using namespace std;
int month[13] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int date, ans1, ans2;
// 判断日期是否回文
bool check1(int date){
    string s = to_string(date);
    if(s[0] == s[7] && s[1] == s[6] && s[2] == s[5] && s[3] == s[4]) return true;
    return false;
}
// 判断日期是否满足 ABABBABA 型回文
bool check2(int date)
{
    string s = to_string(date);
    if(s[0] == s[2] && s[0] == s[5] && s[0] == s[7] && s[1] == s[3] && s[1] == s[4] && s[1] == s[6]) return true;
    return false;
}
signed main()
{
    cin >> date;
    int y = date / 10000, m = date / 100 % 100, d = date % 100;
    for(int i = y ; ; i ++) {
        if(i % 400 == 0 || (i % 100 != 0 && i % 4 == 0)) month[2] = 29;
        else month[2] = 28;
        int j = (i == y) ? m : 1;
        for(; j <= 12 ; j ++) {
            int k = (i == y && j == m) ? d + 1 : 1;
            for(; k <= month[j] ; k ++) {
                int date = i * 10000 + j * 100 + k;
                if(check1(date) && ans1 == 0) ans1 = date;
                if(check2(date)) return cout << ans1 << '\n' << date << '\n', 0; // 当找到了 ABABBABA 型回文日期时，结束程序。
            }
        }
    }
    return 0;
}

1.2.2

#include<bits/stdc++.h>
using namespace std;
// month[1 ~ 12] 分别记录 1 ~ 12 月每月的天数
int date , month[13] = {-1 , 31 , 28 , 31 , 30 , 31 , 30 , 31 , 31 , 30 , 31 , 30 , 31}; 
// 判断日期是否合法
string check(int date){
    string s = to_string(date) , t = to_string(date); // 将整型转换为字符串
    reverse(t.begin() , t.end()); // 翻转
    s += t; // 将 s 翻转后再与 s 拼接，拼接后的字符串一定会是个回文串
    int y = stoi(s.substr(0 , 4)) , m = stoi(s.substr(4 , 2)) , d = stoi(s.substr(6 , 2));
    if(y % 400 == 0 || (y % 4 == 0 && y % 100 != 0)) month[2] = 29;
    else month[2] = 28;
    if(m < 1 || m > 12 || d < 1 || d > month[m]) return "-1";
    return s;
}
// 判断日期是否是 ABABBABA 型回文
string check2(int date){
    string s = to_string(date) , t = to_string(date);
    reverse(t.begin() , t.end()); // 翻转
    s += t;
    if(s[0] == s[2] && s[0] == s[5] && s[0] == s[7] && s[1] == s[3] && s[1] == s[4] && s[1] == s[6]) return s;
    return "-1";
}
signed main()
{
    cin >> date;
    string ans1 = "";
    for(int i = date / 10000 ; ; i ++){
        // 注意：date（读入的日期）不能作为答案
        if(check(i) == "-1" || check(i) == to_string(date)) continue ;
        if(ans1 == "") ans1 = check(i);
        if(check2(i) != "-1") return cout << ans1 << '\n' << check2(i) << '\n' , 0;
    }
    return 0;
}

1.3赢球票

1.3.1

#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int n, a[N], flag[N];
signed main(){
    cin >> n;
    for(int i = 1 ; i <= n ; i ++) cin >> a[i];
    int ans = 0; // ans 表示答案。
    for(int i = 1 ; i <= n ; i ++){ // i 表示枚举的起点
        // 将所有卡片的 flag 初始化为 0
        for(int j = 1 ; j <= n ; j ++) flag[j] = 0; // flag[j] = 1 表示卡片被取走，反之没被取走
        int num = 1 , pos = i , sum = 0, cnt = 0; // num 表示数的数的值，pos 表示当前位置，sum 表示以 i 为起点数数所能取走的卡片的和，cnt 表示拿走的卡片的数量

        // 开始模拟
        while(1){
            // 判断游戏是否结束
            if(cnt == n || num > n) break; // 如果取走了所有卡片，或者数的数大于 n（不可能再取走卡片了）则游戏结束
            // 判断当前位置的卡片是否被取走了
            if(flag[pos] == 1) { // 如果该卡片已被取走，则移动到下一个位置
                // 移动到下一个位置：如果当前位置 pos = n，则下一个位置为 1，否则下一个位置为 pos + 1
                if(pos == n) pos = 1;
                else pos ++;
                continue ;
            }
            // 数的数和当前位置卡片的值相同时取走该卡片（a[pos] 表示第pos张卡片的值）
            if(num == a[pos]){
                sum += a[pos]; // 取走卡片的和 + a[pos]
                cnt ++;        // 取走卡片的个数 + 1
                num = 1;       // 取走卡片后要重新数数
                flag[pos] = 1; // 取走卡片后该卡片对应的 flag 置为 1
                // 移动到下一个位置：如果当前位置 pos = n，则下一个位置为 1，否则下一个位置为 pos + 1
                if(pos == n) pos = 1;
                else pos ++;
            } else {
                // 数的数和当前位置卡片的值不相同时
                num ++ ; // 数的数的值 + 1
                // 移动到下一个位置：如果当前位置 pos = n，则下一个位置为 1，否则下一个位置为 pos + 1
                if(pos == n) pos = 1;
                else pos ++;
            }
        }
        // 模拟结束，判断该模拟结果是否可以作为答案
        if(sum > ans) ans = sum;
    }
    cout << ans << '\n';
    return 0;
}

1.4既约分数

1.4.1

#include<bits/stdc++.h>
using namespace std;
signed main()
{
    int ans = 0;
    for(int i = 1 ; i <= 2020 ; i ++){
        for(int j = 1 ; j <= 2020 ; j ++){
            if(__gcd(i , j) == 1) ans ++ ;
        }
    }
    cout << ans << '\n';
    return 0;
}

1.4.2

#include<bits/stdc++.h>
using namespace std;
int solve(int n){
    int phi = n;
    for(int i = 2 ; i * i <= n ; i ++){
        if(n % i == 0) { // i 是 n 的质因子
            phi = phi - phi / i; // 将其丢入欧拉函数的通项公式中计算
            while(n % i == 0) n /= i;  // 把 n 重复的质因子去掉
        }
    }
    if(n > 1) phi = phi - phi / n;   // n 没有被除尽，是素数，将其丢入欧拉函数的通项公式中计算
    return phi;
}
signed main()
{
    int ans = 0;
    for(int i = 1 ; i <= 2020 ; i ++) ans += solve(i);
    cout << ans * 2 - 1 << '\n';
    return 0;
}

1.4.3

#include<bits/stdc++.h>
using namespace std;
int n , phi[2021] , prime[2021];
signed main(){
    // 欧拉筛
    phi[1] = 1;
    for(int i = 2 ; i <= 2020 ; i ++){
        if(!prime[i]) prime[++ n] = i, phi[i] = i - 1;
        for(int j = 1 ; j <= n && i * prime[j] <= 2020 ; j ++){
            prime[prime[j] * i] = 1;
            if(i % prime[j] == 0){
                phi[i * prime[j]] = phi[i] * prime[j];
                break ;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
    int cnt = 0;
    for(int i = 1 ; i <= 2020 ; i ++) cnt += phi[i];
    cout << 2 * cnt - 1 << '\n';
    return 0;
}

1.5数的分解

1.5.1

#include<bits/stdc++.h>
using namespace std;
// 如果 x 包含 2 或 4 返回 false，否则返回 true
bool check(int x){
    while(x){
        if(x % 10 == 2 || x % 10 == 4) return false;
        x /= 10;
    }
    return true;
}
bool flag[2020];
signed main(){
    int ans = 0;
    for(int i = 1 ; i <= 2019 ; i ++) if(check(i)) flag[i] = 1; // 在枚举前判断一个数是否包含 2 和 4，避免在枚举过程中判断。
    for(int i = 1 ; i <= 2019 ; i ++)
        for(int j = i + 1 ; j < 2019 - i - j ; j ++) // i < j < 2019 - i - j
            if(flag[i] && flag[j] && flag[2019 - i - j]) // 通过 flag 判断，复杂度 O(1)
                ans ++;
    cout << ans << '\n';
    return 0;
}

1.5.2

#include<bits/stdc++.h>
using namespace std;
int dp[5][2][2][2][2][2][2][2020] , num[5] , p[5];
int dfs(int len , bool limit1 , bool limit2 , bool limit3 , bool ok1 , bool ok2 , bool ok3, int sum){
    if(!len) return sum == 2019 && ok1 && ok2 && ok3 ;
    if(~dp[len][limit1][limit2][limit3][ok1][ok2][ok3][sum]) return dp[len][limit1][limit2][limit3][ok1][ok2][ok3][sum];
    int res = 0;
    // num[4] = 2, num[3] = 0 , num[2] = 1 , num[1] = 9
    int up1 = limit1 ? num[len] : 9; // i 当前数位是否达到上限
    int up2 = limit2 ? num[len] : 9; // j 当前数位是否达到上限
    int up3 = limit3 ? num[len] : 9; // k 当前数位是否达到上限
    for(int i = 0 ; i <= up1 ; i ++){
        if(i == 2 || i == 4) continue ;  // 如果 i当前数位的值为 2 或 4 则跳过这种情况
        int d1 = ok1 ? 0 : i;             // 如果 j 还没有大于 i，为保证 j > i，当前数位上的数字需要从 j 开始枚举。
        for(int j = d1 ; j <= up2 ; j ++){
            if(j == 2 || j == 4) continue ; // 如果 j 当前数位的值为 2 或 4 则跳过这种情况
            int d2 = ok2 ? 0 : j;            // 如果 j 还没有大于 k，为保证 k > j，当前数位上的数字需要从 j 开始枚举。
            for(int k = d2 ; k <= up3 ; k ++){
                if(k == 2 || k == 4) continue ; // 如果 k 当前数位的值为 2 或 4 则跳过这种情况
                // 如果 i、j、k 的和超过 2019 则跳过这种情况
                if(sum + i * p[len - 1] + j * p[len - 1] + k * p[len - 1] > 2019) break;
                res += dfs(len - 1 , limit1 && i == up1 , limit2 && j == up2 , limit3 && k == up3 ,
                           // 只要存在一个数位，在该数位下 j 的值大于 i 的值，ok1 就等于 1
                           // 只要存在一个数位，在该数位下 k 的值大于 j 的值，ok2 就等于 1
                           // 只要存在一个数位，在该数位下 i 的值大于 0 的值，ok3 就等于 1
                           ok1 || i < j , ok2 || j < k , ok3 || i,
                           sum + i * p[len - 1] + j * p[len - 1] + k * p[len - 1]);
            }
        }
    }
    return dp[len][limit1][limit2][limit3][ok1][ok2][ok3][sum] = res;
}
int solve(int x){
    memset(dp , -1 , sizeof(dp));
    int len = 0;
    while(x){  // 取出 x（2019）的每一位数字存储在 num 中，进行数位 dp
        num[++ len] = x % 10;
        x /= 10;
    }
    // 传入的 x = 2019，则 num[4] = 2, num[3] = 0 , num[2] = 1 , num[1] = 9
    return dfs(len , 1 , 1 , 1 , 0 , 0 , 0 , 0);
}
signed main(){
    // p[i] 表示 10 的 i 次方，即 p[1] = 10^1 = 10 , p[2] = 10^2 = 100,...]
    p[0] = 1;
    for(int i = 1 ; i <= 4 ; i ++) p[i] = p[i - 1] * 10;
    cout << solve(2019) << '\n';
    return 0;
}

2.搜索与查找

2.1九宫幻方

2.1.1

#include<bits/stdc++.h>
using namespace std;
int p[10] , a[5][5] , b[5][5] , ans[5][5];
signed main()
{
    for(int i = 1 ; i <= 3 ; i ++) for(int j = 1 ; j <= 3 ; j ++) cin >> a[i][j]; //读入样例矩阵
    for(int i = 1 ; i <= 9 ; i ++) p[i] = i;
    int cnt = 0; // 统计九宫幻方的个数
    do{
       // 将排列转换为矩阵
        b[1][1] = p[1] , b[1][2] = p[2] , b[1][3] = p[3];
        b[2][1] = p[4] , b[2][2] = p[5] , b[2][3] = p[6];
        b[3][1] = p[7] , b[3][2] = p[8] , b[3][3] = p[9];
        // 判断排列矩阵和样例矩阵是否匹配
        bool flag = true; // flag = true 表示匹配， flag = false 表示不匹配
        for(int i = 1 ; i <= 3 ; i ++){
            for(int j = 1 ; j <= 3 ; j ++){
                if(!a[i][j]) continue ; // 只看非零部分
                if(a[i][j] != b[i][j]) flag = false;
            }
        }
        if(!flag) continue ; // 如果不匹配，就跳过
        // 判断排列矩阵是否是九宫幻方
        bool ok = true;  // ok = true 表示排列矩阵是九宫幻方，ok = false 表示排列不是九宫幻方
        int sum = b[1][1] + b[2][2] + b[3][3];  // 取一条对角线的值
        if(sum != b[1][3] + b[2][2] + b[3][1]) continue ; // 判断另一条对角线的和是否等于 sum，不等于就跳过
        for(int i = 1 ; i <= 3 ; i ++){
            int tmp1 = 0, tmp2 = 0;  // tmp1 表示行的和，tmp2 表示列的和。
            for(int j = 1 ; j <= 3 ; j ++) tmp1 += b[i][j] , tmp2 += b[j][i];
            if(tmp1 != sum || tmp2 != sum) ok = false; // 如果行的和或列的和不等于 sum，则排列矩阵不是九宫幻方
        }
        if(!ok) continue ; // 如果不是九宫幻方，就跳过
        cnt ++ ;        // 九宫幻方的个数+1
        if(cnt >= 2) return cout << "Too Many\n" , 0; // 九宫幻方的个数 >=2 直接输出 Too Many、结束程序
        for(int i = 1 ; i <= 3 ; i ++) for(int j = 1 ; j <= 3 ; j ++) ans[i][j] = b[i][j]; // 用 ans 记录下该九宫幻方
    }while(next_permutation(p + 1 , p + 1 + 9));
    // 程序没有结束则说明 cnt <= 1。按照题目的意思九宫幻方至少有一个，所以直接输出 ans 记录的矩阵即可。
    for(int i = 1 ; i <= 3 ; i ++) for(int j = 1 ; j <= 3 ; j ++) cout << ans[i][j] << " \n"[j == 3];
    return 0;
}

2.1.2

#include<bits/stdc++.h>
using namespace std;
int vis[10], a[5][5], ans[5][5];
int n, cnt;
pair<int, int>p[10];
bool check(){
    int sum = a[1][1] + a[2][2] + a[3][3]; // 取一条对角线的值
    if(sum != a[1][3] + a[2][2] + a[3][1]) return false; // 判断另一条对角线的和是否等于 sum，不等于则不是九宫幻方
    for(int i = 1 ; i <= 3 ; i ++) {
        int tmp1 = 0, tmp2 = 0;  // tmp1 表示行的和，tmp2 表示列的和。
        for(int j = 1 ; j <= 3 ; j ++) tmp1 += a[i][j], tmp2 += a[j][i];
        if(tmp1 != sum || tmp2 != sum) return false;  // 如果行的和或列的和不等于 sum，则排列矩阵不是九宫幻方
    }
    return true; // 是九宫幻方
}
void dfs(int now){
    // now > n 表示所有被存储的位置都已经被修改了
    if(now > n) {
        if(check()) { // 判断修改后的矩阵是否是九宫幻方
            cnt ++ ;  // 九宫幻方的个数 + 1
            // 用 ans 记录下该九宫幻方
            for(int i = 1 ; i <= 3 ; i ++)
                for(int j = 1 ; j <= 3 ; j ++)
                    ans[i][j] = a[i][j];
        }
        return ;
    }
    int x = p[now].first , y = p[now].second;
    for(int k = 1 ; k <= 9 ; k ++) {
        if(vis[k]) continue ; // 如果 k 这个数已经存在了，就不能被重复使用
        a[x][y] = k;  // 尝试将该位置的值设置为 k
        vis[k] = 1;   // k 被使用了，为其打上标记
        dfs(now + 1); // 继续搜索
        // 回溯
        a[x][y] = 0;
        vis[k] = 0;
    }
}
signed main()
{
    for(int i = 1 ; i <= 3 ; i ++)
        for(int j = 1 ; j <= 3 ; j ++) {
            cin >> a[i][j];  // 读入样例矩阵
            if(!a[i][j]) p[++ n] = make_pair(i, j);  // 如果值为0，就用 pair 存储下来
            vis[a[i][j]] = 1; // 将矩阵中已出现过的数打上标记
        }
    dfs(1); // 开始搜索
    if(cnt == 1) { // 九宫幻方的个数为 1，直接输出 ans 记录的矩阵
        for(int i = 1 ; i <= 3 ; i ++)
            for(int j = 1 ; j <= 3 ; j ++)
                cout << ans[i][j] <<  " \n"[j == 3];
    } else cout << "Too Many\n"; // 九宫幻方的个数为 2 则输出 Too Many
    return 0;
}

2.2穿越雷区

2.2.1

#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int nex[4][2] = {{1, 0} , {-1, 0} , {0, 1} , {0, -1}}; // 表示移动时的四个方向方向
int n, a[N][N]; // a[i][j]表示点的正负信息。a[i][j]=1表示点(i,j)的能量值为正，a[i][j]=0表示点(i,j)的能量值为负,a[i][j] = -1表示点(i,j)为B
int vis[N][N];  // vis[i][j]表示在搜索的过程中点是否走过。vis[i][j]=1表示点(i,j)已经走过，vis[i][j]=0表示点(i,j)还没走过。
pair<int, int>st, ed; // st记录点A的位置，ed存储点B的位置
struct node{
    int x, y, cnt;
};
bool check(int x,  int y){
    if(x < 1 || x > n || y < 1 || y > n || vis[x][y]) return false;
    return true;
}
int bfs(int x, int y){
    pair<int, int>u = make_pair(x, y);
    queue<node>que;
    que.push(node{x, y, 0});
    vis[x][y] = 1;
    while(!que.empty()){
        node u = que.front();
        if(u.x == ed.first && u.y == ed.second) return u.cnt;
        que.pop();
        int x = u.x , y = u.y;
        for(int i = 0; i <= 3; i ++){
            // (tx , ty) 为 (x - 1 , y) 或 (x + 1 , y) 或 (x , y - 1) 或 (x , y + 1) 
            int tx = x + nex[i][0];
            int ty = y + nex[i][1];
            // a[tx][ty] 的能量特征不能等于 a[x][y] 的能量特征 
            if(!check(tx , ty) || a[tx][ty] == a[x][y]) continue ;
            vis[tx][ty] = 1;
            que.push(node{tx, ty, u.cnt + 1});
        }
    }
    return -1;
}
signed main(){
    cin >> n;
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j ++){
            char x;
            cin >> x;
            if(x == 'A') st.first = i, st.second = j, a[i][j] = -1;
            else if(x == 'B') ed.first = i, ed.second = j , a[i][j] = -1;
            else if(x == '+') a[i][j] = 1;
            else a[i][j] = 0;
        }
    }
    cout << bfs(st.first, st.second) << '\n';
    return 0;
}

2.2.2

#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int n , ans; // ans 记录答案
int a[N][N];  // a[i][j]表示点的正负信息。a[i][j]=1表示点(i,j)的能量值为正，a[i][j]=0表示点(i,j)的能量值为负,a[i][j] = -1表示点(i,j)为B
int  vis[N][N]; // vis记录表示到达 (x,y) 的移动次数
pair<int , int>st , ed; // st记录点A的位置、ed存储点B的位置
void dfs(int x , int y , int cnt) {
    // x,y 表示当前点的位置，cnt 表示到达该点的移动次数
    if(cnt > ans) return ; // 剪枝：如果移动次数大于 ans，那么该走法一定不是最优的，就没必要走下去了 
    if(cnt > vis[x][y]) return ; // 剪枝：如果到达(x,y)的移动次数大于 vis[x][y]，说明从起点走到(x,y)有更优秀的走法，那么该走法到达终点的移动次数一定不是最优的。
    if(x < 1 || x > n || y < 1 || y > n) return ; // 保证移动的正确性
    if(x == ed.first && y == ed.second) {
        ans = cnt; // 到达终点，记录（更新）答案
        return ;
    }
    // 记录（更新）走到 (x,y) 的移动次数
    vis[x][y] = cnt;
    // a[tx][ty] 的能量特征不能等于 a[x][y] 的能量特征 
    int tx = x - 1 , ty = y;
    if(a[tx][ty] != a[x][y]) dfs(tx , ty , cnt + 1); 
    tx = x + 1 , ty = y;
    if(a[tx][ty] != a[x][y]) dfs(tx , ty , cnt + 1);
    tx = x , ty = y - 1;
    if(a[tx][ty] != a[x][y]) dfs(tx , ty , cnt + 1);
    tx = x , ty = y + 1;
    if(a[tx][ty] != a[x][y]) dfs(tx , ty , cnt + 1);
}
signed main(){
    cin >> n;
    ans = 0x3f3f3f3f;
    for(int i = 1 ; i <= n ; i ++) for(int j = 1 ; j <= n ; j ++) vis[i][j] = 0x3f3f3f3f;
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j ++){
            char x;
            cin >> x;
            if(x == 'A') st.first = i, st.second = j, a[i][j] = -1;
            else if(x == 'B') ed.first = i, ed.second = j , a[i][j] = -1;
            else if(x == '+') a[i][j] = 1;
            else a[i][j] = 0;
        }
    }
    dfs(st.first , st.second , 0);
    cout << ans << '\n';
    return 0;
}

2.3小朋友崇拜圈

2.3.1

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n , ans , nex[N] , number[N] , vis[N];
// nex[x] 表示 x 的崇拜对象
// number[x] 表示边 x->nex[x] 的编号
void dfs(int x , int cnt , int id){ // x表示当前走到的节点，cnt表示当前边的编号，id表示当前路线的编号
    if(vis[x] && vis[x] != id) return ; // 如果 x 已经被其它路线标记过了，则返回
    if(vis[x]) { // 说明找到了环边
        ans = max(ans , (cnt-1) - number[x] + 1); // 更新答案：cnt-1表示上一条边的编号，即红色箭头的编号
        return ; // 结束递归
    }
    vis[x] = id; // 为节点 x 打上标记
    number[x] = cnt; // 为边 x->nex[i] 添加编号
    dfs(nex[x] , cnt + 1 , id); // 继续搜索
}
signed main(){
    cin >> n;
    for(int i = 1 ; i <= n ; i ++) cin >> nex[i];
    for(int i = 1 ; i <= n ; i ++) dfs(i , 1 , i); 
    cout << ans << '\n';
    return 0;
}

2.4迷宫与陷阱

2.4.1

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
struct node{
  int x , y;  // 表示移动到的位置
  int cnt;      // 表示移动的次数
  int status; // 表示接下来的 status 步都将保持无敌状态。status > 0 则处于无敌状态，status = 0 则处于普通状态
};
int n , k;
int nex[4][2] = {{1 , 0} , {-1 , 0} , {0 , 1} , {0 , -1}}; // 表示移动时的四个方向方向
int a[N][N] , vis[N][N] , s[N][N];  // a[][] 表示格子的类型，vis[][] 标记格子是否被访问过，s[][] 记录经过格子时最大的可保持无敌状态的步数
bool check(int x , int y , int status){
    // 不能离开迷宫、不能经过墙壁
    if(x < 1 || x > n || y < 1 || y > n || a[x][y] == 3) return false;
    // 如果不是无敌状态，不能经过陷阱
    if(a[x][y] == 2 && !status) return false;
    return true;
}
int bfs(){
    queue<node>que;
    que.push(node{1 , 1 , 0 , 0}); // 从 (1,1) 出发
    vis[1][1] = 1;    // 标记 (1,1) 被访问过
    while(!que.empty()){
        node u = que.front();
        que.pop();
        if(u.x == n && u.y == n) return u.cnt; // 到达 (n,n) 点则停止搜索
        for(int i = 0 ; i <= 3 ; i ++){
            int tx = u.x + nex[i][0];
            int ty = u.y + nex[i][1];
            if(!check(tx , ty , u.status)) continue ;
            int status = max(0 , u.status - 1); 
            if(a[tx][ty] == 1){ // 陷阱
                vis[tx][ty] = 1;
                a[tx][ty] = 0; // 陷阱走过就变为普通的格子
                que.push(node{tx , ty , u.cnt + 1 , k});
            }
            else { //普通格子
                if(!vis[tx][ty]) { // 如果没有走过，那么有必要走
                    vis[tx][ty] = 1;
                    que.push(node{tx , ty , u.cnt + 1 , status});
                    continue ;
                }
                if(status <= s[tx][ty]) continue ; // 可保持的无敌状态劣于上一次，没有必要再走一次
                // 可保持的无敌状态优于上一次，有必要再走一次
                s[tx][ty] = status;
                que.push(node{tx , ty , u.cnt + 1 , max(0 , status)});
            }
        }
    }
    return -1;
}
signed main(){
    cin >> n >> k;
    for(int i = 1 ; i <= n ; i ++){
        for(int j = 1 ; j <= n ; j ++){
            char x;
            cin >> x;
            if(x == '%') a[i][j] = 1;
            else if(x == 'X') a[i][j] = 2;
            else if(x == '#') a[i][j] = 3;
        }
    }
    cout << bfs() << '\n';
    return 0;
}

2.5扫地机器人

2.5.1

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n , k , a[N]; // a[i] 表示第 i 个机器人的位置
bool check(int mid){
    int pos = 0; // pos 用来表示 1~pos 区域已被清扫，pos+1~n 区域未被清扫
    for(int i = 1 ; i <= k ; i ++){ // 遍历 k 个机器人
        int t = mid;
        if(pos < a[i]) t -= (a[i] - pos - 1) * 2; // 往左清扫，需要花费的时间为 2 * (a[i] - pos - 1)
        if(t < 0) return false;  // 如果时间小于 0，说明无法清扫完左边的区域、时间不够
        pos = a[i] + t / 2;    // 如果还剩有时间，继续向右清扫
    }
    if(pos < n) return false;  // 如果没有清扫完所有的区域，则说明时间不够
    return true;
}
signed main(){
    cin >> n >> k;
    for(int i = 1 ; i <= k ; i ++) cin >> a[i];
    sort(a + 1 , a + 1 + k); // 位置排序
    int l = 0 , r = 2 * n , ans = 2 * n;
    while(l <= r){
        int mid = l + r >> 1;
        if(check(mid)) ans = mid , r = mid - 1;
        else l = mid + 1;
    }
    cout << ans << '\n';
    return 0;
}

2.6123

2.6.1 20%做法

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N] , sum[N]; // a[] 存储数列的每一项， sum[] 为 a[] 的前缀和数组
signed main(){
  int T = 1;
  cin >> T;
  int up = 1 , x = 1; // x 表示数列第i项的值（从第1项开始），up 表示第i项所在组的编号（从第1组开始）
  for(int i = 1 ; i <= 1000000 ; i ++){ 
    a[i] = x;
    x ++ ;
    if(x > up) up ++ , x = 1; // 模拟数列变化的规律，当 x > up 时，进入下一组。
  }
  for(int i = 1 ; i <= 1000000 ; i ++) sum[i] = sum[i - 1] + a[i];
  while(T --){
    int l , r;
    cin >> l >> r;
    cout << sum[r] - sum[l - 1] << '\n';
  }
  return 0;
}

2.6.240%做法

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int a[N] , sum[N]; // a[] 存储数列的每一项， sum[] 为 a[] 的前缀和数组
signed main(){
  int T = 1;
  cin >> T;
  int up = 1 , x = 1; // x 表示数列第i项的值（从第1项开始），up 表示第i项所在组的编号（从第1组开始）
  for(int i = 1 ; i <= 1000000 ; i ++){ 
    a[i] = x;
    x ++ ;
    if(x > up) up ++ , x = 1; // 模拟数列变化的规律，当 x > up 时，进入下一组。
  }
  for(int i = 1 ; i <= 1000000 ; i ++) sum[i] = sum[i - 1] + a[i];
  while(T --){
    int l , r;
    cin >> l >> r;
    cout << sum[r] - sum[l - 1] << '\n';
  }
  return 0;
}

2.6.3满分做法

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6 + 10;
int pre[N];
int getPre(int x){  // 求 pre[x] 公式
    return x * (x + 1) * (x + 2) / 6;
}
int calc(int x){
    int l = 0 , r = 2e6 , i = 0; // 二分求 x 在第几组
    while(l <= r){
        int mid = l + r >> 1;
        if((mid + 1) * mid / 2 > x) r = mid - 1 , i = mid;
        else l = mid + 1;
    }
    int j = x - (i - 1) * (i - 1 + 1) / 2; // 求 x 在第几组的第几个位置
    // sum[x] = pre[i - 1] + j * (j + 1) / 2; 
    return getPre(i - 1) + j * (j + 1) / 2;
}
signed main(){
    // 递推求 pre[1 ~ 2000000]
    pre[1] = 1;
    for(int i = 2 ; i <= 2000000 ; i ++) pre[i] = pre[i - 1] + i * (i + 1) / 2;
    int T = 1;
    cin >> T;
    while(T --){
        int l , r;
        cin >> l >> r;
        // sum[r] - sum[l - 1]
        cout << calc(r) - calc(l - 1) << '\n';
    } 
    return 0;
}

3.思维与贪心

3.1重复字符串

3.1.1

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n , k , ma[N] , cnt[30];
char s[N];
signed main(){
  cin >> k >> (s + 1); // 从 s[1] 开始存储字符串
  // 当 S 不是 K 的倍数时，无论 S 如何修改，也无法成为 K 次字符串
  if(strlen(s + 1) % k) return cout << -1 << '\n' , 0;
  int n = strlen(s + 1) / k , ans = 0;
  for(int i = 1 ; i <= n ; i ++) {
      // cnt[j] 记录第 i 行第 j 个元素出现的次数。初始化为 0
      for(int j = 0 ; j <= 25 ; j ++) cnt[j] = 0;  
      int ma = 0; // ma 统计第 i 行出现最多的元素
      for(int j = 1 ; j <= k ; j ++){
          int x = s[i + (j - 1) * n]; // S 对应矩阵的第 i 行的第 j 列个元素
          cnt[x - 'a'] ++ ;           // 该元素出现的次数 + 1
          ma = max(ma , cnt[x - 'a']);// 更新出现次数最多的元素
      }
      ans += k - ma;
  }
  cout << ans << '\n';
  return 0;
}

3.2翻硬币

3.2.1

#include<bits/stdc++.h>
using namespace std;
signed main()
{
  int cnt = 0;
  string s, t;
  cin >> s >> t; // s 表示硬币的初始状态 ， t 表示硬币硬币的目标状态
  for(int i = 0 ; i < s.size() - 1; i ++){
    if(s[i] != t[i]){ // 如果第 i 枚硬币的初始状态和目标状态不同，则对第 i 枚硬币操作
      // 操作会改变第 i 枚硬币、第 i+1 枚硬币的状态
      // 由于操作之后第 i 枚硬币的状态必然会答案目标状态，且之后不会再对第 i 枚硬币操作了，所以可以省去对第 i 硬币的「实际修改」
      if(s[i + 1] == '*') s[i + 1] = 'o';  
      else s[i + 1] = '*';
      cnt ++ ;
    }
  }
  cout << cnt << '\n';
  return 0;
}

3.2.2

#include<bits/stdc++.h>
using namespace std;
signed main()
{
  int cnt = 0;
  string s, t;
  cin >> s >> t; // S 表示硬币的初始状态 ， T 表示硬币硬币的目标状态
  vector<int>vec; // vec 用来存储初始状态不等于目标状态的硬币的编号
  for(int i = 0 ; i < s.size() - 1; i ++){
    if(s[i] != t[i]) vec.push_back(i);
  }
  for(int i = 0 ; i < vec.size() ; i += 2) { // 成对枚举
    cnt += vec[i + 1] - vec[i]; // 操作次数 = 结束硬币的编号 - 开始硬币的编号
  }
  cout << cnt << '\n';
  return 0;
}

3.3乘积最大

3.3.1满分做法

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10 , mod = 1e9 + 9;
int n , k , cnt1 = 0 , cnt2 = 0 , res = 1 , a[N];
signed main(){
    cin >> n >> k;
    for(int i = 1 ; i <= n ; i ++) {
        cin >> a[i];
        if(a[i] >= 0) cnt1 ++; // 统计非负数个数
        else cnt2 ++ ;         // 统计负数的个数
    }
    sort(a + 1 , a + 1 + n);   // 排序
    // 对特殊情况进行处理
    if(n == k){
        for(int i = 1 ; i <= n ; i ++) res *= a[i] , res %= mod;
        cout << res << '\n';
    }
    // 对特殊情况进行处理
    else if(!cnt2) {
        for(int i = n ; i >= n - k + 1 ; i --) res *= a[i] , res %= mod;
        cout << res << '\n';
    }
    // 对特殊情况进行处理
    else if(!cnt1) {
        if(k & 1) for(int i = n ; i >= n - k + 1 ; i --) res = res * a[i] % mod;
        else for(int i = 1 ; i <= k ; i ++) res = res * a[i] % mod;
        cout << res << '\n';
    }
    else{
        // 当 cnt1 < k 时，成对取负数，直到 k <= cnt1
        int p = 1;
        while(k > cnt1) {
            res *= (a[p] * a[p + 1]) % mod , res %= mod;
            p += 2 , k -= 2;
        }
        // 每次可以选择符号相同、乘积最大的两个数，直到取完 K 个数。
        int p1 = p , p2 = n;
        while(k > 1) {
            if(a[p1] * a[p1 + 1] >= a[p2] * a[p2 - 1]) {
                res *= (a[p1] * a[p1 + 1]) % mod , res %= mod;
                p1 += 2;
            }
            else {
                res *= (a[p2] * a[p2 - 1]) % mod , res %= mod;
                p2 -= 2;
            }
            k -= 2;
        }
        // 如果 K 为奇数，即最后只能取一个数，那么要选择非负数才能保证乘积最大
        if(k) res = res * a[p2] % mod;
        cout << res << '\n';
    }
    return 0;
}

3.3.260%做法

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N = 1e3 + 10 , mod = 1e9 + 9;
int a[N] , ans[N][N];
double dp[N][N];
signed main(){
    int n , k  , cnt1 = 0 , cnt2 = 0 , res = 1;
    cin >> n >> k;
    for(int i = 1 ; i <= n ; i ++) cin >> a[i];
    sort(a + 1 , a + 1 + n);    // 将数组排序
    for(int i = 1 ; i <= n ; i ++) {
        if(a[i] < 0) cnt2 ++ ;
        else cnt1 ++ ;
    }
    // 对特殊情况进行处理
    if(k == n) {
        for(int i = 1 ; i <= n ; i ++ ) res = res * a[i] % mod;
        return cout << res << '\n' , 0;
    }
    // 对特殊情况进行处理
    if(cnt2 == n){
        if(k & 1) for(int i = n ; i >= n - k + 1 ; i --) res = res * a[i] % mod;
        else for(int i = 1 ; i <= k ; i ++) res = res * a[i] % mod;
        return cout << res << '\n' , 0;
    }
    vector<pair<int , int> >vec;
    vec.push_back(make_pair(0 , 0));
    for(int i = 1 ; i <= n ; i ++) {
        // 将负数两两打包在一起、视为一个物品
        if(a[i] < 0 && a[i + 1] < 0) {
            vec.push_back(make_pair(a[i] * a[i + 1] , 2));
            i ++ ;
        }
        // 正数单独作为一个物品
        else if(a[i] > 0) vec.push_back(make_pair(a[i] , 1));
    }
    memset(dp , -0x3f , sizeof(dp));
    dp[0][0] = 0 , ans[0][0] = 1;  // 初始化
    for(int i = 1 ; i < vec.size() ; i ++) {
        int v = vec[i].first , w = vec[i].second; 
        for(int j = 0 ; j <= k ; j ++){
            // 状态转移
            dp[i][j] = dp[i - 1][j];
            ans[i][j] = ans[i - 1][j];
            if(j - w >= 0){
                if(dp[i][j] < dp[i - 1][j - w] + log2(v)){
                    dp[i][j] = dp[i - 1][j - w] + log2(v);
                    ans[i][j] = ans[i - 1][j - w] * v % mod;
                }
            }
        }
    }
    cout << ans[vec.size() - 1][k] << '\n';
    return 0;
}

3.4巧克力

3.4.1

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
set<int>se;
struct node{
    int val , L , cnt; // 单价，保质期，数量
    bool operator < (const node & b) const { // 重载运算符
        if(val == b.val) return L > b.L; // 单价相同，保质期越长越好
        return val < b.val;                         // 单价不同，价格越低越好
    }
}a[N];
signed main(){
    int x , n;
    cin >> x >> n;
    for(int i = 1 ; i <= n ; i ++){
        cin >> a[i].val >> a[i].L >> a[i].cnt;
    }
    sort(a + 1 , a + 1 + n); // 将巧克力排序
    for(int i = 1 ; i <= x ; i ++) se.insert(i); // 刚开始时， 1~x 天都没安排好要吃的巧克力，因此我们要将 1~x 天都插入到 set 中
    int p = 1 , res = 0;
    while(se.size() && p <= n){  // 安排第 p 种巧克力
        // 第 p 种巧克力一开始有 a[p].cnt 块，一块块地考虑
        while(a[p].cnt && se.size() && *se.begin() <= a[p].L){
            res += a[p].val;
            a[p].cnt --; 
            // 二分找出第一个大于 a[p].L 的日期
            // 自减后，得到的就是小于等于 a[p].L 的最大日期
            auto it = se.upper_bound(a[p].L); 
            it --; 
            se.erase(it); // 安排完巧克力后，要将该日期从 set 中删除
        }
        p ++ ;
    }
    if(se.size()) cout << -1 << '\n'; // 如果无法安排完所有巧克力，则不存在让小蓝吃 x 天的购买方案
    else cout << res << '\n';
    return 0;
}

3.5答疑

3.5.1

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e3 + 10;
struct node{ 
  int s , a , e; 
  bool operator < (const node & x) const { // 重载运算符
    return (s + a + e) < (x.s + x.a + x.e);
  }
}stu[N];
signed main()
{
  int n , ans = 0;
  cin >> n; 
  for(int i = 1 ; i <= n ; i ++) cin >> stu[i].s >> stu[i].a >> stu[i].e;
  sort(stu + 1 , stu + 1 + n); // 排序 ： (s + a + e) 越小的同学安排在越前面答疑 
  for(int i = 1 ; i <= n ; i ++){
    int s = stu[i].s , a = stu[i].a , e = stu[i].e;
    ans += (n - i + 1) * (s + a) + (n - i) * e;
  }
  cout << ans << '\n';
  return 0;
}

3.6皮亚诺曲线

3.6.1

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll p[40];
map<pair<int, int>, int> mp;
ll calc(int n, ll x, ll y, map<pair<int, int>, int> mp) {
    ll x_ = x / p[n - 1], y_ = y / p[n - 1]; // 将 (x , y) 缩放得到 (x_ , y_)
    if (n == 1) return mp[make_pair(x_, y_)] - 1; // 如果 n = 1，返回所在块的编号 - 1
    ll ans = (mp[make_pair(x_, y_)] - 1) * p[n - 1] * p[n - 1];
    map<pair<int, int>, int> mp1;  // mp1 记录 n-1 阶皮亚诺曲线的变化
    if ((x_ == 0 && y_ == 1) || (x_ == 2 && y_ == 1)) {
        for(int i = 0; i <= 2; i++) for(int j = 0; j <= 2; j++) mp1[make_pair(2 - i, j)] = mp[make_pair(i, j)];
    }
    else if ((x_ == 1 && y_ == 2) || (x_ == 1 && y_ == 0)) {
        for(int i = 0; i <= 2; i++) for(int j = 0; j <= 2; j++) mp1[make_pair(i, 2 - j)] = mp[make_pair(i, j)];
    }
    else if (x_ == 1 && y_ == 1) { 
    for(int i = 0; i <= 2; i++) for(int j = 0; j <= 2; j++) mp1[make_pair(2 - i, 2 - j)] = mp[make_pair(i, j)];
    }
    else mp1 = mp;
    return ans += calc(n - 1, x % p[n - 1], y % p[n - 1], mp1);
}
signed main(){
    p[0] = 1;
    for(int i = 1; i < 40; i++) p[i] = p[i - 1] * 3;
    mp[make_pair(0, 0)] = 1; mp[make_pair(0, 1)] = 2; mp[make_pair(0, 2)] = 3;
    mp[make_pair(1, 2)] = 4; mp[make_pair(1, 1)] = 5; mp[make_pair(1, 0)] = 6;
    mp[make_pair(2, 0)] = 7; mp[make_pair(2, 1)] = 8; mp[make_pair(2, 2)] = 9;
    ll k, x1, y1, x2, y2;
    cin >> k >> x1 >> y1 >> x2 >> y2;
    // 由于 3^39 > 10^18，所以 39 阶皮亚诺曲线已包含了横纵坐标在 1 ~ 10^18 范围内的所有点
    // 所以从 39 阶皮亚努曲线开始递归即可 
    ll a = calc(39, x1, y1, mp);
    ll b = calc(39, x2, y2, mp);
    cout << abs(a - b) << '\n';
    return 0;
}

4.简单数论

4.1阶乘约数

4.1.1

#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int cnt[N]; // cnt[i] 存的是质因子 i 的幂次
signed main(){
  for(int i = 1 ; i <= 100 ; i ++){
    int x = i;
    // 质因子分解
    for(int j = 2 ; j * j <= x ; j ++){
      if(x % j == 0) while(x % j == 0) x /= j , cnt[j] ++ ; // j 是其中一个质因子
    }
    if(x > 1) cnt[x] ++ ; // x 是其中一个质因子
  }
  long long ans = 1;
  // 约数定理
  for(int i = 1 ; i <= 100 ; i ++) if(cnt[i] != 0) ans *= (cnt[i] + 1);
  cout << ans << '\n';
  return 0;
}

4.2求值

4.2.1

#include<bits/stdc++.h>
using namespace std;
// 判断 x 的因子个数是否为 100
bool check(int x){
  int cnt = 0;
  for(int i = 1 ; i * i <= x ; i ++) {
    if(x % i == 0) {
      if(x / i == i) cnt += 1;
      else cnt += 2;
    }
  }
  return cnt == 100;
}
signed main(){
  for(int i = 1 ; ; i ++) if(check(i)) {
    cout << i << '\n';
    break ;
  }
  return 0;
}

4.2.2

#include<bits/stdc++.h> 
using namespace std;
int prime[]={-1 , 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47}; // prime[0] 用于占位，prime[1] ~ prime[15] 分别表示第 1~15 个质数
long long ans = 1e18; // ans 表示答案
void dfs(int pos , long long val , int num , int up){ // pos 表示枚举到的质因子，val 表示我们搜寻的数，num 表示搜寻的数的质因子个数，up 表示质因子的幂次上限
  if(num > 1000 ) return ; // 约数的个数不超过 1000，固当 num > 1000 时结束搜索
  if(pos > 15) return;     // 质因子的个数不超过 15，固当 pos > 15 时结束搜索
  if(num == 1000 && val < ans) {ans = val ; return ;}  // 取约数个数为 1000 的最小正数
  for(int i = 1 ; i <= up ; i ++) {
    if(val * prime[pos] > ans) break ; // 剪枝
    val *= prime[pos];
    // 由于质因子越大幂次越小，所以下一个质因子的幂次不能大于 i（当前质因子的幂次）
    dfs(pos + 1 , val  , num * (i + 1) , i); 
  }
}
signed main(){
  dfs(1 , 1 , 1 , 61);
  cout << ans << '\n'; 
  return 0;
}

4.2.3

#include<bits/stdc++.h>
using namespace std;
int prime[]={-1 , 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47}; // 第 1 ~ 15 个质数
long long dp[16][1001] , INF = 1e18;
signed main(){
    memset(dp , 0x3f , sizeof(dp)); // 初始化为无穷大
    dp[0][1] = 1;
    for(int i = 1 ; i <= 15 ; i ++){
        for(int j = 1 ; j <= 1000 ; j ++) {
            long long p = 1;
            for(int k = 0 ; k <= 61 ; k ++) { // 幂次的范围为 0~61
              // 约数个数不能大于 1000 ，即 j * (k + 1) <= 1000
              // INF = 10^18，答案的值不超过 10^18，即 prime[i] * p <= INF
                if(j * (k + 1) > 1000 || INF / prime[i] < p) break ; 
                if(k > 0) p *= prime[i]; // 第 k 轮循环时，p = prime[i]^k。
                if(dp[i][j * (k + 1)] / p >= dp[i - 1][j]) dp[i][j * (k + 1)] = p * dp[i - 1][j];
            }
        }
    }
    cout << dp[15][1000] << '\n';
    return 0;
}

4.3循环小数

4.3.1

#include<bits/stdc++.h>
using namespace std;
signed main(){
  int p , q;
  string s;
  cin >> p >> q >> s;
  if(p == 1) { // 情况1：n 为纯循环小数
    long long a = 0;
    for(int i = 0 ; i < s.size() ; i ++) a = a * 10 + s[i] - '0';
    long long x = a , y = pow(10 , (int)log10(a) + 1) - 1;
    cout << x / __gcd(x , y) << " " << y / __gcd(x , y) << '\n'; // 最简形式
  }
  else { // 情况2： n 为混循环小数
    long long a = 0 , b = 0;
    for(int i = 0 ; i < p - 1 ; i ++) b = b * 10 + s[i] - '0';
    for(int i = p - 1 ; i < q ; i ++) a = a * 10 + s[i] - '0';
    long long x = b * (pow(10 , (int)log10(a) + 1) - 1) + a , y = pow(10 , (int)log10(b) + 1) * (pow(10 , (int)log10(a) + 1) - 1);
    cout << x / __gcd(x , y) << " " << y / __gcd(x , y) << '\n'; // 最简形式
  }
  return 0;
} 

4.4等差数列

4.4.1

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n , d , a[N];
signed main(){
  cin >> n;
  for(int i = 1 ; i <= n ; i ++) cin >> a[i];
  sort(a + 1 , a + 1 + n);
  for(int i = 1 ; i <= n ; i ++) d = __gcd(d , a[i] - a[1]); // 求差值的最大公约数
  if(!d) cout << n << '\n'; // 如果 d = 0，说明 a[1] = a[2] = a[3] = ... = a[n]。
  else cout << (a[n] - a[1]) / d + 1 << '\n';
  return 0;
}

4.5最大比例

4.5.1

#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int n , cnt;
long long a[N] , u[N] , d[N];
long long gcd_sub(long long a , long long b){
  if(a < b) swap(a , b); // 更相减损术总是大减小（a , b 的底数是一样的）
  if(b == 1) return a;  
  return gcd_sub(b , a / b); 
}
signed main(){
  cin >> n;
  for(int i = 1 ; i <= n ; i ++) cin >> a[i];
  sort(a + 1 , a + 1 + n);
  for(int i = 2 ; i <= n ; i ++){
    if(a[i] == a[i - 1]) continue ; // 去重
    long long g = __gcd(a[i] , a[i - 1]);
    // 将 a[i] / a[i - 1] 化为最简分数后分别存储在 u[cnt] 和 d[cnt] 里
    u[++ cnt] = a[i] / g; 
    d[cnt] = a[i - 1] / g;
  }
  long long x = u[1] , y = d[1];
  for(int i = 2 ; i <= cnt ; i ++){
    // 分子分母分开处理
    x = gcd_sub(x , u[i]);
    y = gcd_sub(y , d[i]);
  }
  cout << x << "/" << y << '\n';
  return 0;
}

5.字符串算法

5.1单词分析

5.1.1

#include<bits/stdc++.h>
using namespace std;
int cnt[26];
signed main(){
  string s;
  cin >> s;
  for(int i = 0 ; i < s.size() ; i ++) cnt[s[i] - 'a'] ++ ; // 'a' = 97
  char ans1 = 0 ; int ans2 = 0; 
  for(int i = 0 ; i < 26 ; i ++){
    if(cnt[i] > ans2) ans2 = cnt[i] , ans1 = (i + 'a'); // 'a' = 97;
  }
  cout << ans1 << '\n' << ans2 << '\n';
  return 0;
}

5.2人物相关性分析

5.2.1二分

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
bool check(char x){
    if(x >= 'a' && x <= 'z') return true;
    if(x >= 'A' && x <= 'Z') return true;
    if(x >= '0' && x <= '9') return true;
    return false;
}
vector<int>B , b;
signed main(){
    int k ; string s;
    cin >> k;
    cin.get();
    getline(cin , s); // 整行读入字符串
    int n = s.size();
    B.push_back(-1000000000) , b.push_back(-1000000000); // 边界处理
    for(int i = 0 ; i < n ; i ++){
        if(i + 2 < n && s.substr(i , 3) == "Bob"){
            if(i - 1 >= 0 && check(s[i - 1]) || i + 3 < n && check(s[i + 3])) continue ;
            B.push_back(i + 1) , b.push_back(i + 3);
        }
    }
    B.push_back(1000000000) , b.push_back(1000000000); // 边界处理
    long long ans = 0;
    for(int i = 0 ; i < n ; i ++){
        if(i + 4 < n && s.substr(i , 5) == "Alice"){
            if(i - 1 >= 0 && check(s[i - 1]) || i + 5 < n && check(s[i + 5])) continue ;
            int A = i + 1 , e = i + 5;
            // Alice 在 Bob
            int p1 = upper_bound(B.begin() , B.end() , e + k) - B.begin() - 1; // 找到比e+k大的最小数的下标，把下标-1就是小于等于e+k的最大数的下标。
            int p2 = lower_bound(B.begin() , B.end() , e) - B.begin();
            ans += p1 - p2 + 1;
            // Alice 在 Bob 后面
            p1 = upper_bound(b.begin() , b.end() , A) - b.begin() - 1; // 找到比A大的最小数的下标，把下标-1就是小于等于A的最大数的下标。
            p2 = lower_bound(b.begin() , b.end() , A - k) - b.begin();
            if(b[p2] > A) continue ;
            ans += p1 - p2 + 1;
        }
    } 
    cout << ans << '\n';  
    return 0;
}

5.2.2前缀和&差分

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
bool check(char x){
    if(x >= 'a' && x <= 'z') return true;
    if(x >= 'A' && x <= 'Z') return true;
    if(x >= '0' && x <= '9') return true;
    return false;
}
// 当 Alice 在 Bob 前面时，将所有 Bob 中的 B 视为 1，其它字符视为 0，记录在数组 B[] 中，并用 sum1 表示数组 B[] 的前缀和。
// 当 Alice 在 Bob 后面时，将所有 Bob 中的 b 视为 1，其它字符视为 0，记录在数组 b[] 中，并用 sum2 表示数组 b[] 的前缀和。
int B[N] , b[N] , sum1[N] , sum2[N];  
signed main(){
    int k ; string s;
    cin >> k;
    cin.get();
    getline(cin , s); // 整行读入字符串
    int n = s.size();
    for(int i = 0 ; i < n ; i ++){
        if(i + 2 < n && s.substr(i , 3) == "Bob"){
            if(i - 1 >= 0 && check(s[i - 1]) || i + 3 < n && check(s[i + 3])) continue ;
            B[i + 1] = 1 , b[i + 3] = 1; 
        }
    }
    for(int i = 1 ; i <= n ; i ++) sum1[i] = sum1[i - 1] + B[i] , sum2[i] = sum2[i - 1] + b[i];
    long long ans = 0;
    for(int i = 0 ; i < n ; i ++){
        if(i + 4 < n && s.substr(i , 5) == "Alice"){
            if(i - 1 >= 0 && check(s[i - 1]) || i + 5 < n && check(s[i + 5])) continue ;
            int A = i + 1 , e = i + 5;
            ans += sum1[min(n , e + k)/* e + k 可能大于 n , 因此要对 n 取 min 防止越界*/] - sum1[e + 1 - 1]; // Alice 在 Bob 前面
            ans += sum2[A - 1] - sum2[max(0 , A - 1 - k - 1)/* A - 1 - k - 1 可能小于 0 ，因此要对 0 取 max 防止越界*/]; // Alice 在 Bob 后面
        }
    } 
    cout << ans << '\n';  
    return 0;
}

5.2.3尺取法

#include<bits/stdc++.h>
using namespace std;
bool check(char x){
    if(x >= 'a' && x <= 'z') return true;
    if(x >= 'A' && x <= 'Z') return true;
    if(x >= '0' && x <= '9') return true;
    return false;
}
vector<int>A , B, e , b;
signed main(){   
    ios::sync_with_stdio(false);
    cin.tie(0);
    int k; string s; 
    cin >> k; 
    cin.get();
    getline(cin , s); // 整行读入字符串
    for(int i = 0 ; i < s.size() ; i ++){
        // 找 Alice，将找到的 Alice 中 A 的下标存储进容器 A 中，e 的下标存储进容器 e 中
        if(i + 4 >= s.size() || s.substr(i , 5) != "Alice") continue ;
        if(i - 1 >= 0 && check(s[i - 1]) || i + 5 < s.size() && check(s[i + 5])) continue ;
        A.push_back(i) ; e.push_back(i + 4);
    }
    for(int i = 0 ; i < s.size() ; i ++){
        // 找 Bob，将找到的 Bob 中 B 的下标存储进容器 B 中, b 的下标存储进容器 b 中
        if(i + 2 >= s.size() || s.substr(i , 3) != "Bob") continue ; 
        if(i - 1 >= 0 && check(s[i - 1]) || i + 3 < s.size() && check(s[i + 3])) continue ;
        B.push_back(i) ; b.push_back(i + 2); 
    }
    long long ans = 0;

    // Alice 在后， Bob 在前的情况
    int pl = 0 , pr = 0; // pl 所指向的第一个能和当前枚举到的 Alice 同时出现的 Bob，pr 所指向的则是最后一个
    for(int i = 0 ; i < A.size() ; i ++){
        // 若 pl 所指向的 Bob 和当前枚举到的 Alice 的距离大于 k，
        // 则令 pl 不断指向下一个 Bob，直到 pl 指向的 Bob 和 Alice 的距离不超过 k
        while(pl < b.size() && b[pl] + k < A[i]) pl ++;

        // pr 指向的是最后一个 ，pl 是第一个，所以 pr 一定在 pl 的后面，所以 pr 可以直接从 pl 开始移动
        // b[pr] + k >= b[pl] + k > A[i]
        pr = max(pr , pl);
        // 若 pr 所指向的 Bob 的枚举小于当前枚举到的 Alice，
        // 则令 pr 不断指向下一个 Bob，直到 pr 指向的 Bob 的位置大于 Alice
        // 那么此时 pr - 1 即为最后一个能和当前 Alice 同时出现的 Bob
        while(pr < b.size() && b[pr] < A[i]) pr ++ ; 
        ans += (pr - 1) - pl + 1;   
    }
    // Alice 在前， Bob 在后的情况
    pl = 0 , pr = 0; 
    for(int i = 0 ; i < e.size() ; i ++){
        while(pl < B.size() && B[pl] < e[i]) pl ++ ;
        pr = max(pr , pl);
        while(pr < B.size() && B[pr] - k <= e[i]) pr ++ ;
        ans += (pr - 1) - pl + 1;            
    }
    cout << ans << '\n';
    return 0;
}

5.3子串分值和

5.3.140%做法

#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int ans , cnt[26];
char s[N];
signed main(){
  cin >> s + 1;
  int n = strlen(s + 1);
  for(int l = 1 ; l <= n ; l ++){
      for(int r = l ; r <= n ; r ++){
          for(int i = 0 ; i <= 25 ; i ++) cnt[i] = 0;
          for(int i = l ; i <= r ; i ++) cnt[s[i] - 'a'] ++ ;
          int res = 0;
          for(int i = 0 ; i <= 25 ; i ++) if(cnt[i] > 0) res ++ ;
          ans += res;
        }
  }
  cout << ans << '\n';
  return 0;
}

5.3.260%做法

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
long long ans; // 注意，此时所有子串的分值和 int 可能存不下
int cnt[26];
char s[N];
signed main(){
    cin >> s + 1;
    int n = strlen(s + 1);
    for(int l = 1 ; l <= n ; l ++){
        for(int i = 0 ; i <= 25 ; i ++) cnt[i] = 0;
        int res = 0;
        for(int r = l ; r <= n ; r ++){
            if(cnt[s[r] - 'a'] == 0) res ++ ;
            cnt[s[r] - 'a'] ++ ;
            ans += res;
        }
    }
    cout << ans << '\n';
    return 0;
}

5.3.3满分做法

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
long long ans;
char s[N];
int suf[N] , last[30];
signed main(){
    cin >> s + 1;
    int n = strlen(s + 1);
    for(int j = 0 ; j <= 25 ; j ++) last[j] = n + 1;
    for(int i = n ; i >= 1 ; i --){
        suf[i] = last[s[i] - 'a'];
        last[s[i] - 'a'] = i;
    }
    for(int i = 1 ; i <= n ; i ++){
        // 注意 i * (suf[i] - i) 也有可能超出 int 的范围
        ans += 1ll * i * (suf[i] - i);
    }
    cout << ans << '\n';
    return 0;
}

5.4字串排序

5.4.130%做法

#include<bits/stdc++.h>
using namespace std;
int V;
string ans = "gfedcba";
void dfs(string s){
  int cnt = 0 , len = s.size();
  if(len > 7) return ; // 最大长度不会不超过 7
  string t = s;
  // 模拟冒泡排序
  for(int i = 0 ; i < len - 1 ; i ++){
    for(int j = 0 ; j < len - i - 1 ; j ++){
      if(t[j] > t[j + 1]) {
        cnt ++ ;
        swap(t[j] , t[j + 1]);
        if(cnt > V) return ; 
      }
    }
  }
  if(s.size() > ans.size()) return ;
  if(cnt == V){
    if(s.size() == ans.size()) ans = min(ans , s);
    else ans = s;
    return ;
  }
  for(int i = 0 ; i <= 6 ; i ++) dfs(s + (char)(i + 'a')); // 1 ~ 6 分别表示字符 a ~ g
}
signed main(){
  cin >> V;
  dfs("");
  cout << ans << '\n';
  return 0;
}

5.4.2满分做法

#include<bits/stdc++.h>
using namespace std;
int V , len , pre , cnt[27] , sum[27];
int get_max(int len){ // 计算长度为 len 时的最大逆序对个数
  return ((len - (len / 26 + 1)) * (len / 26 + 1) * (len % 26) + (26 - len % 26) * (len / 26) * (len - len / 26)) / 2;
}
// 当前位置上放置的是第 x 个字母（即 'a' + x ，后面还有 n 个位置
bool check(int x , int n){
  memset(cnt , 0 , sizeof(cnt));
  int add1 = 0; // 当前位置放置 x 后新增的逆序对个数
  int add2 = 0; // 在后续位置放置字母最多可以新增的逆序对个数
  // 统计已放置好的部分（在 x 之前）比 x 大的数的字符个数，即放置 x 后新增的逆序对个数 (add1)
  for(int j = 26 ; j >= x + 1 ; j --) add1 += sum[j];
  sum[x] ++ ; // 在当前位置放置 x，固 x 的个数增加 1
  for(int k = 1 ; k <= n ; k ++){
      int ma = -1; // 在第 k+pos 个位置上放字母后最多能新增的逆序对个数
      int p = 0;   
      int num = 0; // [1,pos] 中大于 j 的字母个数
      for(int j = 25 ; j >= 0 ; j --){
          // 插入第 j 个字符产生的逆序对个数 = [1,pos] 中比 j 大的字符个数
          //                             + [pos+1,len] 中的字符数 - [pos+1,len] 字字符 j 的个数
          if(k - 1 - cnt[j] + num > ma){ // i - 1 表示即将插入第 j 个字符时 [pos+1,len] 中的所有字符的个数
                                          // cnt[j] 表示即将插入第 j 个字符时 [pos+1,len] 中字符 j 的个数
              ma = k - 1 - cnt[j] + num; 
              p = j;
          }
          num += sum[j]; 
      }
      add2 += ma , cnt[p] ++;
  }
  if(pre + add1 + add2 >= V) {
      pre += add1;
      return true;
  }
  else {
      sum[x] -- ;
      return false;
  }
}
signed main(){
  string ans = "";
  cin >> V;
  for(int i = 1 ; ; i ++) {
      if(get_max(i) >= V){
          len = i;
          break ;
      }
  }
  // 构造自断续最小的字符串：依次在第i个位置上放置字符
  for(int i = 1 ; i <= len ; i ++){
      for(int j = 0 ; j <= 25 ; j ++){ // 在位置i上试探性的放置第j个字母
          if(check(j , len - i)){
              ans += char(j + 'a');
              break ;
          }
      }
  }
  cout << ans << '\n';
  return 0;
}

6.动态规划

6.1数字三角形

6.1.1

#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int n , a[N][N];
int dfs(int i , int j){
    if(i == n) return a[i][j]; // 走到底部无法再走了，直接返回
    return max(dfs(i + 1 , j) , dfs(i + 1 , j + 1)) + a[i][j];
}
signed main(){
    cin >> n;
    for(int i = 1 ; i <= n ; i ++) 
      for(int j = 1 ; j <= i ; j ++) 
        cin >> a[i][j];
    cout << dfs(1 , 1) << '\n';
    return 0;
}

6.1.2

#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int n , a[N][N] , res[N][N];
int dfs(int i , int j){
    if(res[i][j]) return res[i][j]; // res[i][j] != 0 说明其记录着 dfs(i , j) 的值，返回从下往上找，到达（i，j）时的最大值。
    if(i == n) return a[i][j];
    return res[i][j] = max(dfs(i + 1 , j) , dfs(i + 1 , j + 1)) + a[i][j];
}
signed main(){
    cin >> n;
    for(int i = 1 ; i <= n ; i ++) 
        for(int j = 1 ; j <= i ; j ++) 
            cin >> a[i][j];
    cout << dfs(1 , 1) << '\n';
    return 0;
}

6.1.3

#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int n , a[N][N] , dp[N][N];
signed main(){
    cin >> n;
    for(int i = 1 ; i <= n ; i ++) 
        for(int j = 1 ; j <= i ; j ++) 
            cin >> a[i][j];
    dp[1][1] = a[1][1];
    for(int i = 2 ; i <= n ; i ++)
        for(int j = 1 ; j <= i ; j ++)
            dp[i][j] = max(dp[i - 1][j] , dp[i - 1][j - 1]) + a[i][j];
    int ans = 0;
    for(int j = 1 ; j <= n ; j ++) ans = max(ans , dp[n][j]);
    cout << ans << '\n';
    return 0;
}

6.1.4

#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int n , a[N][N] , dp[N][N][N];
signed main(){
    memset(dp , -0x3f , sizeof(dp)); // 某些情况可能并不存在，如 dp[2][1][0]：走到位置 (2,1) 时共向下走了 0 次。 为了防止这种情况被转移，需初始化 dp 数组
    cin >> n;
    for(int i = 1 ; i <= n ; i ++)
        for(int j = 1 ; j <= i ; j ++)
            cin >> a[i][j];
    dp[1][1][0] = a[1][1];
    for(int i = 2 ; i <= n ; i ++){
        for(int j = 1 ; j <= i ; j ++){
            for(int k = 0 ; k <= (n - 1) ; k ++){
                if(!k) dp[i][j][k] = dp[i - 1][j - 1][k] + a[i][j];
                else dp[i][j][k] = max(dp[i - 1][j - 1][k] , dp[i - 1][j][k - 1]) + a[i][j];
            }
        }
    }
    int ma = 0;
    if((n - 1) & 1) for(int j = 1 ; j <= n ; j ++) ma = max(ma , max(dp[n][j][(n - 1) / 2] , dp[n][j][(n - 1) / 2 + 1]));
    else for(int j = 1 ; j <= n ; j ++) ma = max(ma , dp[n][j][(n - 1) / 2]);
    cout << ma << '\n';
    return 0;
}

6.1.5

#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int n , a[N][N] , dp[N][N];
signed main(){
    cin >> n;
    for(int i = 1 ; i <= n ; i ++){
        for(int j = 1 ; j <= i ; j ++){
            cin >> a[i][j];
        }
    }
    dp[1][1] = a[1][1];
    for(int i = 2 ; i <= n ; i ++){
        for(int j = 1 ; j <= i ; j ++){
            dp[i][j] = max(dp[i - 1][j - 1] , dp[i - 1][j]) + a[i][j];
        }
    }
    // 根据 n - 1 的奇偶性输出：在满足「向下走的次数与向右下走的次数相差不能超过 1」的条件下可能会达到的位置对应的 dp 值
    if((n - 1) & 1) cout << max(dp[n][1 + (n - 1) / 2] , dp[n][1 + (n - 1) / 2 + 1]) << '\n';
    else cout << dp[n][1 + (n - 1) / 2] << '\n';
    return 0;
}

6.1.6

#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10;
int n , a[N][N] , res[N][N];
int dfs(int i , int j){
    if(res[i][j]) return res[i][j];
    if(i == n) {
        if(n % 2 && j == n / 2 + 1) return a[i][j];
        if(n % 2 == 0 && (j == n / 2 || j == n / 2 + 1)) return a[i][j];
        return -10000000; // 位置不正确时，返回一个极大的负数
    }
    return res[i][j] = max(dfs(i + 1 , j) , dfs(i + 1 , j + 1)) + a[i][j];
}
signed main(){
    cin >> n;
    for(int i = 1 ; i <= n ; i ++) 
        for(int j = 1 ; j <= i ; j ++) 
            cin >> a[i][j];
    cout << dfs(1 , 1) << '\n';
    return 0;
}

6.2砝码称重

6.2.150%做法

#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10 , M = 1e5 + 10;
int n , ans , w[N] , vis[M]; // vis[x] = 1 表示可以称出重量 x
void dfs(int i , int left , int right){
    if(i > n){
        vis[max(left , right) - min(left , right)] = 1; 
        return ;
    }
    // 将第 i 个砝码放置在左边
    dfs(i + 1 , left + w[i] , right);
    // 将第 i 个砝码放置在右边
    dfs(i + 1 , left , right + w[i]);
    // 两边都不放
    dfs(i + 1 , left , right);
}
signed main(){
    cin >> n;
    for(int i = 1 ; i <= n ; i ++) cin >> w[i];
    dfs(1 , 0 , 0);
    for(int i = 1 ; i < M ; i ++) if(vis[i]) ans ++ ;
    cout << ans << '\n';
    return 0;
}

6.2.2满分做法

#include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 10 , M = 1e5 + 10 , offset = 1e5;
int n , ans , w[N] , dp[N][2 * M];
signed main(){
    cin >> n;
    for(int i = 1 ; i <= n ; i ++) cin >> w[i];
    dp[0][0 + offset] = true;
    for(int i = 1 ; i <= n ; i ++){
        for(int j = 0 ; j < M + offset ; j ++){
            if(j - w[i] >= 0) dp[i][j] |= dp[i - 1][j - w[i]];
            dp[i][j] |= dp[i - 1][j + w[i]] | dp[i - 1][j];
        }
    }   
    for(int i = 1 + offset ; i < M + offset ; i ++) if(dp[n][i]) ans ++ ;
    cout << ans << '\n';
    return 0;
}

6.3括号序列

6.3.1

#include<bits/stdc++.h>
using namespace std;
int n , cnt , ans , min_len = 0x3f3f3f3f;
string s;
bool check(string s){
    int left = 0;
    for(int i = 0 ; i < s.size() ; i ++){
        if(s[i] == '(') left ++ ; // 未匹配的左括号个数+1
        else left -- ;            // 拿走一个左括号与该右括号匹配，左括号个数-1
        if(left < 0) return false; // 该右括号之前没有左括号可以与该右括号匹配
    }
    return true;
}
void dfs(int p , string new_s){
    if(p == n){ // 枚举结束
        if(check(new_s) == true){ // 判断这个新的括号序列是否合法
            if(new_s.size() == min_len) ans ++ ; // 如果长度和最小长度相同，则答案个数+1
            else if(new_s.size() < min_len) min_len = new_s.size() , ans = 1; // 如果长度比最小长度还小，则作为新的最小长度
        }
        return ;
    }
    if(s[p] == '(') dfs(p + 1 , new_s + '('); 
    else{
        for(int i = 0 ; i <= cnt ; i ++){ // 如果是右括号则在该右括号前枚举要添加的左括号个数i
            string add = "";
            for(int j = 1 ; j <= i ; j ++) add += '(';
            dfs(p + 1 , new_s + add + ')');
        }
    }
}
signed main(){
    cin >> s;
    n = s.size();
    for(int i = 0 ; i < s.size(); i ++) if(s[i] == ')') cnt ++ ;
    dfs(0 , "");
    cout << ans << '\n';
    return 0;
}

6.3.2

#include<bits/stdc++.h>
using namespace std;
int n , cnt , ans , min_len = 0x3f3f3f3f;
string s;
void dfs(int p , string new_s , int total , int left){
    if(p == n){ // 枚举结束
        if(new_s.size() == min_len) ans ++ ; // 如果长度和最小长度相同，则答案个数+1
        else if(new_s.size() < min_len) min_len = new_s.size() , ans = 1; // 如果长度比最小长度还小，则作为新的最小长度
        return ;
    }
    if(s[p] == '(') dfs(p + 1 , new_s + '(' , total , left + 1); // 未匹配的左括号个数+1
    else{
        int st = 0;  // 枚举起点
        if(left == 0) st = 1; // 该右括号之前未匹配的左括号个数为0，那么为了保证序列合法，它之前至少要添加一个左括号。
        for(int i = st ; i <= total ; i ++){ // 如果是右括号则在该右括号前枚举要添加的左括号个数i，从st开始枚举
            string add = "";
            for(int j = 1 ; j <= i ; j ++) add += '(';
            dfs(p + 1 , new_s + add + ')' , total - i , left + i - 1); // 需要从未匹配的左括号中拿出一个和当前右括号匹配，所以要-1
        }
    }
}
signed main(){
    cin >> s;
    n = s.size();
    for(int i = 0 ; i < s.size(); i ++) if(s[i] == ')') cnt ++ ;
    int need = 0, left = 0;// need 表示最少需要添加的左括号数，left 表示未匹配的左括号数个数
    for(int i = 0 ; i < s.size() ; i ++){
        if(s[i] == '(') left ++ ; // 未匹配的左括号数个数 + 1
        else left --;             // 拿走一个左括号与该右括号匹配，左括号个数-1
        if(left < 0) need ++, left = 0;// 该右括号之前没有左括号可以与该右括号匹配，此时就必须添加左括号使得
    }
    dfs(0 , "" , need , 0);
    cout << ans << '\n';
    return 0;
}

6.3.3

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e3 + 10, mod = 1e9 + 7;
string s;
int dp[N][N], num[N];
int calc(int need, bool flag)
{
    memset(dp, 0, sizeof(dp));
    memset(num, 0, sizeof(num));
    // flag = 1 表示统计添加左括号的方案数 flag = 0 表示统计添加右括号的方案数（翻转）
    if(!flag) {
        reverse(s.begin(), s.end());
        for(int i = 0 ; i < s.size() ; i ++) {
            if(s[i] == ')') s[i] = '(';
            else s[i] = ')';
        }
    }
    int left = 0, cnt = 0;
    for(int i = 0 ; i < s.size() ; i ++) {
        if(s[i] == ')') num[++ cnt] = left; // tot 为右括号的编号
        if(s[i] == '(') left ++;  // left 表示原序列区间[1~i]的左括号的个数
    }
    // 区域1 有左括号时 dp[1][0] = 1, 否则 dp[1][0] = 0
    if(num[1] > 0) dp[1][0] = 1;
    for(int i = 1 ; i <= cnt ; i ++) dp[1][i] = 1;
    for(int i = 2 ; i <= cnt ; i ++) {
        // 1. j+num[i]>=i
        //2.最少添加的数量为 need
        for(int j = max(0ll , i - num[i]) ; j <= need ; j ++) {
            for(int k = 0 ; k <= j ; k ++) {
                dp[i][j] += dp[i - 1][k];
                dp[i][j] %= mod;
            }
        }
    }
    return dp[cnt][need];
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0) , cout.tie(0);
    cin >> s;
    int need = 0, tmp = 0;// need 表示最少需要添加的左括号数，tmp表示序列前缀和
    for(int i = 0 ; i < s.size() ; i ++) {
        if(s[i] == '(') tmp ++ ;
        else tmp --;
        if(tmp < 0) need ++, tmp ++;// tmp < 0 表示右括号数大于左括号数，此时需要添加左括号使得 左括号数>=右括号数
    }
    int need2 = tmp;
    cout << calc(need, 1) * calc(need2, 0) % mod << '\n';
    return 0;
}

6.3.4

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e3 + 10, mod = 1e9 + 7;
string s;
int dp[N][N], num[N], pre[N] , nex[N];
// 计算方案数
int calc(int need, bool flag)
{
    if(!need) return 1; // 不需要添加括号也是一种方案
    memset(dp, 0, sizeof(dp));
    memset(num, 0, sizeof(num));
    memset(pre , 0 , sizeof(pre));
    memset(nex , 0 , sizeof(nex));
    // flag = 1 表示统计添加左括号的方案数 flag = 0 表示统计添加右括号的方案数（翻转）
    if(!flag) {
        reverse(s.begin(), s.end());
        for(int i = 0 ; i < s.size() ; i ++) {
            if(s[i] == ')') s[i] = '(';
            else s[i] = ')';
        }
    }
    int left = 0, cnt = 0; 
    for(int i = 0 ; i < s.size() ; i ++) {
        if(s[i] == ')') num[++ cnt] = left; // tot 为右括号的编号
        if(s[i] == '(') left ++;  // left 表示原序列区间[1~i]的左括号的个数
    }
    // 区域1 有左括号时 dp[1][0] = 1, 否则 dp[1][0] = 0
    if(num[1] > 0) dp[1][0] = 1 , pre[0] = 1;
    for(int i = 1 ; i <= cnt ; i ++) dp[1][i] = 1 , pre[i] = pre[i - 1] + 1;
    for(int i = 2 ; i <= cnt ; i ++){
        for(int j = 0 ; j <= need ; j ++) nex[j] = 0;
        for(int j = max(0ll , i - num[i]) ; j <= need ; j ++){
            dp[i][j] = pre[j];
            if(j - 1 < 0) nex[j] = dp[i][j];
            else nex[j] = (nex[j - 1] + dp[i][j]) % mod;
        }
        for(int j = 0 ; j <= cnt ; j ++) pre[j] = nex[j];// 先用 nex[] 存储 dp[i-1] 的信息，再将 nex[] 的值赋给 pre[]，这样下次循环 pre[] 存的值就是 dp[i-1] 的值
    }
    return dp[cnt][need];
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0) , cout.tie(0);
    cin >> s;
    int need = 0, pre = 0;// need 表示最少需要添加的左括号数，pre表示序列前缀和
    for(int i = 0 ; i < s.size() ; i ++) {
        if(s[i] == '(') pre ++ ;
        else pre --;
        if(pre < 0) need ++, pre ++;// pre < 0 表示右括号数大于左括号数，此时需要添加左括号使得 左括号数>=右括号数
    }
    int need2 = pre;
    cout << calc(need, 1) * calc(need2, 0) % mod << '\n';
    return 0;
}

6.4异或三角

6.4.110%做法

#include<bits/stdc++.h>
using namespace std;
signed main(){
    int T = 1;
    cin >> T;
    while(T --){
        int n , ans = 0;
        cin >> n;
        for(int a = 1 ; a <= n ; a ++)
            for(int b = 1 ; b <= n ; b ++)
                for(int c = 1 ; c <= n ; c ++)
                    if((a ^ b ^ c) == 0 && a + b > c && a + c > b && b + c > a)
                        ans ++ ;
        cout << ans << '\n';
    }
    return 0;
}

6.4.220%做法

#include<bits/stdc++.h>
using namespace std;
signed main(){
    int T = 1;
    cin >> T;
    while(T --){
        int n , ans = 0;
        cin >> n;
        for(int a = 1 ; a <= n ; a ++)
            for(int b = 1 ; b <= n ; b ++){
                int c = (a ^ b); //a ^ b ^ c = 0 , 因为相同数的异或值为 0，所以 c = (a ^ b)
                if(a + b > c && a + c > b && b + c > a) 
                    ans ++ ;
            }
        cout << ans << '\n';
    }
    return 0;
}

6.4.350%做法

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n , dp[21][2][2][2] , num[22];    
int dfs(int len , bool limit , bool zero , bool ok1  , bool ok2){
    if(!len) return ok1 && ok2 ? 1 : 0;
    if(~dp[len][limit][ok1][ok2] && !zero) return dp[len][limit][ok1][ok2];
    int up = limit ? num[len] : 1 ,  res = 0;
    for(int i = 0 ; i <= up ; i ++){
      if(zero && i && !num[len]) continue ;
      res += dfs(len - 1 , limit && i == up , zero && !i , ok1 || (zero && i && num[len]) , ok2 || (i && !num[len]));
    }
    return dp[len][limit][ok1][ok2] = res;
}
int solve(int n){
    memset(dp , -1 , sizeof(dp));
    int len = 0;
    while(n) num[++ len] = n & 1 , n >>= 1;
    return dfs(len , 1 , 1 , 0 , 0);
}
signed main(){
    int T = 1;
    cin >> T;
    while(T --){
      cin >> n;
      int res = 0;
      for(int i = 1 ; i <= n ; i ++) res += solve(i);
      cout << res * 3  << '\n';
    }
    return 0;
}

6.3.460%做法

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n , dp[21][2][2][2] , num[22] , ans[1 << 21];    
int dfs(int len , bool limit , bool zero , bool ok1  , bool ok2){
    if(!len) return ok1 && ok2 ? 1 : 0;
    if(~dp[len][limit][ok1][ok2]) return dp[len][limit][ok1][ok2];
    int up = limit ? num[len] : 1 ,  res = 0;
    for(int i = 0 ; i <= up ; i ++){
      if(zero && i && !num[len]) continue ;
      res += dfs(len - 1 , limit && i == up , zero && !i , ok1 || (zero && i && num[len]) , ok2 || (i && !num[len]));
    }
    return dp[len][limit][ok1][ok2] = res;
}
int solve(int n){
    memset(dp , -1 , sizeof(dp));
    int len = 0;
    while(n) num[++ len] = n & 1 , n >>= 1;
    return dfs(len , 1 , 1 , 0 , 0);
}
signed main(){
    int T = 1 , res = 0;
    // 预处理，将 n = i 的答案记录在 ans[i] 中
    for(int i = 1 ; i <= (1 << 20) ; i ++) res += solve(i) , ans[i] = res * 3;
    cin >> T;
    while(T --){
      cin >> n;
      cout << ans[n] << '\n';
    }
    return 0;
}

6.3.5满分做法

#pragma GCC target ("avx2,fma")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;

template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true);
for(res=ch-48;isdigit(ch=getchar());res=(res<<1)+(res<<3)+ch - 48);flag&&(res=-res);}

template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');}

int n , dp[32][2][2][2][2] , num[32];
inline int dfs(int len , bool limit1 , bool limit2 , bool ok1  , bool ok2){
    if(!len) return ok2 ? 1 : 0;
    if(~dp[len][limit1][limit2][ok1][ok2]) return dp[len][limit1][limit2][ok1][ok2];
    int up1 = limit1 ? num[len] : 1 , res = 0;
    for(int i = 0 ; i <= up1 ; i ++){
        int up2 = limit2 ? i : 1;
        for(int j = 0 ; j <= up2 ; j ++){
            if(!ok1 && !i && j) continue ;
            res += dfs(len - 1 , limit1 && i == up1 , limit2 && j == up2 , ok1 || (j == i && j == 1) , ok2 || (j == 1 && j != i));
        }
    }
    return dp[len][limit1][limit2][ok1][ok2] = res;
}
inline int solve(int n){
    memset(dp , -1 , sizeof(dp));
    int len = 0;
    while(n) num[++ len] = n & 1 , n >>= 1;
    return dfs(len , 1 , 1 , 0 , 0);
}
signed main(){
    int T = 1;
    read(T);
    while(T --){
        read(n);
        Out(solve(n) * 3) , putchar('\n');
    }
    return 0;
}

6.5组合数问题

6.5.120%做法

#include<bits/stdc++.h>
using  namespace std;
const int N = 2e3 + 10 , mod = 1e9 + 7;
int n , m , k;
long long C[N][N];
signed main(){
    int T = 1;
    cin >> T >> k;
    // 预处理得到 C[i][j]
    for(int i = 0 ; i < N ; i ++) {
        C[i][0] = 1;
        for(int j = 1 ; j <= i ; j ++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % k;
    }
    while(T --){
        cin >> n >> m;
        int ans = 0;
        // 暴力枚举 i , j
        for(int i = 1 ; i <= n ; i ++) 
            for(int j = 0 ; j <= min(i , m) ; j ++)
                if(C[i][j] % k == 0) ans ++ ;       
        cout << ans % mod << '\n';
    }
    return 0;
}

6.5.240%做法

#include<bits/stdc++.h>
using  namespace std;
const int N = 2e3 + 10 , mod = 1e9 + 7;
int n , m , k , sum[N][N];
long long C[N][N];
signed main(){
    int T = 1;
    cin >> T >> k;
    for(int i = 0 ; i < N ; i ++) {
        C[i][0] = 1;  // 初始化
        for(int j = 1 ; j <= i ; j ++) 
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % k ;
    }
    for(int i = 1 ; i < N ; i ++)
        for(int j = 1 ; j < N ; j ++){
            // 注意当 j > i 时值为 (i , j) 对应的组合数没有意义，将其值重构为 0
            if(C[i][j] % k != 0 || j > i) C[i][j] = 0;
            else C[i][j] = 1; 
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + (C[i][j]);
                sum[i][j] = (sum[i][j] + mod) % mod;
        }

    while(T --){
        cin >> n >> m;
        m = min(n , m); // m 大于 n 时没有意义
        cout << sum[n][m] << '\n';
    }
    return 0;
}

6.5.370%做法

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int k , num1[65] , num2[65];
long long n , m , dp[65][2][2][2][2];
long long dfs(int len , bool limit1 , bool limit2 , bool ok1 , bool ok2){
    if(!len) return ok1 && ok2;
    int up1 = limit1 ? num1[len] : k - 1;
    int up2 = limit2 ? num2[len] : k - 1;
    if(~dp[len][limit1][limit2][ok1][ok2]) return dp[len][limit1][limit2][ok1][ok2];
    long long res = 0;
    for(int i_ = 0 ; i_ <= up1 ; i_ ++){ // i 在 k 进制下第 len 位的取值
        for(int j_ = 0 ; j_ <= up2 ; j_ ++){ // j 在 k 进制下第 len 位的取值
            res += dfs(len - 1 , limit1 && i_ == up1 , limit2 && j_ == up2 , ok1 || (!ok2 && i_ > j_) , ok2 || j_ > i_);
            res %= mod;
        }
    }
    return dp[len][limit1][limit2][ok1][ok2] = res;
}
long long solve(){
    memset(dp , -1 , sizeof(dp));
    memset(num1 , 0 , sizeof(num1));
    memset(num2 , 0 , sizeof(num2));
    m = min(n , m); // m 大于 n 时没有意义
    int cnt1 = 0 , cnt2 = 0;
    while(n) num1[++ cnt1] = n % k , n /= k; // num1 存储 n 在 k 进制下的每一位 
    while(m) num2[++ cnt2] = m % k , m /= k; // num2 存储 m 在 k 进制下的每一位
    return dfs(cnt1 , 1 , 1 , 0 , 0);
}
signed main(){
    int T = 1;
    cin >> T >> k;
    while(T --){
        cin >> n >> m;
        cout << solve() << '\n';
    }
    return 0;
}

6.5.4满分做法

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7 , inv2 = 5e8 + 4; // 2 的逆元
const int N = 65;
int n , m , k , dp[N][4];
int a[N] , b[N];
int calc1(int n , int m){
    if(n < 0 || m < 0) return 0;
    if(n < m) return (n % mod + 2) * (n % mod + 1) % mod * inv2 % mod;
    return ((m % mod + 2) * (m % mod + 1) % mod * inv2 % mod + (n % mod - m  % mod + mod) % mod * (m % mod + 1) % mod + mod) % mod;
}
int calc2(int n , int m){
    return (min(n , m) + 1 + mod) % mod;
}
int calc3(int n,int m){
    if(n < m) return 0;
    return (n - m + 1 + mod) % mod;
}
signed main(){
    int T = 1;
    cin >> T >> k;
    while(T --){
        memset(dp , 0 , sizeof(dp));
        for(int i = 0 ; i < N ; i ++) a[i] = b[i] = 0;
        cin >> n >> m;
        m = min(n , m);
        int tot = calc1(n , m) , len1 = 0 , len2 = 0;
        while(n) a[++ len1] = n % k , n /= k; // n 在 k 进制下的每一项
        while(m) b[++ len2] = m % k , m /= k; // m 在 k 进制下的每一项
        dp[len1 + 1][3] = 1;
        for(int i = len1 ; i >= 1 ; i --){
          // dp[i][0 ~ 3] 的状态转移
            dp[i][0] = dp[i + 1][0] * calc1(k - 1 , k - 1) % mod + dp[i + 1][1] * calc1(a[i] - 1 , k - 1) % mod +
                        dp[i + 1][2] * calc1(k - 1 , b[i] - 1) % mod + dp[i + 1][3] * calc1(a[i] - 1 , b[i] - 1)%mod;
            dp[i][1] = dp[i + 1][1] * calc2(a[i] , k - 1) % mod + dp[i + 1][3] * calc2(a[i] , b[i] - 1) % mod;
            dp[i][2] = dp[i + 1][2] * calc3(k - 1 , b[i]) % mod + dp[i + 1][3] * calc3(a[i] - 1, b[i]) % mod;
            dp[i][3] = dp[i + 1][3] & (a[i] >= b[i]);
            dp[i][0] %= mod , dp[i][1] %= mod , dp[i][2] %= mod;
        }
        // 原答案 = 所有组合数的个数 - 补问题的答案
        cout << (tot - (dp[1][0] + dp[1][1] + dp[1][2] + dp[1][3]) % mod + mod) % mod << '\n';
    }
    return 0;
}

7.数据结构

7.1修改数组

7.1.1

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n , a[N] , vis[N];
signed main(){
    cin >> n;
    for(int i = 1 ; i <= n ; i ++) cin >> a[i];
    for(int i = 1 ; i <= n ; i ++) {
        if(!vis[a[i]]) vis[a[i]] = 1;
        else {
            while(vis[a[i]]) a[i] ++ ; //  如果 a[i] 对应的值出现过，就让它不断+1 直至对应的值未出现过
            vis[a[i]] = 1;
        }
    }
    for(int i = 1 ; i <= n ; i ++) cout << a[i] << " \n"[i == n];
    return 0;
}

7.1.2

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n , a[N] , vis[N] , tree[N];
int lowbit(int x){
    return x & (-x);
}
void add(int pos , int val){
    while(pos < N) tree[pos] += val , pos += lowbit(pos);
}
int query(int pos){
    int res = 0;
    while(pos) res += tree[pos] , pos -= lowbit(pos);
    return res;
}
signed main(){
    cin >> n;
    for(int i = 1 ; i <= n ; i ++) cin >> a[i];
    for(int i = 1 ; i <= n ; i ++) {
        if(!vis[a[i]]) vis[a[i]] = 1 , add(a[i] , 1); // 将已出现过的值插入树状数组中
        else {
            int l = a[i] , r = N , y = -1;
            while(l <= r){
                int mid = l + r >> 1;
                // 判断区间 [a[i], mid] 的值是否小于 mid - a[i] + 1 
                if(query(mid) - query(a[i] - 1) < mid - a[i] + 1) r = mid - 1 , y = mid;
                else l = mid + 1;
            }
            a[i] = y , vis[y] = 1 , add(a[i] , 1); // 将已出现过的值插入树状数组中
        }
    }
    for(int i = 1 ; i <= n ; i ++) cout << a[i] << " \n"[i == n];
    return 0;
}

7.1.3

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n , a[N] , far[N];
int find(int x){
  return far[x] = x == far[x] ? x : find(far[x]); 
}
signed main(){
    cin >> n;
    for(int i = 1 ; i < N ; i ++) far[i] = i; // 初始化
    for(int i = 1 ; i <= n ; i ++) {
        cin >> a[i];
        a[i] = find(a[i]);
        far[a[i]] = find(a[i] + 1);  // x = a[i] , far[x] = far[x + 1]
    }
    for(int i = 1 ; i <= n ; i ++) cout << a[i] << " \n"[i == n];
    return 0;
}

7.2翻转括号序列

7.2.120%做法

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n , m , a[N];
string s;
signed main(){
    cin >> n >> m >> s;
    // 左括号视为 1，右括号视为 −1
    for(int i = 0 ; i < s.size() ; i ++) {
        if(s[i] == '(') a[i + 1] = 1;
        else a[i + 1] = -1;
    }
    while(m --){
        int op , L , R;
        cin >> op;
        if(op == 1){
            cin >> L >> R;
            // 翻转
            for(int i = L ; i <= R ; i ++) a[i] = -a[i];
        }
        else {
            cin >> L;
            int sum = 0 , ans = 0;
            for(int i = L ; i <= n ; i ++){
                sum += a[i];
                if(sum < 0) break; // 合法括号序列的任意前缀和都必须大于等于 0
                if(!sum) ans = max(ans , i); 
            }
            cout << ans << '\n';
        }
    }
    return 0;
}

7.2.2满分做法

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 1e6 + 10 , inf = 0x3f3f3f3f;
struct Tree{
    int l , r;
    int mi , ma , sum;
    int lazy , add;
}tree[N << 2];
int n , m , a[N] , sum[N];
char s[N];
void F1(int rt){
    tree[rt].add *= -1 , tree[rt].lazy *= -1 , tree[rt].sum *= -1;
    tree[rt].ma *= -1 , tree[rt].mi *= -1;
    swap(tree[rt].ma , tree[rt].mi);
}
void F2(int rt , int val){
    tree[rt].add += val , tree[rt].mi += val , tree[rt].ma += val;
}
void push_up(int rt){
    tree[rt].ma = max(tree[rt << 1].ma , tree[rt << 1 | 1].ma);
    tree[rt].mi = min(tree[rt << 1].mi , tree[rt << 1 | 1].mi);
    tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
}
void push_down(int rt){
    int &x = tree[rt].lazy;
    if(x == -1){
        F1(rt << 1) , F1(rt << 1 | 1);
        x = 1;
    }
    int &y = tree[rt].add;
    if(y){
        F2(rt << 1 , y) , F2(rt << 1 | 1 , y);
        y = 0;
    }
}
void build(int l , int r , int rt){
    tree[rt].l = l , tree[rt].r = r , tree[rt].lazy = 1;
    if(l == r){
        tree[rt].sum = a[l];
        tree[rt].mi = tree[rt].ma = sum[l];
        return ;
    }
    int mid = l + r >> 1;
    build(l , mid , rt << 1);
    build(mid + 1 , r , rt << 1 | 1);
    push_up(rt);
}
void update_change(int L , int R , int rt){
    int l = tree[rt].l , r = tree[rt].r;
    if(L <= l && r <= R){
        F1(rt);
        return ;
    }
    push_down(rt);
    int mid = l + r >> 1;
    if(L <= mid) update_change(L , R , rt << 1);
    if(R  > mid) update_change(L , R , rt << 1 | 1);
    push_up(rt);
}
void update_add(int L , int R , int rt , int val){
    int l = tree[rt].l , r = tree[rt].r;
    if(L <= l && r <= R){
        F2(rt , val);
        return ;
    }
    push_down(rt);
    int mid = l + r >> 1;
    if(L <= mid) update_add(L , R , rt << 1 , val);
    if(R  > mid) update_add(L , R , rt << 1 | 1 , val);
    push_up(rt);
}
int query_range(int L , int R , int rt){
    int l = tree[rt].l , r = tree[rt].r;
    if(L <= l && r <= R) return tree[rt].sum;
    push_down(rt);
    int mid = l + r >> 1 , res = 0;
    if(L <= mid) res += query_range(L , R , rt << 1);
    if(R  > mid) res += query_range(L , R , rt << 1 | 1);
    return res;
}
int query_min(int L , int R , int rt){
    int l = tree[rt].l , r = tree[rt].r;
    if(L <= l && r <= R) return tree[rt].mi;
    push_down(rt);
    int mid = l + r >> 1 , res = inf;
    if(L <= mid) res = query_min(L , R , rt << 1);
    if(R  > mid) res = min(res , query_min(L , R , rt << 1 | 1));
    return res;
}
int query_check(int L , int R , int rt , int val){
    int l = tree[rt].l , r = tree[rt].r;
    if(l == r) return l;
    push_down(rt);
    int mid = l + r >> 1;
    if(tree[rt << 1 | 1].mi <= val) return query_check(L , R , rt << 1 | 1 , val);
    if(L <= mid) return query_check(L , R , rt << 1 , val);
    return 0;
}
void Change(int L , int R){
    int add1 = 2 * query_range(1 , R , 1) * -1;
    update_change(1 , R , 1);
    if(R + 1 <= n) update_add(R + 1 , n , 1 , add1);
    if(L - 1 >= 1){
        int add2 = 2 * query_range(1 , L - 1 , 1) * -1;
        update_change(1 , L - 1 , 1);
        update_add(L , n , 1 , add2);
    }
}
bool check(int L , int mid , int pre){
    if(query_min(L , L + mid , 1) >= pre) return true;
    return false;
}
signed main(){
    cin >> n >> m >> s + 1;
    for(int i = 1 ; i <= n ; i ++){
        if(s[i] == '(') a[i] = 1 , sum[i] = sum[i - 1] + 1;
        else a[i] = -1 , sum[i] = sum[i - 1] - 1;
    }
    build(1 , n , 1);
    while(m --){
        int op , L , R;
        cin >> op;
        if(op == 1){
            cin >> L >> R;
            Change(L , R);
        }
        else{
            cin >> L;
            if(query_range(L , L , 1) == -1){ // 第 L 个字符是右括号，则必然不存在以它为左端点的合法括号序列
                cout << 0 << '\n';
                continue ;
            }
            int pre = query_min(L - 1 , L - 1 , 1); // 查询前 L - 1 个字符的前缀和（即 sum[L - 1]）
            int l = 1 , r = n - L , len = 0;
            while(l <= r){
                int mid = l + r >> 1;
                // 二分找出最小的 len，满足 sum[L] ~ sum[L + len] 的值都大于等于 sum[L - 1]（以 L 为左端点的括号序列的任意前缀都大于等于 0）
                if(check(L , mid , pre)) l = mid + 1 , len = mid;
                else r = mid - 1;
            }
            // 如果 L + len < n，则 sum[L + len] 必然等于 sum[L - 1]
            if(L + len < n){
                cout << L + len << '\n';
                continue ;
            }
            int ans = query_check(L , n , 1 , pre);
            if(ans != L) cout << ans << '\n';
            else cout << 0 << '\n';
        }
    }
    return 0;
}

7.3双向排序

7.3.140%做法

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n , m , a[N];
signed main(){
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i ++) a[i] = i;
    while(m --){
        int p , q;
        cin >> p >> q;
        if(!p) sort(a + 1 , a + 1 + q , greater<int>());
        else sort(a + q , a + 1 + n);
    }
    for(int i = 1 ; i <= n ; i ++) cout << a[i] << " \n"[i == n];
    return 0;
}

7.3.260%做法

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n , m , a[N] , vis[N];
signed main(){
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i ++) a[i] = i;
    while(m --){
        int p , q;
        cin >> p >> q;
        if(!p) {
            for(int i = 1 ; i <= q ; i ++) vis[a[i]] = 1;
            int pos = 0;
            for(int i = n ; i >= 1 ; i --) if(vis[i]) a[++ pos] = i , vis[i] = 0;
        }
        else {
            for(int i = q ; i <= n ; i ++) vis[a[i]] = 1;
            int pos = q - 1;
            for(int i = 1 ; i <= n ; i ++) if(vis[i]) a[++ pos] = i , vis[i] = 0;
        }
    }
    for(int i = 1 ; i <= n ; i ++) cout << a[i] << " \n"[i == n];
    return 0;
}

7.3.3满分做法

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n , m , op , pos;
struct Tree{
    int l , r , sum , lazy;
}tree[N << 2];
void push_up(int rt){
    tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
}
void push_down(int rt){
    int &x = tree[rt].lazy;
    if(~x){
        int len1 = tree[rt << 1].r - tree[rt << 1].l + 1;
        int len2 = tree[rt << 1 | 1].r - tree[rt << 1 | 1].l + 1;
        tree[rt << 1].sum = len1 * x , tree[rt << 1 | 1].sum = len2 * x;
        tree[rt << 1].lazy = tree[rt << 1 | 1].lazy = x;
        x = -1;
    }
}
void build(int l , int r , int rt){
    tree[rt].l = l , tree[rt].r = r , tree[rt].lazy = -1;
    if(l == r) {
        tree[rt].sum = 1;
        return ;
    }
    int mid = l + r >> 1;
    build(l , mid , rt << 1);
    build(mid + 1 , r , rt << 1 | 1);
    push_up(rt);
}
void update1(int L , int R , int rt , int cnt){
    if(!cnt) return ;
    if(tree[rt].sum == cnt){
        tree[rt].sum = tree[rt].lazy = 0;
        return ;
    }
    push_down(rt);
    if(cnt < tree[rt << 1].sum) update1(L , R , rt << 1 , cnt);
    else {
        update1(L , R , rt << 1 | 1 , cnt - tree[rt << 1].sum);
        tree[rt << 1].sum = 0;
        tree[rt << 1].lazy = 0;
    }
    push_up(rt);
}
void update2(int L , int R , int rt , int cnt){
    if(!cnt) return ;
    int len = tree[rt].r - tree[rt].l + 1;
    if(len - tree[rt].sum == cnt){
        tree[rt].sum = len;
        tree[rt].lazy = 1;
        return ;
    }
    push_down(rt);
    int cnt1 = tree[rt << 1].r - tree[rt << 1].l + 1 - tree[rt << 1].sum;
    if(cnt < cnt1) update2(L , R , rt << 1 , cnt);
    else {
        update2(L , R , rt << 1 | 1 , cnt - cnt1);
        tree[rt << 1].sum = tree[rt << 1].r - tree[rt << 1].l + 1;
        tree[rt << 1].lazy = 1;
    }
    push_up(rt);
}
int query(int L , int R , int rt){
    int l = tree[rt].l , r = tree[rt].r;
    if(L <= l && r <= R) return tree[rt].sum;
    push_down(rt);
    int mid = l + r >> 1 , res = 0;
    if(L <= mid) res += query(L , R , rt << 1);
    if(R  > mid) res += query(L , R , rt << 1 | 1);
    return res;
}
signed main(){
    cin >> n >> m;
    build(1 , n , 1);
    while(m --){
        cin >> op >> pos;
        if(!op){
            int cnt0 = n - tree[1].sum; // 整个序列中 0 个个数
            int cnt = max(0 , pos - cnt0); // 1 ~ pos 中 0 的个数
            update1(1 , n , 1 , cnt); // 将最大的 cnt 个 0 改为 1
        }
        else{
            int cnt1 = tree[1].sum;
            int cnt = max(0 , n - pos + 1 - cnt1); // 同上
            update2(1 , n , 1 , cnt);
        }
    }
    for(int i = n ; i >= 1 ; i --) if(!query(i , i , 1)) cout << i << " "; // 输出集合 A
    for(int i = 1 ; i <= n ; i ++) if(query(i , i , 1)) cout << i << " "; // 输出集合 B
    return 0;
}

7.4冰山

7.4.1

#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
signed main(){
  int n , m , k;
  cin >> n >> m >> k;
  vector<int>vec;
  for(int i = 1 ; i <= n ; i ++){
    int x;
    cin >> x;
    vec.push_back(x);
  }
  while(m --){
    int x , y;
    cin >> x >> y;
    for(int i = 0 ; i < vec.size() ; i ++) vec[i] += x;
    vec.push_back(y);
    for(vector<int>::iterator it = vec.begin() ; it != vec.end() ; ) {
      if(*it <= 0) it = vec.erase(it); // 如果值小于等于 0，则删除
      else it ++ ;  
    }
    int cnt = 0; 
    for(int i = 0 ; i < vec.size() ; i ++) if(vec[i] > k) cnt += vec[i] - k , vec[i] = k; // 用 cnt 记录将要添加的 1 的个数
    while(cnt --) vec.push_back(1);
    long long V = 0;
    for(int i = 0 ; i < vec.size() ; i ++) V = (V + vec[i]) % mod;
    cout << V << '\n';
  }
  return 0;
}

7.4.2

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 10 , mod = 998244353;
set<pair<int , int>>se;
map<int , int>mp;
int n , m , k;
signed main(){
    cin >> n >> m >> k;
    for(int i = 1 ; i <= n ; i ++){
        int x;
        cin >> x;
        if(mp.find(x) != mp.end()) se.insert(make_pair(x , 1));
        else {
            se.erase(make_pair(x , mp[x]));
            se.insert(make_pair(x , mp[x] + 1));
        }
        mp[x] ++ ; // mp 用于判断某个数值是否存在
    }
    while(m --){
        int x , y;
        cin >> x >> y;
        set<pair<int , int>>tmp1;
        map<int , int>tmp2;
        // 先将操作的结果保存在 tmp1、tmp2 中，待操作结束后再令 se = tmp1 , mp = tmp2
        int cnt = 0 , tot = 0; // cnt 记录值大于等于 k 的元素的个数， tot 记录即将生成的值为 1 的元素的个数
        for(auto i : se){
            if(i.first + x <= 0) continue ; // 若值小于等于 0 则跳过
            if(i.first + x < k){
                tmp1.insert(make_pair(i.first + x , i.second));
                tmp2[i.first + x] = i.second; 
            }
            else {
                tot += (i.first + x - k) * i.second;
                cnt += i.second;
            }
        }
        if(cnt > 0) tmp1.insert(make_pair(k , cnt));
        if(tot > 0) tmp1.insert(make_pair(1 , tot));
        tmp2[1] = tot , tmp2[k] = cnt;
        if(tmp2.find(y) != tmp2.end()){
            tmp1.erase(make_pair(y , tmp2[y]));
            tmp1.insert(make_pair(y , tmp2[y] + 1));
            tmp2[y] ++ ;
        } else {
            tmp1.insert(make_pair(y , 1));
            tmp2[y] = 1;
        }
        se = tmp1 , mp = tmp2; // 操作结束后
        int ans = 0;
        for(auto i : se) { // 遍历集合，计算答案
            ans += i.first * i.second % mod;
            ans %= mod;
            cout << i.first << " " << i.second << '\n';
        }
        cout << ans << '\n';
    }
    return 0;
}

7.4.3

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 5e5 + 10 , mod = 998244353;
struct FHQ_Tree{
    int l , r , key , lazy = 0;
    int size , sum , val , cnt;
}tree[N];
int root , A , B , Z , tot;
int n , m , k , x , y;
int create(int val , int cnt){
    tree[++ tot].size = cnt;
    tree[tot].cnt = cnt;
    tree[tot].val = val;
    tree[tot].key = rand();
    tree[tot].sum = val * cnt % mod; 
    return tot;
}
void push_up(int rt){
    tree[rt].size = (tree[tree[rt].l].size + tree[tree[rt].r].size + tree[rt].cnt) % mod;
    tree[rt].sum = (tree[tree[rt].l].sum + tree[tree[rt].r].sum + tree[rt].val * tree[rt].cnt % mod + mod) % mod;
}
void push_down(int rt){
    if(tree[rt].lazy){
        int &x = tree[rt].lazy;
        tree[tree[rt].l].lazy += x , tree[tree[rt].r].lazy += x;
        tree[tree[rt].l].val += x , tree[tree[rt].r].val += x;
        tree[tree[rt].l].sum = (tree[tree[rt].l].sum + tree[tree[rt].l].size * x % mod + mod) % mod; 
        tree[tree[rt].r].sum = (tree[tree[rt].r].sum + tree[tree[rt].r].size * x % mod + mod) % mod ;
        x = 0;
    }
}
void split(int rt , int val , int &x , int &y){
    if(!rt) {
        x = y = 0;
        return ;
    }
    push_down(rt);
    if(tree[rt].val <= val){
        x = rt;
        split(tree[rt].r , val , tree[rt].r , y);
    }
    else{
        y = rt;
        split(tree[rt].l , val , x , tree[rt].l);
    }
    push_up(rt);
}
int merge(int x , int y){
    if(!x || !y) return x + y;
    if(tree[x].key > tree[y].key){
        push_down(x);
        tree[x].r = merge(tree[x].r , y);
        push_up(x);
        return x;
    }
    else{
        push_down(y);
        tree[y].l = merge(x , tree[y].l);
        push_up(y);
        return y;
    }
}
void insert(int val , int size){
    split(root , val , A , B);
    root = merge(merge(A , create(val , size)) , B);
}
void update(int x){
    if(!x) return ;
    if(x > 0){
        int val = k - x - 1;
        split(root , val , A , B);
        tree[A].lazy += x , tree[A].val += x;
        tree[A].sum = (tree[A].sum + tree[A].size * x % mod) % mod;
        int cha = (k * tree[B].size % mod - tree[B].sum + mod) % mod;
        int add_cnt = (x * tree[B].size % mod - cha + mod) % mod;
        root = merge(A , create(k , tree[B].size));
        insert(1 , add_cnt);
    }
    else{
        split(root , abs(x) , A , B);
        tree[B].lazy += x , tree[B].val += x;
        tree[B].sum = ((tree[B].sum + tree[B].size * x % mod) % mod + mod) % mod; 
        root = B;
    }
}
signed main(){
    cin >> n >> m >> k;
    for(int i = 1 ; i <= n ; i ++) {
        cin >> x;
        insert(x , 1);
    }
    while(m --){
        cin >> x >> y;
        update(x);
        if(y) insert(y , 1);
        cout << tree[root].sum << '\n';
    }
    return 0;
}