九月题目泛做总结。
Keywords
Problem On Tree, DFS & Optimization, Heap, Greedy, List, Interval&Backpack Dynamic Programming
Table of Contents
- Keywords
- BZOJ 2525 Dynamite
- Description
- Solution
BZOJ 1306 循环赛- Description
- Solution
BZOJ 2151 种树, BZOJ 1150 数据备份- Description
- Solution
BZOJ 1296 粉刷匠- Description
- Solution
BZOJ 2525 Dynamite
Description
一颗 $n$ 个点的树, 有一些关键点, 需要选择关键点, 最小化选点到所有关键点距离的最大值.
Solution
直接做肯定是不好做, 我们转验证.
那么怎么验证距离是否小于等于 $mid$ 呢? 一开始以为要再套个DP, 其实是贪心, 需要记录两种信息, 来确定是子树内部可以解决掉所有关键点, 还是需要外面的帮助.也就是树内已选点到根的最小距离 $d_1$ 和树内未被覆盖的关键点的最大深度 $d_2$.
如果两者相加小于 $mid$, 说明可以自己deal. 直接把 $d_1$置0, $d_2$置 $-\infty$.
如果 $d_2 = mid$, 树根强制选, 记录下答案.
需要注意的是 $d_1 > mid$ 的情况, 这时候要先修正一下 $d_2$. 就算子树中的炸弹都搞定了, 自己也有可能是炸弹, $d_2 = max(d_2, 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
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cctype>
using namespace std;
const int maxn = 300005;
const int inf = 0x3f3f3f3f;
struct edge
{
int to, nxt;
}e[maxn << 1];
int n, m, ptr, lnk[maxn], d[maxn], cnt;
int f[maxn], g[maxn], tot;
inline void add(int bgn, int end)
{
e[++ptr].to = end; e[ptr].nxt = lnk[bgn];
lnk[bgn] = ptr;
}
void dfs(int x, int fa, int mid)
{
f[x] = -inf; g[x] = inf;
for(int p = lnk[x]; p; p = e[p].nxt)
{
int y = e[p].to;
if(y == fa) continue;
dfs(y, x, mid);
f[x] = max(f[x], f[y] + 1);
g[x] = min(g[x], g[y] + 1);
}
if(d[x] && g[x] > mid) f[x] = max(f[x], 0);
if(f[x] + g[x] <= mid) f[x] = -inf;
if(f[x] == mid) ++tot, f[x] = -inf, g[x] = 0;
}
inline bool chk(int mid)
{
tot = 0;
dfs(1, 0, mid);
if(f[1] >= 0) tot++;
return tot <= m;
}
inline int rd()
{
register int x = 0; char c = getchar();
while(!isdigit(c)) c = getchar();
while(isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
return x;
}
int main()
{
scanf("%d%d", &n, &m);
for(register int i = 1; i <= n; ++i) d[i] = (rd() == 1);
int x, y;
for(register int i = 1; i < n; ++i)
{
x = rd(); y = rd();
add(x, y); add(y, x);
}
int l = 0, r = n, ans = 0;
while(l <= r)
{
int mid = (l + r) >> 1;
if(chk(mid)) ans = mid, r = mid - 1;
else l = mid + 1;
}
printf("%d\n", ans);
return 0;
}
|
BZOJ 1306 循环赛
Description
若干支队伍互相比赛, 胜+3, 负0, 平各+1.
给出比分情况, 求可能局面方案数.
$n \le 8$.
Solution
一看这个数据范围就比较适合乱搞.
剪枝三连: 全胜无解, 全负无解, 当前队伍最后一场比赛如果分差为2无解.
加强版就没这么简单了, 有机会做一下.
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
| #pragma GCC optimize(3)
#include <cstdio>
int n, scr[10], ans, tot;
int f[4] = {3, 1, -1, 0};
int tmp[10];
inline void dfs(int x, int y)
{
if(tmp[x] + (n - y + 1) * 3 < scr[x]) return;
if(tmp[x] > scr[x]) return;
if(x == n) {ans++; return;}
if(y == n)
{
int delt = scr[x] - tmp[x];
if(delt == 2) return;
tmp[y] += f[delt];
dfs(x + 1, x + 2);
tmp[y] -= f[delt];
}
else
{
tmp[x] += 3; dfs(x, y + 1); tmp[x] -= 3;
tmp[y] += 3; dfs(x, y + 1); tmp[y] -= 3;
tmp[x]++; tmp[y]++; dfs(x, y + 1); tmp[x]--; tmp[y]--;
}
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%d", &scr[i]);
dfs(1, 2);
printf("%d\n", ans);
return 0;
}
|
BZOJ 2151 种树, BZOJ 1150 数据备份
Description
给定每个位置的权, 不能选择相邻位置, 最大化权值和.
Solution
考虑选择一个的代价, 来修改相邻元素, 以便在更优答案时修正.
这是堆的题的一个典型性质.
这道题中, 将相邻的都删除, 变成一个大点, 点权是 $l + r - 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
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
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <vector>
#include <cctype>
using namespace std;
const int maxn = 200005;
struct node
{
int val, id;
node(int v_ = 0, int i_ = 0):
val(v_), id(i_){}
bool operator < (const node &rhs) const
{
return val < rhs.val;
}
};
int ptr, cnt, ans, lst[maxn], nxt[maxn];
int n, k, d[maxn], tag[maxn];
priority_queue<node> q;
inline int rd()
{
register int x = 0, f = 0; char c = getchar();
while(!isdigit(c)){if(c == '-') f = 1; c = getchar();}
while(isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
return f ? -x : x;
}
inline void remove(int x)
{
tag[x] = 1;
lst[nxt[x]] = lst[x];
nxt[lst[x]] = nxt[x];
}
int main()
{
n = rd(); k = rd();
if(k > n / 2)
{
puts("Error!");
return 0;
}
for(int i = 1; i <= n; ++i) d[i] = rd();
lst[1] = n; nxt[n] = 1;
for(int i = 2; i <= n; ++i) nxt[i-1] = i, lst[i] = i - 1;
for(int i = 1; i <= n; ++i) q.push(node(d[i], i));
cnt = k;
while(cnt--)
{
while(tag[q.top().id]) q.pop();
node u = q.top(); q.pop();
ans += u.val;
int va = d[lst[u.id]], vb = d[nxt[u.id]];
remove(lst[u.id]); remove(nxt[u.id]);
d[u.id] = va + vb - u.val;
q.push(node(d[u.id], u.id));
}
printf("%d\n", ans);
return 0;
}
|
BZOJ 1296 粉刷匠
Description
有若干条木板, 每一格只能刷一种给定的颜色, 不刷或刷错都是错. 颜色只有两种.
刷一次只能在一条木板上刷连续区间, 给定刷 $T$ 次, 问最多刷正确多少块.
Solution
一眼区间DP套背包, 遂上状态 $f[i][j][k]$, 肯定都能明白.
发现跪了. 那$f[i][j][k][0/1]$. 还是很明白.
怎么又跪了的说!!! $f[i][j][k][0/1][0/1]$!
算了算了转移太长了.
其实是在一条上做 $n^2$, 每次枚举断点, 前缀和优化一下.
然后再背包.
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
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
int n, m, t;
int c[55][55], sum[55];
char board[55][55];
int dp[55][2505];
int main()
{
scanf("%d%d%d", &n, &m, &t);
for(int i = 1; i <= n; ++i)
{
scanf("%s", board[i] + 1);
for(int j = 1; j <= m; ++j)
sum[j] = sum[j - 1] + (board[i][j] ^ 48);
for(int T = 1; T <= m; ++T)
for(int j = 1; j <= m; ++j)
{
c[j][T] = 0;
for(int k = 0; k < j; ++k)
{
int cnt = sum[j] - sum[k];
c[j][T] = max(c[j][T], c[k][T - 1] + max(cnt, j - k - cnt));
}
}
for(int j = 1; j <= t; ++j)
for(int k = 1; k <= min(m, j); ++k)
dp[i][j] = max(dp[i][j], dp[i - 1][j - k] + c[m][k]);
}
int ans = 0;
for(int i = 1; i <= t; ++i)
ans = max(ans, dp[n][i]);
printf("%d\n", ans);
return 0;
}
|
