2018 Southern Russia Open Championship

毛子场，题目有点trick，最后B一眼被我提出解法，队友写锅了，有点可惜。

A：

solver：czq

 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 = 1e3 + 10;
15 int n, a[MAXN], b[MAXN];
16 int top1 = 0, top2 = 0, p1 = 0, p2 = 0;
17 struct Node {
18     int index, delta;
19     Node() {}
20     Node(int _idx, int _del): index(_idx), delta(_del) {}
21 } st1[MAXN], st2[MAXN];
22 
23 int main() {
24     ios::sync_with_stdio(false);
25     cin.tie(0);
26     cin >> n;
27     for (int i = 1; i <= n; i++) cin >> a[i];
28     for (int i = 1; i <= n; i++) cin >> b[i];
29     for (int i = 1; i <= n; i++) {
30         int delta = a[i] - b[i];
31         if (delta > 0)
32             st1[top1++] = Node(i, delta);
33         else
34             st2[top2++] = Node(i, delta);
35     }
36     while (p1 < top1) {
37         auto curr = st1[p1++];
38         int index = curr.index, delta = curr.delta;
39         while (delta) {
40             auto t = st2[p2];
41             int tmp = min(delta, -t.delta);
42             if (tmp) cout << index << " " << t.index << " " << tmp << endl;
43             delta -= tmp;
44             st2[p2].delta += tmp;
45             if (!st2[p2].delta) p2++;
46         }
47     }
48     return 0;
49 }

View Code

B：

一眼出做法：对凸包求直径，然后直径把凸包分为左右凸包，求左右凸包上面的点的较小值就行。

唯一坑点就是三点共线。

C：

solver：czq

 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 int n, k, ans = 0;
16 int a[MAXN], nextPos[MAXN];
17 vector<int>pos[MAXN];
18 set<int>nums, used;
19 
20 int main() {
21     for (int i = 0; i < MAXN; i++) nextPos[i] = -1;
22 
23     ios::sync_with_stdio(false);
24     cin.tie(0);
25 
26     cin >> n >> k;
27     for (int i = 0; i < n; i++) {
28         cin >> a[i];
29         pos[a[i]].push_back(i);
30         nums.insert(a[i]);
31     }
32     for (auto num : nums) {
33         for (int i = (int)pos[num].size() - 2; i >= 0; i--) {
34             nextPos[pos[num][i]] = pos[num][i + 1];
35             // cout << nextPos[pos[num][i]] << endl;
36         }
37     }
38     for (int i = 0; i < n; i++) {
39         if (used.find(i) != used.end()) used.erase(i);
40         else {
41             ans++;
42             if ((int)used.size() >= k) used.erase(*used.rbegin());
43         }
44         if (nextPos[i] != -1) {
45             used.insert(nextPos[i]);
46             // cout << nextPos[i] << endl;
47         }
48     }
49     cout << ans << endl;
50     return 0;
51 }

View Code

D：

solver：czq

很晚才发现是水题

 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 int n, m, days, knowEach[MAXN];
16 vector<int>g[MAXN];
17 set<int>canBeKill;
18 
19 int main() {
20     for (int i = 0; i < MAXN; i++) knowEach[i] = 0;
21     ios::sync_with_stdio(false);
22     cin.tie(0);
23 
24     cin >> n >> m;
25     for (int i = 1; i <= m; i++) {
26         int u, v; cin >> u >> v;
27         g[u].push_back(v);
28         g[v].push_back(u);
29     }
30     cin >> days;
31     for (int day = 1; day <= days; day++) {
32         int die; cin >> die;
33         if (day == 1) {
34             for (auto people : g[die]) {
35                 canBeKill.insert(people);
36                 knowEach[people] = 1;
37             }
38         } else {
39             for (auto people : g[die]) {
40                 knowEach[people] = 1;
41             }
42             if (knowEach[die]) {
43                 if (canBeKill.find(die) != canBeKill.end()) canBeKill.erase(die);
44             } else {
45                 set<int>tmp;
46                 for (auto people : g[die]) {
47                     if (canBeKill.find(people) != canBeKill.end()) tmp.insert(people);
48                 }
49                 canBeKill = tmp;
50             }
51         }
52         if (canBeKill.size() == 1) {
53             cout << day << " " << *canBeKill.begin() << endl;
54             return 0;
55         }
56     }
57     cout << "-1" << endl;
58     return 0;
59 }

View Code

E：

solver：zyh、lzh

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int checkStart(int x, int k) {
 4     x %= k;
 5     return x % 2 == 0 ? 1 : 0;
 6 }
 7 int main() {
 8     int n, k;
 9     scanf("%d%d", &n, &k);
10     if (n == 1) {
11         printf("1");
12         return 0;
13     }
14     int maxx = max((n + k - 1) / k, 2);
15     if (maxx == 2 && k % 2 == 0) maxx++;
16     for (int i = 0; i < n; ++i) {
17         printf("%d ", (checkStart(i, k) + i / k) % maxx + 1);
18     }
19 }

View Code

G：

solver：czq

K个任务一个周期去思考就非常简单

1 t, k = map(int, input().split())
2 # print(t, k)
3 totalTime = 2 * t + t * (k - 1)
4 print((totalTime % k != 0) + (totalTime // k))

View Code

H：

solver：zyh

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int T[200001];
 4 set<pair<int, int>> Set[200001];
 5 int s[200001];
 6 int b[200001];
 7 struct query {
 8     int id, val;
 9     query() {}
10     query(int _id, int _val) {
11         id = _id;
12         val = _val;
13     }
14     bool operator< (const query &b) const {
15         return val < b.val;
16     }
17 };
18 query q[200001];
19 int lowbit(int x) {
20     return x & (-x);
21 }
22 struct tree_array {
23     int n, st;
24     int a[200001];
25     inline void setRange(int N) {
26         n = N;
27         st = 1;
28         while ((st << 1) <= n) st <<= 1;
29     }
30     inline void clear() {
31         memset(a, 0, sizeof(a));
32     }
33     inline void add(int pos, int val) {
34         for (int i = pos; i <= n; i += lowbit(i)) a[i] += val;
35     }
36     inline int query(int pos) {
37         int rnt = 0;
38         for (int i = pos; i > 0; i -= lowbit(i)) rnt += a[i];
39         return rnt;
40     }
41 };
42 tree_array tr;
43 int ans[200001];
44 int main() {
45     int n, m, Q;
46     scanf("%d", &n);
47     for (int i = 0; i < n; ++i) scanf("%d", &T[i]);
48 
49     scanf("%d", &m);
50     for (int i = 0; i < m; ++i) {
51         scanf("%d%d", &s[i], &b[i]);
52     }
53     s[m] = INT_MAX;
54     for (int i = 0; i < m; ++i) {
55         Set[b[i]].insert(make_pair(s[i], s[i + 1] - 1));
56     }
57     scanf("%d", &Q);
58     for (int i = 1; i <= Q; ++i) {
59         int x;
60         scanf("%d", &x);
61         q[i] = query(i, -x);
62     }
63     sort(q + 1, q + Q + 1);
64     tr.setRange(Q);
65     //for (int i=1;i<=Q;++i) cout<<q[i].val<<" ";
66     //cout<<endl;
67     for (int i = 1; i <= n; ++i) {
68         for (auto seg : Set[i]) {
69             int l = seg.first - T[i - 1];
70             int r = seg.second - T[i - 1];
71             //cout<<"[debug] "<<i<<' '<<l<<" "<<r<<endl;
72             int l1 = lower_bound(q + 1, q + Q + 1, query(0, l)) - q;
73             int r1 = upper_bound(q + 1, q + Q + 1, query(0, r)) - q;
74             if (l1 < r1) {
75                 if (l1 <= Q && l1 > 0) tr.add(l1, 1);
76                 if (r1 <= Q && r1 > 0) tr.add(r1, -1);
77             }
78         }
79     }
80     for (int i = 1; i <= Q; ++i) {
81         ans[q[i].id] = tr.query(i);
82     }
83     for (int i = 1; i <= Q; ++i) printf("%d ", ans[i]);
84 }

View Code

I：

solver：czq、lzh

 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 = 10;
15 int n, ans = 0, vis[MAXN], mustPass[MAXN][MAXN], notPass[MAXN][MAXN], path[MAXN];
16 
17 int main() {
18     ios::sync_with_stdio(false);
19     cin.tie(0);
20     for (int i = 0; i < MAXN; i++) vis[i] = 0;
21     notPass[1][3] = notPass[3][1] = notPass[4][6] = notPass[6][4] = notPass[7][9] = notPass[9][7] = 1;
22     notPass[1][7] = notPass[7][1] = notPass[2][8] = notPass[8][2] = notPass[3][9] = notPass[9][3] = 1;
23     notPass[1][9] = notPass[9][1] = notPass[3][7] = notPass[7][3] = 1;
24 
25     cin >> n;
26     for (int i = 1; i <= n; i++) {
27         int u, v; cin >> u >> v;
28         mustPass[u][v] = mustPass[v][u] = 1;
29     }
30 
31     function<int(int)> checkVaild = [&](int depth) {
32         int tmp = 0;
33         // 必须穿过所有合法路径
34         for (int i = 1; i < depth; i++) {
35             tmp += mustPass[path[i]][path[i + 1]];
36         }
37         if (tmp != n) return 0;
38         // 不穿过非法路径
39         for (int i = 1; i < depth; i++) {
40             if (notPass[path[i]][path[i + 1]]) {
41                 return 0;
42             }
43         }
44         return 1;
45     };
46 
47     function<void(int)> dfs = [&](int depth) {
48         if (depth >= 3) ans = ans + checkVaild(depth - 1);
49         if (depth >= 10) return;
50         for (int i = 1; i < MAXN; i++) {
51             if (!vis[i]) {
52                 vis[i] = 1;
53                 path[depth] = i;
54                 dfs(depth + 1);
55                 vis[i] = 0;
56             }
57         }
58     };
59 
60     dfs(1);
61 
62     cout << ans << endl;
63 
64     return 0;
65 }

View Code

J：

solver：lzh、zyh

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 struct island {
 5     int num[100010], n, deg[100010], vis[100010];
 6     vector<int> v[100010];
 7     int solve() {
 8         scanf("%d", &n);
 9         for (int i = 1, x, y; i < n; i++) {
10             scanf("%d%d", &x, &y);
11             v[x].push_back(y), v[y].push_back(x);
12             deg[x]++, deg[y]++;
13         }
14         queue<int> q;
15         for (int i = 1; i <= n; i++)
16             if (deg[i] == 1)
17                 q.push(i), vis[i]++;
18         int cur = 0;
19         while (!q.empty()) {
20             int num_q = q.size();
21             while (num_q--) {
22                 int x = q.front();
23                 q.pop();
24                 num[cur]++;
25                 for (auto i : v[x])
26                     if (!vis[i]) {
27                         vis[i]++, q.push(i);
28                     }
29             }
30             cur++;
31         }
32         return cur - 1;
33     }
34 } l, r;
35 
36 int main() {
37     int maxx = max(l.solve(), r.solve());
38     long long ans = 0;
39     int suml = l.n - l.num[0], sumr = r.n - r.num[0];
40 
41     for (int i = 1; i <= maxx; i++) {
42         ans += 1ll * suml * sumr;
43         suml -= l.num[i], sumr -= r.num[i];
44 
45         //printf("%.12lf
", ans);
46     }
47     printf("%.12lf
", 1.0 * ans / l.n / r.n);
48 }

View Code

L：

solver：lzh

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main() {
 4     int n, a, b;
 5     cin >> n >> a >> b;
 6     n *= 60;
 7     int ans = 0;
 8     if (a > b)
 9         ans = (n - b) / a;
10     else
11         ans = (n - a) / b;
12     ans = max(ans, 0);
13     cout << ans << endl;
14 }

View Code