很有意思的一场，上大分啦~
B
题目大意： 有 $n$ 张牌放在一个队列中，每张牌的值为 $a_i$ ，在任何时刻，都只能打出队列中前 $k$ 位的牌，然后把同一张牌放回牌堆底部。
有一张起初位置位于 $p$ 的牌，打出就胜利，但是要求所有牌出牌的总花费不能超过 $m$ ，现在要问你这张牌最多能打出多少次？
数据范围： $1 \leq k,p \leq n \leq 5000, 1 \leq m \leq 5000,1 \leq a_i \leq m$
思路：容易知道如果前 $k$ 个中不含胜利牌，则每次从其中取出最小的，如果含胜利牌，那么肯定取出它，因此可以将它视为 $-1$ ，用一个优先队列维护。
然后，后面的部分就用一个队列维护。
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
|
void solve() {
int n, k, p, m;
cin >> n >> k >> p >> m;
p--;
vi a(n);
rep(i, 0, n - 1) cin >> a[i];
int ans = 0;
int tot = a[p];
int tem = 0;
a[p] = -1;
deque<int> d;
priority_queue<int, vector<int>, greater<>> q;
rep(i, 0, k - 1) q.push(a[i]);
rep(i, k, n - 1) d.push_back(a[i]);
while (tem <= m) {
auto node = q.top();
q.pop();
if (node == -1) {
if (tem + tot > m) break;
ans++;
tem += tot;
d.push_back(-1);
auto tem2 = d.front();
d.pop_front();
q.push(tem2);
} else {
if (tem + node > m) break;
tem += node;
d.push_back(node);
auto tem2 = d.front();
d.pop_front();
q.push(tem2);
}
}
cout << ans << endl;
return;
}
|
C
题目大意：给定 $n$ 个任务，起初你的体力为 $1$ ，对于每个任务，它的整数值为 $c_i$ ，难度为 $p_i$ ，如果你不完成它，那么什么都不会发生，如果完成它，可以拿到 $S \cdot c_i$ 分， $S$ 为当前体力，随后 $S$ 会变成 $S \cdot(1-\frac{p_i}{100})$ ，求能达到的最大得分。
数据范围： $1 \leq n \leq 10^5,1 \leq c_i \leq 100,0 \leq p_i \leq 100$ 。
思路：首先观察到，无论当前的 $S$ 如何，后续能获取的最大值是固定的，也就是 $S \cdot k$ ，这里 $k$ 是与 $S$ 无关的某个常数。
也就是说，完全可以假设 $dp[i]$ 为从这里开始的强度，然后倒着遍历，有 $dp[i]=max(dp[i+1],c[i]+(1-\frac{p[i]}{100})dp[i+1])$ 。
1
2
3
4
5
6
7
8
9
10
|
void solve() {
int n;
cin >> n;
vector<pii> ma(n);
rep(i, 0, n - 1) cin >> ma[i].first >> ma[i].second;
double ans = 0.0;
frep(i, n - 1, 0) { ans = max(ans, (double)ma[i].first + (1.0 - (double)(ma[i].second) / 100.0) * ans); }
cout << fixed << setprecision(10) << ans << endl;
return;
}
|
D1
题目大意：给定一棵带有 $n$ 个节点的无向树，现在给每个边加了一个方向，给定所有元素之间能不能互相到达的矩阵，问是否能还原出加方向后树的结构？
数据范围： $2 \leq n\leq 500, 1 \leq sum(n^3) \leq 500^3$
思路：看到这个必然考虑弗洛伊德，这里有一个反向的思路，就是对于一个已经处理好弗洛伊德的矩阵，怎么把它还原回原来的矩阵，那么就是如果一个点是间接连上的，那么就把它还原。
接着，判断一下处理出来的基图是否是一棵树，并且边数跟连通性对不对即可，赛时确实有点蠢。
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
|
void solve() {
int n;
cin >> n;
vector<string> a(n);
rep(i, 0, n - 1) cin >> a[i];
vvi ma(n, vi(n));
rep(i, 0, n - 1) { rep(j, 0, n - 1) ma[i][j] = a[i][j] - '0'; }
auto ma2 = ma;
rep(i, 0, n - 1) {
if (ma[i][i] == 0) {
cout << "NO" << endl;
return;
}
}
rep(k, 0, n - 1) {
rep(i, 0, n - 1) {
rep(j, 0, n - 1) {
if (ma[i][k] == 1 && ma[k][j] == 1) {
if (k == i || k == j) continue;
if (ma[i][j] == 0) {
cout << "NO" << endl;
return;
}
if (ma[i][j] == 1) ma2[i][j] = 0;
}
}
}
}
vector<pii> res;
vector<vector<bool>> vis(n, vector<bool>(n, false));
rep(i, 0, n - 1) vis[i][i] = true;
auto dfs2 = [&](this auto&& dfs2, int x, int pa) -> void {
rep(i, 0, n - 1) {
if (!ma2[x][i] || i == x) continue;
if (vis[x][i]) continue;
res.emplace_back(x + 1, i + 1);
vis[x][i] = true;
dfs2(i, x);
}
return;
};
rep(i, 0, n - 1) { dfs2(i, -1); }
map<int, int> ma3;
for (auto& p : res) {
ma3[p.first]++;
ma3[p.second]++;
}
if (sz(res) != n - 1 || sz(ma3) != n) {
cout << "NO" << endl;
return;
}
vvi ma4(n);
for (auto& p : res) {
ma4[p.first - 1].push_back(p.second - 1);
ma4[p.second - 1].push_back(p.first - 1);
}
int ans = 0;
vector<bool> vis2(n, false);
auto dfs = [&](this auto&& dfs, int x, int pa) -> void {
vis2[x] = true;
for (auto& p : ma4[x]) {
if (p == pa || vis2[p]) continue;
dfs(p, x);
}
return;
};
rep(i, 0, n - 1) {
if (!vis2[i]) {
ans++;
dfs(i, -1);
}
}
if (ans >= 2) {
cout << "NO" << endl;
return;
}
cout << "YES" << endl;
for (auto& p : res) cout << p.first << ' ' << p.second << endl;
return;
}
|
D2
题目大意与上题相同。
数据范围： $2 \leq n \leq 8000, 1 \leq sum(n^2) \leq 8000^2$ 。
思路：非常显然地，上题的做法过不去，且本题正解应该是 $O(n^2)$ 或者 $O(n^2 \log n)$ ，不过赛时竟然放 $O(\frac{n^3}{w})$ 复杂度的过去了，到底是何意味。
首先考虑 $O(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
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
90
91
92
93
94
95
96
97
98
|
void solve() {
int n;
cin >> n;
vector<string> ma(n);
rep(i, 0, n - 1) cin >> ma[i];
rep(i, 0, n - 1) {
if (ma[i][i] == '0') {
cout << "NO" << '\n';
return;
}
}
rep(i, 0, n - 1) {
rep(j, i + 1, n - 1) {
if (ma[i][j] == '1' && ma[j][i] == '1') {
cout << "NO" << '\n';
return;
}
}
}
vi deg(n);
vvi ma2(n);
rep(i, 0, n - 1) {
rep(j, 0, n - 1) {
if (i == j || ma[i][j] == '0') continue;
ma2[i].push_back(j);
deg[j]++;
}
}
queue<int> q;
rep(i, 0, n - 1) {
if (!deg[i]) q.push(i);
}
vi tem;
while (!q.empty()) {
auto node = q.front();
tem.push_back(node);
q.pop();
for (int& p : ma2[node]) {
if (--deg[p] == 0) q.push(p);
}
}
if (sz(tem) != n) {
cout << "NO" << '\n';
return;
}
vector<pii> res;
rep(i, 0, n - 1) {
int t = tem[i];
rep(j, i + 1, n - 1) {
int v = tem[j];
if (ma[t][v] == '1') {
res.emplace_back(t + 1, v + 1);
if (sz(res) > n - 1) {
cout << "NO" << '\n';
return;
}
for (int& p : ma2[v]) {
if (ma[t][p] == '1') {
ma[t][p] = '0';
} else {
cout << "NO" << '\n';
return;
}
}
}
}
}
if (sz(res) != n - 1) {
cout << "NO" << '\n';
return;
}
vector<bool> vis(n, false);
int ans = 0;
vvi ma3(n);
for (auto& p : res) {
ma3[p.first - 1].push_back(p.second - 1);
ma3[p.second - 1].push_back(p.first - 1);
}
auto dfs = [&](this auto&& dfs, int x) -> void {
vis[x] = true;
for (auto& p : ma3[x]) {
if (!vis[p]) dfs(p);
}
};
rep(i, 0, n - 1) {
if (!vis[i]) {
ans++;
dfs(i);
}
}
if (ans >= 2) {
cout << "NO" << '\n';
return;
}
cout << "YES" << '\n';
for (auto& p : res) cout << p.first << ' ' << p.second << '\n';
return;
}
|
