今天问xy打的什麽比赛，原来是他们学校找了一场neerc在训练
暑假确实要vp区域赛的题，哪怕单开、、
题面传上来了，放在资料栏、链接从文章里面点开会有路径问题..
菜成傻逼了，只会贺题..
没1900没法看数据，也没法看别人的代码（没过题之前），太折磨了
A. Alex Origami Squares
签到题
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include <bits/stdc++.h>
using ll = long long;
int main() {
freopen("alex.in", "r", stdin);
freopen("alex.out", "w", stdout);
double w, h;
std::cin >> w >> h;
if (w < h)
std::swap(w, h);
printf("%.6lf", std::max(h / 2.0, std::min(w / 3.0, h)));
return 0;
}
|
G. Graph
不会做，看的题解，主要是不会处理同一列里面，如果k还有剩余该如何交换顺序，以及断开的各个块
贪心的考虑拓扑序，依次固定数值，用一个小根堆，维护入度为0的点，这些点的拓扑序都可以在满足给出条件的基础上任意指定，如果还有边的话
那么用一个大根堆来维护已经被分配了一条边的点集
如果小根堆中的顶点$x$没有大根堆里面的好，那么把$x$加入到大根堆中，即分配一条边给它
但如果 ($k=0$) 或者 (小根堆的 $size=1$且大根堆为空或者顶点小于$x$)（这个时候分配入边则会成环，或者入度为0的点没有必要加到大根堆里），那么就直接拓扑$x$
在小根堆满足后，再按照大根堆的元素依次拓扑
拓扑的过程中，加入每个点的同时，它所指向的点入度都–，如果为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
| #include <bits/stdc++.h>
using ll = long long;
using std::vector;
int main() {
#ifndef LOCAL
freopen("graph.in", "r", stdin);
freopen("graph.out", "w", stdout);
#endif
int n, m, k;
std::cin >> n >> m >> k;
vector<int> in(n + 1, 0), ord(n + 1, 0);
vector<vector<int>> g(n + 1);
vector<std::pair<int, int>> edge;
for (int i = 1, u, v; i <= m; ++i) {
std::cin >> u >> v;
g[u].push_back(v);
in[v]++;
}
std::set<int> mn, mx;
for (int i = 1; i <= n; ++i)
if (in[i] == 0)
mn.insert(i);
int pre = 0, cnt = 0;
auto topo = [&](int x) -> void {
ord[++cnt] = x; pre = x;
for (auto y : g[x]) {
if (--in[y] == 0) mn.insert(y);
}
};
while (cnt < n) {
if (mn.empty()) {
int x = *--mx.end();
edge.push_back({pre, x});
topo(x);
mx.erase(x);
} else if (!k || mn.size() == 1 && (mx.empty() || *mn.begin() > *--mx.end())) {
int x = *mn.begin();
topo(x);
mn.erase(x);
} else {
--k;
int x = *mn.begin();
mn.erase(x);
mx.insert(x);
}
}
for (int i = 1; i <= cnt; ++i) {
std::cout << ord[i] << " \n"[i == cnt];
}
std::cout << edge.size() << '\n';
for (auto [u, v] : edge) {
std::cout << u << ' ' << v << '\n';
}
return 0;
}
|