A - We Got Everything Covered!
难度: ⭐
题目大意
给定n和k两个整数, 要求用前k个小写字母组成一个字符串; 该字符串的子串应包含所有由前k个字母组成的长度为n的字符串全排列; 要求输出最短的满足条件的字符串;
解题思路
这题题目挺唬人, 但其实是个水题; 所谓最短, 其实就是把前k个小写字母重复输出n遍就是最短情况了;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 1e6 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m;
signed main() {
int t;
cin >> t;
while(t--){
cin >> n >> m;
for(int i = 1; i <= n; i++){
for(int j = 0; j < m; j++){
cout << (char)('a' + j);
}
}
cout << endl;
}
return 0;
}
B - A Balanced Problemset?
难度: ⭐⭐
题目大意
给定两个整数n和m; 要求把n分为m份, 所得的分数就是这m个数的最大公约数; 请问该分数最大是多少
解题思路
设最大分数是x, 我们可以先分出m份x, 然后把剩下的全放在其中一份上, 并且剩下的部分(n - m * x)也一定是x的倍数(包括0); 这样就把n分为了两部分: m * x和 a * x; 其中a * x就是(n - m * x); 既然要x尽可能大, 也就是让(m + a)尽可能小, 而且(m + a)和x都是n的因数; 所以只要找出第一个大于等于m的因数就可以了;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 1e6 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m;
signed main() {
int t;
cin >> t;
while(t--){
cin >> n >> m;
int minn = n;
for(int i = 1; i <= n / i; i++){
if(n % i == 0){
if(i >= m) minn = min(minn, i);
if(n / i >= m) minn = min(minn, n / i);
}
}
cout << n / minn << endl;
}
return 0;
}
C - Did We Get Everything Covered?
难度: ⭐⭐⭐
题目大意
和A题相似, 不过这次是给出由前k个字母组成的字符串s, 请问他是否包含所有由前k个字母组成的长度为n的子串; 如果没有则输出任意未包含的字符串;
解题思路
从A题找到的规律就是如果要s满足条件, 那么s就要可以被分成n份, 每份都至少含有前k个字母; 所以我们可以根据这个规律扫一遍字符串s, 看看能不能找出n份; 如果不能, 设我们只找到了m份, 那么就取这m份格子最后一个字母, 再加上当前这份缺的那个字母, 然后用'a'补齐字符串长度, 所得到的就是一个缺失的字符串; 这里读者可以思考一下为什么要取每份的最后一个字母;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
const int N = 1e6 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m;
signed main() {
int t;
cin >> t;
while(t--){
int k;
cin >> n >> k >> m;
string s, res = "";
cin >> s;
set<int> st;
int idx = 0;
for(int i = 0; i < s.size(); i++){
st.insert(s[i]);
if(st.size() == k){
res += s[i];
idx++;
st.clear();
}
}
if(idx >= n) cout << "YES" << endl;
else {
for(int i = 0; i < 26; i++){
if(!st.count('a' + i)){
res += ('a' + i);
break;
}
}
while(res.size() < n) res += 'a';
cout << "NO" << endl << res << endl;
}
}
return 0;
}