本文合作者：laybxc
赛事信息
A. Anti-knapsack
题目
题目描述
给定 n,k ，请选择 1−n 的若干个整数，使得这些整数的和的子集都不等于 k ，问最多能选出几个整数且分别是多少。
输入格式
第一行是一个整数 t(1≤t≤100) ，表示数据组数。
每组数据有两个整数 n,k(1≤k≤n≤1000)
输出格式
对于每组数据
第一行输出一个整数 m ，表示最多能选出的整数数量。
第二行输出这些选出的整数，顺序任意。
解决方案：
思路：
-
显然对 i∈[1,n] ， i>k 时 i 这个数肯定可以直接选
-
i=k 显然不行
-
考虑 i<k 的情况：我们发现 选 k−1 不选 1 ，选 k−2 不选 2
如何证明其正确性？
如果选了大于 k/2 的数，一定会有两个加起来等于 k ，所以最多选 k/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
| #include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1010;
int t, k, n;
int a[N], ans[N];
int cnt;
int main()
{
ios::sync_with_stdio(0);
cin >> t;
while (t--)
{
cin >> n >> k;
cnt = 0;
memset(a, 0, sizeof(a));
memset(ans, 0, sizeof(ans));
if (n > k)
{
for (int i = k + 1; i <= n; i++)
{
ans[++cnt] = i;
}
}
for (int i = k - 1; i >= 1; i--)
{
if (!a[i])
{
ans[++cnt] = i;
a[k - i] = 1;
}
}
cout << cnt << endl;
for (int i = 1; i <= cnt; i++)
{
cout << ans[i] << " ";
}
cout << endl;
}
return 0;
}
|
B. Planet Lapituletti
题目
题目描述
某行星上的时间一天有 h 小时，一小时有 m 分钟，它的时钟也是HH:MM的形式存在。
当某个点在镜子中显现的时间也是合法的时候，我们认为这个点是合法的。
给定一个时间点，求最近的合法点（如果它本来就是一个合法的时间点，那么就输出这个时间点）
输入格式
第一行是一个整数 t(1≤t≤100) ，表示数据组数。
每组数据有两行：
第一行输入h,m
第二行输入给定的那个时间点 hh:mm
输出格式
对于每组数据
第一行输出一个整数 m ，表示最多能选出的整数数量。
以 hh:mm 的形式输出最近的合法时间点
解决方案：
思路
显然，合法的 必要不充分条件 是 数字在屏幕上显示是正确的。即：1 2 5 8 0可以出现，3 4 6 7 9不能出现。
其次，必须满足对应的 分钟 和 小时 在该行星上时间范围内的条件。
那么就很容易判断一个时间是否合法，问题来到如何找到下一个合法的时间？
枚举即可！
注意前导零？——改用字符串来处理即可
代码：
（比赛的时候写的太冗长了，这是一个需要改进的地方）
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
79
80
81
82
83
84
85
86
87
88
89
90
| #include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1010;
int t, h, m;
int hh, mm;
char H[2], M[2];
char ansh[2], ansm[2];
int nh, nm;
int no[] = {3, 4, 6, 7, 9};
int solve(int x)
{
int res = 0;
char op[2];
if (x == 1)
op[0] = H[0], op[1] = H[1];
else
op[0] = M[0], op[1] = M[1];
for (int j = 1; j >= 0; j--)
{
int num = op[j] - '0';
res *= 10;
if (num == 0)
res += 0;
else if (num == 1)
res += 1;
else if (num == 2)
res += 5;
else if (num == 5)
res += 2;
else if (num == 8)
res += 8;
}
return res;
}
int check()
{
for (int j = 0; j <= 1; j++)
{
int x = H[j] - '0';
for (int i = 0; i < 5; i++)
if (x == no[i])
return 0;
}
for (int j = 0; j <= 1; j++)
{
int x = M[j] - '0';
for (int i = 0; i < 5; i++)
if (x == no[i])
return 0;
}
nh = solve(0), nm = solve(1);
if (nh < h and nm < m)
{
ansh[0] = hh / 10 + '0', ansh[1] = hh % 10 + '0';
ansm[0] = mm / 10 + '0', ansm[1] = mm % 10 + '0';
return 1;
}
return 0;
}
int main()
{
cin >> t;
while (t--)
{
cin >> h >> m;
scanf("%d:%d", &hh, &mm);
H[0] = hh / 10 + '0', H[1] = hh % 10 + '0';
M[0] = mm / 10 + '0', M[1] = mm % 10 + '0';
while (!check())
{
mm = (M[0] - '0') * 10 + M[1] - '0';
hh = (H[0] - '0') * 10 + H[1] - '0';
mm++;
if (mm >= m)
{
mm = 0, hh++;
}
if (hh >= h)
hh = 0;
H[0] = hh / 10 + '0', H[1] = hh % 10 + '0';
M[0] = mm / 10 + '0', M[1] = mm % 10 + '0';
}
cout << ansh[0] << ansh[1] << ":" << ansm[0] << ansm[1] << endl;
}
return 0;
}
|
C. K-beautiful Strings
题目
题目描述
一个字符串是 k 美的定义：字符串中不同字符出现的总次数能整除 k
现在给你一个 n,k ,和一个字符串，n 为字符串的长度，让你求一个字符串满足 k 美的定义并且这个字符串的字典序要尽可能的小（前提是大于等于原字符串）
并且长度和原串长度相同，如果答案字符串不存在，输出-1.
输入格式
第一行是一个整数 t(1≤t≤10000) ，表示数据组数。
每组数据有两行：
第一行输入两个整数 n,k(1≤k≤n≤105) ，分别为字符串 s 的长度和给定的数字 k
第二行输入只含小写字母的字符串 s
输出格式
对于每一组测试数据，输出第一个字典序大于等于 s 且满足 k 美定义的字符串
解决方案
思路：
-
因为要求的字符串要尽可能的小，还必须大于等于原串，那么我们可能的最优解就是原串本身满足k美，直接输出原串。
-
如果一个串满足 k 美，那么说明串的长度是由一组 k 的倍数组成的，所以如果 n 不能整除 k ，那么找不到满足 k 美的字符串，所以我们直接输出 −1 。
注意是 k 的倍数，而不是每个出现次数都是 k ，因此类似 8=2+4+2=6+2(k=2) 这样的数据都是合法的。
-
如何寻找满足 k 美的最小字符串？我们可以这样 贪心 的想，构造一个最小的大于等于原串的k美字符串，那么我们应该对原串从后往前构造，因为越往前，构造出来的字符串就越大，所以尽可能在最后就构造好，这样满足字典序最小的性质。
-
我们首先统计每个字符出现的次数，用一个cnt数组存储，然后统计将所有字符都变成k的倍数时所需增加的字符总数tot：即字符 i 变成 k 的倍数时需要增加的字符数为 (k−cnt[i]%k)%k ;
-
从后往前遍历，遍历到位置 i 时，就判断一下从位置i开始之前的子串是否是一个不用修改的最长前缀子串（因为前面的串不改最优）
-
然后得到位置 i 上的字符 c ，并逐个判断要放哪个字符
代码：
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
79
80
81
82
83
84
85
| #include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int cnt[30];
int n, t, k;
char s[100020];
void solve()
{
memset(cnt, 0, sizeof(cnt));
for (int i = 1; i <= n; i++)
{
cnt[s[i] - 'a']++;
}
int tot = 0;
for (int i = 0; i <= 25; i++)
{
tot += (k - cnt[i] % k) % k;
}
if (tot == 0)
{
for (int i = 1; i <= n; i++)
cout << s[i];
cout << endl;
}
else if (n % k != 0)
cout << "-1" << endl;
else
{
int ans = 0;
for (int i = n; i >= 1 and ans == 0; i--)
{
tot -= (k - cnt[s[i] - 'a'] % k) % k;
cnt[s[i] - 'a']--;
tot += (k - cnt[s[i] - 'a'] % k) % k;
for (int j = s[i] - 'a' + 1; j <= 25; j++)
{
int last = tot;
tot -= (k - cnt[j] % k) % k;
cnt[j]++;
tot += (k - cnt[j] % k) % k;
if (i + tot <= n)
{
for (int x = 1; x < i; x++)
{
cout << s[x];
}
cout << char(j + 'a');
for (int x = 1; x <= n - i - tot; x++)
{
cout << 'a';
}
for (int x = 0; x <= 25; x++)
{
int num = (k - cnt[x] % k) % k;
while (num > 0)
{
tot--, num--;
cout << char(x + 'a');
}
}
cout << endl;
ans = 1;
break;
}
tot = last;
cnt[j]--;
}
}
}
}
int main()
{
cin >> t;
while (t--)
{
cin >> n >> k;
cin >> (s + 1);
solve();
}
return 0;
}
|
D. GCD of an Array
题目
题目描述
一个长度为 n 的数组 a 。处理以下格式的 q 个查询：给定整数 i 和 x ，将 ai 乘以 x。
在处理每个查询之后，您需要输出数组 a 的所有元素的最大公约数（GCD）。
因为答案可能太大，所以要求以 109+7 的模输出它。
输入格式
第一行是两个整数 n,q(1≤n,q≤2⋅105)
第二行包括 n 个整数 a1,a2,…,an(1≤ai≤2⋅105)
接下来 q 行包括 q 个查询，每行包括两个数字 i，x(1≤i≤n,1≤x≤2⋅105)
输出格式
输出 q 行，每行为现在数组的 GCD 对 1e9+7 的模数。
解决方案
数论+数据结构题先不写（
请参阅
