123
D
首先直接贪心是不劣的，因为一个字母肯定是填得最近影响最小，局部最优就是全局最优。然后开一个队列维护当前未满足的字母以及当前找到了哪里，然后每次贪心能放就放，如果冲突那么重新入队接着找，如果出了矩阵就是不行，最后队列空了就有解。
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
| vector fr(n + 2, vector(m + 2, vector<int>()));
queue<array<int, 4>> q;
for(int i = 1; i <= n; i++) {
if(s[i][0] != '.') q.push({i, 1, s[i][0], 3});
if(s[i][m + 1] != '.') q.push({i, m, s[i][m + 1], 1});
}
for(int i = 1; i <= m; i++) {
if(s[0][i] != '.') q.push({1, i, s[0][i], 0});
if(s[n + 1][i] != '.') q.push({n, i, s[n + 1][i], 2});
}
constexpr int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
while(q.size()) {
auto [x, y, val, dir] = q.front();
q.pop();
if(x < 1 || x > n || y < 1 || y > m) {
cout << "NO\n";
return 0;
}
if(s[x][y] == '.') {
s[x][y] = val, fr[x][y].push_back(dir);
} else if(s[x][y] == 'x') {
q.push({x + dx[dir], y + dy[dir], val, dir});
} else if(s[x][y] != val) {
q.push({x + dx[dir], y + dy[dir], val, dir});
for(auto i : fr[x][y]) {
q.push({x + dx[i], y + dy[i], s[x][y], i});
}
s[x][y] = 'x';
} else {
fr[x][y].push_back(dir);
}
}
|
G
1.85kb的代码。。。好短。
考虑如何形式化题目中的限制，令 \(x_i\) 表示在 \(i\) 点从父亲往下有多少只乌龟下去，\(y_i\) 表示有多少只乌龟在子树中不返回，那么限制就是：
- \(x_i\geq c_i\)
- \(x_i\geq y_i\)
- \(2x_i-y_i\leq k_i\)
- \(x_i\geq \max\limits_{j\in Son_x}x_j\)
- \(y_i\geq \sum\limits_{j\in Son_x}y_j\)
容易发现这些限制是充要的，于是有了一个 \(f_{i,x,y}\) 的dp，转移为：
\[
f'_{u,x\geq c_u,y}=\min_{
\substack{
y_{1/2}\leq x_{1/2}\leq x \\
2x_2-y_2\leq k_v \\
y_1+y_2\leq y
}
}\{
(f_{u,x_1,y_1}+f{v,x_2,y_2}+2x_2-y_2)
\}
\]
复杂度 \(O(n^4)\)。
考虑优化，发现当 \(y\) 的取值固定的时候，\(x\) 取 \(\max\{y,子树 c 的最大值\}\) 最优，于是可以少掉一维，状态为 \(f_{i,y}\)，转移为
\[
f'_{u,y}=\min_{
\substack{
y_1+y_2\leq y \\
2c_v-k_v\leq y_2\leq k_v
}
}\{
f_{u,y_1}+f_{v,y_2}+2\cdot\min\{y_2,c_v\}-y_2
\}
\]
由于 \(f_x\) 的初始值为 \(0\)，于是 \(<\min,+>\) 卷积后保持凸性，可以闵可夫斯基和优化转移，转移复杂度 \(O(m)\)，总复杂度 \(O(nm)\)。
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
| auto merge = [&](vector<int> f, vector<int> g, int l, int r) -> vector<int> {
vector<int> res(m + 1, inf);
int i = 0, j = l;
while(i < m && f[i] >= inf) i++;
while(j < r && g[j] >= inf) j++;
while(i + j <= m) {
res[i + j] = f[i] + g[j];
if(j < r && f[i] + g[j + 1] < f[i + 1] + g[j]) j++;
else i++;
}
return res;
};
auto dfs = [&](auto self, int x, int fz) -> void {
fa[x] = fz;
for(auto [y, l, k] : G[x]) if(y != fz) {
ek[y] = k, el[y] = l;
self(self, y, x);
c[x] = max(c[x], c[y]);
for(int i = 0; i <= m; i++) {
f[y][i] += (2 * max(c[y], i) - i) * el[y];
}
if(ek[y] < c[y]) {
f[x] = vector(m + 1, inf);
} else {
f[x] = merge(f[x], f[y], max(2 * c[y] - ek[y], 0ll), min(m, ek[y]));
}
}
};
|
L
考虑原图的割不超过60，可以按边拆成60条不交的链。每次选一个入度为0的点，走到一个出度为0的点。这样\(\sum|in-out|\)会减少2，至多只会有60条链，60条链点并起来就是全部点。考虑每条链，后面能到的一定前面也能到，所以从后向前每个点跑bfs，能到的点就是新增的点。
特判单点连通块。这些单点的答案是1。