A.Puzzle From the Future—贪心

题意:已知用长度相同的两个由 0 和 1 组成的 a 序列和 b 序列生成 d 序列的方法是先每个位置上的数相加,然后合并相同连续的子串用其一个数表示,例如

  • 0110 和 1101 生成 1211,合并后得到 d 序列 121
  • 011000 和 011000 生成 022000,合并后得到 d 序列 020

也就是说 d 只会由 0、1和 2 组成,可能存在前导零,现在给出 a 序列,请你帮忙给出对应的 b 序列来使 d 序列表示的整数数值最大

思路:为了 d 最大肯定尽量先保证 d 序列的长度最长其次位置上的数越大越好,首先第一个位置没有限制是放 1,后面的位置我们就每次尝试在位置上放 1,如果和前面的数不相同就可以放,相同为了保证长度只能放 0

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 100;

int d[maxn];
int ans[maxn];

int cal(char ch) {
return ch - '0';
}

void solve() {
int n;
cin >> n;
string b;
cin >> b;
ans[0] = 1; //第一个位置放1
d[0] = cal(b[0]) + ans[0];
for (int i = 1; i < n; ++i) {
if (1 + cal(b[i]) == d[i - 1]) //判断是否可以放1
ans[i] = 0;
else
ans[i] = 1;
d[i] = ans[i] + cal(b[i]);
}
for (int i = 0; i < n; ++i)
cout << ans[i];
cout << endl;
}

signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
// system("pause");
return 0;
}

B.Different Divisors—贪心+思维

题意:给出一个数 d,请找到最小的整数 a 满足以下条件:

  • a 的除数个数至少为 4
  • 对于 a 的任意两个除数,他们之间的差不小于 d
1
2
d=1 a=6 [1,2,3,6]
d=2 a=15 [1,3,5,15]

思路:注意第二个条件,为什么 d=2 a=12 [1,3,6,12] 不行是因为 12 还有除数 2 不满足条件二对于任意两个除数,对于 a 而言肯定有除数 1 和本身,也就是说我们只需再找两个除数并且避免上述的情况,所以就是找两个满足条件的最小的质数这样 a 就是最小的同时也不会有其他更小的除数了

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

bool check(int x) {
int t = sqrt(x);
if (x == 2) return 1;
for (int i = 2; i <= t + 1; ++i) {
if (x % i == 0) return 0;
}
return 1;
}

signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int t;
cin >> t;
while (t--) {
int d;
cin >> d;
int a, b;
for (int i = 1 + d;; ++i) { //找第一个小的质数
if (check(i)) {
a = i;
break;
}
}
for (int i = a + d;; ++i) { //找第二个小的质数
if (check(i)) {
b = i;
break;
}
}
cout << a * b << endl; //相乘就是a
}
// system("pause");
return 0;
}

C.Array Destruction—暴力+mulitiset容器

题意:有一个数列有 2*n 个数(可能存在相同的数),请判断能够完成下述操作:

  • 开始的时候你随便指定一个整数 x
  • 然后进行 n 次如下操作:
    • 选择数列中加和等于 x 的两个数
    • 从数列中删除这两个数并用更新 x 为这两个数中的较大值

问能否通过这个操作成功删除数列,能请输出 YES、开始选的 x 值和 n 次删除操作中每次选的两个数,不能输出 NO

思路:每次删除操作 x 都会变小也就是说这是个整体递减操作,我们肯定是每次选择删除数列中最大值,否则的就再也删不掉它了。那么初始选的值 x 应该是数列中最大的数和另一个数,所以我们从数组中枚举另一个数确定 x 模拟 n 次删除操作对当前 x 进行判断:

  • 每次选择删除数组中最大值,查看另一个数 x-最大值 是否也在数组中,存在说明可以继续进行操作更新最大值并将这两个数从数组中删除
  • 如果删除不了数组中最大值则不能成功进行 n 次操作删除整个数组,退出判断尝试下一个枚举的数

因为枚举另一个数和对 x 的判断复杂度为 O(n2),所以判断过程中每次删除操作获取数组最大值和查找 x-最大值 复杂度需要低于 O(n),使用 multiset 既可以存储相同的数复杂度也降到 O(logn) 一举两得解决问题

比赛时竟然菜到没有想到树的结构来存储查找,还在手写三重循环从数组中暴力查找,写了 1 个半小时连样例都没过 😣

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
/*
元素存在相同可能并且操作中还需要排序所以用seta
删除的是某一个数所以erase通过迭代器删除
删除后不能通过迭代器操作了所以用sheng来确定后续的maxx
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e3 + 100;

int a[maxn];
int n, sum;
vector<int> ans;

bool cmp(int x, int y) {
return x > y;
}

bool check(int maxx) {
ans.clear();
multiset<int> seta;
for (int i = 0; i < sum; ++i)
seta.insert(a[i]);
for (int i = 0; i < n; ++i) { //循环n次
auto it1 = seta.end();
--it1;
int sheng = maxx - *it1; //确定要寻找的另一个数
seta.erase(it1); //删除该迭代器对应的元素,也就是删除当前最大元素
auto it2 = seta.find(sheng);
if (it2 == seta.end()) { //没找到说明不能删除所有元素
return 0;
} else { //否则就可以
seta.erase(it2); //通过迭代器删除找到的另一个元素的
ans.push_back(maxx-sheng), ans.push_back(sheng); //记录答案
maxx = max(maxx-sheng, sheng); //更新maxx
}
}
return 1;
}

void solve() {
cin >> n;
sum = 2 * n;
for (int i = 0; i < sum; ++i)
cin >> a[i];
sort(a, a + sum, cmp);
for (int i = 1; i < sum; ++i) { //枚举第一次操作a[0]带走的另一个元素
int tot = a[0] + a[i];
if (check(tot)) { //判断是否可以完成删除所有的元素
cout << "YES" << endl;
cout << tot << endl;
for (int i = 0; i < sum; i += 2)
cout << ans[i] << ' ' << ans[i + 1] << endl;
return;
}
}
cout << "NO" << endl;
}

signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
// system("pause");
return 0;
}