A - 11/22 String
题意：定义\(11/22\)串是前面都是\(1\)后面都是\(2\)，\(1,2\)的个数相同，中间是一个'/'。 判断给你的字符串是不是\(11/22\)串。
模拟即可。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::string s;
std::cin >> s;
if (n % 2 == 0 || s.substr(0, n / 2) != std::string(n / 2, '1') || s.substr(n / 2 + 1) != std::string(n / 2, '2') || s[n / 2] != '/') {
std::cout << "No\n";
} else {
std::cout << "Yes\n";
}
}
B - 1122 String
题意：定义\(1122\)串为每个奇数位置\(i\)，都有\(a_i = a_{i+1}\)，并且每个数只能恰好出现两次。判断是不是\(1122\)串。
一样模拟。
点击查看代码
void solve() {
std::string s;
std::cin >> s;
int n = s.size();
if (n & 1) {
std::cout << "No\n";
return;
}
std::vector<int> cnt(26);
for (int i = 0; i < n; i += 2) {
if (s[i] != s[i + 1]) {
std::cout << "No\n";
return;
}
if (cnt[s[i] - 'a']) {
std::cout << "No\n";
return;
}
cnt[s[i] - 'a'] = 1;
}
std::cout << "Yes\n";
}
C - 11/22 Substring
题意：和\(A\)题一样，不过要你判断字符串是\(11/22\)串的最长子串的长度。
在每个'/'处两边扩展记录最长长度即可。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::string s;
std::cin >> s;
int ans = 0;
for (int i = 0; i < n; ++ i) {
if (s[i] == '/') {
int k = 1;
while (i - k >= 0 && i + k < n && s[i - k] == '1' && s[i + k] == '2') {
++ k;
}
ans = std::max(ans, (k - 1) * 2 + 1);
}
}
std::cout << ans << "\n";
}
D - 1122 Substring
题意：和\(B\)题一样，不过要你判断字符串是\(1122\)串的最长子串的长度。
记录每个数出现的次数，分奇数起点和偶数起点分别双指针模拟即可。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
std::vector<int> st(n + 1);
int ans = 0;
for (int i = 0, j = 0; i + 1 < n;) {
j = std::max(i, j);
while (j + 1 < n && a[j] == a[j + 1] && st[a[j]] == 0) {
st[a[j]] = 1;
j += 2;
}
ans = std::max(ans, j - i);
st[a[i]] = 0;
i += 2;
}
for (int i = 1, j = 1; i + 1 < n;) {
j = std::max(i, j);
while (j + 1 < n && a[j] == a[j + 1] && st[a[j]] == 0) {
st[a[j]] = 1;
j += 2;
}
ans = std::max(ans, j - i);
st[a[i]] = 0;
i += 2;
}
std::cout << ans << "\n";
}
E - 11/22 Subsequence
题意：和\(A\)一样，不过有\(Q\)次询问，每次问你\([L, R]\)区间内\(11/22\)最长子序列是多少。
把所有'/'的位置存下来，然后记录\(1\)和\(2\)的前缀和。那么每次找到第一个位置大于等于\(L\)的'/'和最后一个小于等于\(R\)的'/'，那么可以二分，如果当前'/'两边\(1\)的个数大于等于\(2\)的个数我们就应该往左边走，否则往右边走。因为这个二分出来的不一定是最优解，所以我们需要在二分过程中记录答案。
点击查看代码
void solve() {
int n, q;
std::cin >> n >> q;
std::string s;
std::cin >> s;
std::vector<int> sum1(n + 1), sum2(n + 1);
std::vector<int> a;
for (int i = 0; i < n; ++ i) {
sum1[i + 1] = sum1[i] + (s[i] == '1');
sum2[i + 1] = sum2[i] + (s[i] == '2');
if (s[i] == '/') {
a.push_back(i + 1);
}
}
while (q -- ) {
int l, r;
std::cin >> l >> r;
int L = std::lower_bound(a.begin(), a.end(), l) - a.begin();
int R = std::upper_bound(a.begin(), a.end(), r) - a.begin() - 1;
if (L > R) {
std::cout << 0 << "\n";
continue;
}
int ans = 0;
while (L <= R) {
int mid = L + R >> 1;
int one = sum1[a[mid]] - sum1[l - 1], two = sum2[r] - sum2[a[mid]];
ans = std::max(ans, std::min(one, two));
if (one >= two) {
R = mid - 1;
} else {
L = mid + 1;
}
}
std::cout << ans * 2 + 1 << "\n";
}
}
F - 1122 Subsequence
题意：跟\(B\)题一样，不过要你求最长的\(1122\)子序列。
注意值域只有\(20\)，我们可以状压。记录满足\(f_i\)这个状态用到的数的最后位置。用\(suf_{i,j}\)记录第\(i\)个位置后面\(j\)出现的最早位置。那么如果\(suf_{f_i,j}\)与\(suf_{suf_{f_i,j},j}\)都存在，那么\(f_i\)可以转移到\(f_{i|(1<<j)}\)。
点击查看代码
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
std::vector suf(n + 1, std::array<int, 20>{});
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
-- a[i];
}
for (int i = n - 1; i >= 0; -- i) {
suf[i] = suf[i + 1];
suf[i][a[i]] = i + 1;
}
std::vector<int> f(1 << 20, n + 1);
f[0] = 0;
for (int i = 0; i < 1 << 20; ++ i) {
if (f[i] > n) {
continue;
}
for (int j = 0; j < 20; ++ j) {
if ((~i >> j & 1) && suf[f[i]][j] != 0 && suf[suf[f[i]][j]][j] != 0) {
f[i | (1 << j)] = std::min(f[i | (1 << j)], suf[suf[f[i]][j]][j]);
}
}
}
int ans = 0;
for (int i = 0; i < 1 << 20; ++ i) {
if (f[i] <= n) {
ans = std::max(ans, __builtin_popcount(i));
}
}
std::cout << ans * 2 << "\n";
}