2022杭电多校（十）
一、比赛小结
比赛链接：Problems (hdu.edu.cn)
二、题目分析及解法（基础题）
1001、Winner Prediction
题目链接：Problem - 7244 (hdu.edu.cn)
题意：
有 n 个人在打比赛，现在已经有 m1 场比赛胜负已定， 有 m 2 场比赛胜负未知，一个人获得冠军的条件是没有人赢得比赛的次数大于他，问 1 号选手是否有可能赢得冠军
题解：
先让 1 号选手赢下所有和他有关的比赛，设此时选手 i 赢了
a
i
a_i
ai 场比赛。如果存在某个
a
i
>
a
i
+
1
a_i>a_{i+1}
ai>ai+1 则 1 号选手不可能成为冠军。否则选手
i
i
i 至多还能再赢
b
i
=
a
1
−
a
i
b_i=a_1-a_i
bi=a1−ai 场比赛。考虑建立一张网络流图：每场未进行的比赛在图中用一个点表示，源点向它连容量为 1 的边，它向它的两个参赛选手的对应点各自连容量为 1 的边；选手 i 的对应点向汇点连容量为
b
i
b_i
bi 的边。计算该图最大流，若源点出发的边满流则答案为 YES ，否则为 NO 。
代码：
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 505;
int n, T, m1, m2, s[N];
namespace Flow {
struct Edge {
int To, Val, Nxt;
} Ed[10005];
int n, S, T, Head[2005], cur[2005], dis[2005], cnt;
void AddEdge(int x, int y, int val) {
// printf("AddEdge(%d,%d,%d)\n", x, y, val);
Ed[++cnt] = (Edge){y, val, Head[x]};
Head[x] = cnt;
Ed[++cnt] = (Edge){x, 0, Head[y]};
Head[y] = cnt;
}
bool bfs() {
for (int i = 1; i <= n; i++) dis[i] = 1e9;
queue<int> Q;
Q.push(S);
dis[S] = 0;
while (!Q.empty()) {
int Now = Q.front();
Q.pop();
for (int i = Head[Now]; i != -1; i = Ed[i].Nxt) {
if (dis[Ed[i].To] == 1e9 && Ed[i].Val) {
Q.push(Ed[i].To);
dis[Ed[i].To] = dis[Now] + 1;
}
}
}
return dis[T] != 1e9;
}
int dfs(int x, int val) {
if (x == T || val == 0) {
return val;
}
int Out = 0;
for (int &i = cur[x]; i != -1; i = Ed[i].Nxt) {
if (dis[Ed[i].To] != dis[x] + 1 || !Ed[i].Val) continue;
int tmp = dfs(Ed[i].To, min(val, Ed[i].Val));
val -= tmp;
Out += tmp;
Ed[i].Val -= tmp;
Ed[i ^ 1].Val += tmp;
if (val == 0) break;
}
return Out;
}
int Dinic() {
int ans = 0;
while (bfs()) {
memcpy(cur, Head, sizeof(cur));
ans += dfs(S, 1e9);
}
return ans;
}
} // namespace Flow
int main() {
// freopen("1001.in", "r", stdin);
// freopen("1001.out", "w", stdout);
scanf("%d", &T);
while (T--) {
scanf("%d%d%d", &n, &m1, &m2);
for (int i = 1; i <= n; i++) s[i] = 0;
for (int i = 1; i <= m1; i++) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
if (z == 1)
s[x]++;
else
s[y]++;
}
Flow::n = n + m2 + 2;
Flow::S = n + m2 + 1;
Flow::T = n + m2 + 2;
Flow::cnt = -1;
for (int i = 1; i <= Flow::n; i++) {
Flow::Head[i] = -1;
}
int cnt = 0;
for (int i = 1; i <= m2; i++) {
int x, y;
scanf("%d%d", &x, &y);
if (x == 1 || y == 1) {
cnt++;
s[1]++;
continue;
}
Flow::AddEdge(n + i, x, 1);
Flow::AddEdge(n + i, y, 1);
Flow::AddEdge(Flow::S, n + i, 1);
}
bool flag = true;
for (int i = 2; i <= n; i++) {
if (s[i] > s[1]) flag = false;
Flow::AddEdge(i, Flow::T, s[1] - s[i]);
}
if (!flag) {
printf("NO\n");
continue;
}
printf(Flow::Dinic() == m2 - cnt ? "YES\n" : "NO\n");
}
}
1003、Wavy Tree
题目链接：Problem - 7246 (hdu.edu.cn)
题意：
给你一个长度为 n 的数组，你可以对数组中任一一个元素进行 +1 / -1 的操作，问至少要做多少次操作才能使数组变成波浪数组，波浪数组，即对于每一个数 i ii 都有
a
[
i
]
<
min
(
a
[
i
−
1
]
,
a
[
i
+
1
]
)
∨
a
[
i
]
>
max
(
a
[
i
−
1
]
,
a
[
i
+
1
]
)
a[i]<\min (a[i-1], a[i+1]) \ \lor \ a[i]>\max (a[i-1], a[i+1])
a[i]<min(a[i−1],a[i+1]) ∨ a[i]>max(a[i−1],a[i+1])
题解：
贪心或
d
p
dp
dp 即可
代码：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 5;
int a[maxn], b[maxn];
int n;
signed main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int _;
cin >> _;
while (_--) {
cin >> n;
for (int i = 1; i <= n; i++) cin >> b[i], a[i] = b[i];
// ↑ ↓
// f == true -> up
bool f1 = true;
int ans1 = 0;
for (int i = 2; i <= n; i++) {
if (f1) { // a[i] 应该上升
if (a[i - 1] >= a[i]) {
ans1 += (a[i - 1] + 1 - a[i]);
a[i] = a[i - 1] + 1;
}
} else { // a[i] 应该下降
if (a[i] >= a[i - 1]) {
ans1 += (a[i] + 1 - a[i - 1]);
a[i] = a[i - 1] - 1;
}
}
f1 = !f1;
}
// ↓ ↑
bool f2 = false;
int ans2 = 0;
for (int i = 2; i <= n; i++) {
if (f2) { // a[i] 应该上升
if (b[i - 1] >= b[i]) {
ans2 += (b[i - 1] + 1 - b[i]);
b[i] = b[i - 1] + 1;
}
} else { // a[i] 应该下降
if (b[i] >= b[i - 1]) {
ans2 += (b[i] + 1 - b[i - 1]);
b[i] = b[i - 1] - 1;
}
}
f2 = !f2;
}
int ans = min(ans1, ans2);
cout << ans << endl;
}
return 0;
}
1004、Average Replacement
题目链接：Problem - 7247 (hdu.edu.cn)
题意：
给定一张图，每个点均有点权
ω
i
\omega_i
ωi ，假如一个点有
k
k
k 个邻居，点权分别为
a
1
,
a
2
,
.
.
.
,
a
k
a_1, a_2, ..., a_k
a1,a2,...,ak ，那么进行一次 “交换” 后，它的权会变成
ω
i
+
a
1
+
a
2
+
.
.
.
+
a
k
k
+
1
\displaystyle \frac{\omega_i + a_1+a_2+...+a_k}{k+1}
k+1ωi+a1+a2+...+ak ，经过很多次 “交换” 后，每个点的权会收敛至一个固定值，求这些值
题解：
综合以上两点即可解出最后收敛到的那个值。时间复杂度
O
(
n
)
O(n)
O(n) 。
代码：
#include <cstdio>
using namespace std;
int n, m, T, a[100005], deg[100005];
long long Ans[100005], Sum[100005];
int F[100005];
int Find(int x) { return F[x] == x ? x : F[x] = Find(F[x]); }
int main() {
// freopen("1004.in","r",stdin);
// freopen("1005.out","w",stdout);
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
// printf("-- T = %d (n,m) = %d %d\n",T,n,m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
deg[i] = 0;
F[i] = i;
Sum[i] = Ans[i] = 0;
}
for (int i = 1; i <= m; i++) {
int x, y;
scanf("%d%d", &x, &y);
deg[x]++;
deg[y]++;
if (Find(x) != Find(y)) F[Find(x)] = Find(y);
}
for (int i = 1; i <= n; i++) {
Ans[Find(i)] += (long long)(deg[i] + 1) * a[i];
Sum[Find(i)] += (deg[i] + 1);
}
for (int i = 1; i <= n; i++) {
printf("%.6lf\n", (double)((long double)Ans[Find(i)] / Sum[Find(i)]));
// printf("%lld %lld\n",Ans[Find(i)],Sum[Find(i)]);
}
}
}
1007、Even Tree Split
题目链接：Problem - 7250 (hdu.edu.cn)
题意：
给你一个
n
n
n 节点的树（
n
n
n 是偶数），你可以从树中删除至少一条边，使得删除后各个连通块节点的个数为偶数，问有多少种删除方案。答案对
998244353
998244353
998244353 取模。
题解：
对每条边，如果删去该边后两棵树点数都为奇数，则称其为好边。显见一个边集是合法的当且仅当边集内都为好边。则答案为
2
c
−
1
2^c-1
2c−1 ，其中
c
c
c 为好边数量。时间复杂度
O
(
n
)
O(n)
O(n) 。
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int mod = 998244353;
int num[maxn];
struct e {
int to, next;
} edge[maxn << 1];
int head[maxn], tot;
int n;
void addedge(int u, int v) {
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}
int zhishu[maxn];
void init() {
tot = 0;
memset(head, -1, sizeof(head));
zhishu[0] = 1;
for (int i = 1; i < maxn; i++) {
zhishu[i] = (zhishu[i - 1] * 2) % mod;
}
}
void dfs(int u, int fa) {
num[u] = 1;
for (int i = head[u]; i != -1; i = edge[i].next) {
int v = edge[i].to;
if (v == fa) continue;
dfs(v, u);
num[u] += num[v];
}
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int _;
cin >> _;
while (_--) {
init();
cin >> n;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
addedge(u, v);
addedge(v, u);
}
dfs(1, 0);
int ans = 0;
for (int i = 1; i <= n; i++) {
if (num[i] % 2 == 0) ans++;
}
ans = ans - 1;
cout << zhishu[ans] - 1 << endl;
}
return 0;
}
1009、Painting Game
题目链接：Problem - 7252 (hdu.edu.cn)
题意：
给一个 1 × n 的网格，Alice 和 Bob 轮流给一个网格涂成黑色，要求不能在已经涂成黑色的网格旁涂色，Alice 想最小化黑色网格数量，Bob想最大化黑色网格数量，给出 n 和先手的人，输出黑色网格数量。
题解：
我们把涂黑操作想象成剪掉连续的三个格子。如果每个连续段长度都
≤
2
\leq 2
≤2 ，那么结果事实上已经决定了。在此之前，可以发现，Alice 的一种最优策略是：选某个连续段的左数第二个格子涂黑；Bob 的一种最优策略是：选某个连续段的左数第三个格子涂黑。设
f
(
n
)
,
g
(
n
)
f(n), g(n)
f(n),g(n) 分别为 Alice、Bob 面对长度为
n
n
n 的空纸带时的答案。则有
f
(
n
)
=
g
(
n
−
3
)
+
1
,
g
(
n
)
=
f
(
n
−
4
)
+
2
,
n
≥
7
f(n)=g(n-3)+1, g(n)=f(n-4)+2, \ n\geq 7
f(n)=g(n−3)+1,g(n)=f(n−4)+2, n≥7 。时间复杂度
O
(
n
)
O(n)
O(n) 。
代码：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;
int n;
string s;
int A[maxn], B[maxn];
void init() {
A[1] = B[1] = A[2] = B[2] = A[3] = 1;
A[4] = B[3] = B[4] = 2;
for (int i = 5; i < maxn; i++) {
A[i] = B[i - 3] + 1;
B[i] = A[i - 4] + 2;
}
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
init();
int _;
cin >> _;
while (_--) {
cin >> n >> s;
int ans = (n - 1) / 7 * 3 + 1;
int tmp = (n - 1) % 7 + 1;
if (s == "Alice") {
if (tmp >= 4) ans++;
if (tmp >= 6) ans++;
} else if (s == "Bob") {
if (tmp >= 3) ans++;
if (tmp >= 5) ans++;
}
cout << ans << endl;
}
for (int i = 1; i < 20; i++)
cout << "i=" << i << " " << A[i] << " " << B[i] << endl;
return 0;
}
三、题目分析及解法（进阶题）
