noip膜你16
目录
Star Way to Heaven/God Knows/Lost My Music
Star Way to Heaven
我为什么看到这题脑子里首先出现的是把每个点都带上同种电荷然后给小w一个初速度开始模拟
因为点要从左边走到右边（废话）所以必定会穿过一些star和star与边界之间的连线，而题目要求我们求最大的最小值，因此我们可以先连上点与点，点与边界之间所有的边，然后从上到下从上边界开始建立最小生成树。这样就用长度最小的边连上了所有的点。当处理到和下边界的连线时就可以停止了，因为连上这条边后就有一条贯穿上下边界的线了。最后取MST中的最大边权（废话！为什么放着比它大的边权不走）/2即可。
Show You the Code
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
#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int maxn = 20010;
template <class type>
type read() {
type s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
struct POINT {
double x, y;
} pnt[maxn];
double getdis(POINT a, POINT b) {
return sqrt((a.x - b.x) * (a.x - b.x) * 1.0 +
(a.y - b.y) * (a.y - b.y) * 1.0);
}
int n, m, k;
double dism[maxn];
bool vis[maxn];
int main() {
n = read<int>();
m = read<int>();
k = read<int>();
For(i, 1, k) {
pnt[i].x = read<double>();
pnt[i].y = read<double>();
dism[i] = pnt[i].y / 2.0;
}
double ans = 0;
dism[k + 1] = m / 2.0;
For(i, 1, k + 1) {
double minn = 0x7f7f7f7f;
int last = 0;
For(j, 1, k + 1) {
if (!vis[j] && dism[j] < minn) {
minn = dism[j];
last = j;
}
}
ans = max(ans, dism[last]);
if (last == k + 1) {
printf("%.8f", ans);
return 0;
}
vis[last] = true;
For(j, 1, k) {
if (!vis[j]) {
double disss = getdis(pnt[last], pnt[j]) / 2;
dism[j] = min(dism[j], max(dism[last], disss));
}
}
dism[k + 1] = min(dism[k + 1], (m - pnt[last].y) / 2.0);
}
return 0;
}
God Knows
God Knows How to Solve THIS Problem
做法：线段树维护单调栈
我看的这篇博客
正解在上，我说说我的奇妙做法——贪心
如何贪心？贪心相交的边最多？NO！随随便便就可以用一个有很多相交的边但价格高的离谱的数据Hack掉。贪心删边的价格最小？Hack它太容易了吧！贪心每条边的性价比（？），把每条边（不算自己）按照能删掉的边的价值总和排序，从大向小删。能拿20分，4TLE 2WA 2AC
20 Points
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
#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int maxn = 260010;
template <class type>
type read() {
type s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
struct LINE {
int id, t, w, cost, clear;
vector<int> pas;
} ln[maxn];
bool cmp(LINE a, LINE b) { return a.clear > b.clear; }
int n;
bool clred[maxn];
int main() {
n = read<int>();
For(i, 1, n) {
int to;
to = read<int>();
ln[i].t = to;
ln[i].id = i;
}
For(i, 1, n) {
int co;
co = read<int>();
// ln[i].clear = -co;
ln[i].cost = co;
}
For(i, 1, n) {
For(j, i + 1, n) {
if (ln[j].t < ln[i].t) {
ln[i].clear += ln[j].cost;
ln[i].pas.push_back(j);
ln[j].clear += ln[i].cost;
ln[j].pas.push_back(i);
}
}
}
// For(i, 1, n) { cout << ln[i].clear << endl; }
int ans = 0;
sort(ln + 1, ln + 1 + n, cmp);
For(i, 1, n) {
if (!clred[ln[i].id]) {
// cout << "i: " << i << " cost: " << ln[i].cost << endl;
clred[i] = 1;
ans += ln[i].cost;
// cout << ln[i].id << endl;
for (auto j : ln[i].pas) {
// cout << j << endl;
clred[j] = 1;
}
}
}
cout << ans << endl;
return 0;
}
/*
5
3 1 4 5 2
3 4 3 4 1
*/
/*
5
5 1 2 3 4
395 99 99 99 99
*/
Accepted
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
#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int maxn = 1000010;
template <class type>
type read() {
type s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
class lcseg {
#define lid id << 1
#define rid id << 1 | 1
public:
int n, maxid[maxn * 4], val[maxn * 4];
public:
int v, maxr, vl[maxn * 4];
int cal(int id, int l, int r, int R) {
if (l == r) return maxid[id] > R ? val[id] : 0x3f3f3f3f;
int mid = (l + r) >> 1;
if (maxid[rid] >= R)
return min(vl[id], cal(rid, mid + 1, r, R));
else
return cal(lid, l, mid, R);
}
void insert(int id, int l, int r, int x, int pos, int V) {
if (l == r) {
maxid[id] = pos;
val[id] = V;
return;
}
int mid = (l + r) >> 1;
if (x <= mid) insert(lid, l, mid, x, pos, V);
if (x > mid) insert(rid, mid + 1, r, x, pos, V);
maxid[id] = max(maxid[lid], maxid[rid]);
vl[id] = cal(lid, l, mid, maxid[rid]);
}
void query(int id, int l, int r, int x) {
if (r <= x) {
v = min(v, cal(id, l, r, maxr));
maxr = max(maxr, maxid[id]);
return;
}
int mid = (l + r) >> 1;
if (x > mid) query(rid, mid + 1, r, x);
query(lid, l, mid, x);
}
} tr;
int lend[maxn], n, c[maxn];
int main() {
// freopen("knows.in", "r", stdin);
// freopen("knows.out", "w", stdout);
Set(tr.vl, 0x3f);
n = read<int>();
For(i, 1, n) { lend[i] = read<int>(); }
For(i, 1, n) { c[i] = read<int>(); }
For(i, 1, n) {
tr.v = 0x3f3f3f3f;
tr.maxr = 0;
tr.query(1, 1, n, lend[i]);
tr.insert(1, 1, n, lend[i], i, (tr.v == 0x3f3f3f3f ? 0 : tr.v) + c[i]);
}
tr.v = 0x3f3f3f3f;
tr.maxr = 0;
tr.query(1, 1, n, n);
cout << tr.v << endl;
return 0;
}
/*
5
3 1 4 5 2
3 4 3 4 1
*/
/*
5
5 1 2 3 4
395 99 99 99 99
*/