# 题目大意
有 n 种药品，给你一个长度为 2n−1 的只有 0 1 的字符串，包含
- 定义 i (1≤i≤2n−1) 为混合了 1 种或多种药品的状态（如 3=(11)2 表示混合了 1 和 2 种药品）
而状态不一定安全，定义字符串中，如果第 i 个字符是 0 才是安全的
你现在有一个瓶子，每次可以往里面导入一种药品，请问能不能安全地混合 1→n 种药品
# 数据范围
- 1≤T≤40000
- 1≤N≤18
# 题解
C++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
| int n, t;
string s;
vector<bool> vis;
bool dfs(int u) {
if (s[u] == '1')
return false;
if (u == t)
return true;
if (vis[u])
return false;
vis[u] = true;
bool flag = 0;
for (int i = 0; i < n; i++) {
if (!((u >> i) & 1)) {
int to = (u + (1 << i));
if (s[to] == '0')
flag |= dfs(to);
}
}
return flag;
}
void solve () {
cin >> n >> s, s = " " + s, vis = vector<bool>(s.size() + 10);
t = 0;
for (int i = 0; i < n; i++)
t += (1 << i);
cout << (dfs(0) ? "Yes" : "No") << '\n';
}
|
# 题目大意
你一开始有 n 瓶可乐，有 m 家兑换商，第 i 家兑换商可以用 ai 个空瓶换 bi 瓶可乐，每次兑换都可以得到一张贴纸，请问最多能得到多少张贴纸
# 数据范围
- 1≤N≤1e18
- 1≤M≤2×105
- 1≤Bi<Ai≤1e18
# 题解
其实这题思路很容易，对于每家兑换商，可以理解成消耗 Ai−Bi 瓶可乐，兑换一张贴纸，那么我们只需要把兑换商按照 Ai−Bi 升序排列，把所有兑换商全部换完，注意，要全部换完
C++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
| void solve () {
cin >> n >> m;
auto cmp = [](PII &a, PII &b) {
return (a.first - a.second) > (b.first - b.second);
};
priority_queue<PII, vector<PII>, decltype(cmp)> heap(cmp);
for (int i = 1, a, b; i <= m; i++)
cin >> a >> b, heap.push({a, b});
int res = 0;
while (heap.size()) {
auto [a, b] = heap.top();
heap.pop();
if (n < a)
continue;
int del = a - b;
int t = (n - a) / del + 1;
res += t, n -= t * del;
}
cout << res << '\n';
}
|
这里用了 priority_queue 的自定义排序，复杂度还是 log 的，但是其实这题只要 sort 即可，但是为了启示后续能用到的地方，此处作为板子放在这里
# 题目大意
给定 n×m 的网格，每个格子上有 ai,j 个金币，在 dayi→dayn+m−1 中，第 i 天你会
- 捡起你当前所在的位置的金币
- 花 ki 金币去买饭（不然饿死）
- 买完后，你要么往下走，要么往右走（前提是不出界）
请问你，如果想要使得你饿不死，请问你初始时最少要携带多少钱（你的走的路径你自己选，找最少携带钱的路径）
# 数据范围
- 1≤n,m≤n×m≤2×105
# 题解
# bfs + 剪枝错解
C++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
| int n, m, x, y, step, num;
vector<vector<int>> a, pre;
vector<int> p;
void solve () {
cin >> n >> m;
a = vector<vector<int>>(n + 1, vector<int>(m + 1)), p = vector<int>(n + m);
pre = vector<vector<int>>(n + 1, vector<int>(m + 1, 1e18));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
for (int i = 1; i <= n + m - 1; i++)
cin >> p[i];
int ans = 1e18;
queue<pair<PII, pair<PII, int>>> q;
q.push({{1, 1}, {{1, 0}, 0}});
while (q.size()) {
auto [xy, day] = q.front();
q.pop();
x = xy.first, y = xy.second;
step = day.first.first, num = day.first.second;
num += a[x][y];
num -= p[step];
if (num < 0)
day.second = max(day.second, -num);
if (step == n + m - 1)
ans = min(ans, day.second);
if (day.second >= pre[x][y])
continue;
pre[x][y] = day.second;
for (int i = 1; i <= 2; i++) {
int xx = x + dx[i], yy = y + dy[i];
if (xx <= n && yy <= m)
q.push({{xx, yy}, {{step + 1, num}, day.second}});
}
}
cout << ans << '\n';
}
|
# DP 正解
dp[i][j] 表示从 (i,j) 走到 (n,m) 所需要的初始金币个数， dp[i][j] 由 dp[i + 1][j] 和 dp[i][j + 1]
dpi,j+ai,j−pi+j−1=min(dpi+1,j,dpi,j+1)
需要注意的是，初始 dp[n][m] 时，压根就没走，所以初始值应该是 max((int)0, p[i + j - 1] - a[i][j])
C++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
| void solve () {
cin >> n >> m;
a = vector<vector<int>>(n + 1, vector<int>(m + 1));
dp = vector<vector<int>>(n + 1, vector<int>(m + 1));
p = vector<int>(n + m + 1);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
for (int i = 1; i <= n + m - 1; i++)
cin >> p[i];
for (int i = n; i >= 1; i--)
for (int j = m; j >= 1; j--) {
if (i == n && j == m)
dp[i][j] = max((int)0, p[i + j - 1] - a[i][j]);
else {
dp[i][j] = max((int)0, p[i + j - 1] - a[i][j] +
min(i + 1 <= n ? dp[i + 1][j] : (int)1e18, j + 1 <= m ? dp[i][j + 1] : (int)1e18));
}
}
cout << dp[1][1] << '\n';
}
|
这种每次只能从上一步，往右或往下走 n+m−1 步的，可以考虑倒着 DP
