noip爆炸37
目录
我还有十几篇博客没写完……
T1 数列
是道数学题，需要用到exgcd，但是我忘了啊啊啊啊（拍桌.jpg）然后考场就骗了个部分分就滚了。
正解：用exgcd先解出一组特解，再用 $x - kb, y + ka$ 求出通解，因为要让 $abs(x) + abs(y)$ 最小，所以只会用到最小的正x或最大的负x。因为每个数之间都没有联系，因此直接统计答案即可
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
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
#define For(i, l, r) for (long long i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (long long i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const long long maxn = 100010;
template<typename 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;
}
int n, a, b;
int num[maxn];
int exgcd(int a, int b, int&x, int&y, int tmp) {
if (b == 0) {
x = tmp;
y = 0;
return a;
}
int q = exgcd(b, a%b, x, y, tmp);
int t = x;
x = y;
y = t - a / b * y;
return q;
}
int main() {
n = read<int>();
a = read<int>();
b = read<int>();
if (a > b) swap(a, b);
int ans = 0;
For(i, 1, n) {
num[i] = read<int>();
}
int x, y;
For(i, 1, n) {
int x, y;
int gcd = exgcd (a, b, x, y, 1);
int bb = b / gcd;
int aa = a / gcd;
int x1, y1;
x1 = x * num[i] / gcd;
y1 = y * num[i] / gcd;
int k = abs(x1 / bb);
if (x1 >= 0 && y1 >= 0) {
ans += min(abs(x1 - k * bb) + abs(y1 + k * aa),
abs(x1 - (k + 1) * bb) + abs(y1 + (k + 1) * aa));
} else {
if (x1 <= 0 && y1 >= 0) {
ans += min(abs(x1 + k * bb) + abs(y1 - k * aa),
abs(x1 + (k + 1) * bb) + abs(y1 - (k + 1) * aa));
} else {
if (x1 >= 0 && y1 <= 0) {
ans += min(abs(x1 - k * bb) + abs(y1 + k * aa),
abs(x1 - (k + 1) * bb) + abs(y1 + (k + 1) * aa));
}
}
}
}
cout << ans << endl;
return 0;
}
T2 数对
是道线段树优化迪屁题。因为点之间的相互顺序会对答案造成影响，所以 $a_i < b_j$ 且 $b_i < a_j$ 的点一定靠前。因此，按 $a + b$ 排序即可满足要求。在进行优化之前，先写出最基础的 $n^2$ 转移方程：设 $dp[i][j]$ 在前i个数中最大的a为j的最大权值和。分别考虑 $0 \leq j \leq min(a_i, b_i)$ 和 $a_i < j \leq b_i$ 的情况进行转移即可。但这样因为数组大小限制只能拿到60分。发现转移的过程实际上就是区间取max和区间，单点修改。于是可以用线段树优化。
60 pts
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
#include <bits/stdc++.h>
#define For(i, l, r) for (long long i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (long long i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const long long maxn = 6010;
template<typename 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 PR {
long long a, b, w;
} p[maxn];
bool cmpa(PR a, PR b) {
return (a.a + a.b) < (b.a + b.b);
}
long long n, ans;
long long sum[maxn];
long long dp[maxn][maxn]; // ft i a[i] mx j
map<long long, long long> lsh;
int main() {
n = read<long long>();
long long maxa = 0;
For(i, 1, n) {
p[i].a = read<long long>();
p[i].b = read<long long>();
p[i].w = read<long long>();
lsh[p[i].a] = 0;
lsh[p[i].b] = 0;
}
long long cnt = 0;
sort(p + 1, p + 1 + n, cmpa);
long long tmp = 0;
for (map<long long, long long>::iterator it = lsh.begin(); it != lsh.end(); it++) {
(*it).second = ++tmp;
}
For(i, 1, n) {
p[i].a = lsh[p[i].a];
p[i].b = lsh[p[i].b];
}
For(i, 1, n) {
For(j, 1, tmp) {
dp[i][j] = dp[i - 1][j];
}
For(j, 1, min(p[i].a, p[i].b)) {
dp[i][p[i].a] = max(dp[i][p[i].a], dp[i - 1][j] + p[i].w);
}
For(j, p[i].a + 1, p[i].b) {
dp[i][j] = max(dp[i][j], dp[i - 1][j] + p[i].w);
}
}
For(i, 1, tmp) {
ans = max(ans, dp[n][i]);
}
cout << ans << endl;
return 0;
}
/*
5
4 4 1
2 3 3
1 5 1
4 2 2
5 2 3
*/
Accepted 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
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#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 = 864010;
template<typename 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 segtreetmp {
#define lid id << 1
#define rid id << 1 | 1
struct treeNode {
long long l, r;
long long sum, lazy;
} tree[maxn * 8];
void update(long long id) {
tree[id].sum = max(tree[lid].sum, tree[rid].sum);
}
void down(long long id) {
tree[lid].sum += tree[id].lazy;
tree[rid].sum += tree[id].lazy;
tree[lid].lazy += tree[id].lazy;
tree[rid].lazy += tree[id].lazy;
tree[id].lazy = 0;
}
public:
void build(long long id, long long l, long long r) {
tree[id].l = l;
tree[id].r = r;
if (l == r) {
return;
}
long long mid = (l + r) / 2;
build(lid, l, mid);
build(rid, mid + 1, r);
update(id);
}
void addInterval(long long id, long long l, long long r, long long val) {
if (tree[id].l >= l && tree[id].r <= r) {
tree[id].lazy += val;
tree[id].sum += val;
return;
}
if (tree[id].lazy) down(id);
long long mid = (tree[id].l + tree[id].r) / 2;
if (l <= mid) addInterval(lid, l, r, val);
if (r > mid) addInterval(rid, l, r, val);
update(id);
}
void addPoint(long long id, long long x, long long val) {
if (tree[id].l == tree[id].r) {
tree[id].sum = max(tree[id].sum, val);
return;
}
if (tree[id].lazy) down(id);
long long mid = (tree[id].l + tree[id].r) / 2;
if (x <= mid)
addPoint(lid, x, val);
else
addPoint(rid, x, val);
update(id);
}
long long maxInterval(long long id, long long l, long long r) {
long long Max = 0;
long long mid = (tree[id].l + tree[id].r) >> 1;
if (tree[id].l >= l && tree[id].r <= r) return tree[id].sum;
if (tree[id].lazy) down(id);
if (l <= mid)
Max = max(Max, maxInterval(lid, l, r));
if (r > mid)
Max = max(Max, maxInterval(rid, l, r));
return Max;
}
} tr;
struct PR {
int a, b, w;
} p[maxn];
bool cmpa(PR a, PR b) {
return (a.a + a.b) < (b.a + b.b);
}
int n, ans;
int sum[maxn];
map<int, int> lsh;
int main() {
n = read<int>();
int maxa = 0;
For(i, 1, n) {
p[i].a = read<int>();
p[i].b = read<int>();
p[i].w = read<int>();
lsh[p[i].a] = 0;
lsh[p[i].b] = 0;
}
sort(p + 1, p + 1 + n, cmpa);
int tmp = 0;
for (map<int, int>::iterator it = lsh.begin(); it != lsh.end(); it++) {
(*it).second = ++tmp;
}
tr.build(1, 1, tmp);
For(i, 1, n) {
p[i].a = lsh[p[i].a];
p[i].b = lsh[p[i].b];
}
For(i, 1, n) {
if(p[i].a < p[i].b){
tr.addInterval(1, p[i].a + 1, p[i].b, p[i].w);
tr.addPoint(1, p[i].a, tr.maxInterval(1, 1, p[i].a) + p[i].w);
} else {
tr.addPoint(1, p[i].a, tr.maxInterval(1, 1, p[i].b) + p[i].w);
}
}
cout << tr.maxInterval(1, 1, tmp) << endl;
return 0;
}
T3 最小距离
关于SPFA
它死了
跑甚么SPFA，迪杰咔啦（？）它不香嘛。Wait! dijkstra好像是单源最短路。没关系，我们把每个特殊点都放到堆中并将dis设为0不久ok了吗？跑最短路的同时还要记录每个点是被哪个特殊点更新的。最后统计答案时需要判断更新每条边两边的点的特殊点是否相同，若不同则需要更新答案。
Show U 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
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <bits/stdc++.h>
#define For(i, l, r) for (long long i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (long long i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const long long maxn = 400010;
template<typename 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;
}
long long n, m, p;
long long pn[maxn];
struct EDGE {
long long nxt, to, w;
} edge[maxn];
long long head[maxn], tote = 1;
void addEdge(long long from, long long to, long long w) {
edge[++tote].to = to;
edge[tote].nxt = head[from];
edge[tote].w = w;
head[from] = tote;
}
long long ids[maxn];
class SP {
priority_queue<pair<long long, long long> > pq;
bool vis[maxn];
public:
long long dis[maxn];
void ins(long long id) {
pq.push(make_pair(0, id));
}
void dijkstra() {
Set(dis, 0x3f);
For(i, 1, p) {
dis[pn[i]] = 0;
}
while (!pq.empty()) {
long long x = pq.top().second;
pq.pop();
if (vis[x]) continue;
vis[x] = 1;
for (long long i = head[x]; i; i = edge[i].nxt) {
long long to = edge[i].to, w = edge[i].w;
if (dis[to] > dis[x] + w) {
dis[to] = dis[x] + w;
ids[to] = ids[x];
pq.push(make_pair(-dis[to], to));
}
}
}
}
} sp;
long long ans[maxn];
int main() {
Set(ans, 0x3f);
n = read<long long>();
m = read<long long>();
p = read<long long>();
For(i, 1, p) {
pn[i] = read<long long>();
sp.ins(pn[i]);
ids[pn[i]] = pn[i];
}
For(i, 1, m) {
long long from, to, w;
from = read<long long>();
to = read<long long>();
w = read<long long>();
addEdge(from, to, w);
addEdge(to, from, w);
}
sp.dijkstra();
for (long long i = 2; i <= tote; i += 2) {
long long x = ids[edge[i].to];
long long y = ids[edge[i ^ 1].to];
if (x != y) {
ans[x] = min(ans[x], sp.dis[edge[i].to] + sp.dis[edge[i ^ 1].to] + edge[i].w);
ans[y] = min(ans[y], sp.dis[edge[i].to] + sp.dis[edge[i ^ 1].to] + edge[i].w);
}
}
For(i, 1, p) {
cout << ans[pn[i]] << ' ';
}
cout << endl;
return 0;
}
/*
5 6 3
2 4 5
1 2 4
1 3 1
1 4 1
1 5 4
2 3 1
3 4 3
*/
```
</code>
</details>