推荐

GESP C++ 六级历年真题题解

_Separation 2026-5-17 20:30:02 19 浏览 0 点赞 0 收藏
#GESP

GESP C++ 六级历年真题题解

1. 下楼梯

题目大意

一共有 NN 个台阶，每一步可以走 11 个、22 个或 33 个台阶。求走完 NN 个台阶共有多少种不同方案。

解题思路

设 fif_i 表示走到第 ii 个台阶的方案数。

最后一步可能来自：

  • 第 i−1i-1 个台阶；
  • 第 i−2i-2 个台阶；
  • 第 i−3i-3 个台阶。

因此：

fi=fi−1+fi−2+fi−3f_i=f_{i-1}+f_{i-2}+f_{i-3}

初始化：

f0=1f_0=1

表示一个台阶都不走有 11 种方案。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
LL f[N];
int n;
inline void solve() {
    cin >> n;
    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        if (i - 1 >= 0) f[i] += f[i - 1];
        if (i - 2 >= 0) f[i] += f[i - 2];
        if (i - 3 >= 0) f[i] += f[i - 3];
    }
    printf("%lld\n", f[n]);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

2. 亲朋数

题目大意

给定一个数字串 SS 和正整数 pp，统计 SS 的所有连续子串中，有多少个子串对应的整数是 pp 的倍数。子串允许有前导零，相同内容但位置不同的子串算不同子串。

解题思路

设 cnt[r]\text{cnt[r]} 表示当前处理到某个位置之前，所有 以当前位置前一位结尾 的子串中，模 pp 余数为 rr 的个数。

读入新数字 dd 后：

  1. 单独由 dd 组成一个新子串；
  2. 之前所有子串后面接上 dd，新余数变为：
(r×10+d) mod p(r \times 10+d)\bmod p

每处理一位，就把当前余数为 00 的子串数量加入答案。

因为 p≤128p \le 128，所以每个字符枚举所有余数即可。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int p;
string s;
LL cnt[N], tmp[N];
inline void solve() {
    cin >> p >> s;
    LL Ans = 0;
    for (char ch : s) {
        int d = ch - '0';
        for (int i = 0; i < p; i++) tmp[i] = 0;
        tmp[d % p]++;
        for (int r = 0; r < p; r++) {
            int nr = (r * 10 + d) % p;
            tmp[nr] += cnt[r];
        }
        Ans += tmp[0];
        for (int i = 0; i < p; i++) cnt[i] = tmp[i];
    }
    printf("%lld\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

3. 小杨买饮料

题目大意

有 NN 种饮料，每种饮料最多买一瓶。第 ii 种饮料价格为 cic_i，容量为 lil_i。小杨希望购买的总容量不低于 LL，并且花费最少。如果无法满足要求，输出 no solution\texttt{no solution}。

解题思路

这是一个 0/10/1 背包问题。

设 dpjdp_j 表示买到总容量为 jj 时的最小花费。因为只关心是否达到 LL，所以容量超过 LL 的都压缩成 LL。

对于每瓶饮料，倒序更新：

$$dp_{\min(L,j+l_i)}=\min(dp_{\min(L,j+l_i)},dp_j+c_i) $$

最后如果 dpLdp_L 仍然是无穷大，说明无解。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
const LL inf = 4e18;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, L;
LL dp[N];
inline void solve() {
    cin >> n >> L;
    for (int i = 0; i <= L; i++) dp[i] = inf;
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        LL c, l; cin >> c >> l;
        for (int j = L; j >= 0; j--) {
            if (dp[j] == inf) continue;
            int nj = min((LL)L, j + l);
            dp[nj] = min(dp[nj], dp[j] + c);
        }
    }

    if (dp[L] == inf) printf("no solution\n");
    else printf("%lld\n", dp[L]);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

4. 小杨的握手问题

题目大意

有 NN 名同学，学号为 00 到 N−1N-1。他们按给定顺序进入教室。每位同学进入时，会和已经在教室内且学号小于自己的同学握手。求总握手次数。

解题思路

对于当前进入的同学 xx，他要和之前已经进入且学号小于 xx 的同学握手。

所以问题变成：对每个位置，统计它前面有多少个数比它小，逆序对 变形问题。

可以用树状数组维护已经出现过的学号。

由于学号从 00 开始，树状数组下标用 x+1x+1。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
LL tr[N];
void add(int x, int v) {
    for (; x <= n + 2; x += x & -x) tr[x] += v;
}
LL sum(int x) {
    LL s = 0;
    for (; x; x -= x & -x) s += tr[x];
    return s;
}
inline void solve() {
    cin >> n;
    LL Ans = 0;
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        Ans += sum(x);
        add(x + 1, 1);
    }
    printf("%lld\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

也可以用 归并排序 解决，不过和普通的 逆序对 相比，需要使用降序排序。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
LL a[N], tmp[N];
LL invs(int l, int r) {
    if (l >= r) return 0;
    int mid = l + (r - l) / 2;
    LL Ans = 0;
    Ans += invs(l, mid);
    Ans += invs(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] >= a[j]) { // 重点修改这个位置
            tmp[k++] = a[i++];
        } else {
            Ans += (mid - i + 1);
            tmp[k++] = a[j++];
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (int p = l; p <= r; p++) a[p] = tmp[p];
    return Ans;
}
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    printf("%lld\n", invs(1, n));
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

5. 闯关游戏

题目大意

游戏有 NN 关，每关有 MM 个通道。第 ii 个通道可以前进 aia_i 关。离开第 ss 关时，可以获得 bsb_s 分。如果从某关前进后位置不小于 NN，则通关。求从第 00 关开始通关时最多能获得多少分。

解题思路

这是一个有向无环图上的动态规划，因为每次只能向后跳。设 dpidp_i 表示到达第 ii 关之前最多已经获得多少分。

从第 ii 关离开时，会获得 bib_i 分，然后跳到 i+aji+a_j。如果跳出范围，就更新答案；否则更新后续关卡。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
const LL inf = 4e18;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m;
int a[110];
LL b[N], dp[N];
inline void solve() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    
    for (int i = 0; i <= n; i++) dp[i] = -inf;
    dp[0] = 0;
    LL Ans = -inf;
    for (int i = 0; i < n; i++) {
        if (dp[i] == -inf) continue;
        for (int j = 1; j <= m; j++) {
            int to = i + a[j];
            LL val = dp[i] + b[i];
            if (to >= n) Ans = max(Ans, val);
            else dp[to] = max(dp[to], val);
        }
    }
    printf("%lld\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

6. 工作沟通

题目大意

公司有 NN 名员工，00 号是老板。每名员工除了自己以外，还可以被自己的直接领导和间接领导管理。每次给出若干参与合作的员工，要求找一个能够管理所有参与者的员工；如果有多个，输出编号最大的。

解题思路

因为 N≤300N \le 300，可以直接预处理祖先关系。

设 can[x][y] = 1\text{can[x][y] = 1} 表示员工 xx 可以管理员工 yy。

对于每个员工 yy，从 yy 不断向父亲走到根，沿途所有节点都可以管理 yy。

每次询问枚举所有候选员工 xx，检查它是否能管理所有参与者，取编号最大者。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, q;
int fa[310], can[310][310];
inline void solve() {
    cin >> n;
    fa[0] = -1;
    for (int i = 1; i < n; i++) cin >> fa[i];
    for (int y = 0; y < n; y++) {
        int x = y;
        while (x != -1) {
            can[x][y] = 1;
            x = fa[x];
        }
    }
    cin >> q;
    while (q--) {
        int m;
        cin >> m;
        vector<int> v(m);
        for (int i = 0; i < m; i++) cin >> v[i];
        int Ans = 0;
        for (int x = 0; x < n; x++) {
            bool ok = true;
            for (int y : v) {
                if (!can[x][y]) {
                    ok = false;
                    break;
                }
            }
            if (ok) Ans = max(Ans, x);
        }
        printf("%d\n", Ans);
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

7. 游戏

题目大意

给定 n,a,b,cn,a,b,c。每次操作可以把当前 nn 减去 aa 或减去 bb。当 n≤cn\le c 时游戏结束。求不同操作序列的数量，答案对 109+710^9+7 取模。如果 a=ba=b，两种操作也认为不同。

解题思路

设 fxf_x 表示当前数为 xx 时，之后能够形成的操作序列数量。

如果 x≤cx\le c，游戏已经结束，只有空操作序列一种：

fx=1f_x=1

如果 x>cx > c：

fx=fx−a+fx−bf_x=f_{x-a}+f_{x-b}

当 x−a≤cx-a\le c 或 x−b≤cx-b\le c 时，对应部分也算作一种结束方式。

为了处理下标小于 00 的情况，转移时若减完后 ≤c\le c，直接贡献 11。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
const LL mod = 1e9 + 7;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, a, b, c;
LL f[N];
LL get(int x) {
    if (x <= c) return 1;
    return f[x];
}
inline void solve() {
    cin >> n >> a >> b >> c;
    for (int i = 0; i <= c; i++) f[i] = 1;
    for (int i = c + 1; i <= n; i++) f[i] = (get(i - a) + get(i - b)) % mod;
    printf("%lld\n", f[n]);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

8. 好斗的牛

题目大意

有 nn 头牛，每头牛有左攻击范围 aia_i 和右攻击范围 bib_i。若某头牛左边 aia_i 个牛棚或右边 bib_i 个牛棚内有其他牛，它就会挑事。现在要保留一段连续牛棚，并把所有牛放进去，使得没有牛会挑事。求最少需要保留多少个牛棚。

解题思路

n≤9n \le 9，可以枚举牛的排列顺序。

如果牛 uu 放在牛 vv 左边并且相邻，那么它们之间的距离至少要满足：

d>bud > b_u

同时也要满足：

d>avd > a_v

所以最小距离为：

max⁡(bu,av)+1\max(b_u,a_v)+1

对于某个排列，最小保留长度为：

1+∑i=1n−1(max⁡(bpi,api+1)+1)1+\sum_{i=1}^{n-1}(\max(b_{p_i},a_{p_{i+1}})+1)

枚举所有排列取最小值。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
const LL inf = 4e18;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
int a[20], b[20], p[20];
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 1; i <= n; i++) p[i] = i;
    LL Ans = inf;
    do {
        LL len = 1;
        for (int i = 1; i < n; i++) {
            int u = p[i];
            int v = p[i + 1];
            len += max(b[u], a[v]) + 1;
        }
        Ans = min(Ans, len);
    } while (next_permutation(p + 1, p + n + 1));
    printf("%lld\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

9. 计算得分

题目大意

给定计分序列 a1,a2,…,ana_1,a_2,\ldots,a_n 和一个字符串。若一个子串由 kk 个 abc\texttt{abc} 首尾相接组成，则这个子串可以获得 aka_k 分。每个字符最多只能被一个计分子串使用。求最大总得分。

解题思路

设 dpidp_i 表示只考虑字符串前 ii 个字符时的最大得分。

对于位置 ii：

  1. 可以跳过当前字符：
dpi+1=max⁡(dpi+1,dpi)dp_{i+1}=\max(dp_{i+1},dp_i)
  1. 如果从 ii 开始的长度为 3k3k 的子串是 abc\texttt{abc} 重复 kk 次，那么：
dpi+3k=max⁡(dpi+3k,dpi+ak)dp_{i+3k}=\max(dp_{i+3k},dp_i+a_k)

由于 n≤20n\le 20，每个位置最多尝试 2020 种长度即可。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m;
LL a[30], dp[N];
string s;
bool ok(int st, int k) {
    if (st + 3 * k > m) return false;
    for (int i = 0; i < 3 * k; i++) {
        char need = "abc"[i % 3];
        if (s[st + i] != need) return false;
    }
    return true;
}
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> m >> s;
    for (int i = 0; i <= m; i++) dp[i] = 0;
    for (int i = 0; i < m; i++) {
        dp[i + 1] = max(dp[i + 1], dp[i]);
        for (int k = 1; k <= n; k++) {
            if (ok(i, k)) {
                dp[i + 3 * k] = max(dp[i + 3 * k], dp[i] + a[k]);
            }
        }
    }
    printf("%lld\n", dp[m]);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

10. 二叉树

题目大意

给定一棵以 11 为根的二叉树，每个节点初始为黑色或白色。每次操作选择一个节点，将它的整棵子树颜色反转。求所有操作完成后每个节点的最终颜色。

解题思路

子树操作可以转化为 DFS\text{DFS} 序上的区间操作。

先对树做 DFS\text{DFS}，得到每个节点子树对应的区间：

[tinu,toutu][tin_u,tout_u]

每次反转子树 uu，就相当于对区间 [tinu,toutu][tin_u,tout_u] 异或 11。

用差分数组维护：

tag[tin[u]] ^= 1;
tag[tout[u] + 1] ^= 1;

最后按 DFS\text{DFS} 序做前缀异或，就能知道每个节点被反转了几次。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, q, tim;
vector<int> g[N];
int tin[N], tout[N], id[N], tag[N], val[N];
string s;
inline void solve() {
    cin >> n;
    for (int i = 2; i <= n; i++) {
        int f;
        cin >> f;
        g[f].push_back(i);
    }
    cin >> s;
    stack<pair<int, int> > st;
    st.push({1, 0});
    while (!st.empty()) {
        int u = st.top().first;
        int op = st.top().second;
        st.pop();
        if (op == 0) {
            tin[u] = ++tim;
            id[tim] = u;
            st.push({u, 1});
            for (int i = (int)g[u].size() - 1; i >= 0; i--) {
                st.push({g[u][i], 0});
            }
        } else {
            tout[u] = tim;
        }
    }
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        tag[tin[x]] ^= 1;
        tag[tout[x] + 1] ^= 1;
    }
    int cur = 0;
    for (int i = 1; i <= n; i++) {
        cur ^= tag[i];
        int u = id[i];
        val[u] = (s[u - 1] - '0') ^ cur;
    }
    for (int i = 1; i <= n; i++) {
        printf("%d", val[i]);
    }
    printf("\n");
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

11. 小杨和整数拆分

题目大意

给定正整数 nn，要把它拆分成若干个完全平方数之和，求需要的完全平方数的最少数量。

解题思路

这是完全背包模型。

设 dpidp_i 表示凑出整数 ii 所需的最少完全平方数个数。

初始化：

dp0=0dp_0=0

枚举所有完全平方数 j2j^2，进行完全背包转移：

dpi=min⁡(dpi,dpi−j2+1)dp_i=\min(dp_i,dp_{i-j^2}+1)

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, inf = 1e9;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
int dp[N];
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) dp[i] = inf;
    dp[0] = 0;
    for (int x = 1; x * x <= n; x++) {
        int v = x * x;
        for (int i = v; i <= n; i++) {
            dp[i] = min(dp[i], dp[i - v] + 1);
        }
    }
    printf("%d\n", dp[n]);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

12. 算法学习

题目大意

小杨要学习 mm 种算法。第 ii 道题对应知识点 aia_i，能让该算法掌握程度增加 bib_i。每道题最多学一次。要求每种算法掌握程度至少为 kk，并且学习顺序中不能连续学习两道相同知识点的题。

求最少学习多少道题；如果不可能，输出 −1-1。

解题思路

先对每种算法分别处理。

对于某种算法，为了用尽量少的题达到 kk，应该优先选择提升值最大的题。于是把每类题的 bib_i 从大到小排序，取前若干个直到和至少为 kk，得到该算法最少需要的题数 need[i]\text{need[i]}。

设：

S=∑neediS=\sum need_i

如果某类题数量最多为 mxmx，要能排成 不相邻相同 ，必须满足：

mx≤S−mx+1mx \le S-mx+1

如果满足，答案就是 SS。

否则需要额外选择一些其他类别的题作为 隔板 。若最多的那一类数量为 mxmx，至少需要总题数达到：

2mx−12mx-1

缺少的额外题数为：

2mx−1−S2mx-1-S

只要其他类别还有足够没选的题，就可以补齐，否则无解。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int m, n;
LL k;
int a[N];
LL b[N];
vector<LL> v[N];
inline void solve() {
    cin >> m >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        v[a[i]].push_back(b[i]);
    }
    LL S = 0;
    int mx = 0;
    int id = -1;
    vector<int> need(m + 1, 0);
    for (int i = 1; i <= m; i++) {
        sort(v[i].begin(), v[i].end(), greater<LL>());
        LL sum = 0;
        int cnt = 0;
        while (cnt < (int)v[i].size() && sum < k) {
            sum += v[i][cnt];
            cnt++;
        }
        if (sum < k) {
            printf("-1\n");
            return;
        }
        need[i] = cnt;
        S += cnt;
        if (cnt > mx) {
            mx = cnt;
            id = i;
        }
    }
    if (mx <= S - mx + 1) {
        printf("%lld\n", S);
        return;
    }
    LL target = 2LL * mx - 1;
    LL extra = target - S;
    LL rest = 0;
    for (int i = 1; i <= m; i++) {
        if (i == id) continue;
        rest += (int)v[i].size() - need[i];
    }
    if (rest >= extra) printf("%lld\n", target);
    else printf("-1\n");
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

13. 树上游走

题目大意

有一棵无限二叉树，根节点编号为 11。节点 ii 的左儿子为 2i2i，右儿子为 2i+12i+1。给定初始节点 ss 和一串操作：

  • U\texttt{U}：移动到父节点，如果已经在根节点则不动；
  • L\texttt{L}：移动到左儿子；
  • R\texttt{R}：移动到右儿子。

求所有操作后所在节点编号。

解题思路

直接模拟即可。

对于当前节点 xx：

  • U\texttt{U}：如果 x>1x > 1，令 x=x/2x = x/2；
  • L\texttt{L}：令 x=2xx = 2x；
  • R\texttt{R}：令 x=2x+1x = 2x+1。

题目保证最终编号不超过 101210^{12}，所以用 long long\text{long long}，但是并不行，因为有可能会一直往左子树或者右子树走，然后超过了 101810^{18} ，然后再往上走回 101210^{12} 以内，也就是说中途会溢出。

所以需要先把操作压缩一下再处理，使用 U\texttt{U} 抵消一下 L\texttt{L} 或者 R\texttt{R}。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
LL n, s;
char t[N];
deque<char> dq;
inline void solve() {
    cin >> n >> s;
    scanf("%s", t + 1);
    for (int i = 1; i <= n; i++) {
        if (t[i] == 'U') {
            if (dq.size()) dq.pop_back();
            else if (s != 1) s >>= 1;
        }
        else dq.push_back(t[i]);
    }
    while (dq.size()) {
        char c = dq.front(); dq.pop_front();
        if (c == 'L') s <<= 1;
        else s = (s << 1) + 1;
    }
    printf("%lld\n", s);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

14. 运送物资

题目大意

有 nn 个运输站点，第 ii 个站点的位置为 pip_i，最多可以作为 cic_i 辆车的初始站点。

共有 mm 辆车，第 ii 辆车每天要向 A 市运输 aia_i 次，向 B 市运输 bib_i 次。A 市坐标为 00，B 市坐标为 xx。

如果一辆车放在位置 pp，它每天的总路程为：

2aip+2bi(x−p)2a_ip+2b_i(x-p)

现在要求为每辆车选择一个初始站点，使所有车辆的总路程之和最小。

解题思路

对于第 ii 辆车，如果它被放在位置 pp，费用为：

2aip+2bi(x−p)2a_ip+2b_i(x-p)

展开可得：

2aip+2bix−2bip2a_ip+2b_ix-2b_ip

整理为：

2bix+2(ai−bi)p2b_ix+2(a_i-b_i)p

其中 2bix2b_ix 与站点位置 pp 无关，是这辆车的固定贡献。

真正影响选择站点的是：

2(ai−bi)p2(a_i-b_i)p

令：

wi=2(ai−bi)w_i=2(a_i-b_i)

问题转化为：在满足站点容量限制的前提下，最小化

∑wip\sum w_i p

根据 wiw_i 的正负分情况讨论。

1. 当 wi>0w_i > 0 时

此时费用项为：

wipw_i p

因为 wiw_i 是正数，所以 pp 越小，费用越小。

也就是说，这类车辆应该尽量放在靠近 A 市，也就是位置更小的站点。

并且 wiw_i 越大，对位置越敏感，越应该优先放到更小的位置。

因此：

wi>0w_i > 0

的车辆按 wiw_i 从大到小排序，从左往右分配站点。

2. 当 wi<0w_i < 0 时

此时费用项为：

wipw_i p

因为 wiw_i 是负数，所以 pp 越大，费用越小。

也就是说，这类车辆应该尽量放在靠近 B 市，也就是位置更大的站点。

并且 wiw_i 越小，负得越多，对位置越敏感，越应该优先放到更大的位置。

因此：

wi<0w_i < 0

的车辆按 wiw_i 从小到大排序，从右往左分配站点。

3. 当 wi=0w_i = 0 时

说明：

ai=bia_i=b_i

此时费用为：

2bix2b_ix

与站点位置无关，放在哪里都一样。

所以只需要把固定贡献加入答案即可，不需要专门参与贪心分配。

需要 注意 不能直接把所有车辆按 wiw_i 从大到小排序，然后从左往右分配。

因为题目只保证：

∑ci≥m\sum c_i \ge m

也就是说，站点容量可能有剩余。

如果某辆车 wi<0w_i < 0，它应该被放到靠右的站点，而不是从左边开始分配。

例如只有一辆车只去 B 市，那么它显然应该放在最靠近 B 市的站点。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
struct Sta {
    LL p, c;
};
int n, m;
LL x;
vector<Sta> st;
vector<LL> lf, rg;
inline void solve() {
    cin >> n >> m >> x;
    st.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> st[i].p >> st[i].c;
    }
    LL Ans = 0;
    for (int i = 0; i < m; i++) {
        LL a, b; cin >> a >> b;
        Ans += 2 * b * x;
        LL w = 2 * (a - b);
        if (w > 0) {
            lf.push_back(w);
        } else if (w < 0) {
            rg.push_back(w);
        }
    }
    sort(st.begin(), st.end(), [](Sta A, Sta B) {
        return A.p < B.p;
    });
    sort(lf.begin(), lf.end(), greater<LL>());
    sort(rg.begin(), rg.end());
    int l = 0, r = n - 1;
    for (LL w : lf) {
        while (l < n && st[l].c == 0) l++;
        Ans += w * st[l].p;
        st[l].c--;
    }
    for (LL w : rg) {
        while (r >= 0 && st[r].c == 0) r--;
        Ans += w * st[r].p;
        st[r].c--;
    }
    printf("%lld\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

15. 树上漫步

题目大意

给定一棵 nn 个节点的树。对于每个节点，问从它出发，经过偶数步后能够结束漫步的节点有多少个。漫步过程中允许经过重复节点。

解题思路

树是二分图。

从某个节点出发，每走一步，深度奇偶性都会改变。经过偶数步后，只能到达与起点深度奇偶性相同的节点。

反过来，任意两个深度奇偶性相同的节点，它们之间的简单路径长度就是偶数，因此可以到达。

所以只需要统计树上深度为偶数的节点数和深度为奇数的节点数。

对每个节点输出它所属奇偶类的数量。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
vector<int> g[N];
int dep[N], cnt[2];
inline void solve() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    queue<int> q;
    q.push(1);
    dep[1] = 0;
    vector<int> vis(n + 1, 0);
    vis[1] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cnt[dep[u] % 2]++;
        for (int v : g[u]) {
            if (!vis[v]) {
                vis[v] = 1;
                dep[v] = dep[u] + 1;
                q.push(v);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (i > 1) printf(" ");
        printf("%d", cnt[dep[i] % 2]);
    }
    printf("\n");
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

16. 环线

题目大意

给定一个环形序列，每个位置有一个快乐值。可以选择环上一段连续路径，至少经过一个车站，且不能重复经过车站。求能获得的最大快乐值。

解题思路

这是最大环形子段和。

有两种情况：

  1. 不跨过首尾连接处：普通最大子段和；
  2. 跨过首尾连接处：等价于总和减去中间没有选择的最小子段和。

所以答案为：

max⁡(最大子段和, 总和−最小子段和)\max(\text{最大子段和},\ \text{总和}-\text{最小子段和})

但如果所有数都是负数，第二种会变成空段，不合法，此时答案就是最大子段和。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
const LL inf = 4e18;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
LL a[N];
inline void solve() {
    cin >> n;
    LL sum = 0;
    LL mx = -inf, mn = inf;
    LL curMax = 0, curMin = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
        curMax = max(a[i], curMax + a[i]);
        mx = max(mx, curMax);
        curMin = min(a[i], curMin + a[i]);
        mn = min(mn, curMin);
    }
    if (mx < 0) printf("%lld\n", mx);
    else printf("%lld\n", max(mx, sum - mn));
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

17. 学习小组

题目大意

有 nn 名同学，要划分成若干学习小组。若某个小组恰好有 kk 名同学，则这个小组的积极度为 aka_k。求所有划分方案中，积极度总和的最大值。

解题思路

设 dpidp_i 表示把 ii 名同学划分成若干小组时的最大积极度。

最后一个小组大小可以是 kk，那么：

dpi=max⁡(dpi−k+ak)dp_i=\max(dp_{i-k}+a_k)

其中：

1≤k≤i1\le k\le i

这是典型整数拆分 DP\text{DP}。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
LL a[N], dp[N];
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        dp[i] = 0;
        for (int k = 1; k <= i; k++) {
            dp[i] = max(dp[i], dp[i - k] + a[k]);
        }
    }
    printf("%lld\n", dp[n]);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

18. 最大因数

题目大意

有一棵有根树，根节点为 11。对于编号为 kk 的节点，它的父节点是 kk 的最大真因数。给定多组询问 (x,y)(x,y)，求两个节点在树上的距离。

解题思路

一个数 kk 的最大真因数是：

kk 的最小质因子\frac{k}{k\text{ 的最小质因子}}

所以从节点 kk 走向根节点的过程，就是每次删掉当前数的最小质因子。

把 kk 分解成质因数，并从小到大排列：

k=p1p2⋯ptk=p_1p_2\cdots p_t

那么它到根的路径依次删除 p1,p2,…p_1,p_2,\ldots。

因此两个节点的公共祖先，等价于两个质因数序列从后往前的最长公共后缀。

若两个数的质因数个数分别为 A,BA,B，公共后缀长度为 CC，距离为：

A+B−2CA+B-2C

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
vector<int> pri;
int vis[N];
void init() {
    for (int i = 2; i < N; i++) {
        if (!vis[i]) {
            pri.push_back(i);
            for (LL j = 1LL * i * i; j < N; j += i) {
                vis[j] = 1;
            }
        }
    }
}
vector<int> fac(int x) {
    vector<int> v;
    for (int p : pri) {
        if (1LL * p * p > x) break;
        while (x % p == 0) {
            v.push_back(p);
            x /= p;
        }
    }
    if (x > 1) v.push_back(x);
    return v;
}
int q;
inline void solve() {
    cin >> q;
    while (q--) {
        int x, y; cin >> x >> y;
        vector<int> a = fac(x);
        vector<int> b = fac(y);
        int i = (int)a.size() - 1;
        int j = (int)b.size() - 1;
        int same = 0;
        while (i >= 0 && j >= 0 && a[i] == b[j]) {
            same++;
            i--;
            j--;
        }
        printf("%d\n", (int)a.size() + (int)b.size() - 2 * same);
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    init();
    int _ = 1;
    while (_--) solve();
    return 0;
}

19. 划分字符串

题目大意

给定长度为 nn 的小写字母串 ss，要把它划分成若干子串。每个子串中每个字母至多出现一次。划分后长度为 ii 的子串价值为 aia_i。求最大总价值。

解题思路

因为一个合法子串中每个字母最多出现一次，小写字母只有 2626 个，所以每个合法子串长度最多为 2626。

设 dpidp_i 表示前 ii 个字符的最大价值。

枚举以第 ii 个字符结尾的合法子串长度 lenlen，如果这段子串没有重复字母，则：

dpi=max⁡(dpi,dpi−len+alen)dp_i=\max(dp_i,dp_{i-len}+a_{len})

每个位置最多向前看 2626 个字符，复杂度 O(26n)O(26n)。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
string s;
LL a[N], dp[N];
inline void solve() {
    cin >> n;
    cin >> s;
    s = " " + s;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        dp[i] = 0;
        int vis[26] = {0};
        for (int j = i; j >= 1 && i - j + 1 <= 26; j--) {
            int c = s[j] - 'a';
            if (vis[c]) break;
            vis[c] = 1;
            int len = i - j + 1;
            dp[i] = max(dp[i], dp[j - 1] + a[len]);
        }
    }
    printf("%lld\n", dp[n]);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

20. 货物运输

题目大意

给定一棵以 11 号城市为首都的树，边有长度。车队从首都出发，需要经过所有城市，但最后可以不返回首都。求经过道路长度总和的最小值。

解题思路

如果必须从根出发并回到根，那么每条边都要走两次，总长度为：

2∑wi2\sum w_i

现在最后可以停在某个城市不回来。为了省最多的路，应该选择从根到某个城市的一条最长路径作为最后不返回的路径。

因此答案为：

2∑wi−max⁡vdist(1,v)2\sum w_i-\max_{v} dist(1,v)

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
struct Edge {
    int to;
    LL w;
};
int n;
vector<Edge> g[N];
LL sumw, mx;
inline void solve() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        LL w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
        sumw += w;
    }
    queue<int> q;
    vector<int> vis(n + 1, 0);
    vector<LL> dis(n + 1, 0);
    q.push(1);
    vis[1] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        mx = max(mx, dis[u]);
        for (auto e : g[u]) {
            int v = e.to;
            if (!vis[v]) {
                vis[v] = 1;
                dis[v] = dis[u] + e.w;
                q.push(v);
            }
        }
    }
    printf("%lld\n", 2 * sumw - mx);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

21. 路径覆盖

题目大意

给定一棵以 11 为根的有根树。每个节点染黑有代价 cic_i。要求染黑若干节点，使得每条从叶子到根的路径上至少有一个黑色节点。求最小总代价。

解题思路

树形 DP\text{DP}。

设 dpudp_u 表示在以 uu 为根的子树中，保证每条叶子到 uu 的路径上至少有一个黑点的最小代价。

对于节点 uu：

  1. 直接染黑 uu，代价为 cuc_u；
  2. 不染黑 uu，则每个子树都必须自己完成覆盖，代价为：
∑dpv\sum dp_v

所以：

dpu=min⁡(cu,∑dpv)dp_u=\min(c_u,\sum dp_v)

叶子节点没有子节点，只能染自己：

dpu=cudp_u=c_u

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
vector<int> g[N];
LL c[N], dp[N];
inline void solve() {
    cin >> n;
    for (int i = 2; i <= n; i++) {
        int f;
        cin >> f;
        g[f].push_back(i);
    }
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int u = n; u >= 1; u--) {
        if (g[u].empty()) {
            dp[u] = c[u];
        } else {
            LL sum = 0;
            for (int v : g[u]) {
                sum += dp[v];
            }
            dp[u] = min(c[u], sum);
        }
    }
    printf("%lld\n", dp[1]);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

22. 道具商店

题目大意

有 nn 件道具，第 ii 件道具可以提升 aia_i 点攻击力，价格为 cic_i。每件道具最多买一次。你有 kk 枚金币，求最多能提升多少攻击力。

解题思路

金币数 kk 可能很大，不能按金币做背包。

但 ai≤500a_i\le 500，n≤500n\le 500，总攻击力最多为：

500×500=250000500\times 500=250000

所以可以按攻击力做背包。

设 dpvdp_v 表示获得攻击力 vv 所需的最少金币。

每个道具做 0/10/1 背包：

dpv+ai=min⁡(dpv+ai,dpv+ci)dp_{v+a_i}=\min(dp_{v+a_i},dp_v+c_i)

最后找最大的 vv，满足：

dpv≤kdp_v\le k

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
const LL inf = 4e18;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
LL k;
LL dp[N];
inline void solve() {
    cin >> n >> k;
    int S = 500 * n;
    for (int i = 1; i <= S; i++) dp[i] = inf;
    dp[0] = 0;
    int mx = 0;
    for (int i = 1; i <= n; i++) {
        int a;
        LL c;
        cin >> a >> c;
        for (int v = mx; v >= 0; v--) {
            if (dp[v] == inf) continue;
            dp[v + a] = min(dp[v + a], dp[v] + c);
        }
        mx += a;
    }
    int Ans = 0;
    for (int v = 0; v <= mx; v++) if (dp[v] <= k) Ans = v;
    printf("%d\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

23. 选数

题目大意

给定数组 aa 和 bb。需要选择若干下标：

p1<p2<⋯<pkp_1 < p_2 < \cdots < p_k

并满足：

pi+1≥pi+bpip_{i+1}\ge p_i+b_{p_i}

求所选下标对应的 aa 值之和最大。

解题思路

设 dpidp_i 表示只考虑下标 ii 到 nn 时能得到的最大和。

对于位置 ii，有两种选择：

  1. 不选 ii：
dpi=dpi+1dp_i=dp_{i+1}
  1. 选 ii，那么下一个可选位置至少是：
max⁡(i+1,i+bi)\max(i+1,i+b_i)

所以：

dpi=ai+dpmax⁡(i+1,i+bi)dp_i=a_i+dp_{\max(i+1,i+b_i)}

取两者最大即可。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
LL a[N], b[N], dp[N];
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = n; i >= 1; i--) {
        int nxt = max((LL)i + 1, (LL)i + b[i]);
        LL take = a[i];
        if (nxt <= n) take += dp[nxt];
        dp[i] = max(dp[i + 1], take);
    }
    printf("%lld\n", dp[1]);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

24. 完全二叉树

题目大意

给定一棵有根二叉树。每个节点都有左儿子 lil_i 和右儿子 rir_i，不存在则为 00。对于每个节点，都有一棵以它为根的子树。求这些子树中有多少棵是完全二叉树。

解题思路

需要同时判断两种性质：

  1. full[u]\text{full[u]}：以 uu 为根的子树是否为满二叉树；
  2. ok[u]\text{ok[u]}：以 uu 为根的子树是否为完全二叉树；
  3. h[u]\text{h[u]}：子树高度。

空树认为既是满二叉树，也是完全二叉树，高度为 00。

对于节点 uu，设左儿子为 ll，右儿子为 rr。

满二叉树条件：

fulll∧fullr∧hl==hrfull_l \land full_r \land h_l == h_r

完全二叉树有两种合法结构：

  1. 左子树是满二叉树，右子树是完全二叉树，且左右高度相同；
  2. 左子树是完全二叉树，右子树是满二叉树，且左子树高度比右子树高 11。

即：

$$ok_u=(ok_l\land ok_r)\land \left[ (full_l\land h_l == h_r)\lor(full_r\land h_l == h_r+1) \right] $$

最后统计所有 ok[u]\text{ok[u]} 的数量。

代码

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n;
int lch[N], rch[N], h[N];
int full[N], ok[N];
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> lch[i] >> rch[i];
    full[0] = 1;
    ok[0] = 1;
    h[0] = 0;
    vector<int> ord;
    stack<int> st;
    st.push(1);
    while (!st.empty()) {
        int u = st.top();
        st.pop();
        ord.push_back(u);
        if (lch[u]) st.push(lch[u]);
        if (rch[u]) st.push(rch[u]);
    }
    reverse(ord.begin(), ord.end());
    LL Ans = 0;
    for (int u : ord) {
        int l = lch[u], r = rch[u];
        h[u] = max(h[l], h[r]) + 1;
        full[u] = full[l] && full[r] && h[l] == h[r];
        ok[u] = ok[l] && ok[r] && ((full[l] && h[l] == h[r]) || (full[r] && h[l] == h[r] + 1));

        if (ok[u]) Ans++;
    }
    printf("%lld\n", Ans);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _ = 1;
    while (_--) solve();
    return 0;
}

评论

0 条
还没有评论。
  1. 评测队列
  2. 服务状态
  3. 兼容模式
  4. 主题
  5. 京ICP备2024092232号-2
  6. 京公网安备图标 京公网安备11010802045784号
  7. DAMON THRONE