A

直接统计 $12$ 个骰子的结果为 $y$ 的个数与 $x$ 比大小即可。

#include <bits/stdc++.h>

int main() {
  
  int t;
  std::cin >> t;
  while (t--) {
    std::vector<int> a(12);
    for (int i = 0; i < 12; i++) {
      std::cin >> a[i];
    }
    int x, y;
    std::cin >> x >> y;
    int cnt = 0;
    for (int i = 0; i < 12; i++) {
      if (a[i] == y) {
        cnt++;
      }
    }
    std::cout << (cnt < x ? "win" : "lose") << '\n';
  }
  
  return 0;
}

B

注意到 $Max\ge Mid$ ，以及 $v_i$ 只有两种 $0,1$ 两种取值，记 $one$ 为序列中 $1$ 的个数， $zero$ 为序列中 $0$ 的个数。

$Max-Mid$ 只可能出现三种情况：

$1-1=0$ ： $1$ 可选的个数超过 $k$ 的一半。
$0-0=0$ ： $0$ 可选的个数足够 $k$ 个。
$1-0=1$ ：否则中位数还是 $0$ ，然后 $1$ 也没法不选。

$ans = \begin{cases} 0 & \text{若 } \left( one > \lfloor \frac{k}{2} \rfloor \right) \lor \left( zero \ge k \right) \\ 1 & \text{否则} \end{cases}$

#include <bits/stdc++.h>

int main() {

  int t;
  std::cin >> t;
  while (t--) {
    int n, k;
    std::cin >> n >> k;
    int one = 0;
    for (int i = 0; i < n; i++) {
      int x;
      std::cin >> x;
      if (x == 1) {
          one += 1;
      }
    }
    if ((n - one >= k) || one > k / 2) {
      std::cout << 0 << '\n';
    } else {
      std::cout << 1 << '\n';
    }
  }

  return 0;
}

C

记初始序列中正数个数为 $pos$ ，负数个数为 $neg$ ，零的个数为 $zero$ 。

注意两个地方：

$0$ 只能消除正数但不能增加正数。
负数可以增加正数也可以消除正数， $x$ 个负数最多变成 $x-1$ 个正数。

$ans = \begin{cases} -1 & \text{若 } \left( pos > m \land zero = 0 \land neg = 0 \right) \lor \left( pos < m \land pos + neg - 1 < m \right) \\ |pos - m| & \text{否则} \end{cases}$

#include <bits/stdc++.h>

int main() {
  int t;
  std::cin >> t;
  while (t--) {
    int n, m;
    std::cin >> n >> m;
    int pos = 0, neg = 0, zero = 0;
    for (int i = 0; i < n; i++) {
      int x;
      std::cin >> x;
      if (x > 0) {
        pos += 1;
      } else if (x < 0) {
        neg += 1;
      } else {
        zero += 1;
      }
    }
    int ans = std::abs(pos - m);
    if ((pos > m && !zero && !neg) || (pos < m && pos + neg - 1 < m)) {
      ans = -1;
    }
    std::cout << ans << '\n';
  }

  return 0;
}

D

对于任意一个从 $x\to y$ 的操作序列来说，一定可以通过调整操作 $1,2$ 的顺序先使用操作 $1$ 后使用操作 $2$ ，使得操作次数不变，且仍然可以让 $x\to y$ 。
在最优操作中， $|$ 操作至多使用一次。

证明:

用 $1$ 表示操作 $1$ ， $2$ 表示操作 $2$ 。

考虑这样的一个操作序列： $P+[2,1]+Q$ ，其中 $P,Q$ 分别表示前缀操作序列和后缀操作序列。

令 $x$ 做完前缀操作序列 $P$ 之后的值为 $a$ ，操作 $2$ 选的那个数为 $u$ ， $b=a|u$ ， $c=\lfloor\frac{b}{2}\rfloor$ 。

我们交换两个操作的顺序，先做操作 $1$ 再做操作 $2$ ，令 $d=\lfloor\frac{a}{2}\rfloor$ 。

我么只要证明存在一个 $v$ ，使得 $d|v=c$ 即可，不难注意到 $v=\lfloor\frac{u}{2}\rfloor$ 即可。

所以我们证明了对于任意一个相邻的操作，如果 $2$ 在 $1$ 的前面，一定可以交换顺序，且交换之后操作完得到的数还是一样的，同时后缀 $Q$ 的操作序列没变，所以最后得到的结果还是 $y$ ，且操作总次数没变多。

故任意一种可行的序列一定可以通过交换顺序变成 $[1,1,1,1,1,2,2,2,2,2....]$ 。

然后我们在注意到连续的操作 $2$ 是没意义的，因为只要令 $z=z_1|z_2|...|z_n$ ，那么这一段连续的操作 $2$ 可以被合并为一段。

综上最优操作序列一定只有两种情况： $[1,1,1,1...]$ 或者 $[1,1,1,1,...,2]$ 。

所以可以枚举操作 $1$ 的操作次数，然后判断是否还需要一次操作 $2$ 去让 $x\to y$ 。

时间复杂度 $O(\log x\times T)$ 。

#include <bits/stdc++.h>

int main() {
  int t;
  std::cin >> t;
  while (t--) {
    long long x, y;
    std::cin >> x >> y;
    int ans = 0;
    while ((x & y) != x) {
      ans++;
      x >>= 1;
    }
    std::cout << ans + (x != y) << '\n';
  }

  return 0;
}

E

做法一：预处理前后缀

子序列的匹配是贪心的，对于 $P[l\backsim r]$ 来说，他一定是在前缀 $P[1\backsim l-1]$ 从左到右找某些项匹配，在后缀 $P[r+1\backsim n]$ 从右往左找某些项拼接起来，所以考虑计算两个数组 $lsz[i]$ 与 $rsz[i]$ 。

$lsz[i]$ 表示满足 $P[i,i+x-1]$ 是 $P[1\backsim i-1]$ 的子序列的 $x$ 的最大值。

$rsz[i]$ 表示满足 $P[i-x+1,n]$ 是 $P[i+1\backsim n]$ 的子序列的 $x$ 的最大值。

答案即为 $\sum_{i=2}^{n-1}\sum_{j=i}^{n-1} [lsz[i]+rsz[j]\ge j-i+1]$ 。

显然处理 $lsz,rsz$ 与计算答案复杂度都是 $O(N^2)$ 的。

#include <bits/stdc++.h>

int main() {
  
  int n;
  std::cin >> n;
  std::vector<int> P(n + 1);
  for (int i = 1; i <= n; i++) {
    std::cin >> P[i];
  }
  std::vector<int> lsz(n + 1), rsz(n + 1);
  for (int i = 2; i < n; i++) {
    int jl = 1, jr = n;
    while (jl < i && i + lsz[i] <= n) {
      if (P[jl] == P[i + lsz[i]]) {
        lsz[i]++;
      }
      jl++;
    }
    while (jr > i && i - rsz[i] >= 1) {
      if (P[jr] == P[i - rsz[i]]) {
        rsz[i]++;
      }
      jr--;
    }
  }
  int ans = 0;
  for (int i = 2; i < n; i++) {
    for (int j = i; j < n; j++) {
      ans += lsz[i] + rsz[j] >= j - i + 1;
    }
  }
  std::cout << ans << '\n';

  return 0;
}

做法二：二分

首先要注意到：

对于 $2\leq l_1\leq r_1<n$ ，若 $P[l_1\backsim r_1]$ 是 $P[1\backsim l_1-1]+P[r_1+1\backsim n]$ 的子序列，那么一个更小的区间 $l_1<l_2\leq r_2<r_1$ ，也必然满足 $P[l_2\backsim r_2]$ 是 $P[1\backsim l_2-1]+P[r_2+1\backsim n]$ 的子序列。

基于这个性质，我么可以枚举 $l$ ，通过二分出最大的一个 $r$ 满足 $P[l,r]$ 是 $P[1\backsim l-1]+P[r+1\backsim n]$ 的子序列，那么对于 $r'\in[l,r]$ 都是满足条件的。

时间复杂度 $O(N^2\times \log N)$

#include <bits/stdc++.h>

int main() {
  
  int n;
  std::cin >> n;
  std::vector<int> P(n + 1);
  for (int i = 1; i <= n; i++) {
    std::cin >> P[i];
  }
  int ans = 0;
  auto check = [&](int l, int r) {
    int idx = l;
    for (int i = 1; i <= n; i++) {
      if (i == l) {
        i = r;
        continue;
      }
      if (idx <= r && P[idx] == P[i]) {
        idx++;
      }
    }
    return idx == r + 1;
  };
  for (int i = 2; i < n; i++) {
    int l = i - 1, r = n - 1;
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (check(i, mid)) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    ans += l - i + 1;
  }
  std::cout << ans << '\n';

  return 0;
}

做法三：双指针

同样注意到上面的那个性质，不难发现对于 $l$ 如果存在满足条件的 $r$ ，那么 $r_{max}$ 随着 $l$ 的增加是单调不降的，所以可以用双指针。

时间复杂度 $O(N^2)$ 。

#include <bits/stdc++.h>

int main() {
  
  int n;
  std::cin >> n;
  std::vector<int> P(n + 1);
  for (int i = 1; i <= n; i++) {
    std::cin >> P[i];
  }
  int ans = 0;
  auto check = [&](int l, int r) {
    int idx = l;
    for (int i = 1; i <= n; i++) {
      if (i == l) {
        i = r;
        continue;
      }
      if (idx <= r && P[idx] == P[i]) {
        idx++;
      }
    }
    return idx == r + 1;
  };
  for (int i = 2, j = 2; i < n; i++) {
    j = std::max(j, i);
    while (j < n && check(i, j)) {
      j++;
    }
    ans += j - i;
  }
  std::cout << ans << '\n';

  return 0;
}

F

先考虑暴力 DP 怎么做。

令 $dp[i][j]$ 表示考虑了前 $i$ 个位置，若 $i$ 为奇数，则 $j$ 表示第 $i$ 个位置 $P_i$ 的值；若 $i$ 为偶数，则 $j$ 表示 $|P_{i} \ - \ P_{i-1}|$ 的值的方案数。

枚举 $j$ 与当前位置 $i$ 的取值 $P_i=k(0\leq k\leq A_i)$ 去转移：

若 $i$ 为奇数，若满足 $L_{i-1}\leq j\oplus k\leq R_{i-1}$ ，则 $dp[i-1][j]\to dp[i][k]$ 。
若 $i$ 为偶数，则 $dp[i-1][j]\to dp[i][|j-k|]$ 。

这样的 DP 复杂度是 $O(N\times 2^{10}\times 2^{10})$ 的，显然无法通过。

考虑能否优化掉转移枚举 $k(0\leq k\leq A_i)$ 。

首先 $i$ 为偶数的情况是好优化的：

若 $A_i\leq j$ ，那么对于 $k(0\leq k\leq A_i)$ 来说， $|j-k|$ 形成的是一个连续的区间 $[j-A_i,j]$ 。
若 $A_i>j$ ，那么对于 $k(0\leq k\leq A_i)$ 来说， $|j-k|$ 可以形成两个连续的区间： $[0,j]$ 与 $[1,j-A_i]$ 。

那么我么需要对这些区间的 $dp[i][|j-k|]$ 加上 $dp[i-1][j]$ ，这个过程显然可以通过差分优化到 $O(1)$ 。

对于 $i$ 为奇数的情况：

首先需要先注意到对于给定的 $y,z$ ，所有满足 $x\oplus y\leq z$ 的 $x$ 至多形成 $\log$ 个互不重叠的连续区间。

考虑前缀和思想，我么可以分两部做：

对满足 $k\oplus j\leq R_{i-1}$ 的所有 $dp[i][k]$ 都加上 $dp[i-1][j]$ 。
对满足 $k\oplus j\leq L_{i-1}-1$ 的所有 $dp[i][k]$ 都减去 $dp[i-1][j]$ 。

所以，我们可以先求出对于固定的 $j$ ，满足 $k\oplus j\leq R_{i-1}$ 的 $k$ 形成的 $\log$ 个互不重叠的连续区间。（这个性质可以从经典的 $01$ 字典树去想，考虑从二进制高位到低位去确定可能的 $x$ 的范围）

这个过程可以用 $\log_2 2^{10}=10$ 的复杂度算出来，那么再结合 $k$ 的限制 $0\leq k\leq A_i$ ，我么可以得到最终满足条件的 $\log$ 个区间： $[\max(l_1,0),\min(r_1,A_i)],[\max(l_2,0),\min(r_2,A_i)],...,[\max(l_n,0),\min(r_n,A_i)]$ 。

此时需要对这些区间的 $dp[i][k]$ 加上 $dp[i-1][j]$ ，这个过程也可以用差分优化，同理处理 $k\oplus j\leq L_{i-1}-1$ 也一样。

综上对于 $i$ 为奇偶的情况都可以用差分优化，所以 DP 的时间复杂度可以降为 $O(N\times 2^{10}\times \log_22^{10})$ 。

最后答案即为 $\sum_{i=0}^{2^{10}-1}dp[n][i]$ ，故总的时间复杂度 $O(N\times 2^{10}\times \log_22^{10}+2^{10}\times T)$ 。

#include <bits/stdc++.h>

constexpr int mod = 1e9 + 7;
constexpr int MAX = 1 << 10;
constexpr int MAX_BIT = 10;

void Add(int& x, int y) {
  x += y;
  if (x >= mod) {
    x -= mod;
  }
  if (x < 0) {
    x += mod;
  }
}

std::vector<std::array<int, 2>> GetSegXOR(int x, int y) {
  std::vector<std::array<int, 2>> seg;
  if (y < 0) {
    return seg;
  }
  int p = 0;
  for (int i = MAX_BIT - 1; i >= 0; i--) {
    if (y >> i & 1) {
      if (x >> i & 1) {
        seg.push_back({p | (1 << i), p | ((1 << (i + 1)) - 1)});
      } else {
        seg.push_back({p, p | ((1 << i) - 1)});
        p |= 1 << i;
      }
    } else {
      if (x >> i & 1) {
        p |= 1 << i;
      }
    }
  }
  assert((p ^ x) == y);
  seg.push_back({p, p});
  return seg;
}

void Solve() {
  int n;
  std::cin >> n;
  std::vector<int> A(n + 1), L(n + 1), R(n + 1);
  for (int i = 1; i <= n; i++) {
    std::cin >> A[i] >> L[i] >> R[i];
  }
  std::vector<int> dp(MAX);
  for (int i = 0; i <= A[1]; i++) {
      Add(dp[i], 1);
  }
  for (int i = 2; i <= n; i++) {
    std::vector<int> ndp(MAX);
    for (int j = 0; j < MAX; j++) {
      if (dp[j] == 0) {
        continue;
      }
      if (i % 2 == 0) {
        if (j >= A[i]) {
          Add(ndp[j - A[i]], dp[j]);
          if (j + 1 < MAX) {
            Add(ndp[j + 1], -dp[j]);
          }
        } else {
          Add(ndp[0], dp[j]);
          if (j + 1 < MAX) {
            Add(ndp[j + 1], -dp[j]);
          }
          Add(ndp[1], dp[j]);
          if (A[i] - j + 1 < MAX) {
            Add(ndp[A[i] - j + 1], -dp[j]);
          }
        }
      } else {
        auto segl = GetSegXOR(j, L[i - 1] - 1);
        auto segr = GetSegXOR(j, R[i - 1]);
        for (auto& [l, r] : segr) {
          l = std::max(0, l);
          r = std::min(r, A[i]);
          if (l > r) {
            continue;
          }
          Add(ndp[l], dp[j]);
          if (r + 1 < MAX) {
            Add(ndp[r + 1], -dp[j]);
          }
        }
        for (auto& [l, r] : segl) {
          l = std::max(0, l);
          r = std::min(r, A[i]);
          if (l > r) {
            continue;
          }
          Add(ndp[l], -dp[j]);
          if (r + 1 < MAX) {
            Add(ndp[r + 1], dp[j]);
          }
        }
      }
    }
    for (int j = 1; j < MAX; j++) {
      Add(ndp[j], ndp[j - 1]);
    }
    dp.swap(ndp);
  }
  int ans = 0;
  for (int i = 0; i < MAX; i++) {
    Add(ans, dp[i]);
  }
  std::cout << ans << '\n';
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int t;
  std::cin >> t;
  while (t--) {
    Solve();
  }

  return 0;
}

小白月赛122 出题人题解

A

B

C

D

E

F