08-23 21:19 已编辑郑州大学 C++ 发布于江西

关注

题解报告

河南萌新联赛2025第（六）场：郑州大学

补完题以后发现没有人写题解，发现很久没写文章了，简单写一篇本场的题解。

非官方题解，写的不好的地方轻喷o(╥﹏╥)o

以下题目顺序根据赛时的AC情况排序，实际难度视个人情况而定。

(D题数据弱了，原先代码有误，已更新，抱歉。2025/8/23)

L 整数商店的购物之旅

前置知识：基本数学，二分
通过人数： $630$

不难发现，假设我们买得起一个数字 $n$ ，那么必然能卖得起所有比 $n$ 小的整数，满足单调性，因此采用二分的形式找到答案，注意商店的整数不超过 $10 ^ 9$ 即可。

时间复杂度： $O(logn)$ 。

代码实现：

#include<bits/stdc++.h>
using namespace std;

//#define int long long
#define endl '\n'
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define pi pair<int, int>
#define all(x) x.begin(), x.end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using ll = long long;
using lll = __int128;

const int mod = 1e9 + 7;
const int MOD = 998244353;
const int N = 2e5 + 7;
const int INF = 1e18;

int dx[] = { 1, 0, -1, 0, 1, -1, 1, -1 }, dy[] = { 0, 1, 0, -1, 1, -1, -1, 1 };
int n, m, k, q, x, y, ans;

ll qpow(ll a, ll b, ll p = 1e18) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

void solve() {
    ll a, b, x;
    cin >> a >> b >> x;
    //这里我枚举了一下数字的位数，直接二分0-1e9这个区间也是可以的
    for(int i = 10; i >= 1; i--){
        if(qpow(10, i - 1) * a + i * b > x) continue;
        ll l = qpow(10, i - 1), r = qpow(10, i) - 1;
        while(l < r){
            ll mid = (l + r - 1) / 2 + 1;
            if(mid * a + i * b > x) r = mid - 1;
            else l = mid;
        }
        cout << (l > 1e9 ? (ll)1e9 : l) << endl;
        return;
    }
    cout << 0 << endl;
}

signed main() {

    IOS;

    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

E 数字支配

前置知识：字典序
通过人数： $574$

对于一个 $n$ 位数，例如 $1234$ 不难发现如果有 $3$ 个 $9$ 必然是比这个 $4$ 位数小的，只需要检查是否存在一个 $n$ 位数的字典序大于这个 $n - 1$ 位数即可，根据字典序的定义，我们把这个 $n$ 位数拓展为 $n - 1$ 位，相当于在末尾添加一个字典序非常小的数，比 $0$ 的字典序还小。
比如 $1234$ 首先找到 $999$ 那么至少要是 $9990$ 字典序才会比 $999$ 大，只需要判断输入的数的高 $n - 1$ 位是否全是 $9$ 即可。

时间复杂度： $O(log(n))$ ， $n$ 为输入的数的位数。

代码实现：

#include<bits/stdc++.h>
using namespace std;

#define debug(x) cout << x << endl
//#define int long long
#define endl '\n'
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define pi pair<int, int>
#define lowbit(x) (x&-x)
#define all(x) x.begin(), x.end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define sqrt __builtin_sqrtl

using ll = long long;
using lll = __int128;

const int mod = 1e9 + 7;
const int MOD = 998244353;
const int N = 2e5 + 7;
const int INF = 1e18;

int dx[] = { 1, 0, -1, 0, 1, -1, 1, -1 }, dy[] = { 0, 1, 0, -1, 1, -1, -1, 1 };
int n, m, k, q, x, y, ans;

void solve() {
    string s; cin >> s;
    cout << string(s.size() - 1, '9');
    if(s.substr(0, s.size() - 1) == string(s.size() - 1, '9')) cout << s.back() << endl;
}

signed main() {

    IOS;

    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

I 外卖大战

前置知识：模拟
通过人数： $478$

一个比较基础的模拟题，感觉通过率不应该这么低的，题目已经给得很清楚了，按照题目模拟即可，不再赘述。

时间复杂度： $O(n)$ 。

#include<bits/stdc++.h>
using namespace std;

#define debug(x) cout << x << endl
//#define int long long
#define endl '\n'
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define pi pair<int, int>
#define lowbit(x) (x&-x)
#define all(x) x.begin(), x.end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define sqrt __builtin_sqrtl

using ll = long long;
using lll = __int128;

const int mod = 1e9 + 7;
const int MOD = 998244353;
const int N = 2e5 + 7;
const int INF = 1e18;

int dx[] = { 1, 0, -1, 0, 1, -1, 1, -1 }, dy[] = { 0, 1, 0, -1, 1, -1, -1, 1 };
int n, m, k, q, x, y, ans;

int cnt[3], b[3], c[3];

void solve() {
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < n; i++){
        bool vis = false;
        for(int j = 0; j < 3; j++){
            if(b[j] >= a[i] && !vis) cnt[j]++, b[j]++, c[j] = 0, vis  = true;
            else{
                c[j]++;
                if(c[j] == 3) b[j] += 2, c[j] = 0;
            }
        }
    }

    for(int i = 0; i < 3; i++) cout << cnt[i] << ' ';
    cout << endl;
}

signed main() {

    IOS;

    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

K 还在分糖果

前置知识：数学，进制转换
通过人数： $438$

给定一个集合 $S$ ， $S$ 中包含了 [ $1, n$ ]中所有不包含 $7$ 的数字，那我们就取每一位上可以是 $0 - 6$ 和 $8 - 9$ 这样 $9$ 个数字，不妨假设世界上没有 $7$ 这个数字， $6$ 的后面就是 $9$ 我们发现我们这个集合中的数字就变成了一系列的 $9$ 进制数，于是问题就变成了在我们给定的进制转换条件下，第 $n$ 个数是什么，也就是把十进制的 $n$ 转换为跳过 $7$ 的九进制数即可。（不用有人用数位 $dp$ 吧）

时间复杂度 $O(Tlogn)$ 。

代码实现：

#include<bits/stdc++.h>
using namespace std;

#define debug(x) cout << x << endl
//#define int long long
#define endl '\n'
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define pi pair<int, int>
#define lowbit(x) (x&-x)
#define all(x) x.begin(), x.end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define sqrt __builtin_sqrtl

using ll = long long;
using lll = __int128;

const int mod = 1e9 + 7;
const int MOD = 998244353;
const int N = 2e5 + 7;
const int INF = 1e18;

int dx[] = { 1, 0, -1, 0, 1, -1, 1, -1 }, dy[] = { 0, 1, 0, -1, 1, -1, -1, 1 };
ll n, m, k, q, x, y, ans;

ll qpow(ll a, ll b, ll p = 1e18) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

string trans(int x){
    ll t = qpow(9, 13);
    string res;
    while(t >= 1){
        res += x / t + '0';
        x %= t;
        t /= 9;
    }
    while(res.size() > 1 && res[0] == '0') res.erase(0, 1);
    for(int i = 0; i < res.size(); i++){
        if(res[i] >= '7') res[i]++;
    }
    return res;
}

void solve() {
    cin >> n;
    cout << trans(n) << endl;
}

signed main() {

    IOS;

    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

J 凹包

前置知识：几何代数
通过人数： $404$

凹多边形顾名思义，存在一个外角超过 $180 ^ \circ$ ,题目中的点是按照多边形逆时针给出的，假设每一条边都是一个向量，逆时针给点相当于将每条边再不断地逆时针旋转，根据右手定则，相领两个向量的叉乘应该大于 $0$ ，只需检查是否存在某两条相领的边叉乘小于 $0$ 即可

时间复杂度： $O(n)$ 。

代码实现：

#include<bits/stdc++.h>
using namespace std;

#define debug(x) cout << x << endl
//#define int long long
#define endl '\n'
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define pi pair<int, int>
#define pll pair<long long, long long>
#define lowbit(x) (x&-x)
#define all(x) x.begin(), x.end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define sqrt __builtin_sqrtl

using ll = long long;
using lll = __int128;

const int mod = 1e9 + 7;
const int MOD = 998244353;
const int N = 2e5 + 7;
const int INF = 1e18;

int dx[] = { 1, 0, -1, 0, 1, -1, 1, -1 }, dy[] = { 0, 1, 0, -1, 1, -1, -1, 1 };
int n, m, k, q, x, y, ans;

void solve() {
    cin >> n;
    vector<pll> a(n);
    for(int i = 0; i < n; i++) cin >> a[i].F >> a[i].S;

    for(int i = 0; i < n - 2; i++){
        ll x1 = a[i + 1].F - a[i].F, y1 = a[i + 1].S - a[i].S;
        ll x2 = a[i + 2].F - a[i + 1].F, y2 = a[i + 2].S - a[i + 1].S;
        ll k = x1 * y2 - x2 * y1;
        if(k < 0){
            cout << "Yes" << endl;
            return;
        }
    }

    cout << "No" << endl;
}

signed main() {

    IOS;

    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

D 穿过哈气之门

前置知识：双指针通过人数： $324$

对于本题，暴力的做法显然是枚举每一个区间左端点 $l$ ，找到所有的区间右端点 $r$ ，满足区间[ $l, r$ ] 中包含了 [ $1, m$ ] 的每个数，这样的做法显然是 $O(n ^ 2)$ 的，但是我们发现，我们能找到的区间最小的满足的右端点，所有比这个点大的右端点都满足，比这个点小的右端点都不满足，就变成了标准的双指针问题。

时间复杂度： $O(n)$ 。

代码实现：

#include<bits/stdc++.h>
using namespace std;

#define debug(x) cout << x << endl
//#define int long long
#define endl '\n'
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define pi pair<int, int>
#define lowbit(x) (x&-x)
#define all(x) x.begin(), x.end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define sqrt __builtin_sqrtl

using ll = long long;
using lll = __int128;

const int mod = 1e9 + 7;
const int MOD = 998244353;
const int N = 2e5 + 7;
const int INF = 1e18;

int dx[] = { 1, 0, -1, 0, 1, -1, 1, -1 }, dy[] = { 0, 1, 0, -1, 1, -1, -1, 1 };
int n, m, k, q, x, y, ans;

void solve() {
    cin >> n >> m;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    unordered_set<int> st;
    vector<int> cnt(m + 1);
    int l = 0, r = 0;
    while(l < n){
        while(r < n && st.size() < m) st.insert(a[r]), cnt[a[r++]]++;
        if(r == n && st.size() < m) break;
        ans += n - r + 1;
        cnt[a[l]]--;
        if(cnt[a[l]] == 0) st.erase(a[l]);
        l++;
    }

    cout << ans << endl;
}

signed main() {

    IOS;

    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

F 迷宫穿越

前置知识：BFS，队列
通过人数： $210$

比较板的题目，就不细讲了，不懂的可以深入学习一下BFS。
设 $vis_{ijk}$ 为到达坐标 $(i, j)$ 使用了 $k$ 张瞬移卷轴的状态，如果访问过了那就是 true，否则是false，因为权值均为1，队列中的时间必然是单调非降的，直接BFS即可，每个状态访问后直接打上标记。

时间复杂度： $O(nmk)$ 。

代码实现：

#include<bits/stdc++.h>
using namespace std;

#define debug(x) cout << x << endl
#define int long long
#define endl '\n'
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define pi pair<int, int>
#define lowbit(x) (x&-x)
#define all(x) x.begin(), x.end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define sqrt __builtin_sqrtl

using ll = long long;
using lll = __int128;

const int mod = 1e9 + 7;
const int MOD = 998244353;
const int N = 1e3 + 5;
const int INF = 1e18;

int dx[] = { 1, 0, -1, 0, 1, -1, 1, -1 }, dy[] = { 0, 1, 0, -1, 1, -1, -1, 1 };
int n, m, k, q, x, y, ans;

struct node{
    int x, y, d, t;
};

char g[N][N];
int vis[N][N][15];

void solve() {
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        string s; cin >> s;
        for(int j = 1; j <= m; j++) g[i][j] = s[j-1];
    }

    vis[1][1][0] = true;
    queue<node> q;
    q.push({1, 1, 0, 0});
    while(q.size()){
        auto [x, y, d, t] = q.front();
        q.pop();
        if(x == n && y == m){
            cout << d << endl;
            return;
        }
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 1 || ny < 1 || nx > n || ny > m) continue;
            if(g[nx][ny] == '#'){
                if(t == k || vis[nx][ny][t + 1]) continue;
                q.push({nx, ny, d + 1, t + 1});
                vis[nx][ny][t + 1] = true;
            }
            else{
                if(vis[nx][ny][t]) continue;
                q.push({nx, ny, d + 1, t});
                vis[nx][ny][t] = true;
            }
        }
    }

    cout << -1 << endl;
}

signed main() {

    IOS;

    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

G 宝石收集

前置知识：位运算，动态规划，状态压缩
通过人数： $199$

每个宝石的编号为 $0 - n - 1$ ，由于 $n$ 并不大，采用状态压缩存储每个地下城拥有的宝石种类，采用二进制存储，如果二进制数的第 $i$ 位为1，代表该地下城拥有编号为 $i$ 的宝石。
那么对于我们拥有的宝石状态为 $statu$ ，我们每进入一个地下城，只可能获得宝石，并不会丢失宝石，只会让 $statu$ 变大而不会变小，只会向更大的状态转移，不会影响小状态，满足无后效性，考虑动态规划。令 $dp_i$ 表示我们拥有的宝石的状态为 $i$ 时的最小花费。
假设标号为 $j$ 的地下城拥有的宝石的状态为 $a_j$ ，那么状态转移方程为： $dp_{i | a_j} = min(dp_{i | a_i}, dp_i + v_j)$ 。

时间复杂度： $O(m2^n)$ 。

代码实现：

#include<bits/stdc++.h>
using namespace std;

#define debug(x) cout << x << endl
//#define int long long
#define endl '\n'
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define pi pair<int, int>
#define lowbit(x) (x&-x)
#define all(x) x.begin(), x.end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define sqrt __builtin_sqrtl

using ll = long long;
using lll = __int128;

const int mod = 1e9 + 7;
const int MOD = 998244353;
const int N = 2e5 + 7;
const int INF = 0x3f3f3f3f;

int dx[] = { 1, 0, -1, 0, 1, -1, 1, -1 }, dy[] = { 0, 1, 0, -1, 1, -1, -1, 1 };
int n, m, k, q, x, y, ans;

void solve() {
    cin >> n >> m;
    vector<int> dp(1 << n, INF);

    dp[0] = 0;
    vector<pi> a(m);
    for(int i = 0; i < m; i++){
        cin >> a[i].S >> x;
        int sta = 0;
        for(int i = 0; i < x; i++){
            cin >> y;
            sta += 1 << y;
        }
        a[i].F = sta;
    }

    for(int i = 0; i < (1LL << n); i++){
        for(int j = 0; j < m; j++){
            int t = i | a[j].F;
            dp[t] = min(dp[t], dp[i] + a[j].S);
        }
    }

    cout << (dp[(1 << n) - 1] == INF ? -1 : dp[(1 << n) - 1]) << endl;
}

signed main() {

    IOS;

    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

H 分词器

前置知识：字符串，Trie
通过人数： $170$

题目描述还是比较抽象的，简单来讲就是，给定了一系列的 $token$ 和一个字符串 $s$ 我们找到 $s$ 的最长前缀，该前缀存在于给定的 $token$ 序列中，如果不存在该前缀，直接取其长度为 $1$ 的前缀，直接输出这个前缀，并从原字符串删去该前缀，重复以上操作，直至该字符串为空。
我们将所有的 $token$ 构成一个字典树，记录下每个节点是否是某一个 $token$ 的结束位置，遍历 $S$ 直到某个前缀在字典树中不存在为止，记录下期间遍历到的最长 $token$ ，然后更新字符串 $s$ 即可。

时间复杂度： $O(nl)$ , $l$ 为 $token$ 的最长的长度。

代码实现：

#include<bits/stdc++.h>
using namespace std;

#define debug(x) cout << x << endl
//#define int long long
#define endl '\n'
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define pi pair<int, int>
#define lowbit(x) (x&-x)
#define all(x) x.begin(), x.end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define sqrt __builtin_sqrtl

using ll = long long;
using lll = __int128;

const int mod = 1e9 + 7;
const int MOD = 998244353;
const int N = 2e5 + 7;
const int INF = 1e18;

int dx[] = { 1, 0, -1, 0, 1, -1, 1, -1 }, dy[] = { 0, 1, 0, -1, 1, -1, -1, 1 };
int n, m, k, q, x, y, ans;

int nex[100000][26], cnt;
int ed[100000];  
int pre[100000];

void insert(string s) { 
    int p = 0, l = s.size();
    pre[0]++;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) nex[p][c] = ++cnt;  
      p = nex[p][c];
      pre[p]++;
    }
    ed[p]++;
}

void solve() {
    cin >> n;
    for(int i = 0; i < n; i++){
        string s; cin >> s;
        insert(s);
    }

    string s; cin >> s;
    int l = 0;
    vector<int> b;
    while(l < s.size()){
        int p = 0, pos = l, r = -1;
        int next_pos = s[pos] - 'a';
        while(pos < s.size() && nex[p][next_pos]) {
            p = nex[p][next_pos], pos++, next_pos = s[pos] - 'a';
            if(ed[p] != 0) r = pos - 1;
        }
        if(r == -1) b.pb(l), l++;
        else b.pb(r), l = r + 1;
    }

    int cnt = 0;
    for(int i = 0; i < s.size(); i++){
        cout << s[i];
        if(i == b[cnt]){
            cout << ' ';
            cnt++;
        }
    }
}

signed main() {

    IOS;

    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

B 配送物资

前置知识：dfs序，树状数组
通过人数： $81$

对于每一个节点 $i$ ， $j$ 为 $i$ 的子节点，那么 $i$ 所能获得的物资，是对于它所有的子节点 $j$ ，满足: $depth_j - d_j \leq depth_i$
的节点个数，假设每个节点的权值 $w_i = depth_i - d_i$ ，要找到以每个点为根的子树中，有多少个节点的权值不大于根的深度即可，转换为了一个树上求逆序对的问题。
对于子树，不难想到 $dfs$ 序，采用前序遍历，每一个节点都有一个进入时间和退出时间，而这个时间内进入的点都是这个节点的子结点，对于每一个节点，转换成了一个区间查询的问题，查询一段段的区间的和，采用树状数组实现（线段树自然也是可行的）。
首先获取每个节点的入栈和出栈时间，得到 $dfs$ 序，按照深度的大小遍历节点，遍历到每个节点时，将还未插入树状数组的点的权值不大于当前深度的节点插入树状数组中，相当于就是把对应节点的入队时间对应的值在树状数组中设为 $1$ , 然后查询对应区间的和即可。

时间复杂度： $O(nlogn)$ 。

代码实现：

#include<bits/stdc++.h>
using namespace std;

#define debug(x) cout << x << endl
//#define int long long
#define endl '\n'
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define pi pair<int, int>
#define lowbit(x) (x&-x)
#define all(x) x.begin(), x.end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define sqrt __builtin_sqrtl

using ll = long long;
using lll = __int128;

const int mod = 1e9 + 7;
const int MOD = 998244353;
const int N = 2e6 + 7;
const int INF = 1e18;

int dx[] = { 1, 0, -1, 0, 1, -1, 1, -1 }, dy[] = { 0, 1, 0, -1, 1, -1, -1, 1 };
int n, m, k, q, x, y;

template <typename T>
struct Fenwick {
    int n;
    vector<T> a;
    
    Fenwick(int n_ = 0) {
        init(n_);
    }
    
    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }
    
    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }
    
    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }
    
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
};

int a[N], l[N], r[N], dep[N], w[N], tim = 0, ans[N];
vector<int> g[N];

void dfs(int pos, int pre){
    dep[pos] = dep[pre] + 1;
    l[pos] = ++tim;
    for(auto v : g[pos]) {
        if(v == pre) continue;
        dfs(v, pos);
    }
    r[pos] = tim;
}

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

    for(int i = 1; i <= n; i++) cin >> a[i];

    dfs(1, 0);
    
    for(int i = 1; i <= n; i++) {
        if(a[i] > dep[i]) a[i] = dep[i] - 1;
        w[i] = dep[i] - a[i];
    }

    vector<pi> b;
    for (int i = 1; i <= n; i++) b.pb({w[i], l[i]});
    sort(all(b));
    
    vector<pi>c;
    for (int i = 1; i <= n; i++) c.pb({dep[i], i});
    sort(all(c));

    Fenwick<int> fenw(n);

    int j = 0;
    for (auto &[d, id] : c){
        while (j < b.size() && b[j].first <= d) fenw.add(b[j++].second - 1, 1);
        ans[id] = fenw.rangeSum(l[id] - 1, r[id]);
    }

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

signed main() {

    IOS;

    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

C 谁在呼叫舰队

前置知识：差分，前缀和，快速幂，逆元，费马小定理，动态规划
通过人数： $51$

$n$ 只有 $8000$ ，考虑 $n ^ 2$ 的做法，对于每一个位置 $i$ ，可以转移到 [ $i + 1, i + a_i$ ] 这个区间内的点中，满足无后效性，定义 $dp_{ij}$ 为转移到节点 $i$ 一共用了 $j$ 次的概率，但将每个点直接转移到后续的每一个节点显然会变成了 $n ^ 3$ 的做法，我们无法接受，但由于转移到每一个节点时等概率的，因此相当于将 [ $i + 1, i + a_i$ ] 整个区间加上这个概率，变成了一个区间修改的问题，考虑差分，可以在 $O(1)$ 的时间内完成修改，完美完成任务，但还有一个问题，我们在用费马小定理处理概率时，会用到快速幂，这是 $O(logn)$ 的，那么整体的时间复杂度就是 $(n ^ 2logn)$ 很抱歉，在本题中它超时了，所以我们还需要预处理每一个 $a_i$ 的逆元，就可以完美AC本题啦。

时间复杂度： $O(n ^ 2 + nlogn)$

代码实现：

#include<bits/stdc++.h>
using namespace std;

#define debug(x) cout << x << endl
#define int long long
#define endl '\n'
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define pi pair<int, int>
#define lowbit(x) (x&-x)
#define all(x) x.begin(), x.end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define sqrt __builtin_sqrtl

using ll = long long;
using lll = __int128;

const int mod = 1e9 + 7;
const int MOD = 998244353;
const int N = 8e3 + 7;
const int INF = 1e18;

int dx[] = { 1, 0, -1, 0, 1, -1, 1, -1 }, dy[] = { 0, 1, 0, -1, 1, -1, -1, 1 };
int n, m, k, q, x, y, ans;

ll qpow(ll a, ll b, ll p = 1e18) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

int sub[N][N], pre[N][N];

void solve() {
    cin >> n;
    vector<int> a(n), inv(n);
    for(int i = 1; i < n; i++) {
        cin >> a[i];
        inv[i] = qpow(a[i], MOD - 2, MOD);
    }
    pre[1][0] = 1;
    for(int i = 1; i < n; i++){
        for(int j = min(i - 1, 1LL); j <= n; j++){
            if(j != 0) pre[i][j] = (pre[i - 1][j] + sub[i][j]) % MOD;
            if(pre[i][j] == 0) continue;
            int t = pre[i][j] * inv[i] % MOD;
            sub[i + 1][j + 1] += t;
            sub[i + 1][j + 1] %= MOD;
            sub[i + a[i] + 1][j + 1] -= t;
            sub[i + a[i] + 1][j + 1] %= MOD;
        }
    }

    for(int i = 1; i <= n; i++){
        pre[n][i] = (pre[n - 1][i] + sub[n][i]) % MOD;
        ans += pre[n][i] * pre[n][i] % MOD;
        ans %= MOD;
    }

    cout << ans << endl;
}

signed main() {

    IOS;

    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

A 守护者之战

前置知识：排序，双指针，贪心
通过人数： $37$

本题的数据较弱，可能你通过各种错误的做法AC了本题，但并不一定是对的，如果想检验代码的正确性，请移步传送门测试你的代码，与本题大致相同，稍微修改即可。

题面较抽象，简单来说就是，你有 $n$ 个侍从， $m$ 个敌人，你的每个侍从最多攻击一次，如果该侍从的血量不为 $0$ ，它就可以释放攻击，会使得自己和被攻击者同时扣除一点血量，如果侍从或者敌人血量归 $0$ ，就会对场上所有单位进行打击，包括队友，全部扣除一点血量，请问你是否能通过某种攻击顺序击败所有敌人。
考虑贪心，不难发现，我们应该最大化自己的攻击次数，对于血量为 $1$ 的侍从，一旦它攻击，自己就会死，并且让其他血量同为 $1$ 的侍从一起死，总共只能攻击一次，并且不能太早进行攻击，否则会影响到其他血量稍高的侍从后续的攻击，为了尽量攻击更多次，我们假设存在一种贪心方案，可以让所有血量非 $1$ 的侍从都能攻击一次，验证该方案是否存在，血量大于 $1$ 的侍从只要攻击血量非 $1$ 的敌人，就不会引发爆炸，如果不存在这种选择，说明所有敌人血量都是 $1$ 了，此时我们选择就会炸死所有敌人，已经结束了，否则我们就能一直选下去，保证最大化攻击次数。
于是考虑双指针，由于我们假定了每个人都能攻击到一次，那么实际上每个侍从的实际血量就是 $a_i - 1$ ，记录当前爆炸的造成的伤害，初始为 $0$ ，如果血量最小的侍从或者血量最少的敌人血量低于爆炸伤害，就让爆炸伤害加 $1$ ，并且让指针右移，否则的话就让血量最少的侍从攻击血量最少的敌人，试图引爆对方来造成爆炸，重复上述步骤即可。

时间复杂度： $O(n + m)$

代码实现：

#include<bits/stdc++.h>
using namespace std;

#define debug(x) cout << x << endl
#define int long long
#define endl '\n'
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define pi pair<int, int>
#define lowbit(x) (x&-x)
#define all(x) x.begin(), x.end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define sqrt __builtin_sqrtl

using ll = long long;
using lll = __int128;

const int mod = 1e9 + 7;
const int MOD = 998244353;
const int N = 2e6 + 7;
const int INF = 1e18;

int dx[] = { 1, 0, -1, 0, 1, -1, 1, -1 }, dy[] = { 0, 1, 0, -1, 1, -1, -1, 1 };
int n, m, k, q, x, y, ans;

void solve() {
    cin >> n >> m;
    vector<int> a(n), b(m);
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int j = 0; j < m; j++) cin >> b[j];
    sort(all(a));
    sort(all(b));

    int cnt = 0;
    bool vis = false;
    for(int i = 0; i < n; i++){
        if(!vis && a[i] == 1) cnt++, vis = true;
        else if(a[i] != 1) cnt++;
    }

    bool f = false;
    int now = 0, l = 0, r = 0;
    while(cnt > 0 || f){
        f = false;
        bool vis = false;
        while(l < n && a[l] - 1 <= now) now++, l++, vis = true;
        if(!vis && cnt > 0) {
            cnt--;
            b[r]--;
        }
        while(r < m && b[r] <= now) now++, r++, f = true;
        if(r == m) break;
    }

    cout << (r == m ? "YES" : "NO") << endl;
}

signed main() {

    IOS;

    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

感谢您的阅读，希望对您有所帮助。