2025.7.27 模拟赛

和除或

容斥 组合数学

首先，我们通过观察可以猜测 $f(X,Y)=\lceil \frac{X+Y}{X|Y}\rceil$ 的值不是 $1$ 就是 $2$，很明显我们猜对了因为打表找不出反例，因此我们需要进行思考什么情况下取 $1$ 什么情况下取 $2$。

由于这里是向上取整，因此取 $1$ 情况只有 $X+Y=X|Y$ 了，也就是 $X$ 和 $Y$ 的 $1$ 位没有相交的，即 $X\&Y=0$。其余所有 $X\&Y\ne 0$ 的场景，都是取的 $2$。原函数的值转化为 $1+[X\&Y\ne 0]$。

$$\begin{array}{rl}\sum _{1\le i<j\le n}f(a_i,x_j)& =\sum _{1\le i<j\le n}1+\sum _{1\le i<j\le n}[X\&Y\ne 0]\\ & =\frac{n(n-1)}{2}+\sum _{1\le i<j\le n}[X\&Y\ne 0]\end{array}$$

后面的不好计算，因此使用容斥原理。令 $P_k$ 表示第 $k$ 位都为 $1$ 的集合，我们要求的是 $|{\cup }_k{P}_k|$，根据容斥原理

$$|{\cup }_k{P}_k|=\sum |P_k|-\sum |P_k\cap P_l|+\sum |P_k\cap P_l\cap P_m|$$

令 $g(x)$ 表示满足 $a_i\&x=x$ 的 $i$ 的数量，那么所有满足 $[a_i\&a_j\ne 0]$ 的数对的数量为

$$\sum _{x\ne 0}(-1{)}^{\text{popcount(x)}-1}\times \frac{g(x)\times g(x)-1)}{2}$$

因此我们只需要预先计算出 $g(x)$（即多少个 $a_i$ 的子集是 $x$ 的数量）就行了。

#include <iostream>
#include <map>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 2e5 + 5;
 
LL a[kMaxN], t, n, ans;
map<LL, LL> f, dp;
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> t; t; t--) {
    cin >> n;
    f.clear(), dp.clear();
    for (LL i = 1; i <= n; i++) {
      cin >> a[i];
      f[a[i]]++;
    }
    ans = n * (n - 1) / 2;
    for (auto &i : f) {
      for (LL j = i.first; j; j = (j - 1) & i.first) {
        dp[j] += i.second;
      }
      dp[0] += i.second;
    }
    for (auto &i : dp) {
      if (!i.first) {
        continue;
      }
      if (__builtin_popcount(i.first) % 2) {
        ans += i.second * (i.second - 1) / 2;
      } else {
        ans -= i.second * (i.second - 1) / 2;
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

礼物

贪心

既然是不能有连续的长度为 $k$ 的段，那么我就找到第一个连续的长度为 $k$ 的段的位置 $l$，然后往右枚举 $r$，判断一下替换 $[l,r]$ 能否满足条件即可。

至于判断是否满足条件还是有一点复杂的，过程如下：

• $s_l\ne s_r$，否则 $s_r$ 反转过去仍然能够组成长度为 $k$ 的连续段；
• 反转的区间 $[l,r]$ 内部不能有长度为 $k$ 的连续段，因为反转操作不会破坏反转区间内的连续段；
• 如果 $s_l=s_{r+1}$ 的话，那么 $l$ 往后的连续段的长度加上 $r+1$ 往后的连续段的长度要小于 $k$，因为 $l$ 反转过去后会和 $r+1$ 拼起来。

如果以上条件都满足，那么就是有解的。

欸，但我们提交上去就会发现大样例 wa 了，被 7 4 AABBBBB 卡了，因为我们总是往后反转而不是往前反转，但是重新写一遍又太复杂了。

于是我就正着跑一遍贪心，反着跑一遍贪心，这样子就可以通过所有数据了，欢迎来 Hack。

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int kMaxN = 2e5 + 5;
 
int suf[kMaxN], len[kMaxN], t, n, k;
char s[kMaxN];
 
bool check() {
  int cnt = 1;
  suf[n + 1] = 1;
  len[n + 1] = 0;
  for (int i = n; i >= 1; i--) {
    if (s[i] == s[i + 1]) {
      cnt++;
    } else {
      cnt = 1;
    }
    suf[i] = suf[i + 1] && cnt < k;
    len[i] = cnt;  // i 往后的相同段的长度
  }
  if (suf[1]) {
    return 1;
  }
  cnt = 1;
  bool ans = 0;
  s[n + 1] = 'C';
  for (int i = 2; i <= n; i++) {
    if (s[i] == s[i - 1]) {
      cnt++;
    } else {
      cnt = 1;
    }
    if (cnt >= k) {
      // 反转 [i, j]
      cnt = 1;
      int pre = 1;
      bool lead = 1;
      for (int j = i + 1; j <= n; j++) {
        if (s[j] == s[j - 1]) {
          cnt++;
        } else {
          cnt = 1;
        }
        if (lead && s[j] == s[i]) {
          pre++;
        } else {
          lead = 0;
        }
        if (cnt >= k) {
          break;
        }
        if (s[j] == s[i]) {
          continue;
        }
        if (suf[j + 1] && (s[i] != s[j + 1] || pre + len[j + 1] < k)) {
          return 1;
        }
      }
      break;
    }
  }
  return 0;
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> t; t; t--) {
    cin >> n >> k >> (s + 1);
    bool ans = check();
    reverse(s + 1, s + n + 1);
    ans |= check();
    cout << (ans ? "YES" : "NO") << '\n';
  }
  return 0;
}

连续段的价值

二分 状压dp

首先答案肯定是有单调性的，如果 $ans$ 是答案的话 $ans-1$ 也可以满足，因此我们可以考虑使用二分答案。注意到 $k\le 17$，这很有状压的嫌疑。

接下来我们考虑如何对我们二分的值进行判断。假设当前二分的答案为 $x$，那么我们设 $d{p}_{i,j}$ 表示为当前已经满足条件的字符集位为 $i$，字符串的长度能否为 $j$，转移就是枚举一个新的字符在 $i$ 里面没出现的，然后往后遍历原始字符串找到一个长度为 $x$ 的连续段进行转移，判断函数时间复杂度 $\mathcal{O}(2^{k}k{n}^2)$，非常恐怖。

考虑预处理转移部分，令 $e_{i,j}$ 表示为 $i$ 字符在第 $j$ 个字符开始，往后至少要到 $e_{i,j}$，在 $[j,e_{i,j}]$ 这个段里面有长度为 $x$ 的连续 $i$ 字符段。$e$ 可以 $\mathcal{O}(kn)$ 预处理出来，转移就变成 $\mathcal{O}(1)$ 的了，判断函数时间复杂度将为 $\mathcal{O}(2^{k}kn)$，可以通过 $75$ 分。

接下来优化 dp 状态。其实我们没必要存储状态 $j$，因为对于所有 $d{p}_{i,j}$ 值为 $1$ 的当中，$j$ 越小的状态是越优的，而且经过相同字符的转移时不会比 $j$ 更大的状态更劣，因此我们将 $j$ 拆掉作为 $d{p}_i$ 的一个最优化属性。

设 $d{p}_i$ 表示为当前已经选择的字符集为 $i$，至少需要 $d{p}_i$ 长度的前缀。转移时枚举字符 $j$，由 $d{p}_i\to d{p}_{i|j}+e_{j,d{p}_i}$。判断函数时间复杂度 $\mathcal{O}(kn+2^{k}k)$，总时间复杂度 $\mathcal{O}\left(\left(n+2^k\right)k{\log }_2\left(\frac{n}{k}\right)\right)$。

#include <iostream>
 
using namespace std;
 
const int kMaxN = 2e5 + 5, kMaxK = 18;
 
int e[kMaxK][kMaxN], dp[1 << kMaxK], n, k, ans;
char s[kMaxN];
 
bool check(int x) {
  for (int i = 0; i < k; i++) {
    e[i][n + 1] = n + 1;
    for (int j = n, cnt = 0; j >= 1; j--) {
      if (s[j] == '?' || s[j] == 'a' + i) {
        cnt++;
      } else {
        cnt = 0;
      }
      if (cnt >= x) {
        e[i][j] = j + x - 1;
      } else {
        e[i][j] = e[i][j + 1];
      }
    }
  }
  fill(dp, dp + (1 << kMaxK), 1e9);
  dp[0] = 0;
  for (int i = 0; i < (1 << k); i++) {
    for (int j = 0; j < k; j++) {
      if (!(i & (1 << j)) && dp[i] < n) {
        dp[i | (1 << j)] = min(dp[i | (1 << j)], e[j][dp[i] + 1]);
      }
    } 
  }
  return dp[(1 << k) - 1] <= n;
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> k >> (s + 1);
  for (int l = 0, r = n / k; l <= r; ) {
    int m = (l + r) / 2;
    if (check(m)) {
      ans = m;
      l = m + 1;
    } else {
      r = m - 1;
    }
  }
  cout << ans << '\n';
  return 0;
}

送外卖

线段树 树状数组

本题我写的是暴力。

• 对于子任务 1，模拟蜗蜗的送餐操作。最初时间戳 $tm=x_l$，每次往后送餐 $tm\leftarrow tm+t_i$，但是如果时间太早了就要等 $tm\leftarrow \max (tm,x_{i+1})$，如果 $tm>y_{i+1}$ 就是超时了。
• 对于子任务 3，用树状数组维护 $t_i$ 的区间和，如果区间内 $t_i$ 的和超过了任意 $y-x$，那么就是超时了。

#include <iostream>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 1e6 + 5;
 
LL l[kMaxN], r[kMaxN], a[kMaxN], tr[kMaxN], t, n, q;
 
bool same() {
  for (int i = 2; i <= n; i++) {
    if (l[i] != l[i - 1] || r[i] != r[i - 1]) {
      return 0;
    }
  }
  return 1;
}
 
void modify(int x, int y) {
  for (; x <= n; x += x & -x) {
    tr[x] += y;
  }
}
 
int query(int x) {
  int res = 0;
  for (; x; x -= x & -x) {
    res += tr[x];
  }
  return res;
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> t; t; t--) {
    cin >> n;
    for (LL i = 1; i <= n; i++) {
      cin >> l[i];
    }
    for (LL i = 1; i <= n; i++) {
      cin >> r[i];
    }
    for (LL i = 1; i < n; i++) {
      cin >> a[i];
    }
    cin >> q;
    if (n <= 2000 && q <= 2000) {
      for (LL o, p, x, y; q; q--) {
        cin >> o;
        if (o == 0) {
          cin >> x >> y;
          LL p = l[x], ans = 1;
          for (LL i = x; i < y; i++) {
            p = max(l[i + 1], p + a[i]);
            if (p > r[i + 1]) {
              ans = 0;
              break;
            }
          }
          cout << (ans ? "Yes" : "No") << '\n';
        } else if (o == 1) {
          cin >> x >> y;
          a[x] = y;
        } else if (o == 2) {
          cin >> p >> x >> y;
          l[p] = x;
          r[p] = y;
        }
      }
    } else if (same()) {
      fill(tr + 1, tr + n + 1, 0);
      for (LL i = 1; i <= n; i++) {
        modify(i, a[i]);
      }
      for (LL o, p, x, y; q; q--) {
        cin >> o;
        if (o == 0) {
          cin >> x >> y;
          cout << (query(y - 1) - query(x - 1) <= r[y] - l[x] ? "Yes" : "No") << '\n';
        } else if (o == 1) {
          cin >> x >> y;
          modify(x, -a[x]);
          a[x] = y;
          modify(x, a[x]);
        } else if (o == 2) {
        }
      }
    }
  }
  return 0;
}