2024.10.21 模拟赛

题目：2024.10.21 题目

串串串

有两个长度为 $n,m$ 的 $0/1$ 字符串 $S,T$，给定 $Q$ 次询问，每次询问给出 $(l_1,r_1,l_2,r_2)$，其中 $r_1-l_1=r_2-l_1$，令 $a=S_{l_1\sim r_1},b=T_{l_2\sim r_2}$，求 $a_i\ne b_i$ 的位置数量对 $2$ 取模的结果。

---

手推可以发现，交换区间内的任意两个位置 $i,j$，答案的奇偶性都是不变的。具体而言：如果位置 $i$ 与位置 $j$ 相等，那么交换了就跟没交换一样；如果两个位置上的数不一样，那么答案可能会根据实际情况加 $2$ 或减 $2$，答案的奇偶性没有变化。

因此我们只需要使用两个前缀和数组记录 $S$ 和 $T$ 任意区间的 $1$ 的数量，如果询问的两个区间 $1$ 的数量相等就输出 $0$，否则输出 $1$。

// 出题人，柠檬熟了
 
#include <fstream>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 2e5 + 5;
 
ifstream cin("string.in");
ofstream cout("string.out");
 
LL p1[kMaxN], p2[kMaxN], n, m, q;
char s[kMaxN], t[kMaxN];
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m >> (s + 1) >> (t + 1) >> q;
  for (LL i = 1; i <= n; i++) {
    p1[i] = p1[i - 1] + (s[i] == '1');
  }
  for (LL i = 1; i <= m; i++) {
    p2[i] = p2[i - 1] + (t[i] == '1');
  }
  for (LL l1, r1, l2, r2; q; q--) {
    cin >> l1 >> r1 >> l2 >> r2;
    cout << (LL)((p1[r1] - p1[l1 - 1]) % 2 != (p2[r2] - p2[l2 - 1]) % 2) << '\n';
  }
  return 0;
}

方格计数

给定 $H,W$，有 $(H+1)\times (W+1)$ 的网格，现在要在网格上找 $N$ 个不同的结点，使得这些点在同一条直线上，并且在这条直线上相邻点的距离不小于 $D$，求方案数对 $10^9+7$ 取模的值。

---

枚举 $N$ 个点分别在哪个位置上肯定不行，因此我们不如枚举 $N$ 个点所在的直线上。很容易想到枚举直线的斜率，然后再枚举直线上的两个端点，在算出答案。但是这样子代码过于复杂，而且枚举斜率很容易重复。

小学老师交过我们一件事：「两点确定一条直线」。这也就意味着我们根本就没有必要枚举直线的斜率，我们可以直接枚举直线两边的端点，即可确定这一条直线/线段。根据初中老师所讲的知识，假设两点之间 $x$ 坐标差值为 $\Delta x$，$y$ 坐标差值为 $\Delta y$，则这两点之间连接的线段将会在网格上经过 $\gcd (\Delta x,\Delta y)$ 个点。

此时我们已经选择了两个端点，因此还需要选择 $N-2$ 个直线上的端点。由于题目中指出相邻两点距离至少为 $D$，因此我们将直线经过的点编号，令任意相邻两个点编号差不能小于 $l$，这时学过组合数的都应该知道了，答案为

$$\left(\genfrac{}{}{0ex}{}{g-(l-1)\times (N-3)-2\times k+1}{N-2}\right)$$

因此我们预处理杨辉三角用来计算组合数，或者预处理阶乘使用费马小定理计算组合数（因为在这题当中模数为质数）。此时时间复杂度为 $\mathcal{O}(W^2{H}^2)$，可以通过 $30$ 分。

接下来考虑如何得到满分，其实非常简单。不难发现，在枚举的过程中，有很多直线它们斜率相等或互为倒数，这时我们就可以把这些直线看成相等的，同一枚举并计算。假设有一个矩形框，这条直线就是矩形的对角线，矩形的宽为 $w$，高为 $h$，则为同样的矩形有 $(W-w+1)(H-h+1)$ 个，乘上即可。

最后就是细节的处理了。对于 $h,w\ne 0$ 的矩形，我们需要将答案翻倍，很明显是因为对角线有 $2$ 条。这样我们就成功地将时间复杂度优化到了 $\mathcal{O}(WH)$，可以通过 $100$ 分。

#include <fstream>
#include <cmath>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 3005, kMod = 1e9 + 7;
 
ifstream cin("count.in");
ofstream cout("count.out");
 
LL c[kMaxN][kMaxN], f[kMaxN], t, n, w, h, d, ans;
 
void pre() {
  cin.tie(0)->sync_with_stdio(0);
  c[0][0] = 1;  // 没有初始化
  for (LL i = 1; i <= 3000; i++) {
    c[i][0] = 1;
    for (LL j = 1; j <= i; j++) {
      c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % kMod;
    }
  }
  // f[0] = 1;
  // for (int i = 1; i <= 3000; i++) {
  //   f[i] = f[i - 1] * i % kMod;
  // }
}
 
LL gcd(LL a, LL b) { return !b ? a : gcd(b, a % b); }
 
double dis(LL x, LL y) { return sqrt(x * x + y * y); }
 
// LL pow(LL a, LL b) {
//   LL res = 1;
//   for (; b; b /= 2) {
//     b & 1 && (res = res % a % kMod);
//     a = a * a % kMod;
//   }
//   return res;
// }
//
// LL inv(LL x) { return pow(x, kMod - 2); }
 
LL fuck(LL i, LL j) {
  LL g = gcd(i, j), l = (LL)ceil(1.0 * d / dis(i / g, j / g)) /* 差 */;
  if ((n - 1) * l > g) { return 0; }
  return c[g - (n - 3) * (l - 1) - 2 * l + 1][n - 3 + 1] *  // 组合数
         (i && j ? 2 : 1) % kMod *                          // 一正一反
         (w - i + 1) % kMod *                               // 横方向
         (h - j + 1) % kMod;                                // 竖方向
}
 
int main() {
  pre();
  for (cin >> t; t; t--) {
    cin >> n >> w >> h >> d;
    // BYD 的，没有特判调了半小时，我 /* */
    if (n == 1) {
      cout << (w + 1) * (h + 1) << '\n';
      continue;
    }
    ans = 0;
    for (LL i = 0; i <= w; i++) {
      for (LL j = 0; j <= h; j++) {
        if (!i && !j) {
          continue;
        }
        ans = (ans + fuck(i, j)) % kMod;
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

树数树

有 $n$ 个结点的树，现在求一个最长的序列 $a$，满足：

• $\forall i\in (1,m]$，$a_i$ 为 $a_{i-1}$ 的祖先或 $a_{i-1}$ 为 $a_i$ 的祖先；
• $\forall 1\le i<j\le m$，$a_i\ne a_j$。

$T$ 组数据。

---

不会写，只判断了树为链或菊花的情况，获得 $30$ 分，赛后发现没有特判完全二叉树的形状，本来能拿 $40$ 分。本体正解合并堆（左偏树），虽然好渴鹅学过，但是没有发现！你干嘛——哈哈哎哟~

序列

对于数 $S$，它的数位和为 $10$ 的字段被称作 se 序列，如果它的被一个数位都至少在一个 se 序列中，则称 $S$ 是 II 数。给定 $n$ 和 $b_i$ $(i\in [0,10))$，令 $a_i=\frac{b_i}{\sum _{j=0}^9{b}_j}$（满足 $\sum _{i=0}^9{a}_i=1$），随机生成一个 $[0,10^n)$ 范围内的数，每一位上生成数字 $i$ 的概率为 $a_i$，求这个数为 II 数的概率，答案对 $10^9+7$ 取模。

---

不会写，对于 $n=1$ 的情况特判并输出 $0$，在 widwolf 上面理所应当地获得了 $5$ 分的好成绩，但是在 lemon 上面没有分，老师说题面改了（具体的可以查看 2024.10.21 星期一），不知道最后在 linux 上面能够获得多少分，反正都一样。

总结

• 排名：$4$；
• 比赛分数：$235/400$；
• 情况：相比 2024.10.20 模拟赛，还可以；
• 问题：突然不会左偏树的应用了。