C - 11/22 Substring

暴力模拟
遍历每个字符/ 然后往左右分别找1和2
因为要求的是连续的，比如上一个“/”号左右符合的在下一个“/”就不会遍历了 所以时间复杂度 $O(N)$

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n;
string s;
bool check(int n, string s) {
  if (n % 2 == 0)
    return false;
  for (int i = 0; i < (n + 1) / 2 - 1; i++) {
    if (s[i] != '1')
      return false;
  }
  if (s[(n + 1) / 2 - 1] != '/')
    return false;
  for (int i = (n + 1) / 2; i < n; i++) {
    if (s[i] != '2')
      return false;
  }
  return true;
}
int solve()
{
  if (check(n, s))
    return n;
  int ans = 1;
  for (int i = 0; i < s.size(); i++)
  {
    if (s[i] != '/')
      continue;
    int l = i - 1, r = i + 1;
    if (l < 0 || r >= n || s[l] != '1' || s[r] != '2')
      continue;
    int len = 1;
    while (l >= 0 && r < s.size() && s[l] == '1' && s[r] == '2')
      len += 2, l --, r++;
    ans = max(ans, len);
  }
  return ans;
}
int main() {
  cin >> n >> s;
  cout << solve();
  return 0;
}

D - 1122 Substring

双指针，对于一串连续的1122 Substring，考虑到每种字符第一次出现的位置要么都位于奇数位置上，要么都位于偶数位置上。
所以分别从1和2开始，跑两次双指针即可

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, ans, a[N], vis[N];
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++)
    cin >> a[i];
  for (int l = 1, r = 0; l <= n; l += 2)
  {
    r = max(r, l - 1);
    while (r + 2 <= n && a[r + 1] == a[r + 2] && !vis[a[r + 1]])
      vis[a[r + 1]] = true, r += 2;
    ans = max(ans, r - l + 1);
    vis[a[l]] = false;
  }
  memset(vis, 0, sizeof vis);
  for (int l = 2, r = 0; l <= n; l += 2)
  {
    r = max(r, l - 1);
    while (r + 2 <= n && a[r + 1] == a[r + 2] && !vis[a[r + 1]])
      vis[a[r + 1]] = true, r += 2;
    ans = max(ans, r - l + 1);
    vis[a[l]] = false;
  }
  cout << ans;
  return 0;
}

E - 11/22 Subsequence

前缀和+二分

分别求出字符/、1、2的前缀和，同时存一下所有/的位置

对于一个要查询的区间[L, R]内，先二分找到区间内所有/的位置

很容易想到，想找到最长的非连续11/22序列，/的位置越右，/左边1的数量越多,/右边2的数量越少。为了最长，肯定要让1的数量和2的数量尽量接近一些。

所以可以二分找到区间内最前面的满足1的数量>=2的数量的/的位置，显然最优答案要么在这个斜杠，要么在前一个斜杠，要么在后一个斜杠

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, q, pre[N], pre1[N], pre2[N];
vector<int> pos;
string s;
int check(int p, int l, int r) {
  // 斜杠为p
  int cnt1 = pre1[p - 1] - pre1[l - 1]; // [l, p - 1]
  int cnt2 = pre2[r] - pre2[p]; // [p + 1, r]
  return min(cnt1, cnt2) * 2 + 1;
}
int solve(int L, int R)
{
  if (pre[R] - pre[L - 1] == 0) // 如果[L, R]内没有斜杠
    return 0;
  // 找到pos里第一个>=L的下标
  int st = lower_bound(pos.begin(), pos.end(), L) - pos.begin();
  // 找到pos里最后一个<=R的下标
  int ed = upper_bound(pos.begin(), pos.end(), R) - pos.begin() - 1;
  // 二分找到 [st, ed]里 第一个cnt1>=cnt2的斜杠
  int l = st, r = ed;
  while (l < r)
  {
    int mid = (l + r) >> 1;
    int cnt1 = pre1[pos[mid] - 1] - pre1[L];
    int cnt2 = pre2[R] - pre2[pos[mid]];
    if (cnt1 >= cnt2)
      r = mid;
    else
      l = mid + 1;
  }
  int ans = check(pos[l], L, R);
  if (l - 1 >= st)
    ans = max(ans, check(pos[l - 1], L, R));
  if (l + 1 <= ed)
    ans = max(ans, check(pos[l + 1], L, R));
    return ans;
}
int main() {
  cin >> n >> q;
  s.resize(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> s[i];
    pre[i] = pre[i - 1] + (s[i] == '/' ? 1 : 0);
    pre1[i] = pre1[i - 1] + (s[i] == '1' ? 1 : 0);
    pre2[i] = pre2[i - 1] + (s[i] == '2' ? 1 : 0);
    if (s[i] == '/')
      pos.push_back(i);
  }
  while (q--)
  {
    int L, R;
    cin >> L >> R;
    cout << solve(L, R) << '\n';
  }
  return 0;
}

F - 1122 Subsequence

看数据范围, $A_i$的范围很小，考虑状压DP

设DP[S]表示为二进制集合S所对应的1122序列最早出现的位置
显然出现位置越早越能往后转移找到更长的1122序列

集合S肯定是从更小的集合转移过来的

首先初始化DP数组，先存一下每种a[i]出现的所有位置

假设数集S中只有一个元素，即S为1<<i，显然DP[S]为i第二次出现的位置，
否则都初始化为INF

状态转移时，就二进制枚举所有S
对于每个S，i从0遍历到小于20, 如果集合S中没有i这个数, 并且dp[S] != INF
显然能从集合S转移到集合S加上i这个数的新集合，即S | (1 << i)

因为DP[S]存的是符合集合S的1122序列结尾元素最早的位置
所以二分从i的所有位置中找到第二个大于DP[S]的位置，因为后面要跟上两个i，所以这里是找第二个位置，因此集合S | (1 << i)最早出现的位置就是这个位置

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f, N = 2e5 + 10;
int n, ans, a[N], dp[1 << 20];
vector<int> pos[20]; // pos[i] 存储i这个数出现的所有位置
// dp[S] 选择数集为S的情况下序列结尾对于原序列的最小位置
int main() {
  cin >> n;

  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    pos[--a[i]].push_back(i); // 为了方便实现，将所有a[i]都减1
  }

  memset(dp, 0x3f, sizeof dp);

  for (int i = 0; i < 20; i++)
    if (pos[i].size() >= 2)
      dp[1 << i] = pos[i][1]; // 数集中只有i这个数，最小位置为pos[i][1]

  for (int S = 0; S < (1 << 20); S++) 
  {
    for (int i = 0; i < 20; i++)
    {
      // 如果数集S中没有i
      if (!(S >> i & 1) && dp[S] != INF)
      {
        // 二分找到从i的所有位置中找到第一个大于dp[S]
        auto idx = upper_bound(pos[i].begin(), pos[i].end(), dp[S]) - pos[i].begin();
        if (idx + 1 < pos[i].size()) {
          dp[S | (1 << i)] = min(dp[S | (1 << i)], pos[i][idx + 1]);
        }
      }
    }
    if (dp[S] != INF)
      ans = max(ans, (int)__builtin_popcount(S) * 2);
  }
  cout << ans;
  return 0;
}