D. Flip and Adjust (DP)
题目:
$n$ 张卡片, 正面数字 $a_i$, 背面数字 $b_i$
你来决定每张卡片正面朝上还是反面朝上
但是最后卡片上显示的数字总和必须为 $s$
思路:
定义 $dp[i][j]$: 是否能从 $1, 2, …, i$ 张卡片中得到总和 $j$
转移:
- $dp[i + 1][j] = 0$
- if $dp[i][j] == 1$
2.1: if $j + a_i < s$, 则 $dp[i + 1][j + a_i] = 1$
2.2: if $j + b_i < s$, 则 $dp[i + 1][j + b_i] = 1$
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
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, s;
cin >> n >> s;
vector<int> a(n), b(n);
for (int i = 0; i < n; i++)
{
cin >> a[i] >> b[i];
}
vector<vector<bool>> dp(n + 1, vector<bool>(s + 1, false));
dp[0][0] = true;
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= s; j++)
{
if (dp[i][j])
{
if (j + a[i] <= s)
{
dp[i + 1][j + a[i]] = true;
}
if (j + b[i] <= s)
{
dp[i + 1][j + b[i]] = true;
}
}
}
}
if (dp[n][s])
{
cout << "Yes" << endl;
string ans(n, 'H');
for (int i = n - 1; i >= 0; i--)
{
if (s >= a[i] && dp[i][s - a[i]])
{
ans[i] = 'H';
s -= a[i];
} else {
ans[i] = 'T';
s -= b[i];
}
}
cout << ans << endl;
} else {
cout << "No" << endl;
}
return 0;
}
E. Subsequence Path (DP)
题目:
现在有 $n$ 个点, $m$ 条带权有向边, 现在我们给定一个序列 $E$ , 我们称从 $1$ 到 $n$ 的一条路径为好的, 当且仅当他经过的边的编号, 是 $E$ 的子序列, 现在请找出最短的好的路径, 如果没有则输出 $-1$
思路:
因为给定了固定的序列, 那么我们对于一个路径其实就是选与不选两种选择, 我们可以dp递推一下, 用这条路径更新dist[v]即可
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
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
vector<int> a(m), b(m), c(m);
for (int i = 0; i < m; i++)
{
cin >> a[i] >> b[i] >> c[i];
a[i] -= 1;
b[i] -= 1;
}
vector<long long> dist(n, 1e18);
dist[0] = 0;
while (k--)
{
int e;
cin >> e;
e--;
if (dist[b[e]] > dist[a[e]] + c[e])
{
dist[b[e]] = dist[a[e]] + c[e];
}
}
if (dist[n - 1] == 1e18)
{
cout << -1 << endl;
} else {
cout << dist[n - 1] << endl;
}
return 0;
}
F. XOR on Grid Path (meet-in-the-middle)
题目:
给定一个 $n * n$ 的矩阵, 每个点上都有一个权值, 问从左上角出发到右下角, 并且路径权值异或和为0的方案数
思路:
- 正常DP: 时间复杂度$O(2^{2n})$
- meet-in-the-middle(双向广搜): 从 $(1, 1)$ 向对角线搜, $(n, n)$ 也向对角线搜, 最后合并结果
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
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<vector<int>> a(n, vector<int>(n, 0));
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
cin >> a[i][j];
}
}
vector<vector<vector<int>>> src(n, vector<vector<int>>(n, vector<int>()));
src[0][0].push_back(a[0][0]);
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (i + j >= n)
{
continue;
}
if (i > 0)
{
for (const int x : src[i - 1][j])
{
src[i][j].push_back(x ^ a[i][j]);
}
}
if (j > 0)
{
for (const int x : src[i][j - 1])
{
src[i][j].push_back(x ^ a[i][j]);
}
}
}
}
vector<vector<vector<int>>> dst(n, vector<vector<int>>(n, vector<int>()));
dst[n - 1][n - 1].push_back(a[n - 1][n - 1]);
for (int i = n - 1; i >= 0; --i)
{
for (int j = n - 1; j >= 0; --j)
{
if (i + j < n - 1)
{
continue;
}
if (i + 1 < n)
{
for (const int x : dst[i + 1][j])
{
dst[i][j].push_back(x ^ a[i][j]);
}
}
if (j + 1 < n)
{
for (const int x : dst[i][j + 1])
{
dst[i][j].push_back(x ^ a[i][j]);
}
}
}
}
long long ans = 0;
for (int i = 0; i < n; ++i)
{
const int j = n - i - 1;
sort(begin(dst[i][j]), end(dst[i][j]));
for (const int x : src[i][j])
{
const int val = a[i][j] ^ x;
ans += upper_bound(begin(dst[i][j]), end(dst[i][j]), val) - lower_bound(begin(dst[i][j]), end(dst[i][j]), val);
}
}
cout << ans << '\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
unordered_map<int, int> f[N][N];
int a[N][N], ans, n, m;
void dfs1(int x, int y, int v) {
if(x + y == n) {
f[x][y][v] ++ ;
return ;
}
else {
if(x + y < n) dfs1(x + 1, y, v ^ a[x + 1][y]);
if(x + y < n) dfs1(x, y + 1, v ^ a[x][y + 1]);
}
}
void dfs2(int x, int y, int v) {
if(x + y == n) {
ans += f[x][y][v ^ a[x][y]];
return ;
}
else {
if(x + y > n) dfs2(x - 1, y, v ^ a[x - 1][y]);
if(x + y > n) dfs2(x, y - 1, v ^ a[x][y - 1]);
}
}
signed main() {
cin >> n;
for(int i = 1; i <= n ; i ++ )
for(int j = 1; j <= n ; j ++ )
cin >> a[i][j];
dfs1(1, 1, a[1][1]);
dfs2(n, n, a[n][n]);
cout << ans << endl;
}