ZOJ Monthly, June 2018 Solution
分类:
IT文章
•
2025-01-09 08:42:32
A - Peer Review
Water.
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 int t, n;
5
6 int main()
7 {
8 scanf("%d", &t);
9 while (t--)
10 {
11 scanf("%d", &n);
12 for (int i = 1; i <= n; ++i) printf("0%c", "
"[i == n]);
13 }
14 return 0;
15 }
View Code
B - Boring Game
Unsolved.
C - Enigma Machine
Unsolved.
D - Number Theory
Unsolved.
E - Chasing
Solved.
题意：两个人在一个二维平面上，刚开始两个人在第二象限或者第三象限，A跑到Y轴B就不能追了，B的速度是A的K倍，求B能否追到B
思路：k < 0 那么必然不行
k == 0 判断是不是在同一高度，如果是判断起始位置
k > 0 假设y轴上存在某个点 使得A B 能够在该点相遇，列方程求解
![]()
1 #include<bits/stdc++.h>
2
3 using namespace std;
4
5 double xa, xb, ya, yb, k;
6
7 int main()
8 {
9 int t;
10 scanf("%d", &t);
11 while(t--)
12 {
13 scanf("%lf %lf %lf %lf %lf", &xa, &ya, &xb, &yb, &k);
14 if(k < 1.0)
15 {
16 puts("N");
17 }
18 else if(k == 1.0)
19 {
20 if(ya != yb) puts("N");
21 else if(xb < xa) puts("N");
22 else puts("Y");
23 }
24 else
25 {
26 double a = k * k - 1.0;
27 double b = -2.0 * k * k * ya + 2.0 * yb;
28 double c = k * k * xa * xa - xb * xb + k * k * ya * ya - yb * yb;
29 double d = b * b - 4.0 * a * c;
30 if(d >= 0) puts("N");
31 else puts("Y");
32 }
33 }
34 return 0;
35 }
View Code
F - Carrot Gathering
Unsolved.
G - Virtual Singers
Upsolved.
题意：
H - How Many Palindromes
Unsolved.
题意：
有$n个A数和m个B数 m <= n，对每个B数都匹配一个A数，使得sum_{i = 1}^{i = m} |B[i] - A[i]| 最小$
思路：
考虑费用流的思想，维护三个堆
将$A、B 数放在一起排序，然后从左往右枚举$
$如果当前数是A$
如果左边有未匹配的$B_1数，那么与之匹配即可，此操作不用考虑反悔操作$
$因为假如有另一个B_2，使得B_2 与 这个A匹配更优$
那么后面必然要有另一个$A_2 来匹配这个B_1 $
$贡献是 A_2 - B_1 + B_2 - A_1 这个式子显然小于 A_2 - B_2 + A_1 - B_1$
因为这四个数字存在大小关系
$A_2 - B_1 大于 A_2 - B_2 + A_1 - B_1$
如果左边没有未匹配的$B_1数，那么考虑B的反悔操作是否更优$
$更优的话就反悔并且将代价取反并算上A往右匹配的贡献放入堆Q_A中， 相当于反悔操作$
$如果当前数是B$
$如果左边有未匹配的A数，那么与之匹配，并且将代价取反并且算上B往右匹配的贡献放入堆Q_C中$
否则放入堆$Q_B$中表示还未匹配
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define ll long long
5 #define N 100010
6 int t, n, m; ll x;
7 struct node
8 {
9 ll v; int Type;
10 node () {}
11 node (ll v, int Type) : v(v), Type(Type) {}
12 bool operator < (const node &r) const { return v < r.v; }
13 }arr[N << 1];
14 priority_queue <ll, vector <ll> , greater <ll> > A, B, C;
15
16 int main()
17 {
18 scanf("%d", &t);
19 while (t--)
20 {
21 while (!A.empty()) A.pop();
22 while (!B.empty()) B.pop();
23 while (!C.empty()) C.pop();
24 scanf("%d%d", &n, &m);
25 for (int i = 1; i <= n; ++i)
26 {
27 scanf("%lld", &x);
28 arr[i] = node(x, 0);
29 }
30 for (int i = 1; i <= m; ++i)
31 {
32 scanf("%lld", &x);
33 arr[n + i] = node(x, 1);
34 }
35 sort(arr + 1, arr + 1 + n + m);
36 ll res = 0;
37 for (int i = 1; i <= n + m; ++i)
38 {
39 if (arr[i].Type == 1)
40 {
41 if (!A.empty())
42 {
43 x = A.top(); A.pop();
44 res += arr[i].v + x;
45 C.push(-x - 2 * arr[i].v);
46 }
47 else
48 B.push(-arr[i].v);
49 }
50 else
51 {
52 if (!B.empty())
53 {
54 x = B.top(); B.pop();
55 res += arr[i].v + x;
56 }
57 else if (!C.empty())
58 {
59 x = C.top();
60 if (arr[i].v + x < 0)
61 {
62 C.pop();
63 res += arr[i].v + x;
64 A.push(-x - 2 * arr[i].v);
65 }
66 else
67 A.push(-arr[i].v);
68 }
69 else
70 A.push(-arr[i].v);
71 }
72 }
73 printf("%lld
", res);
74 }
75 return 0;
76 }
View Code
