题面
题解
A
题目大意：
判断一个正整数 \(w\) 能否表示成两个正偶数之和。
解题思路：
考虑分类讨论 \(w\)。
对于 \(1\) 和 \(2\)，显然为 NO；
对于 \(w \ge 3\)，考虑将其表示为 \(x + 2\)。根据题意，若 \(x\) 为偶数，则答案显然必为 YES；否则必然为 NO。因为 \(2\) 是偶数，所以 \(w\) 与 \(x\) 同奇偶。结论的证明留作思考题。
综上，若 \(w \ge 3\) 且 \(w\) 为偶数则答案为 YES，否则为 NO。
#include <bits/stdc++.h>
using namespace std;
int main() {
int w;
scanf("%d", &w);
if (w % 2 == 0 && w != 2) puts("YES");
else puts("NO");
return 0;
}
B
题目大意：
构造一个数组 \(a\)，使得 \(\text {minTime}_i \le a_i \le \text{maxTime}_i(1 \le i \le d)\)，且 \(\sum _{i=1} ^ d a_i = \text{sumTime}\)，或输出
NO表示不存在这样的数组。
解题思路：
先求出 \(x = \sum _{i=1} ^ d \text{minTime}_i\) 和 \(y = \sum _{i=1} ^ d \text{maxTime}_i\)。若满足 \(x \le d \le y\)，则存在这样的数组，否则不存在。下面是一种构造思路：
接下来，考虑先设 \(a_i = \text{minTime}_i\)，然后求 \(z = \text{sumTime} - x\)。接下来，考虑从 \(1 \le i \le d\)，将 \(a_i\) 的值设为 \(\text{maxTime}_i\)，并将 \(z\) 减去 \(\text{maxTime}_i - \text{minTime}_i\)，直到 \(z \le 0\)。此时令 \(a_i \leftarrow a_i + z\)，即为答案。证明过程略。
#include <bits/stdc++.h>
using namespace std;
int sum, d, x, y, z;
int a[100010], b[100010], c[100010];
int main() {
scanf("%d%d", &d, &sum);
for (int i = 1; i <= d; i++) scanf("%d%d", &b[i], &c[i]), x += b[i], y += c[i];
if (x <= sum && sum <= y) {
puts("YES");
if (x == sum) {
for (int i = 1; i <= d; i++) printf("%d ", b[i]);
putchar('\n');
} else if (y == sum) {
for (int i = 1; i <= d; i++) printf("%d ", c[i]);
putchar('\n');
} else {
for (int i = 1; i <= d; i++) a[i] = b[i];
z = sum - x;
for (int i = 1; i <= d; i++) {
int tmp = c[i] - b[i];
if (z > tmp) {
z -= tmp;
a[i] += tmp;
} else {
a[i] += z;
break;
}
}
for (int i = 1; i <= d; i++) printf("%d ", a[i]);
putchar('\n');
}
} else {
puts("NO");
}
return 0;
}
C
题目大意：
给定 \(n\) 次操作，每次向集合中加入一个字符串（当集合中没有这个字符串时），或加入【该字符串，连接，最小能使其不重复的正整数】的字符串。
解题思路：
这道题可以用 STL 中的 map 解决。使用 map 统计字符串出现的次数即可。
#include <bits/stdc++.h>
using namespace std;
int n;
map<string, int> mp;
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
while (n--) {
string s;
cin >> s;
if (!mp[s]) {
mp[s] = 1;
cout << "OK\n";
} else {
cout << s << mp[s] << '\n';
mp[s]++;
}
}
return 0;
}
D
题目大意：
求去除一些元素之后，严格二维上升子排列。
解题思路：
注意到 \(O(n^2)\) 可过。记忆化搜索即可。
可以使用链表存储序列。
#include <bits/stdc++.h>
using namespace std;
int n, d, w, a[5005], b[5005], f[5005], nxt[5005];
bool nok[5005];
int dfs(int x) {
if (f[x]) return f[x];
f[x] = 1;
for (int i = 1; i <= n; i++) {
if (nok[i]) continue;
if (a[i] > a[x] && b[i] > b[x] && f[x] < dfs(i) + 1) {
f[x] = dfs(i) + 1;
nxt[x] = i;
}
}
return f[x];
}
int main() {
scanf("%d%d%d", &n, &d, &w);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &a[i], &b[i]);
if (a[i] <= d || b[i] <= w) nok[i] = 1;
}
printf("%d\n", dfs(0) - 1);
int pos = nxt[0];
while (pos) {
printf("%d ", pos);
pos = nxt[pos];
}
return 0;
}