本篇题解只是记录我的做题过程代码，不提供最优解
（另外这里所有的时间复杂度都只分析单个样例，不算$t$的时间复杂度）

A

点击此处查看对应的题目.
本题设计算法：模拟
用map存一下每个元素的次数，然后按题目要求输出yes or no

时间复杂度 $O(nlogn)$

#include 
#include 
#include 
#include 
#include 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

---

B

点击此处查看对应的题目.
本题设计算法：dfs

dfs遍历一遍图即可

时间复杂度 $O(n)$

#include 
#include 
#include 
#include 
#include 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

---

C

点击此处查看对应的题目.
本题设计算法：dfs

题目要求在1 - m的数中，选n个，且保证字典序和不重复

直接使用dfs保证其字典序，然后再临界条件处加一个判重的过程即可

时间复杂度 $O(nlogn\ast (1-m^n)/1-m)$

#include 
#include 
#include 
#include 
#include 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

---

D

点击此处查看对应的题目.
本题设计算法：动态规划(线性dp)

本题根据题意实际上就是找两个节点的最佳位置使得整体和最小，那么如果硬枚举会超时。

但我们发现，实际上整个序列被分成了三段，所以我们这里采用动态规划的方式，将二维枚举转化成对三个状态分别进行枚举迭代。

状态表示： dp[i][j]表示 : 当i == 0时，表示前 j 个元素是 l 段的最小和，当i == 1，表示前 j 个元素的最小和，当i == 2，表示前 j 个元素中 r 段的最小和

状态转移：

• dp[0][i] = dp[0][i - 1] + l;
• dp[1][i] = min(dp[1][i - 1] + a[i],dp[0][i]);
• dp[2][i] = min(dp[2][i - 1] + r,dp[1][i]);

但注意这三段的dp数组更新是具有顺序的，因为实际上是根据 l -> a[i] -> r 的更新方式，本质是线性的。

l段 只能由 l段更新
a[i]段 只能由 a[i]段 或 l段更新
r段只能由a[i]段 或 r段更新

时间复杂度 $O(n)$

#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
typedef pair PII;
const int N = 2e5 + 10;
//当i==0时，表示前j个元素是l段的最小和，当i==1，表示前j个元素的最小和，当i==2，表示前j个元素中r段的最小和
ll dp[3][N];
ll a[N];

int main()
{
    int n,l,r;
    cin >> n >> l >> r;
    for (int i = 1;i <= n;i ++ ) scanf("%lld",&a[i]);

    memset(dp,0x3f,sizeof dp);
    dp[0][0] = dp[1][0] = dp[2][0] = 0;
    for (int i = 1;i <= n;i ++ ) {
        dp[0][i] = dp[0][i - 1] + l;
        dp[1][i] = min(dp[1][i - 1] + a[i],dp[0][i]);
        dp[2][i] = min(dp[2][i - 1] + r,dp[1][i]);
    }

    cout << dp[2][n] << '\n';
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

---

E

点击此处查看对应的题目.
本题设计算法：快速幂求逆元 + 动态规划(期望dp) + 前缀和

状态表示： dp[i] 表示从 i 走到点n的期望步数，dp[n] = 0

状态转移：

• dp[i] = (dp[i + 1] + dp[i + 2] + dp[i + 3] + … + dp[i + a[i]]) / a[i] + 1

所以我们从后往前枚举即可，并且记录一个后缀和 pre 数组，这样时间复杂度就降低了，其中注意出发不可直接取模，需要转化为乘以其逆元，又因为本题模数是 998244353(质数)，所以可以用快速幂求逆元。

时间复杂度 $O(nlog(mod-2))$

#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const ll N = 2e5 + 10,mod = 998244353;
ll a[N],dp[N],pre[N];// dp[i] 表示从 i 走到点n的期望步数，dp[n] = 0

ll qmi(ll a,ll b) 
{
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}
int main()
{
    int n;
    cin >> n;
    for (int i = 1;i < n;i ++ ) cin >> a[i];
    for (int i = n - 1;i >= 1;i -- ) {
        dp[i] = (((pre[i + 1] - pre[i + a[i] + 1] + mod + 1) % mod * qmi(a[i],mod - 2)) + 1 + mod) % mod;
        pre[i] = (pre[i + 1] + dp[i]) % mod;
    }
    cout << dp[1] << '\n';
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31