A - Dreamoon and Ranking Collection
1.题意
小明参加了n场比赛，名次分别是ai ，求他再参加 x 场比赛后，所能达到的名次的最大值（数字最大），要求这个名次之前的所有名次都曾获得过。
2.题解
用一个数组记录是否获得过此名次，然后遍历所有名次，没有获得就 x - - ，再注意下细节就过了。
3.代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t;
int main() {
ios::sync_with_stdio(false);
cin >> t;
while(t--) {
int n, x;
cin >> n >> x;
int a[1000] = {0};
for(int i = 1; i <= n; i++) {
int temp;
cin >> temp;
a[temp] = 1;
}
// for(int i = 1; i <= n; i++) {
// cout << a[i] << ' ';
// }
int ans = 1;
for(int i = 1; i <= 1000 && x >= 0; i++) {
if(a[i] == 0) {
x--;
}
ans = i;
}
cout << ans - 1 << endl;
}
return 0;
}
B - Dreamoon Likes Permutations
1.题意
给定一个数列，要求把此数列砍一刀，分割成两个数列，且两个数列的任意一个数列都满足数字不重复、包含从1到数列长度的每一个数，求有几种分割方法，输出分割出的两个数列长度。
2.题解
砍一刀并且要求两个序列从1开始连续不重复，即两个序列的最大值就是它们的序列长度，原序列的最大值肯定在其中一个序列中是最大值，最大值所在的那个序列长度必须是max才有可能满足题意，因为不知道max 在原序列哪个位置，所以最多有两种分割方式：max ，n - max 和 n - max ，max ，分别检测两种情况的两个序列是否满足条件，我检查的方法是对两个序列排序，判断是否ai == i 。另外，如果max 是n 的一半，最多一种切割方式。
3.代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e6 + 5;
int t, n;
int a[maxn];
int b[maxn];
int check(int p) {
for(int i = 1; i <= p; i++) {
if(a[i] != i) {
return 0;
}
}
for(int i = p + 1; i <= n; i++) {
if(a[i] != i - p) {
return 0;
}
}
return 1;
}
int main() {
ios::sync_with_stdio(false);
cin >> t;
while(t--) {
int mmax = 1;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
b[i] = a[i];
mmax = max(mmax, a[i]);
}
int flag1 = 0;
int flag2 = 0;
sort(a + 1, a + 1 + mmax);
sort(a + 1 + mmax, a + 1 + n);
// for(int i = 1; i <= n; i++) {
// cout << a[i] << ' ';
// }
// cout << endl;
flag1 = check(mmax);
//cout << "flag1 = " << flag1 << endl;
for(int i = 1; i <= n; i++) {
a[i] = b[i];
}
sort(a + 1, a + 1 + n - mmax);
sort(a + 1 + n - mmax, a + 1 + n);
// for(int i = 1; i <= n; i++) {
// cout << a[i] << ' ';
// }
// cout << endl;
flag2 = check(n - mmax);
//cout << "flag2 = " << flag2 << endl;
if(flag1 || flag2) {
if(mmax * 2 == n) {
cout << 1 << endl;
cout << mmax << ' ' << n - mmax << endl;
} else {
if(flag1 && flag2) {
cout << 2 << endl;
cout << mmax << ' ' << n - mmax << endl;
cout << n - mmax << ' ' << mmax << endl;
} else if(flag1) {
cout << 1 << endl;
cout << mmax << ' ' << n - mmax << endl;
} else {
cout << 1 << endl;
cout << n - mmax << ' ' << mmax << endl;
}
}
} else {
cout << 0 << endl;
}
}
return 0;
}
C - Exercising Walk
1.题意
给定一个矩阵，边界为x1，x2，y1，y2，初始点为x，y，问是否能在这个矩阵中完成向左走a步，向右走b步，向下走c步，向上走d步。
2.题解
水平位置走 a - b 步，竖直位置走 c - d 步，判断走后是否在范围内即可，另外如果 x1 == x2，a - b ==0 但 a != 0，也没法完成，竖直位置同理。
3.代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e6 + 5;
int t;
int main() {
ios::sync_with_stdio(false);
cin >> t;
while(t--) {
int a, b, c, d;
cin >> a >> b >> c >> d;
int x, y, x1, y1, x2, y2;
cin >> x >> y >> x1 >> y1 >> x2 >> y2;
int xx = x + b - a;
int yy = y + d - c;
if(xx < x1 || xx > x2 || yy < y1 || yy > y2) {
cout << "No" << endl;
} else if(x1 == x2 && a || y1 == y2 && c) {
cout << "No" << endl;
} else {
cout << "Yes" << endl;
}
}
return 0;
}
D - Composite Coloring
1.题意
给定 n 个合数，要求用 m 种颜色把这 n 个数染色，如果两个数的最大公约数大于1，那么这两个数可以染同一种颜色，不必最小化 m ，输出一种解即可。
2.题解
因为全是合数，所以可以分解出质因子，ai <= 1000，根下1000约等于31，而1到31的质因子正好有11个，分别是2，3，5，7，11，13，17，19，23，29，31，所以按这些质因子分组即可，最后把结果处理一下（例：把2 9 3 5 3 变成 1 2 3 4 3）。
3.代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e6 + 5;
int t;
int main() {
ios::sync_with_stdio(false);
cin >> t;
while(t--) {
int n;
cin >> n;
int a[n + 1] = {0};
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
int k = 0;
int num[11] = {2,3,5,7,11,13,17,19,23,29,31};
int book[11] = {0};
vector<int> ans;
for(int i = 1; i <= n; i++) {
for(int j = 0; j < 11; j++) {
if(a[i] % num[j] == 0) {
//cout << j << ' ';
book[j] = 1;
ans.push_back(j + 1);
break;
}
}
}
int cnt = 0;
for(int i = 0; i < 11; i++) {
if(book[i] == 1) {
cnt++;
}
}
cout << cnt << endl;
int res[12] = {0};
int x = 1;
for(vector<int>::iterator it = ans.begin(); it < ans.end(); it++) {
if(res[*it] == 0) {
res[*it] = x;
x++;
}
}
for(vector<int>::iterator it = ans.begin(); it < ans.end(); it++) {
if(it == ans.begin()) {
cout << res[*it];
} else {
cout << ' ' << res[*it];
}
}
cout << endl;
}
return 0;
}
E - K-th Beautiful String
1.题意
给定两个正整数 n，k，要求用 n - 2个 a 和 两个 b 构造一个按字典排序第 k 小的字符串。
2.题解
任意指定一个 n ，写下所有排列情况，可以找到规律。先找第一个 b ，可以从 n - 1向前枚举，每次枚举有 n - i 种情况，如果 k <= n - i，第一个 b 就确定下来了，再找第二个 b，在第一个 b 后面的第 n - i - k + 1个字符（k是更新后的），否则 k -= n - i 。用一个变量记录输出了多少个子符。
3.代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e6 + 5;
int t;
int main() {
ios::sync_with_stdio(false);
cin >> t;
while(t--) {
int n, k;
cin >> n >> k;
int cnt = 0;
for(int i = n - 1; i > 0; i--) {
if(k <= n - i) {
for(int j = 1; j < i; j++) {
cout << 'a';
}
cout << 'b';
cnt += i;
for(int j = 1; j <= n - i - k; j++) {
cout << 'a';
}
cout << 'b';
cnt += n - i - k + 1;
for(int j = cnt; j < n; j++) {
cout << 'a';
}
break;
} else {
k -= n - i;
}
}
cout << endl;
}
return 0;
}
F - Carousel
1.题意
n个旋转木马围成一个环，旋转木马的类型是它们上面的数字，现在要给所有木马染色，要求不同类型的相邻木马不能同色，最小化颜色使用数，输出一种染色方案。
2.题解
如果所有木马类型一样，都涂同一种颜色；如果 n 为偶数，两种颜色间隔涂即可；如果 n 为奇数，但是其中有两个木马类型相同且相邻，则把它俩看成一个，再按偶数涂即可；如果 n 为奇数，但是其中没有两个木马类型相同且相邻，那就按偶数涂，把最后一个涂上第三种颜色。
3.代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e6 + 5;
int t;
int main() {
ios::sync_with_stdio(false);
cin >> t;
while(t--) {
int n;
cin >> n;
int a[n + 1];
bool flag = true;
for(int i = 1; i <= n; i++) {
cin >> a[i];
if(a[i] != a[1]) {
flag = false;
}
}
if(flag) {
cout << 1 << endl;
for(int i = 1; i <= n; i++) {
cout << 1 << ' ';
}
} else if(n % 2 == 0) {
cout << 2 << endl;
for(int i = 1; i<= n; i++) {
if(i % 2 == 0){
cout << 2 << ' ';
} else {
cout << 1 << ' ';
}
}
} else {
int pos = 0;
if(a[1] == a[n]) {
pos = n;
}
if(pos != n) {
for(int i = 1; i < n; i++) {
if(a[i] == a[i + 1]) {
pos = i;
break;
}
}
}
if(pos == 0) {
cout << 3 << endl;
for(int i = 1; i< n; i++) {
if(i % 2 == 0){
cout << 1 << ' ';
} else {
cout << 2 << ' ';
}
}
cout << 3;
} else if(pos == n) {
cout << 2 << endl;
cout << 2 << ' ';
for(int i = 2; i < n; i++) {
if(i % 2 == 0){
cout << 1 << ' ';
} else {
cout << 2 << ' ';
}
}
cout << 2 << ' ';
} else {
cout << 2 << endl;
for(int i = 1; i < n; i++) {
if(i == pos) {
if(i % 2 == 0){
cout << 1 << ' ';
cout << 1 << ' ';
} else {
cout << 2 << ' ';
cout << 2 << ' ';
}
} else {
if(i % 2 == 0){
cout << 1 << ' ';
} else {
cout << 2 << ' ';
}
}
}
}
}
cout << endl;
}
return 0;
}