Codeforces Round #601 (Div. 2)
A. Changing Volume
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// ------- 变量 ------- //
int a, b;
// ------- 函数 ------- //
void Init() {
scanf("%d%d", &a, &b);
}
int Solve() {
int cha = abs(a - b);
int ans = 0;
ans += cha / 5;
cha %= 5;
ans += cha / 2;
cha %= 2;
ans += cha;
return printf("%d\n", ans);
}
B. Fridge Lockers
代码
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
const int N = (int)2e3+7;
// ------- 变量 ------- //
int n, m;
struct node {
int w, id;
} a[N];
// ------- 函数 ------- //
void Init() {
scanf("%d%d", &n, &m);
rep(i, 1, n+1) scanf("%d", &a[i].w), a[i].id = i;
}
int Solve() {
sort(a + 1, a + n + 1, [](node a, node b){
return a.w < b.w;
});
if (n == 2) return puts("-1");
a[n+1] = a[1];
int cnt, cost = 0;
vector <pii> ans;
cnt = n;
rep(i, 1, n+1) {
ans.pb(mp(a[i].id, a[i+1].id));
cost += a[i].w * 2;
}
if (cnt > m) return puts("-1");
if (m > cnt) {
rep(i, 0, m - cnt) ans.pb(mp(a[1].id, a[2].id));
cost += (m - cnt) * (a[1].w + a[2].w);
}
printf("%d\n", cost);
for (auto o : ans) printf("%d %d\n", o.fi, o.se);
return 0;
}
C. League of Leesins
代码
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
const int N = (int)1e5+7;
// ------- 变量 ------- //
int n;
int a[N][3];
vi v[N];
int cnt[N], vis[N];
vi ans;
// ------- 函数 ------- //
void work(int st) {
ans.pb(st); vis[st] = 1;
int id = v[st][0];
int cur;
rep(i, 0, 3) if (cnt[a[id][i]] == 2) cur = a[id][i];
ans.pb(cur); vis[cur] = 1;
rep(i, 0, 3) if (cnt[a[id][i]] == 3) cur = a[id][i];
ans.pb(cur); vis[cur] = 1;
rep(k, 0, n - 5) {
int t1 = ans[sz(ans)-1], t2 = ans[sz(ans)-2];
for (auto id : v[t1]) {
int ok1 = 0, ok2 = 0;
rep(i, 0, 3) {
if (a[id][i] == t2) ok1 = 1;
else if (a[id][i] != t1 && !vis[a[id][i]])
cur = a[id][i], ok2 = 1;
}
if (ok1 && ok2) {
vis[cur] = 1;
ans.pb(cur);
break;
}
}
}
for (auto id : v[cur]) {
int t2 = -1, t1 = -1;
rep(i, 0, 3) {
if (!vis[a[id][i]] && cnt[a[id][i]] == 2) t2 = a[id][i];
if (!vis[a[id][i]] && cnt[a[id][i]] == 1) t1 = a[id][i];
}
if (t2 != -1 && t1 != -1) {
ans.pb(t2); ans.pb(t1);
return ;
}
}
}
void Init() {
scanf("%d", &n);
memset(cnt, 0, sizeof(cnt));
memset(vis, 0, sizeof(vis));
rep(i, 0, n-2) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
a[i][0] = x; a[i][1] = y; a[i][2] = z;
v[x].pb(i); v[y].pb(i); v[z].pb(i);
cnt[x]++; cnt[y]++; cnt[z]++;
}
}
int Solve() {
rep(i, 1, n+1) if (cnt[i] == 1) {
work(i);
break;
}
rep(i, 0, sz(ans)) printf("%d%c", ans[i], " \n"[i==sz(ans)-1]);
return 0;
}
D. Feeding Chicken
代码
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
const int N = (int)107;
// ------- 变量 ------- //
int r, c, k, num;
char s[N][N], ans[N][N];
// ------- 函数 ------- //
void Init() {
scanf("%d%d%d", &r, &c, &k);
rep(i, 1, r+1) scanf("%s", s[i] + 1);
num = 0;
rep(i, 1, r+1) rep(j, 1, c+1) if (s[i][j] == 'R') num++;
}
int Solve() {
int shan = num / k;
rep(i, 1, r+1) rep(j, 1, c+1) ans[i][j] = k - 1;
int cur = 0, cnt = shan, i = 1, j = 1, f = 1, tmp = num % k;
if (tmp) { tmp--; cnt++; }
while (1) {
ans[i][j] = cur;
if (s[i][j] == 'R') {
cnt--;
if (cnt == 0) {
cnt = shan;
if (tmp) { tmp--; cnt++; }
cur++;
if (cur == k) break;
}
} else {
}
if (f) {
if (j == c) i++, f = 0;
else j++;
} else {
if (j == 1) i++, f = 1;
else j--;
}
}
rep(i, 1, r+1) rep(j, 1, c+1) {
if (ans[i][j] <= 9) ans[i][j] += '0';
else if (ans[i][j] <= 9 + 26) ans[i][j] += 'a' - 10;
else ans[i][j] += 'A' - 9 - 26 - 1;
}
rep(i, 1, r+1) ans[i][c+1] = '\0';
rep(i, 1, r+1) printf("%s\n", ans[i] + 1);
return 0;
}
E. Send Boxes to Alice
代码
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
const int N = 1e6+7;
// ------- 变量 ------- //
int n, a[N], b[N];
ll ans;
// ------- 函数 ------- //
void Init() {
scanf("%d", &n);
rep(i, 1, n+1) scanf("%d", b+i);
ans = LINF;
}
int Solve() {
ll sum = 0;
rep(i, 1, n+1) sum += b[i];
if (sum == 1) return puts("-1");
vector <ll> pf;
ll x = sum;
for (ll i = 2; i * i <= x; ++i) if (x % i == 0) {
pf.pb(i);
while (x % i == 0) x /= i;
}
if (x > 1) pf.pb(x);
for (auto o : pf) {
rep(i, 1, n+1) a[i] = b[i] % o;
ll tmp = 0, cur = 0, mid = -1;
vector < pair<ll, ll> > pos;
rep(i, 1, n+1) if (a[i]) {
pos.pb(mp(i, a[i]));
cur += a[i];
if (mid == -1 && cur >= (o + 1) / 2) mid = i;
if (cur >= o) {
ll num = 0;
rep(j, 0, sz(pos)-1) {
tmp += abs(mid - pos[j].fi) * pos[j].se;
num += pos[j].se;
}
tmp += abs(mid - pos.back().fi) * (o - num);
pos.clear();
cur -= o;
mid = -1;
if (cur) pos.pb(mp(i, cur));
if (cur >= (o + 1) / 2) mid = i;
}
}
ans = min(ans, tmp);
}
return printf("%lld\n", ans);
}
ll solve(ll x) {
ll res = 0;
rep(i, 1, n+1) res += min(s[i] % x, x - (s[i] % x));
return res;
}
F. Point Ordering
题意
$n$ 个二维平面上的点，坐标范围 $[-10^9, 10^9]$ 。
没有三点共线。
这些点是凸包上的点。
可以问最多 $3 n$ 个问题
- 三点形成的三角形的面积的两倍
- 两个向量的叉积的符号
输出凸包的逆时针排列，排列的第一个点是 $a_1$
题解
以点 $1$ 和点 $2$ 为轴
用叉积将剩下的点分左右两堆
每堆用面积算出距离轴最远的点
通过该点再将这堆点分左右两边
用距离排序即可
代码
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
const int N = 1007;
// ------- 变量 ------- //
int n;
vi ans, l, r, p1, p2, p3, p4;
ll dis[N];
// ------- 函数 ------- //
ll qry(int t, int i, int j, int k) {
printf("%d %d %d %d\n", t, i, j, k);
fflush(stdout);
ll res; scanf("%lld", &res);
return res;
}
void Init() {
scanf("%d", &n);
ans.clear();
l.clear(); r.clear();
}
int Solve() {
rep(i, 3, n+1) {
ll res = qry(2, 1, 2, i);
if (res == 1) l.pb(i);
else r.pb(i);
}
ans.pb(1);
if (sz(r)) {
ll mx = -LINF, id;
for (auto o : r) {
ll res = qry(1, 1, 2, o);
dis[o] = res;
if (res > mx) { mx = res; id = o; }
}
p4.clear(); p1.clear();
for (auto o : r) if (o != id) {
ll res = qry(2, 1, id, o);
if (res == 1) p1.pb(o);
else p4.pb(o);
}
sort(all(p4), [](int a, int b){ return dis[a] < dis[b]; });
sort(all(p1), [](int a, int b){ return dis[a] > dis[b]; });
for (auto o : p4) ans.pb(o);
ans.pb(id);
for (auto o : p1) ans.pb(o);
}
ans.pb(2);
if (sz(l)) {
ll mx = -LINF, id;
for (auto o : l) {
ll res = qry(1, 1, 2, o);
dis[o] = res;
if (res > mx) { mx = res; id = o; }
}
p2.clear(); p3.clear();
for (auto o : l) if (o != id) {
ll res = qry(2, 1, id, o);
if (res == 1) p3.pb(o);
else p2.pb(o);
}
sort(all(p2), [](int a, int b){ return dis[a] < dis[b]; });
sort(all(p3), [](int a, int b){ return dis[a] > dis[b]; });
for (auto o : p2) ans.pb(o);
ans.pb(id);
for (auto o : p3) ans.pb(o);
}
printf("0");
for (auto o : ans) printf(" %d", o);
return puts("");
}
