写在前面：
省赛选手，省银（邀请铜尾），前面猛猛掉分，最后的 $G$ 还一直没开出来，图论想到死都没开出来，结果赛后一看是 $DP$

省赛牛魔不配有和牌的合照
补题连接

# A

# 题目大意

算 $(a+b+c) * d$

# 题解

C++

void solve () {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << (a + b + c) * d << endl;
}

# D

# 题目大意

现在有一个长方体，两个顶点分别位于 $(0,0,0)$ 和 $(a,b,c)$
有 $n$ 藤蔓，分别从 $(x_1,y_1,z_1)$ 到 $(x_2,y_2,z_2)$
你现在可以发动一攻击，任意从垂直 $x,y,z$ 轴的任意位置发动，切断与这一个截面相交的所有藤蔓
请问你最多切断多少条藤蔓？
（只需要考虑长方体内即可）

# 数据范围

$1 \le n \le 10^5$
$1 \le a,b,c \le 10^9$

# 题解

这题其实可以考虑成，在 $x,y,z$ 三个方向上的， 最多重复字段数 ，取最大即可

# 写法 1 - 贪心

这是我们队赛时的写法，利用贪心 + 优先队列，跑三遍最多重叠的区间数量
注意要按左端点排序（ while 条件里是 heap.top() < v[i].first ）

C++

int n, a, b, c;

bool cmp(PII x, PII y) {
    return x.first < y.first;
}

int getRes(vector<PII>& v) {
    sort(v.begin(), v.end(), cmp);
    int res = 0;

    priority_queue<int, vector<int>, greater<int>> heap;
    for (int i = 0; i < v.size(); i++) {
        int t = 0;
        while (heap.size() && heap.top() < v[i].first)
            heap.pop();
        heap.push(v[i].second);
        res = max(res, int(heap.size()));
    }

    return res;
}

void solve () {
    cin >> n >> a >> b >> c;
    vector<PII> x, y, z;
    for (int i = 1; i <= n; i++) {
        int x1, y1, z1, x2, y2, z2;
        cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2;
        if (x1 >= x2)   swap(x1, x2);
        if (y1 >= y2)   swap(y1, y2);
        if (z1 >= z2)   swap(z1, z2);

        x.push_back({max(0, x1), min(a, x2)});
        y.push_back({max(0, y1), min(b, y2)});
        z.push_back({max(0, z1), min(c, z2)});
    }

    cout << max({getRes(x), getRes(y), getRes(z)}) << endl;
}

# 写法 2 - 离散化差分

利用 map 自动排序的特性，进行离散化差分

C++

void solve () {
    map<int, int> mp;

    cin >> n >> a >> b >> c;
    mp[a] = mp[b] = mp[c] = 0;

    vector<array<int, 6>> t(n + 1);

    for (int i = 1; i <= n; i++) {
        for (auto& tt : t[i])
            cin >> tt;
        auto &[x1, y1, z1, x2, y2, z2] = t[i];

        if (x1 >= x2)   swap(x1, x2);
        if (y1 >= y2)   swap(y1, y2);
        if (z1 >= z2)   swap(z1, z2);

        mp[x1] = mp[x2] = mp[y1] = mp[y2] = mp[z1] = mp[z2] = 0;
    }

    int idx = 0;
    for (auto& [t1, t2] : mp)
        t2 = ++idx;

    vector<int> cfx(idx + 2), cfy(idx + 2), cfz(idx + 2);
    
    for (int i = 1; i <= n; i++) {
        auto &[x1, y1, z1, x2, y2, z2] = t[i];
        cfx[mp[x1]]++, cfx[mp[x2] + 1]--;
        cfy[mp[y1]]++, cfy[mp[y2] + 1]--;
        cfz[mp[z1]]++, cfz[mp[z2] + 1]--;
    }

    int res = 0;
    for (int i = 1; i <= idx; i++) {
        cfx[i] += cfx[i - 1], cfy[i] += cfy[i - 1], cfz[i] += cfz[i - 1];
        res = max({res, cfx[i], cfy[i], cfz[i]});
    }

    cout << res << endl;
}

# M

# 题目大意

现在小 $A$ 和小 $B$ 在玩抛硬币游戏，一共有 $n$ 枚最初都是正面朝上的硬币。现在他们有一个数字 $k$ ，小 $A$ 把 $k$ 枚硬币翻转成反面朝上了，但是小 $B$ 不知道有哪些硬币是被翻转了的，小 $B$ 需要对每枚硬币执行下面四种操作中的一种

放入第一堆
翻转后放入第一堆
放入第二堆
翻转后放入第二堆

若把所有硬币放完后，两堆硬币中，正面朝上的数量相同，则小 $B$ 赢游戏（允许某一堆硬币数为 $0$ ）
你现在要输出一个操作序列，使得对于小 $A$ 的任意翻转顺序，小 $B$ 都能赢

# 数据范围

$1 \le n \le 10^4$

# 题解

题目最终是要两堆操作后正面向上硬币相同，不妨列出以下表格

	第一堆	第二堆
总数	$k$	$n-k$
选取到的反面个数	$x$ （假设）	$k-x$
选取到的正面硬币个数	$k-x$	$n-2*k+x$

我们可以发现，此时，第一堆的选取到的正面硬币个数 = 第二堆的选取到的反面硬币个数，所以我们只需要， $k$ 个硬币选 1. 操作放入第一堆， $n-k$ 个硬币选 4. 操作放入第二堆，即可实现题目要求

C++

void solve() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= k; i++)
        cout << 1;
    for (int i = k; i < n; i++)
        cout << 4;
    cout << endl;
}

# F

# 题目大意

对于小 $A$ ，在接下来的 $n$ 天中，若在第 $i$ 天摄入了 $r_i$ 卡路里，消耗了 $c_i$ 克质量，那么他的能量损失是

$c_i=p \times c_{i-1}+(1-p) \times r_{i-1}$

其中， $r_0,c_0,p$ 已知
但是，小 $A$ 在这 $n$ 天中，有 $k$ 天的放纵日，这 $k$ 天的卡路里摄入量是预定的

除了放纵日的摄入，其余天的卡路里摄入量必须在 $[L,R]$ 范围内
请你安排不是放纵日的日子，使得接下来 $n$ 天的总能量损失最大，即 $max \sum\limits_{i=1}^n(c_i-r_i)$

# 输入格式

第一行包含两个整数 $n$ 和 $k$ ，表示未来有 $n$ 天， $k$ 天有预定摄入量
第二行包含五个实数 $r_0,c_0,p,L,R$
接下来 $k$ 行，每行有一个整数 $p_i$ 和一个实数 $v_i$ ，表示 $r_{p_i}$ 是 $v_i$

# 数据范围

$1 \le k \le n \le 10^5$
$1 \le n \le 2 \times 10^5$
$1 \le L \le r_0 \le R \le 10^9$
$0 < p < 1$
$1 \le c_0 \le 1 \times 10^9$

# 题解

根据题目给出的公式有

$c_i-r_i=p \times c_{i-1}+(1-p) \times r_{i-1}-r_i$

求和有

$\sum\limits_{i=1}^{n}{(c_i-r_i)}=\sum\limits_{i=1}^{n}{(p \times c_{i-1} + (1-p) \times r_{i-1} - r_i)}$

展开有

$\sum\limits_{i=1}^{n}{(c_i-r_i)}=p \times \sum\limits_{i=1}^{n}{(c_{i-1}-r_{i-1})}+ \sum\limits_{i=1}^{n}{r_{i-1}}-\sum\limits_{i=1}^{n}{r_i}$

移项并合并同类项有

$(1-p) \times \sum\limits_{i=1}^{n}{(c_i-r_i)}= [p\times c_0 + (1-p) \times r_0] - [p \times c_n-(1-p) \times r_n]=c_1 - c_{n+1}$

即

$\sum\limits_{i=1}^{n}{(c_i-r_i)} = \frac{c_1-c_{n+1}}{1-p}$

因为答案是求 $max \sum\limits_{i=1}^n(c_i-r_i)$ ，所以我们只需要让 $c_{n+1}$ 最小即可，又因为

$c_i=p \times c_{i-1} + (1-p) \times r_{i-1}$

故我们每次只当没有指定的时候，让 $r_{i-1}$ 取最小值 $L$ 即可

C++

double r0, c0, p, L, R, day, v;

void solve () {
    int n, k;
    cin >> n >> k;
    cin >> r0 >> c0 >> p >> L >> R;

    map<int, double> mp;
    for (int i = 0; i < k; i++) {
        cin >> day >> v;    // 表示第 day 天摄入了 v 卡路里
        mp[day] = v;
    }

    double c1 = p * c0 + (1 - p) * r0;
    double cn = c1;
    for (int i = 2; i <= n + 1; i++) {
        if (!mp.count(i - 1))
            cn = p * cn + (1 - p) * L;
        else
            cn = p * cn + (1 - p) * mp[i - 1];
    }

    printf("%.10lf\n", (c1 - cn) / (1 - p));
}

# K

# 题目大意

你有 $n$ 个箭头，箭头可以朝向 ↑ ↓ ← → 四个方向，你有两种操作

选中一个箭头，选中的箭头方向不变，其他箭头顺时针旋转 $90°$
所有箭头顺时针旋转 $90°$

给定各个箭头初始时的朝向，如果要使所有箭头朝向变为 ↑ ，最少需要操作多少次？

# 数据范围

$1 \le n \le 10^6$

# 题解

初始方向第 $i$ 个指向 $a_i$
操作 1. 相当于，当前这个选中的第 $i$ 的箭头逆时针旋转，即 -1 操作，但进行一次操作 $1$ ，会给全局带来一个 +1 的偏移量，所以我们可以暴力计算四个方向 0 1 2 3 ，先统一 $n$ 个箭头的方向，记操作数为 $b_i$
此时， $n$ 个箭头的绝对指向是 $(i + b_i) \% 4$ ，所以我们只需要进行 (4 - (i + b[i]) % 4) % 4 次 2. 操作，即可将所有箭头都转至 $0$
故，最终答案是 b[i] + (4 - (i + b[i]) % 4) % 4

C++

void solve () {
    cin >> n;
    vector<int> a(n), b(4);

    for (auto& t : a)
        cin >> t;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < 4; j++)
            b[j] += (a[i] - j + 4) % 4;

    int res = 1e18;
    for (int i = 0; i < 4; i++)
        res = min(res,  b[i] + (4 - (b[i] + i) % 4) % 4);

    cout << res << endl;
}

写题目的时候，要注重相对和整体系统的概念，比如此题中的操作 $1$ ，它会使得选中的那个箭头，相对全局 $-1$ ，但是不要忽略了，他对系统整体方向 $+1$ 的影响，最终考虑方向的时候要把这个 $+1$ 考虑进去

以上五题是赛时开的题目，下面是赛后补的题

# G

# 题目大意

有一个 $n$ 个点 $m$ 条单向边的图
一开始，你有体力 $x$ ，当你通过一条长为 $d$ 的边时，你的体力会变成 $\lfloor{\frac{x}{d}}\rfloor$ ，当你的体力变为 $0$ 的时候，代表体力耗尽，你将不再继续探索
现在有 $Q$ 个问题，对于第 $i$ 个问题，请问，若从 $p_i$ 点开始，初始体力为 $x$ ，若想让体力耗尽，则最少要走多少条边？

# 数据范围

$1 \le n, Q \le 2 \times 10^5$
$n \le m \le 5 \times 10^5$
$1 \le u, v \le n, 2 \le d \le 10^9$
$1 \le x \le 10^9$

# 题解

这个题目的核心是，把走若干条边的除法转换为了 $d_1 \times d_2 \times ... \times d_{...} > x$

定义 $DP$ 为 dp[i][j] 表示从 $j$ 点出发，经过 $i$ 步后，消耗乘积的最大值

$dp[i][u] = max\{d_{u \to v_1} \times ... \times d_{v_{i-1} \to v_{i}}\}$

那么状态转移方程为

$dp[i][u] = \max_{(u \to v) \in E} \left( dp[i - 1][v] \times d_{u \to v} \right)$

$x$ 最大值是 $10^9$ ，在 $30$ 次内便可以除完

C++

int n, m, q, p, x;
vector<PII> g[N];

void solve () {
    cin >> n >> m >> q;
    for (int i = 1, u, v, w; i <= m; i++)
        cin >> u >> v >> w, g[u].push_back({v, w});

    vector<vector<int>> dp(31, vector<int>(n + 1, 1));
    for (int i = 1; i <= 30; i++) {
        vector<int> tmp(n + 1, 1);

        for (int u = 1; u <= n; u++) {
            // 最大是 1e9，也就是说，如果超出了 1e9 就没必要更新了，这是小小的优化
            // if (dp[i - 1][u] >= 1e9)
            //     continue;

            for (auto &[v, w] : g[u])
                tmp[u] = max(tmp[u], dp[i - 1][v] * w);
        }

        dp[i] = tmp;
    }

    while (q--) {
        cin >> p >> x;

        for (int i = 1; i <= 30; i++)
            if (dp[i][p] > x) {
                cout << i << endl;
                break;
            }
    }
}

对于这种超大数据范围的图论题、最短路 / $DFS$ / $BFS$ 走不通的题目
其实基本上不用考虑图论里的算法了，可以考虑下 $DP$ ，特别是这种走若干步的，基本上不太可能 $DFS$ / $BFS$ 了
如果题目出现连除下取整，考虑转换为乘法 + $DP$ 去做

# I

# 题目大意

我一天有 $n$ 个时间段，一个字符串 $s$ 描述我的日程安排

$s_i = 1$ 表示我在 $i$ 时间段很忙
$s_i = 0$ 表示我在 $i$ 时间段有空

现在我必须执行一次这个操作：

选择一个范围 $[l, r]$ ， $l \to r$ 有 $k$ 个时间段很忙（ $k$ 是一个确定的常数）
选择后，任意修改 $l \to r$ 的忙 / 闲状态，但是你需要保证的是，修改后 $l \to r$ 中，忙的时间段的数量和修改前是一样的

请问，我最多可以得到多少个不同的时间表？答案很大，需模 $998244353$

# 数据范围

$1 \le n \le 10^5$

# 题解

需要预处理的数据

fac[i] ：表示 $i$ 的阶层
inv[i] ：表示 $i$ 的阶层的逆元
suf[i] ：表示 $i$ 位置后连续的 $0$ 的长度

因为操作只能做一次，我们可以用双指针滑动窗口找满足 $1$ 的个数恰好是 $k$ 的区间
对于一个合法的操作窗口，我们的答案累加上

$C_{(r - l + 1) + \text{suf}_i}^{k}$

代表从 窗口 + 窗口后连续的 1 进行排列组合，选取 $k$ 个位置放 $1$
用一个 $flag$ 标记是否是第一次操作滑动窗口，如果不是第一次操作滑动窗口，则还需要去重，需要减去

$C_{r-l}^{k-1}$

为什么要减？
- 因为 新窗口 = 旧窗口 + 下面新延伸到的第一个 1
- 而对于保持新延伸到的 $1$ 不变的方案，是之前重复了的
- 所以需要减去，最后一个 $1$ 确定放在最后一个位置，前面的 $k - 1$ 个 $1$ 在 $r-l$ 区间中随机放的方案数

C++

const int N = 1e5 + 5, MOD = 998244353;

// fac[i] 是 i 的阶层，inv[i] 是 i! 的逆元
vector<int> fac(N), inv(N);

int qmi(int a, int b) {
    int res = 1;

    while (b) {
        if (b & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }

    return res;
}

// 组合数 cal(n, k)
int cal(int n, int k) {
    return fac[n] * inv[k] % MOD * inv[n - k] % MOD;
}

void solve() {
    int n, k;
    string s;
    cin >> n >> k >> s;
    s = " " + s;

    // suf[i] = 从 i 往后连续的 0 的长度
    vector<int> suf(n + 2, 0);
    int cur = 0;

    for (int i = n; i >= 1; i--) {
        cur += (s[i] == '0');
        suf[i] = cur;
        
        if (s[i] == '1')
            cur = 0;
    }

    int ans = 0, cnt = 0;
    bool flag = false;

    for (int l = 1, r = 1; r <= n; r++) {
        if (s[r] == '1') {
            cnt++;

            while (l <= r && cnt > k) {
                if (s[l] == '1')
                    cnt--;
                l++;
            }

            if (cnt == k) {
                // [l..r] 最小窗口里正好 k 个 1，
                // 把所有以 r 开始后面接 0 的区间一次性加上：
                // 长度 = (r-l+1) + suf[r]
                ans = (ans + cal((r - l + 1) + suf[r], k)) % MOD;

                // 从第二个“合法窗口”开始，每次减掉 cal(r-l, k-1) 去重
                if (!flag)
                    flag = true;
                else
                    ans = (ans - cal(r - l, k - 1) + MOD) % MOD;
            }
        }
    }

    if (k == 0)
        ans = 1;

    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    fac[0] = 1;
    for (int i = 1; i < N; i++)
        fac[i] = fac[i - 1] * i % MOD;

    inv[N - 1] = qmi(fac[N - 1], MOD - 2);
    for (int i = N - 2; i >= 0; i--)
        inv[i] = inv[i + 1] * (i + 1) % MOD;

    int _ = 1;
    cin >> _;

    while (_--)
        solve();
    
        return 0;
}

# E

# 题目大意

定义一个 $k$ 折叠字符串的概念

当且仅当存在一个字符串 $t$ ，使得 $s = t^k$ ，即 $t$ 重复连续 $k$ 次恰好形成 $s$

对于给定的字符串 $S$ ，每个查询给出正整数 $x$ 和 $y$ ，请问有多少对正整数 $l, r$ 满足

$x \le l < r \le y$
$S_{[l, R]}$ 可以重排成 $k$ 折叠字符串

你需要回答 $q$ 个查询

# 数据范围

$1 \le n, k, q \le 3 \times 10^5$
时间限制 $3~seconds$

# 题解

重排字符串很容易能理解成，对于 $S_{[l, r]}$ ，其内部所有字符的出现次数，都能被 $k$ 整除

我们统计一个 vector<int> cnt(26) 计算各个位置上的字符个数（均为对 $k$ 取模后的值）
那么，如果遍历到 $i$ 时候计算得到的 $cnt_i$ 和遍历到 $j$ 得到的 $cnt_j$ 数组完全相同的话（ $i < j$ ），那么即说明， $S_{[i+1, j]}$ 是 $k$ 折叠字符串
可以把第 $i$ 个位置的 vector<int> cnt(26) 哈希至 hash[i]

所以原问题被转换为，对于每个查询 $(x,y)$ ，能找到多少对 $(i, j)$ 满足

$x - 1 \le i < j \le y$
hash[i] == hash[j]

为了方便描述解释，此处先给出代码

cpp

int n, k, q, idx, res;
string s;
vector<int> pos(N);
vector<int> c;

struct Md {
    int l, r, id;
};

void add(int x) {
    res += c[x];
    c[x]++;
}

void sub(int x) {
    c[x]--;
    res -= c[x];
}

void solve() {
    cin >> n >> k >> q;
    cin >> s, s = " " + s;
    int len = sqrt(n);

    vector<int> cnt(26, 0);
    map<vector<int>, int> mp;
    vector<int> hash(n + 1);
    mp[cnt] = 0;

    for (int i = 1; i <= n; i++) {
        cnt[s[i] - 'a']++, cnt[s[i] - 'a'] %= k;

        if (!mp.count(cnt))
            mp[cnt] = ++idx;

        hash[i] = mp[cnt], pos[i] = i / len;
    }

    c = vector<int>(idx + 1, 0);

    vector<Md> md(q + 1);
    for (int i = 1; i <= q; i++)
        cin >> md[i].l >> md[i].r, md[i].id = i;

    // 按所在块和右端点排序
    sort(md.begin() + 1, md.begin() + q + 1, [](const Md &a, const Md &b) {
        return pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l];
    });

     

    // 答案数组
    vector<int> ans(q + 1);

    // 维护已知区间的左端点和右端点
    int cl = 0, cr = 0;
    add(hash[0]);

    for (int i = 1; i <= q; i++) {
        auto &que = md[i];
        int l = que.l - 1, r = que.r, id = que.id;
        cout << "l: " << l << ", r: " << r << ", id: " << id << endl;
        while (cl > l) add(hash[--cl]);
        while (cr < r) add(hash[++cr]);
        while (cl < l) sub(hash[cl++]);
        while (cr > r) sub(hash[cr--]);

        ans[id] = res;
    }

    for (int i = 1; i <= q; i++)
        cout << ans[i] << endl;
}

如何理解两个关键函数 add 和 sub ?

C++

void add(int x) {
    res += c[x];
    c[x]++;
}

void sub(int x) {
    c[x]--;
    res -= c[x];
}

分别以右边加一个值和左边减一个值为例，进行说明

我们的目的是找对于给定的 $[x, y]$ 中，能找到多少个 $(i,j)$ 满足 $x-1 \le i < j \le y$ 并且 hash[i] == hash[j]
直接暴力计算是肯定不行的，我们可以考虑利用桶来计数，用 $c[hash[t]]$ 计算已有的 $hash[t]$ 出现次数，那么当新出现一个 $hash[t]$ 的时候，它可以和前面已经有的 $hash[t]$ 组成 $k$ 折叠字符串，也就是可以加上 $c[hash[t]]$
而在莫队的过程中
- 当右边加上一个值时（假计下标为 $t$ ），也就是说，加上 $t$ 位置后，多了一个 hash[t] ，这个新的 hash[t] 可以和前面已经有的 hash[t] 组成 $k$ 折叠序列，所以应该先让 $res$ 加上已有的 c[hash[t]] 再让 c[hash[t]]++
- 当左边减去一个值时（假计下标为 $t$ ），也就是说，减去 $t$ 位置后，少了一个 hash[t] ，而借鉴前面的加上一个值的过程，实际上 $k$ 折叠字符串其实是少了 c[hash[t]] - 1 个，所以我们先让 c[hash[t]]-- ，再让答案 $res$ 减去 c[hash[t]]

为什么要先 add(hash[0]) ?
因为我们查询的是在区间 [x - 1, y] 中，这样的 (i, j) 对有多少个满足 i < j 并且 hash[i] == hash[j] ，那么一开始 hash[0] 也要被加入进去，因为 cnt{0, 0, ..., 0} 对于后面 $26$ 个字母全部都出现 $ik$ 次，实际上是一个前缀，也就是说 hash[0] 要被第一个加入，即使可能很少被运算到

贪心图论小学数学 DP 预处理逆元差分离散化莫队桶哈希

# A

# 题目大意

# 题解

# D

# 题目大意

# 数据范围

# 题解

# 写法 1 - 贪心

# 写法 2 - 离散化差分

# M

# 题目大意

# 数据范围

# 题解

# F

# 题目大意

# 输入格式

# 数据范围

# 题解

# K

# 题目大意

# 数据范围

# 题解

# G

# 题目大意

# 数据范围

# 题解

# I

# 题目大意

# 数据范围

# 题解

# E

# 题目大意

# 数据范围

# 题解

SQL数据库操作

2024蓝桥杯国赛B组