A - Sum of Odd Integers
1.题意
给定正整数 n 和 k，问 n 是否能被 k 个不同的奇数相加所得。
2.题解
奇数能被奇数个奇数构成，偶数能被偶数个奇数构成，所以 n 和 k 奇偶性必须相同，用等差数列得k 个不同的奇数所能构成的最小 n 是 k * k （1 + 3 + 5 + ··· +（2 * k）- 1 ），显然对于更大的 n 可以通过把小奇数不断+2所得到，所以只要n 和 k 奇偶性相同且 n >= k * k 即可。
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--) {
ll n, k;
cin >> n >> k;
int flag1 = n % 2;
int flag2 = k % 2;
if(flag1 == flag2 && n >= k * k) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
return 0;
}
B - Princesses and Princes
1.题意
有 n 个公主和 n 个王子，每个公主都有一份对王子的喜爱名单（喜欢哪几个王子），公主按下标顺序在自己的喜爱名单中依次选取王子，前提是这个王子还没被别的公主选中，下标小的王子优先被选中，如果最后每个公主都选到了属于自己的王子，则输出“OPTIMAL”，否则让你给某个选取失败的公主寻找一位单身王子（显然，该王子没在这个公主的喜爱名单里），输出“IMPROVE”并输出这个公主和王子的下标，如果有多个解决方案，输出任意一个即可。
2.题解
模拟即可，用一个桶维护王子的状态，用 ans 记录选取失败的公主。
3.代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5 + 5;
int t;
int main() {
ios::sync_with_stdio(false);
cin >> t;
while(t--) {
int n;
cin >> n;
int a[n + 5] = {0};
int cnt;
int ans = 0;
for(int i = 1; i <= n; i++) {
cin >> cnt;
int flag = 0;
for(int j = 1; j <= cnt; j++) {
int v;
cin >> v;
if(a[v] == 0 && flag == 0) {
a[v] = 1;
flag = 1;
}
}
if(flag == 0) {
ans = i;
}
}
if(ans == 0) {
cout << "OPTIMAL" << endl;
} else {
cout << "IMPROVE" << endl;
for(int j = 1; j <= n; j++) {
if(a[j] == 0) {
cout << ans << ' ' << j << endl;
break;
}
}
}
}
return 0;
}
C - EhAb AnD gCd
1.题意
给定一个正整数 x，让你找到两个正整数 a，b，使得 a，b 的最大公约数和最小公倍数之和为 x，如果有多组答案，输出任意一组即可。
2.题解
任意一个数与1的最大公约数是1，最小公倍数是这个数，所以直接输出1和 x - 1即可。
3.代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5 + 5;
int t;
int main() {
ios::sync_with_stdio(false);
cin >> t;
while(t--) {
int x;
cin >> x;
cout << 1 << ' ' << x - 1 << endl;
}
return 0;
}
D - CopyCopyCopyCopyCopy
1.题意
给定一个整数数组 a，我们可以对 a 复制任意多次放进数组 b，然后可以对数组 b 进行任意元素的删除，得到一个严格递增序列，输出序列的长度。
2.题解
因为可以复制任意多次，所以考虑最坏情况，第一次复制把除最小之外的数都删除，第二次把除倒数第二小之外的数都删除，以此类推，所以只要把数组 a 中重复的元素去掉即可，可以用 set 自动去重。
3.代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5 + 5;
int t;
int main() {
ios::sync_with_stdio(false);
cin >> t;
while(t--) {
int n;
cin >> n;
set<int> st;
int v;
for(int i = 1; i <= n; i++) {
cin >> v;
st.insert(v);
}
cout << st.size() << endl;
}
return 0;
}
F - Yet Another Tetris Problem
1.题意
给定 n 列俄罗斯方块，每列的高度是 ai，只能向上添加高度为2，宽度为1的方块，问最后是否能把所有俄罗斯方块全部消除。
2.题解
如果其中任意两列的高度差为奇数，则无法用高度为2的方块使它们高度相等，所以遍历每列高度，判断奇偶性，如果有一列与第一列高度奇偶性不同，说明它们的高度差是奇数，无法完成消除。另外，如果只有一列，直接可以消除。
3.代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5 + 5;
int t;
int main() {
ios::sync_with_stdio(false);
cin >> t;
while(t--) {
int n;
cin >> n;
int a[n + 5] = {0};
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
if(n == 1) {
cout << "YES" <<endl;
continue;
}
int x = a[1] % 2;
int flag = 1;
for(int i = 2; i <= n; i++) {
if(a[i] % 2 != x) {
flag = 0;
break;
}
}
if(flag) {
cout << "YES" <<endl;
} else {
cout << "NO" <<endl;
}
}
return 0;
}
G - Yet Another Palindrome Problem
1.题意
给定一个由正整数组成的数组，要求找到一个长度至少为3的回文子序列（子序列的元素在原序列中不必连续）。
2.题解
既然长度至少为3，那就判断长度为3的子序列，用两层循环判断 i + 1之后是否有与 ai 相同的元素。
3.代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5 + 5;
int t;
int main() {
ios::sync_with_stdio(false);
cin >> t;
while(t--) {
int n;
cin >> n;
int a[n + 5] = {0};
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
int flag = 0;
for(int i = 1; i <= n - 2; i++) {
for(int j = i + 2; j <= n; j++) {
if(a[i] == a[j] ) {
flag = 1;
break;
}
}
if(flag) {
break;
}
}
if(flag) {
cout << "YES" <<endl;
} else {
cout << "NO" <<endl;
}
}
return 0;
}
H - Frog Jumps
1.题意
有一个青蛙尝试从坐标0跳过一个数组，数组从1到 n，数组上的元素是L或R，意味着青蛙在这个单元格上只能向左或向右跳，在坐标0式只能向右跳，求出青蛙能完成任务的最长跳跃长度的最小值。
2.题解
只要青蛙能跳过连续的L，就能最终到达终点，所以找到连续的最长L的长度再加一即可，可以用前缀和记录L的连续长度，用变量 ans 维护最大值。
3.代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5 + 5;
int t;
int main() {
ios::sync_with_stdio(false);
cin >> t;
while(t--) {
string s;
cin >> s;
int n = s.size();
int a[n + 5] = {0};
if(s[0] == 'L') {
a[0] = 1;
}
int ans = a[0];
for(int i = 1; i < n; i++) {
if(s[i] == 'L') {
a[i] += a[i - 1];
a[i]++;
} else {
a[i] = 0;
}
ans = max(ans, a[i]);
}
cout << ans + 1 << endl;
}
return 0;
}