前言
没时间打，所以 VP 了一下。
我的 VP 成绩：5 / 7
71.428571428571428571428571428571%
A Make it White
题目大意
给定一个字符串，由 W 和 B 组成，我们现在可以将字符串中的连续 $k$ 个字母都变成 W。求 $k$ 的最小值使得整个字符串都是 W。
思路
很简单，如果找出最左边和最右边的 B，那么这两个中间（包括这两个）的所有字符都必须变成 W。那么这个长度就是最小长度了。
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T; cin >> T;
while (T --) {
int I = 0, J = 0;
int n; string s;
cin >> n >> s;
for (int i = 0; i < s.size(); i ++) {
if (s[i] == 'B') {
I = i;
break;
}
}
for (int i = 0; i < s.size(); i ++) {
if (s[i] == 'B') {
J = i;
}
}
cout << J - I + 1 << "\n";
}
return 0;
}B Following the String
题目大意
对于字符串 $s$ ，我们可以生成一个数组 $a$，定义 $a_i$ 为从 $s_1$ 到 $s_{i – 1}$ 中和 $s_i$ 相等和个数。
现在给定数组 $a$，求出一个合法的 $s$。
思路
维护多个双端队列，第 $j$ 个双端队列里面的字符是到字符串的第 $i$ 个位置，出现的 $j$ 次的字符。
最开始我们把所有字母都加入到第 $0$ 个队列。然后遍历数组 $a$，每次把第 $a_i$ 个队列中的一个输出，出队，并放到第 $a_{i + 1}$ 个队列里面。
双端队列可以用
std::list 实现。代码
#include <bits/stdc++.h>
using namespace std;
list <char> l[200005];
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T; cin >> T;
while (T --) {
int n, a[200005];
cin >> n;
for (int i = 0; i <= n; i ++) l[i].clear();
for (int i = 0; i <= 25; i ++) {
l[0].push_back(i + 'a');
}
for (int i = 1; i <= n; i ++) {
cin >> a[i];
cout << l[a[i]].front();
int t = l[a[i]].front();
if (l[a[i]].size() == 0) break;
l[a[i]].pop_front();
l[a[i] + 1].push_front(t);
}
cout << "\n";
}
return 0;
}C Choose the Different Ones!
题目大意
给定两个数组和偶数 $k$，保证从两个数组中各选择 $\frac{k}{2}$ 个数，使得这 $k$ 个数是 $1$ 到 $k$。
思路
用 map。
如果对于两个数组，每个数组中不同的 $1$ 到 $k$ 的数的个数大于等于 $\frac{k}{2}$；而且两个数组合起来后 $1$ 到 $k$ 中的每个数都有，那么就输出 YES，否则输出 NO。
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T; cin >> T;
while (T --) {
int n, m, k, a[200005], b[200005];
map <int, int> m1, m2, m3;
cin >> n >> m >> k;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
m1[a[i]] ++;
m3[a[i]] ++;
}
for (int i = 1; i <= m; i ++) {
cin >> b[i];
m2[b[i]] ++;
m3[b[i]] ++;
}
int bb = 1;
int cnt = 0;
for (int i = 1; i <= k; i ++) {
if (m1[i]) cnt ++;
}
if (cnt < k / 2) bb = 0;
// cout << cnt << " ";
cnt = 0;
for (int i = 1; i <= k; i ++) {
if (m2[i]) cnt ++;
}
if (cnt < k / 2) bb = 0;
// cout << cnt << " ";
cnt = 0;
for (int i = 1; i <= k; i ++) {
if (m3[i]) cnt ++;
}
if (cnt < k) bb = 0;
// cout << cnt << " ";
cnt = 0;
cout << (bb == 1 ? "YES" : "NO") << "\n";
}
return 0;
}D Find the Different Ones!
题目大意
给定一个数组和多个询问，对于每个询问有 $l, r$，输出 $[l,r]$ 中两个不一样的数的下标（下标从 $1$ 开始）。如果区间 $[l,r]$ 中的每个数都一样，那么输出 -1 -1。
思路
运用 ST 表，见代码。
代码
#include <bits/stdc++.h>
using namespace std;
int solve() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n, m, a[1000005], dp[100005][25];
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
dp[i][0] = a[i];
}
cin >> m;
for (int i = 1; i <= 21; i ++) {
for (int j = 1; j + (1 << i) - 1 <= n; j ++) {
dp[j][i] = max(dp[j][i - 1], dp[j + (1 << (i - 1))][i - 1]);
}
}
while (m --) {
int l, r; cin >> l >> r;
int c = __lg(r - l + 1);
cout << max(dp[l][c], dp[r - (1 << c) + 1][c]) << "\n";
}
return 0;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T; cin >> T;
while (T --) {
solve();
}
return 0;
}E Klever Permutation
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T; cin >> T;
while (T --) {
int n, k; cin >> n >> k;
int p = 1;
p = 1;
int a[200005];
memset(a, 0, sizeof(a));
for (int i = 1; i <= k; i ++) {
if (i % 2) {
for (int j = i; j <= n; j += k) a[j] = p ++;
} else {
int tmp = n / k * k + i;
if (tmp > n) tmp -= k;
for (int j = tmp; j >= 1; j -= k) a[j] = p ++;
}
}
for (int i = 1; i <= n; i ++) cout << a[i] << " ";
cout << "\n";
}
return 0;
}