D. Explorer Space
题目链接： D. Explorer Space
题意：
给定一个 $n\times m$ 的矩阵，每个点只能走到相邻的点上，并且有各自的花费，问从每个点出发，走恰好 $k$ 步，再回到起点，最小花费是多少。
解题思路：
如果 $k$ 为奇数，显然无解。
若 $k$ 为偶数，那么就可以用 DP ，设 $f[i,j,k]$ 为已经走了第 $k$ 步，当前在 $(i,j)$ 的所有方案，属性是花费最小值。因为整个过程一定是走某一条路径，再原路返回，因此只需要做 $\frac{k}{2}$ 次转移即可。
代码如下：
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
int main()
{
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> r(n, vector<int>(m));
for (int i = 0; i < n; i ++ )
for (int j = 1; j < m; j ++ )
cin >> r[i][j];
vector<vector<int>> c(n, vector<int>(m));
for (int i = 1; i < n; i ++ )
for (int j = 0; j < m; j ++ )
cin >> c[i][j];
if (k & 1)
{
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
cout << -1 << " \n"[j == m - 1];
return 0;
}
vector<vector<int>> f(n, vector<int>(m));
for (int it = 0; it < k / 2; it ++ )
{
vector<vector<int>> nxt(n, vector<int>(m));
for (int x = 0; x < n; x ++ )
for (int y = 0; y < m; y ++ )
{
int mn = INF;
if (x + 1 < n) mn = min(mn, f[x + 1][y] + c[x + 1][y]);
if (x > 0) mn = min(mn, f[x - 1][y] + c[x][y]);
if (y + 1 < m) mn = min(mn, f[x][y + 1] + r[x][y + 1]);
if (y > 0) mn = min(mn, f[x][y - 1] + r[x][y]);
nxt[x][y] += mn;
}
f.swap(nxt);
}
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
cout << 2 * f[i][j] << " \n"[j == m - 1];
return 0;
}
D. White Lines
题目链接： D. White Lines
题意：
给定一个大小为 $n\times n$ 黑白矩阵，点击某个点，以这个点为左上角， $k\times k$ 大小的区域都变成白色，问只能点击一次的情况下，最多可以形成多少条长度为 $n$ 的水平和垂直的白线。
解题思路：
这题唯一的知识点就是前缀和，但非常讲究细节。
要确定点击每个点后，所变白的区域中，形成了多少条白线，然后在其它区域本身有多少白线。
代码如下：
#include <iostream>
using namespace std;
const int N = 2010;
int n, k;
int row[N][N], col[N][N];
int cnt_r[N], cnt_c[N];
int r[N][N], c[N][N];
int g[N][N];
char s[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i ++ )
{
cin >> s + 1;
for (int j = 1; j <= n; j ++ )
g[i][j] = (s[j] == 'B' ? 0 : 1);
}
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
{
row[i][j] = row[i][j - 1] + g[i][j];
col[i][j] = col[i - 1][j] + g[i][j];
}
for (int i = 1; i <= n; i ++ )
{
cnt_r[i] = cnt_r[i - 1] + (int)(row[i][n] == n);
cnt_c[i] = cnt_c[i - 1] + (int)(col[n][i] == n);
}
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
{
if (j + k - 1 <= n) r[i][j] += (int)(row[i][j - 1] + row[i][n] - row[i][j + k - 1] == n - k);
if (i + k - 1 <= n) c[i][j] += (int)(col[i - 1][j] + col[n][j] - col[i + k - 1][j] == n - k);
}
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
{
r[i][j] += r[i - 1][j];
c[i][j] += c[i][j - 1];
}
int res = 0;
for (int i = 1; i + k - 1 <= n; i ++ )
for (int j = 1; j + k - 1 <= n; j ++ )
{
int A = cnt_r[i - 1];
int B = cnt_r[n] - cnt_r[i + k - 1];
int C = cnt_c[j - 1];
int D = cnt_c[n] - cnt_c[j + k - 1];
int E = r[i + k - 1][j] - r[i - 1][j];
int F = c[i][j + k - 1] - c[i][j - 1];
res = max(res, A + B + C + D + E + F);
}
cout << res << '\n';
return 0;
}
C. Choosing flowers
题目链接： C. Choosing flowers
题意：
有 $m$ 种花，每种都有无限数量，一共要送 $n$ 朵。对于每种花，第一朵有 $a$ 快乐值，其它有 $b$ 快乐值，问最多能够形成多少快乐值。
解题思路：
可以发现，最终的方案如果如果有超过一朵的种类，那么一定只有一种超过一朵，其它都只送一朵。对于这类 只有一种特殊，其它常规 的情况，比较常见的做法就是枚举特殊的种类，也就是枚举哪些花是超过一朵的。
对于当前的花的 $a$ 和 $b$ ，通过二分找到比 $b$ 大的所有花的 $a$ 之和，然后加上当前的 $a$ ，并且剩下的数量都送当前花，剩下的数量每个都贡献 $b$ 。
但是要注意，如果 $a>b$ ，意味着二分找到比 $b$ 大的所有花的 $a$ 之和包括了当前的 $a$ ，和 $a\leq b$ 的情况要分别讨论。
代码如下：
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int T;
cin >> T;
while (T -- )
{
int n, m;
cin >> n >> m;
vector<pair<int, int>> a(m);
for (int i = 0; i < m; i ++ ) cin >> a[i].first >> a[i].second;
sort(a.begin(), a.end());
vector<long long> sum(m + 1);
for (int i = 0; i < m; i ++ ) sum[i + 1] = sum[i] + a[i].first;
long long res = 0;
for (int i = 0; i < m; i ++ )
{
int b = a[i].second;
long long tot = 0;
pair<int, int> t = {b, -0x3f3f3f3f};
int a_cnt = 0, b_cnt = 0;
int p = upper_bound(a.begin(), a.end(), t) - a.begin();
if (a[i].first > b)
{
a_cnt = min(n, m - p);
b_cnt = n - a_cnt;
}
else
{
tot = a[i].first;
a_cnt = min(n - 1, m - p);
b_cnt = n - 1 - a_cnt;
}
tot += sum[m] - sum[m - a_cnt];
tot += (long long)b * b_cnt;
res = max(res, tot);
}
cout << res << '\n';
}
return 0;
}
F. Robots on a Grid
题目链接： F. Robots on a Grid
题意：
给定一个大小为 $n\times m$ 的黑白矩阵，以及相同大小的操作矩阵，表示站在某点时，只能往某个方向走，问初始时最多能够放多少个机器人使得永远不会有两个机器人在某一个点上相遇，在满足这个前提下，初始时最多可以将多少个机器人放在黑点上。
解题思路：
可以发现任意一个机器人在某个点出发，走不超过 $n\times m$ 步，就会进入循环里面，如果两个机器人会在某个点相遇，那么之后走的路径都是一样的，也就是说，如果两个机器人会相遇，那么第 $n\times m$ 步的时候，它们肯定是在一起的，可以把这些机器人看作是同一类的。
因此可以用倍增优化 DP ，定义 $f[i,j]$ 为初始时将机器人放在编号为 $i$ 的格子上，走 $2^j$ 步后的位置。最后检查有多少个点能够成为终点即可，再看对于每个终点，是否存在黑色的点能够走到这个终点上。
代码如下：
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000010;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
vector<int> LOG2(N);
for (int i = 2; i < N; i ++ ) LOG2[i] = LOG2[i / 2] + 1;
int T;
cin >> T;
while (T -- )
{
int n, m;
cin >> n >> m;
vector<string> color(n);
for (auto &s : color) cin >> s;
vector<string> op(n);
for (auto &s : op) cin >> s;
vector<vector<int>> id(n, vector<int>(m));
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
id[i][j] = i * m + j;
int K = LOG2[n * m] + 2;
vector<vector<int>> f(n * m, vector<int>(K));
auto get = [&](int i, int j) -> pair<int, int>
{
if (op[i][j] == 'L') return make_pair(i, j - 1);
if (op[i][j] == 'R') return make_pair(i, j + 1);
if (op[i][j] == 'U') return make_pair(i - 1, j);
if (op[i][j] == 'D') return make_pair(i + 1, j);
};
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
{
auto [x, y] = get(i, j);
int cur = id[i][j];
int nxt = id[x][y];
f[cur][0] = nxt;
}
for (int j = 1; j < K; j ++ )
for (int i = 0; i < n * m; i ++ )
f[i][j] = f[f[i][j - 1]][j - 1];
vector<int> from(n * m), black(n * m);
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ )
{
int cur = f[id[i][j]][K - 1];
from[cur] ++ ;
if (color[i][j] == '0') black[cur] ++ ;
}
int res = 0, ans = 0;
for (int i = 0; i < n * m; i ++ )
{
res += (int)(from[i] > 0);
ans += (int)(black[i] > 0);
}
cout << res << ' ' << ans << '\n';
}
return 0;
}
D - Crossing
题目链接： D - Crossing
题意：
给定一个 $n$ ，问是否存在一种方案使得 $[1,n]$ ，每个数都恰好出现在两个数集，且任意两个数集都有且仅有一个数相同。
解题思路：
直接做不太好做，按照题目的意思，可以试试把有两个相同数的集合连一条边，可以发现这是一个完全图，一个有 $k$ 个点的完全图有 $\frac{k\times (k-1)}{2}$ 条边，题目给出的 $n$ 相当于是边数，因为有 $n$ 对数是相同的嘛，因此要找到一个满足这个等式的 $k$ ，然后直接把每个数分配到某对集合中去就行。
注意事项：
要注意的是 $n$ 为 $1$ 的特例。
代码如下：
#include <vector>
#include <iostream>
using namespace std;
int main()
{
long long n;
cin >> n;
if (n == 1)
{
cout << "Yes\n2\n";
cout << "1 1\n1 1\n";
return 0;
}
long long k = -1;
for (long long i = 1; i <= n; i ++ )
if ((i - 1) * i / 2 == n)
{
k = i;
break;
}
if (k == -1) cout << "No\n";
else
{
cout << "Yes\n";
cout << k << '\n';
vector<vector<int>> f(k);
for (int i = 0, t = 1; i < k; i ++ )
for (int j = i + 1; j < k; j ++ , t ++ )
{
f[i].emplace_back(t);
f[j].emplace_back(t);
}
for (int i = 0; i < k; i ++ )
{
cout << (int)f[i].size();
for (auto &u : f[i]) cout << ' ' << u;
cout << '\n';
}
}
return 0;
}
Protecting Zonk
题目链接： Protecting Zonk
题意：
给定一棵树，每个节点可以：
- 放一个 $A$ 装置，花费为 $c_1$ ，它可以覆盖与这个节点相邻的所有边；
- 放一个 $B$ 装置，花费为 $c_2$ ，它可以覆盖与这个节点相邻的所有边，以及覆盖与这个节点相邻的所有点相邻的所有边；
- 什么都不放。
问最少花费多少可以使得所有边被覆盖。
解题思路：
比较容易想到应该是个类背包的树形 DP ，但是状态定义比较巧妙，定义好了状态就很容易做了。
定义如下：
- $f[u][0]$ ：以 $u$ 为根的子树里面的边全被覆盖，而且 $u$ 上面的边没有被覆盖；
- $f[u][1]$ ：以 $u$ 为根的子树里面的边全被覆盖，而且 $u$ 往上延伸的一条边被覆盖；
- $f[u][2]$ ：以 $u$ 为根的子树里面的边全被覆盖，而且 $u$ 往上延伸的两一条边被覆盖；
- $f[u][3]$ ： $u$ 的儿子为 $v$ ，以 $v$ 为根的子树里面的边全被覆盖。
转移如下：
- $f[u][0]$ ：所有 $f[v][1]$ 之和。
- $f[u][1]$ ：第一种情况是在 $u$ 放 $A$ 装置，对于每个 $v$ ，取 $min(f[v][0],f[v][1],f[v][2])$ ，第二种情况是存在某个 $v$ 放了 $B$ ，其它儿子取 $min(f[v][0],f[v][1],f[v][2])$ ；
- $f[u][2]$ ：在 $u$ 放 $B$ 装置，对于每个 $v$ ，取 $min(f[v][0],f[v][1],f[v][2],f[v][3])$ ；
- $f[u][3]$ ：对于每个 $v$ ，取 $min(f[v][0],f[v][1],f[v][2])$ ；
最后对根的取 $min(f[root][0],f[root][1],f[root][2])$ 即可。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, c1, c2;
int MIN(int a, int b, int c)
{
return min(a, min(b, c));
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
while (cin >> n >> c1 >> c2, n || c1 || c2)
{
vector<vector<int>> g(n);
for (int i = 0; i < n - 1; i ++ )
{
int a, b;
cin >> a >> b;
a -- , b -- ;
g[a].emplace_back(b);
g[b].emplace_back(a);
}
vector<vector<int>> f(n, vector<int>(4));
function<void(int, int)> dfs = [&](int u, int fa)
{
f[u][0] = f[u][3] = 0;
f[u][1] = c1, f[u][2] = c2;
int mn = INF, tot = 0;
for (auto &v : g[u])
{
if (v == fa) continue;
dfs(v, u);
int t = MIN(f[v][0], f[v][1], f[v][2]);
f[u][0] += f[v][1];
f[u][1] += t;
f[u][2] += min(t, f[v][3]);
f[u][3] += t;
tot += t;
mn = min(mn, f[v][2] - t);
}
f[u][1] = min(f[u][1], tot + mn);
};
dfs(0, -1);
cout << MIN(f[0][0], f[0][1], f[0][2]) << '\n';
}
return 0;
}
