Codeforces Round #618 (Div. 2)

题目链接：https://codeforces.com/contest/1300

A：

贪心

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson (curpos<<1)
15 #define rson (curpos<<1|1)
16 /* namespace */
17 using namespace std;
18 /* header end */
19 
20 const int maxn = 101;
21 int n, a[maxn];
22 
23 int main() {
24     int t; scanf("%d", &t);
25     while (t--) {
26         int ans = 0, sum = 0;
27         scanf("%d", &n);
28         for (int i = 1; i <= n; i++) {
29             scanf("%d", &a[i]);
30             if (!a[i]) {
31                 a[i] = 1, ans++;
32             }
33             sum += a[i];
34         }
35         if (!sum) ans++;
36         printf("%d
", ans);
37     }
38     return 0;
39 }

View Code

B：

白给

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson (curpos<<1)
15 #define rson (curpos<<1|1)
16 /* namespace */
17 using namespace std;
18 /* header end */
19 
20 const int maxn = 2e5 + 10;
21 int n, a[maxn];
22 
23 int main() {
24     int t; scanf("%d", &t);
25     while (t--) {
26         scanf("%d", &n);
27         n = n * 2;
28         for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
29         sort(a + 1, a + 1 + n);
30         printf("%d
", a[n / 2 + 1] - a[n / 2]);
31     }
32     return 0;
33 }

View Code

C：

从高到低地检查每一个数的每一位，找出满足如下条件的一个数：该数的某一位只在该数出现过一次，其他数没有。如果存在这样的数，就把它放到数组最前面并输出整个数组；否则直接输出整个数组。

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson (curpos<<1)
15 #define rson (curpos<<1|1)
16 /* namespace */
17 using namespace std;
18 /* header end */
19 
20 const int maxn = 1e5 + 10;
21 int n, a[maxn];
22 
23 int main() {
24     scanf("%d", &n);
25     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
26     for (int j = 30; ~j; j--) {
27         int cnt = 0, pos;
28         for (int i = 1; i <= n; i++)
29             if ((a[i] >> j) & 1) {
30                 cnt++;
31                 pos = i;
32             }
33         if (cnt == 1) {
34             printf("%d ", a[pos]);
35             for (int i = 1; i <= n; i++) {
36                 if (i != pos) printf("%d ", a[i]);
37             }
38             puts("");
39             return 0;
40         }
41     }
42     for (int i = 1; i <= n; i++) printf("%d ", a[i]);
43     puts("");
44     return 0;
45 }

View Code

D：

题目有点长但其实很简单的一道题。给定一个凸包S，定义凸包T为凸包S能覆盖原点的区域(可以想象到T就是S在原点周围平移的可行域)，问S与T是否相似。

满足相似的充要条件是凸包S点数为偶数，且S为中心对称图形。

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define pb emplace_back
 6 #define mp make_pair
 7 #define eps 1e-8
 8 #define lson (curpos<<1)
 9 #define rson (curpos<<1|1)
10 /* namespace */
11 using namespace std;
12 /* header end */
13 
14 const int maxn = 1e5 + 10;
15 map<pair<ll, ll>, int>m;
16 pair<ll, ll>a[maxn];
17 int n;
18 ll midX = 0, midY = 0;
19 
20 int main() {
21     scanf("%d", &n);
22     for (int i = 1; i <= n; i++) {
23         scanf("%lld%lld", &a[i].first, &a[i].second);
24         // 放缩坐标，防止出现小数
25         a[i].first *= n, a[i].second *= n;
26         midX += a[i].first, midY += a[i].second;
27         m[mp(a[i].first, a[i].second)] = 1;
28     }
29     midX /= n, midY /= n;
30     for (int i = 1; i <= n; i++) {
31         if (!m.count(mp(2 * midX - a[i].first, 2 * midY - a[i].second))) {
32             return puts("NO"), 0;
33         }
34     }
35     puts("YES");
36     return 0;
37 }

View Code

E：

做法比较贪心。例如现在手上有一个已经处理好的数组[x1,x1,...,x1][x2,x2,...,x2]，第一块平均值为x1，第二块平均值为x2,。倘若在该数组后面加上一个新数x3，那么就需要比较x3跟x2的大小关系。如果x3<x2，就肯定要把x3合并到前一块里，再比较第二块新平均值与x1的大小关系，再决定是否要进行比较。

写起来像O(n^2)，但其实每合并一块就会使得块的数量-1，所以总体复杂度为均摊O(n)。

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define pb emplace_back
 6 #define mp make_pair
 7 #define eps 1e-8
 8 #define lson (curpos<<1)
 9 #define rson (curpos<<1|1)
10 /* namespace */
11 using namespace std;
12 /* header end */
13 
14 const int maxn = 1e6 + 10;
15 int n, p;
16 double a[maxn], len[maxn], ans[maxn];
17 
18 int main() {
19     scanf("%d", &n);
20     for (int i = 1; i <= n; i++) scanf("%lf", &a[i]);
21     for (int i = 1; i <= n; i++) {
22         ans[++p] = a[i];
23         len[p] = 1;
24         while (p > 1 && ans[p - 1] > ans[p]) {
25             ans[p - 1] = (ans[p] * len[p] + ans[p - 1] * len[p - 1]) / (len[p] + len[p - 1]);
26             len[p - 1] += len[p];
27             p--;
28         }
29     }
30     for (int i = 1; i <= p; i++) {
31         for (int j = 1; j <= len[i]; j++) {
32             printf("%.12f ", ans[i]);
33         }
34     }
35     return 0;
36 }

View Code