Mail.Ru Cup 2018 Round 3 Solution
分类:
IT文章
•
2022-05-16 11:10:57
A. Determine Line
Water.
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 int n, vis[110];
5
6 int main()
7 {
8 while (scanf("%d", &n) != EOF)
9 {
10 memset(vis, 0, sizeof vis);
11 for (int i = 1, tot, x; i <= n; ++i)
12 {
13 scanf("%d", &tot);
14 while (tot--)
15 {
16 scanf("%d", &x);
17 ++vis[x];
18 }
19 }
20 for (int i = 1; i <= 100; ++i) if (vis[i] == n) printf("%d ", i);
21 puts("");
22 }
23 return 0;
24 }
View Code
B. Divide Candies
Solved.
题意：
有$n cdot n 的网格，每个网格放的糖数是(i^2 + j^2), i, j 表示行列$
求有多少个格子上的糖数是$m的倍数$
思路：
因为$m很小，处理出m的每个余数所对应的数字个数，再加加乘乘就好了$
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define ll long long
5 int n, m;
6 ll cnt[1010];
7
8 ll calc(ll x, ll y)
9 {
10 if (x % m >= y) return x / m + 1;
11 return x / m;
12 }
13
14 int main()
15 {
16 while (scanf("%d%d", &n, &m) != EOF)
17 {
18 memset(cnt, 0, sizeof cnt);
19 for (int i = 0; i < m; ++i)
20 cnt[i * i % m] += calc(n, i);
21 --cnt[0]; cnt[m] = cnt[0];
22 ll res = 0;
23 for (int i = 0; i < m; ++i) res += cnt[i] * cnt[m - i];
24 printf("%lld
", res);
25 }
26 return 0;
27 }
View Code
C. Pick Heroes
Solved.
![]()
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 #define N 2010
5 #define pii pair <int, int>
6 int n, m, t;
7 vector <pii> v, p;
8 map <int, int> mp;
9 int vis[N];
10
11 int main()
12 {
13 while (scanf("%d%d", &n, &m) != EOF)
14 {
15 v.clear(); mp.clear(); p.clear();
16 memset(vis, 0, sizeof vis);
17 for (int i = 1, x; i <= 2 * n; ++i)
18 {
19 scanf("%d", &x);
20 p.emplace_back(x, i);
21 }
22 for (int i = 1, x, y; i <= m; ++i)
23 {
24 scanf("%d%d", &x, &y);
25 mp[x] = y;
26 mp[y] = x;
27 v.emplace_back(x, y);
28 }
29 scanf("%d", &t);
30 for (auto &it : v) if (p[it.first - 1].first < p[it.second - 1].first) swap(it.first, it.second);
31 sort(p.begin(), p.end(), [](pii a, pii b) { return a.first > b.first; });
32 if (t == 1)
33 {
34 int x;
35 for (auto &it : v)
36 {
37 printf("%d
", it.first);
38 fflush(stdout);
39 scanf("%d", &x);
40 vis[it.first] = 1;
41 vis[x] = 1;
42 }
43 for (int i = v.size() + 1, r = 0; i <= n; ++i)
44 {
45 while (vis[p[r].second]) ++r;
46 printf("%d
", p[r].second);
47 fflush(stdout);
48 scanf("%d", &x);
49 vis[p[r].second] = 1;
50 vis[x] = 1;
51 }
52 }
53 else
54 {
55 int x;
56 for (int i = 1, r1 = 0, r2 = 0; i <= n; ++i)
57 {
58 scanf("%d", &x);
59 vis[x] = 1;
60 if (mp.find(x) != mp.end() && vis[mp[x]] == 0)
61 {
62 printf("%d
", mp[x]);
63 vis[mp[x]] = 1;
64 }
65 else
66 {
67 while (r1 < v.size() && vis[v[r1].first]) ++r1;
68 if (r1 < v.size())
69 {
70 printf("%d
", v[r1].first);
71 vis[v[r1].first] = 1;
72 }
73 else
74 {
75 while (vis[p[r2].second]) ++r2;
76 printf("%d
", p[r2].second);
77 vis[p[r2].second] = 1;
78 }
79 }
80 fflush(stdout);
81 }
82 }
83
84 }
85 return 0;
86 }
