WHEZOJ Easy Round 4 简要题解

简单

描述

大道至简,这就是出题人没有写题目背景的原因。

给出 $2n$ 个数字,skipher 打算将它们划分成 $n$ 组,每组的得分为这一组中两个数字的较小值,求最大得分。

对于 $100\%$ 的数据,$n\le 100000,1\le a_i\le 10^9$。

分析

一道比较简单的贪心题目,考试的时候因为不会证明贪心的正确性,写了一个暴力的部分分 qwq

将原序列排序,每次取第 $i$ 个数放到第一个序列中,取第 $i + 1$ 个数放到第二个序列中,然后 $\Theta(n)$ 扫一遍,去两个序列中的最小值即可。

代码

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
//  Created by ZJYelizaveta on Tuesday, November 07, 2017 PM01:11:36 CST
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 100000 + 3;
const int INF = 0x3f3f3f3f;
int n, m;
ll a[MAX_N << 1];

namespace subtaskOne {
int vis[MAX_N << 1];
ll ans;

inline int count(int x) {
return __builtin_popcount(x);
}

ll s1[MAX_N], s2[MAX_N];
inline ll calculate() {
// for (int i = 0; i < m; ++i) printf("%d ", vis[i]); printf("\n");
int cnt1 = 0, cnt2 = 0;
for (int i = 0; i < m; ++i) {
if (vis[i]) s1[cnt1++] = a[i];
else s2[cnt2++] = a[i];
}
sort(s1, s1 + cnt1); sort(s2, s2 + cnt2);

ll res = 0;
for (int i = 0; i < cnt1; ++i) res = res + min(s1[i], s2[i]);

return res;
}

inline void solve(int sum) {
ans = 0;
for (int S = 0; S < sum; ++S) if (count(S) == n) {
memset(vis, 0, sizeof vis);
for (int i = 0; i < m; ++i) if (S & (1 << i)) {
vis[i] = 1;
}
ans = max(ans, calculate());
}
printf("%lld\n", ans);
}
}

namespace subtaskTwo {
ll s1[MAX_N], s2[MAX_N], ans;

inline void solve() {
sort(a, a + m);

int cnt = 0;
for (int i = 0; i < m; i += 2) {
s1[cnt] = a[i];
s2[cnt] = a[i + 1];
++cnt;
}
ans = 0;
for (int i = 0; i < cnt; ++i) ans += min(s1[i], s2[i]);

printf("%lld\n", ans);
}
}

int main()
{
freopen("simple.in", "r", stdin);
freopen("simple.out", "w", stdout);

n = readIn<int>(); m = 2 * n;
for (int i = 0; i < m; ++i) a[i] = readIn<ll>();

if (n <= 8) subtaskOne::solve((1 << m) - 1);
else subtaskTwo::solve();

return 0;
}

刷题

描述

现在 $n$ 张卷子,第 $i$ 张卷子的难度是 $d_i$。

现在 skipher 要从第 $1$ 张卷子刷到第 $n$ 张卷子。 如果他做完了第 $i$ 张卷子,那么他可以选择做第 $i+1,i+2,\ldots,i+k$ 张卷子(dalao 做题总是有选择性的)。 如果 skipher 选择做一张难度值不小于当前卷子难度的卷子,那么他的劳累值会 $+1$,否则不会。

为了保证足够的刷题量,同时保留足够的精力使得期中考试 AK,skipher 打算最小化劳累值。你可以认为一开始 skipher 已经刷掉了第一张卷子且劳累值为 $0$,且你必须保证 skipher 做完了第 $n$ 张卷子——压轴卷。

有 $Q$ 组询问,每组询问中 $k$ 值不同。

对于 $100\%$ 的数据,$n\le 10^6,Q \le 5, d_i \le {10}^9$。

分析

没有看出来是单调队列优化 dp,用贪心水了 80 分 qwq

令 $dp[i]$ 为做到第 $i$ 张卷子最小的劳累值。

那么有一个 $\Theta(n^{2})$ 的 dp 方程:

对于两个位置 $j, k (j < k)$ ,如果有 $dp[j] < dp[k]$ ,那么 $j$ 一定优于 $k$ ,因为就算 $d[j] \leq d[i] < d[k]$ ,那么顶多是由 $dp[j] \rightarrow dp[i]$ 和从 $dp[k] \rightarrow dp[i]$ 的 $dp[i]$ 值是相等的。

所以维护一个第一关键字是 $dp$ 值,第二关键字是劳累值的单调队列,单调队列中保存的是位置。

如果存在 $dp[j] = dp[k]$ ,那么比较两个位置上的劳累值,劳累值更大的更优。

这样可以用单调队列 $\Theta(n)$ 的来求啦,具体细节看代码,总时间复杂度 $\Theta(nq)$ 。

代码

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
//  Created by ZJYelizaveta on Thursday, November 09, 2017 AM11:52:31 CST
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 1000000 + 3;
const int INF = 0x3f3f3f3f;
int n;
int h[MAX_N];
int dp[MAX_N];

int q[MAX_N];
inline void solve(int k) {
int head = 1, tail = 1;
q[tail++] = 1;

for (int i = 2; i <= n; ++i) {
while (head < tail && q[head] + k < i) ++head;
dp[i] = dp[q[head]] + (h[q[head]] <= h[i] ? 1 : 0);

while (head < tail && (dp[i] < dp[q[tail - 1]] || dp[i] == dp[q[tail - 1]] && h[q[tail - 1]] <= h[i])) --tail;
q[tail++] = i;
}
printf("%d\n", dp[n]);
}

int main()
{
n = readIn<int>();
for (int i = 1; i <= n; ++i) h[i] = readIn<int>();

int q = readIn<int>();
while (q--) {
int k = readIn<int>();
solve(k);
}

return 0;
}

礼物

描述

skipher 想给他的妹子买圣诞礼物。

现在有 $n$ 件物品,skipher 想制作一个订单。对于每件物品 $i$,它的原价是 $v_i$, 每个物品 $i$ 有一张优惠劵,可以再原价的基础上便宜 $m_i$,但使用优惠劵是有限制的,如果要使用 $i$ 物品的优惠劵,则还需要使用另一给定物品 $p_i$ 的优惠劵。换句话说如果 skipher 的订单中同时包含物品 $p_i(1\le p_i< i)$,并且使用了 $p_i$ 的优惠劵,则购买物品 $i$ 的时候可以在原价的基础上便宜 $m_i$,每件物品仅可购买一次, 并且第一个物品没有限制,也就是说第一个物品的价格就是 $v_1 - m_1$。

现在 skipher 有 $S$ 元,请问他最多可以购买多少物品呢?

对于 $60\%$ 的数据,满足 $n\le 500$;

对于 $100\%$ 的数据,满足 $n\le 5000, S\le 10^9, 1\le m_i < v _i\le 10^9$。

分析

看出来了是一个有依赖的树形 dp 呢,但是由于是无智商选手所以有些细节没想清楚,连 $\Theta(n^{3})$ 的 dp 都没有写出来呢, 所以最后就只交了一个 $\Theta(2^{n}n)$ 的暴力 qwq

根据题目中的依赖关系来连边,然后连完边之后发现这是一个有根树,因为点 $1$ 没有依赖关系所以 $1$ 为根,同时 $p_{i} < i$ 保证了这个依赖关系中不存在环。在点 $i$ 处使用优惠券意味着可以折扣购买点 $i$ ,同事也意味着必须选择结点 $p_{i}$ ;当然也可以选择原价购买点 $i$ 处的商品。

这样一来我们就有一个 dp 转移方程。

令 $f[i][j]$ 为在购买了商品 $i$ (使用了 $i$ 的优惠券)在 $i$ 的子树中购买了 $j$ 个商品(可以使用优惠券)的最小花费。

$g[i][j]$ 为在 $i$ 的字数中购买了 $j$ 个商品且不使用优惠券的最小花费。

很明显,对于所有的叶子结点初始化为:

有转移方程:

我们可以证明这个转移方程实现的时候的时间复杂度是 $\Theta(n^{2})$ 而不是 $\Theta(n^{3})$ 的,这里没时间进行详细的证明,等有时间再来填吧!感性的理解一下,一个是更新所有的子树,再对当前节点进行更新;而将 size[u] += size[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
69
70
71
72
//  Created by ZJYelizaveta on 2017年11月09日 星期四 19时15分07秒
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 5000 + 3;
const int INF = 0x3f3f3f3f;
int n; ll S;
ll v[MAX_N], m[MAX_N];
vector<int> G[MAX_N << 1];
ll f[MAX_N][MAX_N], g[MAX_N][MAX_N];

int size[MAX_N];
ll tmpf[MAX_N], tmpg[MAX_N];
inline void dfs(int u) {
size[u] = 1;
f[u][0] = INF, f[u][1] = v[u] - m[u], g[u][1] = v[u];

for (int i = 0; i < (int)G[u].size(); ++i) {
int v = G[u][i];
dfs(v);
memset(tmpf, INF, sizeof tmpf); memset(tmpg, INF, sizeof tmpg);

// size[u] += size[v] 时间复杂度 $\Theta(n^{3})$
for (int j = 0; j <= size[u]; ++j) {
for (int k = 0; k <= size[v]; ++k) {
tmpf[j + k] = min(tmpf[j + k], f[u][j] + min(f[v][k], g[v][k]));
tmpg[j + k] = min(tmpg[j + k], g[u][j] + g[v][k]);
}
}

memcpy(f[u], tmpf, sizeof tmpf);
memcpy(g[u], tmpg, sizeof tmpg);

size[u] += size[v];
}
}


int main()
{
n = readIn<int>(), S = readIn<ll>();

for (int i = 0; i < n; ++i) {
v[i] = readIn<ll>(), m[i] = readIn<ll>();
if (i) {
int u = readIn<int>() - 1;
G[u].push_back(i);
}
}

dfs(0);

int mx = -INF;
for (int i = 0; i <= n; ++i) if (min(f[0][i], g[0][i]) <= S) {
mx = max(mx, i);
}

printf("%d\n", mx);

return 0;
}
Compartir