比赛链接
DANCEMOVES
题意
给你起点和终点，每次可以往前走两步或者往后走一步，问最少多少步能从起点走到终点
题解
分类讨论即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include <bits/stdc++.h>
using namespace std;
int T, x, y;
int main() {
cin >> T;
while (T--) {
cin >> x >> y;
if (x >= y)
cout << x - y << endl;
else if ((y - x) % 2 == 0)
cout << (y - x) / 2 << endl;
else
cout << (y + 3 - x) / 2 << endl;
}
return 0;
}
|
MINLCM1
题意
给定两个数x和k，你需要找两个位于\([x, x*k]\)内的不同的数i,j，问i和j的LCM的最大值和最小值分别是什么
题解
最大值很简单，只要i和j取最大的两个数即可，因为相邻的数互质，不会有比最大的两个数乘起来更大的
最小值即为\(2x\)，不妨设j较大，因为\(\frac j {GCD(i,j)} \ge 2\)，因此LCM最小为2i，i取最小值x即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| #include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL T, x, k;
int main() {
cin >> T;
while (T--) {
cin >> x >> k;
cout << 2 * x << " " << x * k * (x * k - 1) << endl;
}
return 0;
}
|
RRR
题意
n个人进行循环赛，胜者2分，负者0分，不并列名次，问第k名最多得多少分
题解
第k名可以把比他排名低的人全赢了，而比他排名高的最多赢一半
若超过一半可以计算出前k名的积分总量不对
可以简单构造出一种赢一半的情况，即为每个人赢自身编号往后数的一半人
1
2
3
4
5
6
7
8
9
10
11
12
13
| #include <bits/stdc++.h>
using namespace std;
int T, k, n;
int main() {
cin >> T;
while (T--) {
cin >> n >> k;
cout << 2 * (n - k + (k - 1) / 2) << endl;
}
return 0;
}
|
EQBEAUTY
题意
给定一个数组A，可以做任意次如下操作：给数组中一个数加一或减一
用最少的操作次数使其能分为两个极差相等的数组，问最小操作次数
题解
首先将数组排序
若有一个数组只有一个数，那另一个数组全部都相等，显然这种情况下只有一个数的那个数应当为最大的数或最小的数，而另一个数组均等于原数组（指去掉了一个数的A）的中位数
若两个数组均不止一个数，显然一个数组最小值为a[1],可以枚举其最大值a[i], 那么另一个数组最大值为a[n],最小值应为a[1]+a[n]-a[i], 二分查找前后距离这个数最近的数暴力修改即可，需要判断是否能覆盖整个数组
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
| #include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 1e5 + 10;
int T, n;
int a[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
if (n == 2) {
cout << 0 << endl;
continue;
}
else if (n == 3) {
cout << min(a[2] - a[1], a[3] - a[2]) << endl;
continue;
}
LL mn = 1e18;
for (int i = 2; i < n; ++i) {
int tar = a[n] + a[1] - a[i];
int pos = lower_bound(a + 2, a + n, tar) - a;
if (pos != n && (pos < i || pos == i + 1))
mn = min(mn, 0LL + a[pos] - tar);
if ((pos - 1 < i && pos != 2) || pos == i + 2)
mn = min(mn, 0LL + tar - a[pos - 1]);
}
LL sum = 0LL;
int tar = a[n / 2];
for (int i = 1; i < n; ++i) {
sum += abs(tar - a[i]);
}
mn = min(mn, sum);
sum = 0;
tar = a[n / 2 + 1];
for (int i = 2; i <= n; ++i) {
sum += abs(tar - a[i]);
}
mn = min(mn, sum);
cout << mn << endl;
}
return 0;
}
|
BINFLIP
题意
给定一个长度为n的01串，其中前k个字符均为1
你需要将其变为全0串
操作如下：
你的第i次操作可以翻转一个长度为\(2^{i-1}\)的子串
任何时候翻转的字符不能越界
问能否成功，若能输出任意一种操作序列
题解
k为0输出Yes无需操作，由奇偶性可得出k为其他偶数均不行
k为奇数的情况下，首先找出最少需要的操作次数cnt，显然cnt为\(log_2k+1\)，下面构造一种用只用cnt次操作的方法
首先算出\(\frac {2^{cnt}-1-k} 2\),这些数是用来将0翻转为1的，这样将1翻转为0的数量才能等于k
为了避免下标越界，只使用前k个位置即可
具体为对于将1翻转为0的操作（除了最后一次）从1开始
而将0翻转为1的操作以及最后一次将1翻转为0的操作从\(k - 2 ^ {cnt - 1} + 1\)开始即可
可以证明从\(k - 2 ^ {cnt - 1} + 1\)开始的\(\frac {2^{cnt}-1-k} 2\)个位置均被翻转了三遍，其余位置翻转了一遍
PS: 这里有个小问题是我没有证明将1翻转为0的操作（除了最后一次）的结束点一定比0翻转为1的结束点更大（即代码中那句assert）, 这个证明起来并不困难，就让读者自己想想吧
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
| #include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL gcd(LL a, LL b) {
return b == 0 ? a : gcd(b, a % b);
}
const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
LL T, k, n;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
while (T--) {
cin >> n >> k;
if (k == 0) {
cout << "YES" << endl << 0 << endl;
} else if (k % 2 == 0) {
cout << "NO" << endl;
} else if (k == 1) {
cout << "YES" << endl << 1 << endl << 1 << endl;
} else {
int lim = 1, cnt = 0;
while (lim < k)
lim *= 2, cnt++;
lim -= 1;
int delta = (lim - k) / 2;
int pos = 1, neg = k - (1 << (cnt - 1)) + 1;
cout << "YES" << endl << cnt << endl;
for (int i = 0; i < cnt - 1; ++i) {
if (delta >> i & 1) {
cout << neg << endl;
neg += 1 << i;
} else {
cout << pos << endl;
pos += 1 << i;
}
}
assert(pos >= neg);
cout << k - (1 << (cnt - 1)) + 1 << endl;
}
}
return 0;
}
|