“蔚来杯“2022牛客暑期多校训练营（补题合集）

补题合集

训练营 1
- J-Serval and Essay
训练营 2
- K-Link with Bracket Sequence I
- L-Link with Level Editor I
训练营 3
- F-Fief
训练营 5
- D-Birds in the tree
- A-Don't Starve
训练营 6
- M-Z-Game on grid
训练营 8
- F-Longest Common Subsequence
训练营9
- B-Two Frogs
- I-The Great Wall II
待更新——

训练营 1

J-Serval and Essay

TP

题意：

n 个点多条限制关系，某个点为真当且仅当所有限制它的点 都为真，最开始定义一个点为真。
问初始设置哪个点为真时，能让关系推导后为真的点数最多

思路：

对所有限制我们建反向边；
如果知道初始点是谁，我们只需要跑一遍拓扑，所有入队的点数就答案；
但点数很多，暴力去枚举初始点是谁不可行。可以考虑记忆化的手段优化枚举。
把某点限制的点称为儿子，限制该点的点称为父亲。当一个点为真时，它可以有可能推导出自己的儿子；这个点的父亲如果为真，有可能能推导出这个点；
所以我们枚举某点时，如果该点能让自己的儿子变成 true，这个儿子我们之后就不需要枚举到了。
问题就变成，我们该如何改变枚举的顺序，使得先枚举父亲标记儿子，再枚举到儿子跳过优化。
两种解法：1. 随机化 2. 强连通标记 dfn 序
第一种方法就是靠随机枚举卡过出题人造的特殊数据，跑了一秒多。
此代码是第二种方法：优先枚举拓扑图中拓扑序在前的点，这样能保证标记优化的点更多；虽然这个图不是拓扑图，但可以通过强连通转化。

$C o d e :$

#include
#include
#define debug cout << "debug---  "
#define debug_ cout << "\n---debug---\n"
#define oper(a) operator<(const a& ee)const
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define endl "\n"
#define ul (u << 1)
#define ur (u << 1 | 1)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> PII;

const int N = 2e5 + 10, M = 2e6 + 10, mod = 998244353;
int INF = 0x3f3f3f3f; ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, B = 10, ki;

int h[N], ne[M], e[M], idx;
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int iru[N], ru[N], id[N], tid, aa[N];
bool st[N];
queue<int> q;

bool cmp(int a, int b) {
    return id[a] > id[b];
}

int dfn[N], low[N], tim, stk[N], top;
bool v[N];
void tarjan(int x) {
    dfn[x] = low[x] = ++tim;
    stk[++top] = x;
    v[x] = true;
    for (int i = h[x]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j);
            low[x] = min(low[x], low[j]);
        }
        else if (v[j])low[x] = min(low[x], dfn[j]);
    }
    if (dfn[x] == low[x]) {
        int y;
        do
        {
            y = stk[top--];//tarjan先出队时拓扑序在后
            id[y] = ++tid;
            v[y] = false;
        } while (y != x);
    }
}

void init() {
    for (int i = 1; i <= n; i++) {
        h[i] = -1;
        iru[i] = ru[i] = st[i] = 0;
        dfn[i] = low[i] = 0;
    }
    tim = top = tid = idx = 0;
}

int top_sort(int x) {
    q.push(x);
    set<int> se;
    se.insert(x);
    ru[x] = 0;

    int sum = 0;
    while (q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = true;//标记
        sum++;//能成真的点数

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            se.insert(j);
            //每一个遍历到的点，不一定最后会成真，但--入度改变了
            if (--ru[j] == 0)q.push(j);
            //当入度为 0，限制都没了，这点就成真了
        }
    }
    for (auto j : se)ru[j] = iru[j];//所以最后要恢复
    return sum;
}

void solve() {
    cin >> n;
    init();

    for (int i = 1; i <= n; i++) {
        cin >> ki; int a;
        while (ki--)
        {
            cin >> a;
            add(a, i);
            iru[i]++;//记录一下初始的入度
        }
    }

    forr(i, 1, n) {
        ru[i] = iru[i];
        if (!dfn[i])tarjan(i);
        aa[i] = i;
    }
    sort(aa + 1, aa + 1 + n, cmp);//根据拓扑序枚举点

    int ans = 0;
    forr(i, 1, n)//某点没被标记过就跑一遍
        if (!st[aa[i]])ans = max(ans, top_sort(aa[i]));

    cout << ans << endl;
}

int main() {
    cinios;
    int T = 1;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        cout << "Case #" << t << ": ";
        solve();
    }
    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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

训练营 2

K-Link with Bracket Sequence I

TP

题意：

给定一个长度 n 的 a 括号序列，求有多少个长度为 m 的 b 括号序列包含 a （子序列类型，即不连续），同时 b 要求是个 合法括号序列。

思路：

转化为 dp 求解：
$d p [i] [j] [k] 表示 a 数组匹配到前 i 个位置， b 数组匹配到前 j 个位置，此时多余的未匹配的左括号数量为 k$
如果了解括号序列，这个多余左括号就很好理解，因为一个合法括号序列里要求每个左括号一定与其右边的一个右括号匹配。
转移就分为当前匹配的是左括号还是右括号。
题意保证全部数据 m 总和不超过 $10^3$ ，理论上会超时，不清楚原因。

$C o d e :$

#include
#include
#define debug cout << "debug---  "
#define debug_ cout << "\n---debug---\n"
#define oper(a) operator<(const a& ee)const
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define endl "\n"
#define ul (u << 1)
#define ur (u << 1 | 1)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll, int> PII;

const int N = 2e2 + 10, M = 2e6 + 10, mod = 1e9 + 7;
int INF = 0x3f3f3f3f; ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, B = 10, ki;

int dp[N][N][N];
char a[N];

inline void add(int& x, int y) {
    x += y;
    if (x > mod)x -= mod;
}

void solve() {
    cin >> n >> m;
    cin >> a + 1;
    a[n + 1] = '?';

    dp[0][0][0] = 1;
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int k = 0; k <= m; k++) {

                //当前匹配的是左括号时，不管如何 b 长度都增加，左括号个数增加，a 匹配长度要看是否匹配成功
                add(dp[i + (a[i + 1] == '(')][j + 1][k + 1], dp[i][j][k]);

                //同理右括号
                if (k)add(dp[i + (a[i + 1] == ')')][j + 1][k - 1], dp[i][j][k]);
            }

    cout << dp[n][m][0] << endl;

    //清空多一位
    for (int i = 0; i <= n + 1; i++)
        for (int j = 0; j <= m + 1; j++)
            for (int k = 0; k <= m + 1; k++)
                dp[i][j][k] = 0;
}

int main() {
    cinios;
    int T = 1;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        solve();
    }
    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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

L-Link with Level Editor I

TP

题意：

n 层图，每层都有 m 个点和一样的路径。初始在 1 层，每次可以选择走一条路到另一个点或者停留，之后会自动到下一层。
要求 n 层中选最少的连续的 k 层，使得你走完 k 层后能到达 m 点。

思路：

一开始当成分层图写，还看错题，写麻烦了。事实上直接当成 dp 处理即可；
任意层的 1 点都可以当成起点，其他点都由前面层最小值 + 1 转移过来。
要开一个备用数组防止转移出现问题。

$C o d e :$

#include
#include
#define debug cout << "debug---  "
#define debug_ cout << "\n---debug---\n"
#define oper(a) operator<(const a& ee)const
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define endl "\n"
#define ul (u << 1)
#define ur (u << 1 | 1)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll, int> PII;

const int N = 2e3 + 10, M = 2e6 + 10, mod = 1e9 + 7;
int INF = 0x3f3f3f3f; ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, B = 10, ki;

int dp[N], tmp[N];

void solve() {
    cin >> n >> m;
    mem(dp, 0x3f);
    mem(tmp, 0x3f);

    int ans = INF;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ++dp[j];
            tmp[j] = dp[j];
        }
        tmp[1] = dp[1] = 1;

        cin >> ki;
        for (int j = 1; j <= ki; j++) {
            int a, b;
            cin >> a >> b;
            dp[b] = min(dp[b], tmp[a]);
        }
        ans = min(ans, dp[m]);
    }

    if (ans > INF / 2)ans = -1;
    cout << ans;
}

signed main() {
    cinios;
    int T = 1;
    for (int t = 1; t <= T; t++) {
        solve();
    }
    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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

训练营 3

F-Fief

TP

题意：

给定一个图和 q 次询问；
每次询问的两点作为两个起点 x、y，判断是否有 [1,n] 的某个排列，满足任意取 [1,i ], [ i+1,n] 的两个点集合（两个点集合必须分别包括 x 、y）彼此连通。

思路：

~~显然的~~ 双连通割点题，构思图寻找性质。可以发现：如果图不连通，或者一个连通分量与大于 2 个其他分量连接，或者一个割点与大于 2 个分量连接，即无解。之后还要判断询问的两点是否在两端点。

$C o d e :$

#include
#include
#define debug cout << "debug---  "
#define debug_ cout << "\n---debug---\n"
#define oper(a) operator<(const a& ee)const
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define endl "\n"
#define ul (u << 1)
#define ur (u << 1 | 1)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll, int> PII;

const int N = 1e5 + 10, M = 2e6 + 10, mod = 1e9 + 7;
int INF = 0x3f3f3f3f; ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, B = 10, ki;

int h[N], e[M], ne[M], idx;
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int dfn[N], low[N], tim;
int root, stk[N], top, dcnt;
bool cut[N];
vector<int> dcc[N];
int fen[N], id[N];
//记录每个双连通分量内有多少个割点，特别的如果该点是割点则记录自己在多少个分量中
//记录每个点属于哪个分量

//只记录删掉某点后会形成的连通块数量是错的
//点双的图应该是一个个双连通分量由割点连接在一起

//当且仅当当前分量有三个及以上割点，或者某个割点连着三个及以上连通块
//是不合法的情况

void tarjan(int x) {
    dfn[x] = low[x] = ++tim;
    stk[++top] = x;

    if (x == root && h[x] == -1) {
        dcc[++dcnt].push_back(x);
        return;
    }

    int cnt = 0;
    for (int i = h[x]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j);
            low[x] = min(low[x], low[j]);
            if (dfn[x] <= low[j]) {
                cnt++;
                if (x != root || cnt > 1)cut[x] = true;
                dcnt++;
                int y;
                do
                {
                    y = stk[top--];
                    dcc[dcnt].push_back(y);
                } while (y != j);
                dcc[dcnt].push_back(x);//别忘记放割点
            }
        }
        else low[x] = min(low[x], dfn[j]);
    }
}

void solve() {
    cin >> n >> m;

    mem(h, -1);
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }

    int q; cin >> q;

    if (n == 2) {
        while (q--)cout << "YES\n";
        return;
    }

    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) {
            root = i;
            cnt++;
            tarjan(i);
        }

    //图不连通肯定不合法
    if (cnt > 1) { 
        while (q--)cout << "NO\n";
        return;
    }

    int num = dcnt;
    for (int i = 1; i <= n; i++)
        if (cut[i])id[i] = ++num;//对割点也给予一个连通块编号

    for (int i = 1; i <= dcnt; i++)
        for (int j = 0; j < sz(dcc[i]); j++) {
            int v = dcc[i][j];
            if (cut[v])fen[i]++, fen[id[v]]++;//所属连通块 以及 自身作为割点
            else id[v] = i;//记录某点属于哪个连通块
        }

    for (int i = 1; i <= num; i++) {
        if (fen[i] > 2) {
            while (q--)cout << "NO\n";
            return;
        }
    }

    while (q--)
    {
        int u, v;
        cin >> u >> v;
        u = id[u], v = id[v];

        if (fen[u] == 0 && fen[v] == 0) { 
            //如果起点终点都在一个块中，无割点
            cout << "YES\n";
        }
        else if (fen[u] == 1 && fen[v] == 1 && u != v) {
            //不在一个块就需要保证在链的两端，要特判 u != v
            cout << "YES\n";
        }
        else cout << "NO\n";
    }
}

int main() {
    cinios;
    int T = 1;
    for (int t = 1; t <= T; t++) {
        solve();
    }
    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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

训练营 5

D-Birds in the tree

TP

题意：

给定一棵树，每个节点有 0/1 两种颜色，求这个无根树有多少个不同的子树，满足子树的所有叶子节点的颜色一致。

思路：

树形dpppppppppp，比赛时d死我，d出来时有种丰收的喜悦。
定义状态集合为 $d p [i] [0/1]$ ：表示以 i 结点为根，根颜色为 0/1 的所有子树中，满足所有叶子结点都为 0/1 色的方案数。

$C o d e :$

#include
#include
#define debug cout << "debug---  "
#define debug_ cout << "\n---debug---\n"
#define oper(a) operator<(const a& ee)const
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define endl "\n"
#define ul (u << 1)
#define ur (u << 1 | 1)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> PII;

const int N = 3e5 + 10, M = 1e7 + 10, mod = 1e9 + 7;
int INF = 0x3f3f3f3f; ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, B = 10, ki;

vector<int> e[N];
ll dp[N][2], ans, tmp[N][2];
//定义状态集合为 dp[i][0/1]：
//表示以 i 结点为根，不在意根颜色的所有子树中，满足 所有叶子结点都为 0/1 色的方案数。
//tmp[i][0/1]: 是在意根节点颜色 0/1 ..... balabala
int col[N];
char s[N];

void dfs(int x, int f) {
    tmp[x][0] = tmp[x][1] = 1;

    ll t[2] = { 0 };
    for (int j : e[x]) {
        if (j == f)continue;
        dfs(j, x);

        //显然转移由该子树选和不选得来
        tmp[x][0] = (tmp[x][0] * (dp[j][0] + 1)) % mod;
        tmp[x][1] = (tmp[x][1] * (dp[j][1] + 1)) % mod;

        t[0] = (t[0] + dp[j][0]) % mod;
        t[1] = (t[1] + dp[j][1]) % mod;
    }

    dp[x][0] = tmp[x][0];
    dp[x][1] = tmp[x][1];

    //但是该点的颜色被 col[x] 限制
    //如果叶子结点唯一，形成一条链，则根节点也成为一个叶子，根节点的颜色也需要和叶子结点相同
    //这类的情况数是 ∑ dp[j][0/1]，需要减去

    int to = !col[x];
    //实际颜色是 col[x]，!col[x] 的情况要去除根节点颜色和叶子结点不同的方案
    tmp[x][to] = (tmp[x][to] - t[to] - 1 + mod) % mod;
    //还需要减去只有 x 结点的 1 个情况

    dp[x][to]--;
    //同理，要减去只有 x 结点的 1 个不存在的情况

    ans = (ans + tmp[x][0] + tmp[x][1]) % mod;
    //答案就是累计 tmp
}

void solve() {
    cin >> n;
    cin >> s + 1;
    forr(i, 1, n) {
        col[i] = s[i] - '0';
    }

    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        e[a].push_back(b), e[b].push_back(a);
    }

    dfs(1, -1);

    cout << ans;
}

signed main() {
    cinios;
    int T = 1;
    for (int t = 1; t <= T; t++) {
        solve();
    }
    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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

A-Don’t Starve

TP

题意：

平面内 n 个点，初始起点在零点，每次可以走到某一个点，但要求比上一次走的路径长度严格小。可以重复走点，问最多可以走过多少次点。

思路：

一开始写的爆搜，寄得不能再寄，优化不下来。正解是 ~~最小生成树~~ dp。
因为要求路径边权严格递减，所以根据边权排序，先考虑图中大的边，从大到小dp。

$C o d e :$

#include
#include
#define debug cout << "debug---  "
#define debug_ cout << "\n---debug---\n"
#define oper(a) operator<(const a& ee)const
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define endl "\n"
#define ul (u << 1)
#define ur (u << 1 | 1)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll, int> PII;

const int N = 2e3 + 10, M = 2e6 + 10, mod = 1e9 + 7;
int INF = 0x3f3f3f3f; ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, B = 10, ki;

struct pon
{
    ll x, y;
}a[N];
struct edge {
    int a, b; ll w;
    bool oper(edge) { return w > ee.w; }
}ed[N * N];

inline ll get(pon a, pon b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

struct stk
{
    int to, st;
}stk[N * N];
int top, dp[N];
//dp[i] 表示结尾为 i 点的最大经过点数

void solve() {
    cin >> n;

    forr(i, 1, n) {
        cin >> a[i].x >> a[i].y;
    }

    int len = 0;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == j)continue;
            ed[++len] = { i,j,get(a[i],a[j]) };
        }
    }

    sort(ed + 1, ed + 1 + len);
    //大到小从 0 开始搜点，保证先考虑大的边，严格递减

    mem(dp, -0x3f);
    INF = dp[0];//初始只能从 0 点开始
    dp[0] = 0;

    for (int i = 1; i <= len; i++) {
        int j = i;
        while (j + 1 <= len && ed[j + 1].w == ed[i].w)j++;
        //权值相同的边得同时考虑，不然会彼此更新

        top = 0;
        for (int k = i; k <= j; k++) {
            if (ed[k].a)//当且仅当 a 不是零点时，题意零点是不算次数的
                stk[++top] = { ed[k].a,dp[ed[k].b] };

            //用个栈存起来，防止同层更新出错
        }

        for (int k = 1; k <= top; k++) {
            int y = stk[k].to;

            dp[y] = max(dp[y], stk[k].st + 1);
        }

        i = j;
    }
    //长得跟求是否存在次小生成树一样...

    int mx = 0;
    for (int i = 0; i <= n; i++)
        mx = max(mx, dp[i]);

    cout << mx;
}

int main() {
    cinios;
    int T = 1;
    for (int t = 1; t <= T; t++) {
        solve();
    }
    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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

训练营 6

M-Z-Game on grid

TP

别人的博客

题意：

两个人在 𝑁∗𝑀 的网格上轮流移动一个棋子。棋子初始位为 (1,1) ，每次只能向右或下移动一格。网格上有一些特殊点，移到标 ’A’ 的点先手胜，移到标 ‘B’ 的点先手败，没有移到特殊点且不能再移动棋子则为平局。问先手是否有必胜、必平局、必败的策略。

思路：

这题是个套了博弈框架的 dp 题，难点还是在对博弈的理解上。
问先手是否有必胜、必平局、必败的策略。可以考虑每个格子，每个格子属于什么态必定是由右边或下边格子状态转移过来。
比如往右是必胜，下是必败，就需要看当前格子轮到谁走了。
到 Alice 走，A 肯定会往右走，所以只要有一个格子必胜，A就必胜，是或的关系。
到 Bob 走，Bob肯定往下走不想让 A赢，此格子想要必胜，必须满足右下都是必胜，B怎么走都不影响，是与的关系。
想通博弈这点，剩下就是个维护三种情况的记忆化搜索了。

$C o d e :$

#include
#include
#include
#define debug cout << "debug---  "
#define debug_ cout << "\n---debug---\n"
#define oper(a) operator<(const a& ee)const
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define endl "\n"
#define ul (u << 1)
#define ur (u << 1 | 1)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll, int> PII;

const int N = 5e2 + 10, M = 2e6 + 10, mod = 1e9 + 7;
int INF = 0x3f3f3f3f; ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, B = 10, ki;

int dp[N][N];
char s[N][N];
bool st[3];

bool check(int x, int y) {
    return x <= n && y <= m;
}

int dfs(int x, int y, char ch) {
    if (!check(x, y))return 0;//越界情况
    if (dp[x][y] != -1)return dp[x][y];

    if (s[x][y] == '.') {
        if ((x + y) % 2 == 0) { // %2=0 时代表到 Alice 走
            dp[x][y] = dfs(x + 1, y, ch) | dfs(x, y + 1, ch);
        }
        else {
            //与的话需要在意越界情况
            if (check(x + 1, y))dp[x][y] = dfs(x + 1, y, ch);
            if (check(x, y + 1)) {
                if (dp[x][y] == -1)dp[x][y] = dfs(x, y + 1, ch);
                else dp[x][y] &= dfs(x, y + 1, ch);
            }
            if (dp[x][y] == -1)dp[x][y] = 0;
        }
    }
    else {
        //如果是目标符号就是必胜态，反之
        if (s[x][y] == ch)dp[x][y] = 1;
        else dp[x][y] = 0;
    }
    return dp[x][y];
}

bool work(char ch) {
    mem(dp, -1);
    //必胜的话站在 A，必败站在 B，必平局要求不必胜不必败地走到右下角且右下角是 .

    if (ch == '.')dp[n][m] = s[n][m] == '.' ? 1 : 0;
    return dfs(1, 1, ch);
}

void solve() {
    cin >> n >> m;
    forr(i, 1, n)cin >> s[i] + 1;

    //标记三种情况，Alice是否有 必胜、必平局、必败 的手段

    st[0] = work('A');
    st[1] = work('.');
    st[2] = work('B');

    for (int i = 0; i < 3; i++)
        if (st[i])cout << "yes ";
        else cout << "no ";
    cout << endl;
}

signed main() {
    cinios;
    int T = 1;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        solve();
    }
    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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

训练营 8

F-Longest Common Subsequence

TP

题意：

折磨场。
裸的要你求最长公共子序列，但是要 $O (n l o g n)$ ，哈哈😄签到太简单辣。

思路：

队友写的，贴个算法博客。

LCS(最长公共子序列)及其O(n)空间优化，O(nlogn)时间复杂度优化

#include 

#define int long long

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 1000010, M = 2 * N;
const int mod = 998244353;
const int MOD = 1e9 + 7;

int T;

int n, m, p, x, a, b, c;
int s[N], t[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    cin >> T;
    while (T --) {
        cin >> n >> m >> p >> x >> a >> b >> c;

        for (int i = 1; i <= n; i ++) {
            x = (((a * x) % p * x) % p + (b * x) % p + c) % p;
            s[i] = x;
        }

        for (int i = 1; i <= m; i ++) {
            x = (((a * x) % p * x) % p + (b * x) % p + c) % p;
            t[i] = x;
        }

        // for (int i = 1; i <= n; i ++) cout << s[i] << ' ';
        // cout << '\n';

        // for (int i = 1; i <= m; i ++) cout << t[i] << ' ';
        // cout << '\n';

        unordered_map<int, vector<int> > mp;
        
        for(int i = 1; i <= n; i ++) {
            if(mp.count(s[i]) == 0)
                mp[s[i]].push_back(-1);
        }

        for(int i = 1; i <= m; i ++) {
            if(mp.count(t[i]) == 1)
                mp[t[i]].push_back(i);
        }

        vector<int> dp;

        for(int i = 1; i <= n; i ++) {
            if(mp[s[i]].size() > 1) {
                for(int j = mp[s[i]].size() - 1; j > 0; j --)
                    dp.push_back(mp[s[i]][j]);
            }
        }

        // for (auto x : dp) cout << x << ' ';
        // cout << '\n';
        
        vector<int> v;
        for (int i = 0; i < dp.size(); i ++) {
            if (i == 0 || dp[i] > v.back()) {
                v.push_back(dp[i]);
            } else {
                int num = lower_bound(v.begin(), v.end(), dp[i]) - v.begin();
                v[num] = dp[i];
            }
        }

        cout << v.size() << '\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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

训练营9

B-Two Frogs

TP

题意：

两个人过河，河上 n 个石头，站在 i 石头上能跳到 $(i, i + a [i]]$ 的范围，问两个人跳同样步数到 n 石头的可能性是多少。

思路：

dp解决，状态定义为 $d p [i] [j] 表示跳 i 步到 j 石头的可能性$
因为涉及可能性，分式取模，需要求逆元。转移起来跟转移方案数差不多。

#include
#include
#define debug cout << "debug---  "
#define debug_ cout << "\n---debug---\n"
#define oper(a) operator<(const a& ee)const
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define endl "\n"
#define ul (u << 1)
#define ur (u << 1 | 1)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll, int> PII;

const int N = 8e3 + 10, M = 2e6 + 10, mod = 998244353;
int INF = 0x3f3f3f3f; ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, B = 10, ki;

ll ksm(ll a, ll b) {
    ll ans = 1;
    while (b)
    {
        if (b & 1)ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

ll inv[N];
int a[N];
int dp[N][N];
//跳 i 次，到 j 位置的可能性

void add(int& x, int y, bool f) {
    if (f)x += y;
    else x -= y;
    if (x >= mod)x -= mod;
    if (x < 0)x += mod;
}

void solve() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        cin >> a[i];
        inv[i] = ksm(a[i], mod - 2);//逆元
    }

    dp[0][1] = 1, dp[0][2] = -1;
    //根据差分定义初始化，只有 跳 0 次 到 1 位置才有 1 可能

    int ans = 0;

    for (int i = 0; i < n; i++) {

        for (int j = 1; j <= n; j++) {
            add(dp[i][j], dp[i][j - 1], 1);
            //将差分序列转化成正常序列

            int r = min(j + a[j], n) + 1;
            int l = j + 1;

            int w = inv[j] * dp[i][j] % mod;
            //当前位置转移到下一步的可能性，转移范围是一个区间

            //直接差分转移
            add(dp[i + 1][l], w, 1);
            add(dp[i + 1][r], w, 0);
        }

        //答案就是两次跳同样步数到 n 点的可能性和
        int res = (ll)dp[i][n] * dp[i][n] % mod;
        add(ans, res, 1);
    }

    cout << ans;
}

signed main() {
    cinios;
    int T = 1;
    for (int t = 1; t <= T; t++) {
        solve();
    }
    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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

I-The Great Wall II

TP

题意：

n 个数划分成 k 段，每段的值为此段最大的数，要使得每段总和尽可能小。求 k 从 1 - n 的不同最小值。

思路：

线性最值dp问题，刚好卡着的时间空间就是为了让你用栈观察性质优化。

博客图解

状态集合 $d p [i] [j]$ 表示前 i 位分成 j 段的最小总和。
需要观察出：对于 i 位，可以由之前第一个大于自己的地方 pre[i] ，即 $d p [i] [j] = min (d p [i] [j], d p [p re [i]] [j])$ ；
而区间 $[p re [i], i]$ 需要栈维护一个单调递减的区间max 值，对于不同的区间 max，维护一个最小的 $d p [区间位置] [j - 1]$ 。
讲不清楚，还是看博客吧，~~我是five~~

$C o d e :$

#include
#include
#define debug cout << "debug---  "
#define debug_ cout << "\n---debug---\n"
#define oper(a) operator<(const a& ee)const
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define endl "\n"
#define ul (u << 1)
#define ur (u << 1 | 1)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll, int> PII;

const int N = 8e3 + 10, M = 2e6 + 10, mod = 1e9 + 7;
int INF = 0x3f3f3f3f; ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, B = 10, ki;

int dp[N][N];
struct node
{
    int id, mi;
};
node stk[N];
int top, a[N];

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

    mem(dp, 0x3f);
    dp[0][0] = 0;

    a[0] = INF;
    for (int j = 1; j <= n; j++) {
        top = 0;
        stk[++top] = { 0,0 };//放一个极值边界

        for (int i = 1; i <= n; i++) {
            int mi = dp[i - 1][j - 1];
            //维护区间 [pre[i],i] 之间最小的 dp[][j-1]

            while (top && a[stk[top].id] <= a[i]) {
                mi = min(mi, stk[top].mi);
                --top;
                //最小值维护在mi中，所以可以删掉了
            }

            dp[i][j] = min(dp[stk[top].id][j], mi + a[i]);
            //dp[pre[i]][j]，或者 min(dp[][j-1]) + a[i] 转移过来

            stk[++top] = { i,mi };
            //重新把最小值放回栈中
        }

        cout << dp[n][j] << endl;
    }
}

signed main() {
    cinios;
    int T = 1;
    for (int t = 1; t <= T; t++) {
        solve();
    }
    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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

待更新——

相关阅读:
3.8 PCIe控制器——运行机制——错误处理
07 Qt自绘组件：图片预览小组件ImageViewer
VirtualBox Ubuntu系统硬盘扩容
webSocket连接数太多启动不起来怎么办？
mybatis-plus中wrapper的用法（详细）
蓝眼开源云盘部署全过程（手动安装）
波奇学C++：抽象类和搜索二叉树
CRM客户管理系统的功能模块有哪些
java之普通代码块
英语翻译时态及语法检查句子分层结构例句讯飞星火远远超越GPT4 AI大模型测评

原文地址：https://blog.csdn.net/weixin_51797626/article/details/126463633