ABC381(A-F)

A - 11/22 String

题目大意

对于 11/22 字符串的定义，A题、C题、E题相同。

满足以下所有条件的字符串 \(T\) 称为 11/22 字符串：

• \(|T|\) 是奇数。
• \(T\) 的第 \(1\) 个字符到第 \((\frac{|T|+1}{2}-1)\) 个字符都是 1。
• \(T\) 的第 \(\frac{|T|+1}{2}\) 个字符是 /。
• \(T\) 的第 \((\frac{|T|+1}{2}-1)\) 个字符到第 \(|T|\) 个字符都是 2。

给你一个长度为 \(N\) 的字符串 \(S\)，判断 \(S\) 是不是11/22 字符串。

参考代码

C++

#include <iostream>
#include <string>

using namespace std;

int main()
{
    int n;
    string s;
    cin >> n >> s;

    auto check = [](const string &s, int l, int r, char ch) -> bool
    {
        for(int i = l; i <= r; i++)
            if(s[i] != ch)
                return false;
        return true;
    };

    int mid = n / 2;
    if(n % 2 == 1 && s[mid] == '/' && check(s, 0, mid-1, '1') && check(s, mid+1, n-1, '2'))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

---

B - 1122 String

题目大意

满足以下所有条件的字符串 \(T\) 称为 1122 字符串：

• \(|T|\) 是偶数。
• 对于任意的 \(1 \le i \le \frac{|T|}{2}\)，\(T\) 的第 \((2i-1)\) 个字符和第 \(2i\) 个字符相等。
• \(T\) 中所有的字符都恰好出现 \(2\) 次。

给你一个长度为 \(N\) 的字符串 \(S\)，判断 \(S\) 是不是1122 字符串。

参考代码

C++

#include <iostream>
#include <string>
#include <unordered_set>

using namespace std;

int main()
{
    string s;
    cin >> s;

    auto check = [](const string &s) -> bool
    {
        unordered_set<char> cnt;
        int n = s.size();
        if(n % 2 == 1)
            return false;
        for(int i = 0; i < n; i += 2)
        {
            if(s[i] != s[i+1] || cnt.count(s[i]))
                return false;
            cnt.insert(s[i]);
        }
        return true;
    };

    cout << (check(s) ? "Yes" : "No") << endl;
    return 0;
}

---

C - 11/22 Substring

题目大意

对于 11/22 字符串的定义，A题、C题、E题相同。

满足以下所有条件的字符串 \(T\) 称为 11/22 字符串：

• \(|T|\) 是奇数。
• \(T\) 的第 \(1\) 个字符到第 \((\frac{|T|+1}{2}-1)\) 个字符都是 1。
• \(T\) 的第 \(\frac{|T|+1}{2}\) 个字符是 /。
• \(T\) 的第 \((\frac{|T|+1}{2}-1)\) 个字符到第 \(|T|\) 个字符都是 2。

给你一个长度为 \(N(1 \le N \le 2 \times 10 ^ 5)\) 的字符串 \(S\)，其中 \(S\) 只包括字符 1，2 和 /，求出 \(S\) 中最长的（连续的）子串使得这个子串是 11/22 字符串。

解题思路

遍历一遍，记录下连续的 1 的个数，碰到 / 的时候往后找有多少个连续的 2，统计答案即可。

参考代码

C++

#include <iostream>
#include <string>

using namespace std;

int main()
{
    int n;
    string s;
    cin >> n >> s;
    int one = 0, ans = 0;
    for(int i = 0; i < n; i++)
    {
        if(s[i] == '2')
        {
            one = 0;
            continue;
        }
        if(s[i] == '1')
            one++;
        else
        {
            int j = i;
            while(j + 1 < n && s[j+1] == '2')
                j++;
            int k = min(one, j-i);
            ans = max(ans, 2 * k + 1);
            i = j;
            one = 0;
        }
    }
    cout << ans << endl;
    return 0;
}

---

D - 1122 Substring

题目大意

对于 1122 序列的定义，D 题和 F 题相同。

对于一个正整数序列 \(X = (X_1, X_2, ...)\) 如果满足以下所有条件的，则被称为 1122 序列：

• \(|X|\) 是偶数。
• 对于任意的 \(1 \le i \le \frac{|X|}{2}\)，\(X_{2i-1}\) 和 \(X_{2i}\) 相等。
• \(X\) 中所有的数字都恰好出现 \(2\) 次。

给你一个长度为 \(N(1 \le N \le 2 \times 10 ^ N)\) 的序列 \(A = (A_1, A_2, ..., A_N)\)，求出 \(A\) 中最长的（连续的）子序列，使得这个子序列是一个 1122 序列。

解题思路

构造一个新的序列 \(B\)，遍历 \(1 \le i \le \frac{N}{2}\)，如果 \(A_{2i-1} = A_{2i}\)，则 \(B_i = A_{2i}\)，否则 \(B_i = -1\) 。原问题等价于求出 \(B\) 中最长的连续子序列，且这个子序列不包括 \(-1\) 且数字只出现一次，这可以通过滑动窗口实现。

不过这个方法是从 \(i=1\) 开始的，还要考虑一种情况从 \(i = 2\) 开始的，也就是再构造一个序列 \(C\)，遍历 \(2 \le i \le \frac{N}{2}\)，如果 \(A_{2i} = A_{2i+1}\)，则 \(C_i = A_{2i}\)，否则 \(C_i = -1\)。

参考代码

C++

#include <iostream>
#include <unordered_set>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    auto solve = [](const vector<int> &b) -> int
    {
        int n = b.size();
        int ans = 0;
        unordered_set<int> vis;
        for (int l = 0, r = 0; r < n; r++)
        {
            if (b[r] == -1)
            {
                vis.clear();
                l = r + 1;
                continue;
            }
            if (vis.count(b[r]))
            {
                while (b[l] != b[r])
                    vis.erase(b[l++]);
                l++;
            }
            else
                vis.insert(b[r]);
            ans = max(ans, r - l + 1);
        }
        return ans * 2;
    };

    vector<int> b, c;
    for (int i = 0; i < n; i += 2)
        b.push_back(a[i] == a[i + 1] ? a[i] : -1);
    for (int i = 1; i < n; i += 2)
        c.push_back(a[i] == a[i + 1] ? a[i] : -1);
    cout << max(solve(b), solve(c)) << endl;
    return 0;
}

---

E - 11/22 Subsequence

题目大意

对于 11/22 字符串的定义，A题、C题、E题相同。

满足以下所有条件的字符串 \(T\) 称为 11/22 字符串：

• \(|T|\) 是奇数。
• \(T\) 的第 \(1\) 个字符到第 \((\frac{|T|+1}{2}-1)\) 个字符都是 1。
• \(T\) 的第 \(\frac{|T|+1}{2}\) 个字符是 /。
• \(T\) 的第 \((\frac{|T|+1}{2}-1)\) 个字符到第 \(|T|\) 个字符都是 2。

给你一个长度为 \(N(1 \le N \le 1 \times 10 ^ 5)\) 的字符串 \(S\)，其中 \(S\) 只包括字符 1，2 和 /，给你 \(Q(1 \le Q \le 1 \times 10 ^ 5)\) 个询问，每个询问包括两个数字 \(L_i\) 和 \(R_i\)，设 \(S\) 从第 \(L_i\) 个字符到第 \(R_i\) 个字符组成的子串是 \(T\) ，你需要求出 \(T\) 中最长的一个（不连续的）子序列，使得这个子序列是 11/22 字符串。

解题思路

因为是子序列，所以当确定某个位置的 / 之后，实际只关心这个 / 前面有多少个 1，以及后面又多少个 2，对于 \([L_i, R_i]\) 的某个 /，如果前面的 1 更少，则答案显然是应该从后半部分的 / 中选择。因此，再维护所有 / 的位置，然后在其中二分即可，在 check 的时候需要知道 1 和 2 的数量，再维护 1 和 2 数量的前缀和即可。

参考代码

C++

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
    int n, q;
    string s;
    cin >> n >> q >> s;
    vector<int> one(n + 1), two(n + 1), slash;
    for(int i = 1; i <= n; i++)
    {
        char ch = s[i-1];
        one[i] = one[i-1];
        two[i] = two[i-1];
        if(ch == '1')
            one[i]++;
        else if(ch == '2')
            two[i]++;
        else
            slash.push_back(i);
    }
    while(q--)
    {
        int l, r;
        cin >> l >> r;
        int beg = lower_bound(slash.begin(), slash.end(), l) - slash.begin();
        int end = upper_bound(slash.begin() + beg, slash.end(), r) - slash.begin() - 1;
        if(beg > end)
        {
            cout << 0 << endl;
            continue;
        }
        int ans = 0;
        while(beg < end)
        {
            int mid = (beg + end) / 2;
            int cnt1 = one[slash[mid]] - one[l-1];
            int cnt2 = two[r] - two[slash[mid]-1];
            if(cnt1 == cnt2)
            {
                ans = 2 * cnt1 + 1;
                break;
            }
            int k = min(cnt1, cnt2);
            ans = max(ans, 2 * k + 1);
            if(cnt1 > cnt2)
                end = mid - 1;
            else
                beg = mid + 1;
        }
        int cnt1 = one[slash[beg]] - one[l-1];
        int cnt2 = two[r] - two[slash[beg]-1];
        int k = min(cnt1, cnt2);
        ans = max(ans, 2 * k + 1);
        cout << ans << endl;
    }
    return 0;
}

---

F - 1122 Subsequence

题目大意

对于 1122 序列的定义，D 题和 F 题相同。

对于一个正整数序列 \(X = (X_1, X_2, ...)\) 如果满足以下所有条件的，则被称为 1122 序列：

• \(|X|\) 是偶数。
• 对于任意的 \(1 \le i \le \frac{|X|}{2}\)，\(X_{2i-1}\) 和 \(X_{2i}\) 相等。
• \(X\) 中所有的数字都恰好出现 \(2\) 次。

给你一个长度为 \(N(1 \le N \le 2 \times 10 ^ N)\) 的序列 \(A = (A_1, A_2, ..., A_N)\)，其中 \(1 \le A_i \le 20\)，求出 \(A\) 中最长的（不连续的）子序列，使得这个子序列是一个 1122 序列。

解题思路

因为 \(1 \le A_i \le 20\)，考虑状压 DP，不能用 \(dp[i][s]\) 表示前 \(i\) 个数字能否凑出状态 \(s\) 的，因为 \(O(N2^{\max A_i})\) 肯定是会超时的，但实际上像这种 dp 代表的值是 bool 值的模式可以把一些维度压缩进来，考虑 \(dp[s]\) 表示所有凑出状态 \(s\) 的子序列方案中，最后一个字符的位置的最小值（如果凑不出 \(s\)，则 \(dp[s] = N+1\)）。转移时，需要从 \(dp[s]\)（也就是最后一个字符）的位置把一个新的字符扩进来，又因为 \(A_i \le 20\)，直接用 \(O(N\max (A_i))\) 的空间存储每一个位置的下一个数字，即 \(ne[i][j]\) 表示位置 \(i\) 的下一个数字 \(j\) 的位置。这样每个状态只需转移 \(\max(A_i)\) 次，总的时间复杂度就是 \(O(M2^M)\)，其中 \(M = \max(A_i)\)。

为了减少 \(M\)，还可以离散化进一步压缩。（下面的代码就是离散化过后的）

参考代码

C++

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> x(n+1);
    for(int i = 1; i <= n; i++)
        cin >> x[i];
    set<int> set(x.begin(), x.end());
    vector<int> xs(set.begin(), set.end());
    int m = xs.size();
    vector<vector<int>> next_pos(n+2, vector<int>(m));
    next_pos[n+1].assign(m, n+1);
    vector<int> right(m, n+1);
    for(int i = n; i >= 0; i--)
    {
        for(int j = 0; j < m; j++)
            next_pos[i][j] = right[j];
        int num = lower_bound(xs.begin(), xs.end(), x[i]) - xs.begin();
        right[num] = i;
    }
    int len = 1 << m;
    vector<int> dp(len, n+1);
    dp[0] = 0;
    int ans = 0;
    for(int s = 0; s < len; s++)
    {
        int now = dp[s];
        if(now == n+1)
            continue;
        int cnt = 0;
        for(int i = 0; i < m; i++)
        {
            if(s >> i & 1)
                cnt += 2;
            else
            {
                int ns = s | 1 << i;
                dp[ns] = min(dp[ns], next_pos[next_pos[now][i]][i]);
            }
        }
        ans = max(ans, cnt);
    }
    cout << ans << endl;
    return 0;
}

---

---

最后更新: 2024-12-30
创建日期: 2024-12-30