2024.10.23 模拟赛

题目：2024.10.23 题目

GCD

给定 $a,b$，求 $\sum _{i=a}^{b}f(i)$，其中 $f(i)$ 为 $\gcd (x:x|i\mathrm{and}x\ne 1)$。

---

手玩一下不难发现，对于一个数 $x$，如果他是质数，那么 $f(x)=x$（不是废话么）。观察小样例，可以猜出若 $x$ 为合数则 $f(x)=1$。那么这件事究竟成不成立呢？

把质数筛的代码打出来，跑大样例就可以发现我们程序输出的答案比标准代码输出的答案要小。这又是为何呢？我们尝试找出范例，终于找到了数 $9=3\times 3$。程序认为既然 $9$ 是质数，那么 $f(9)$ 也就应该为 $1$，但是实际上 $f(9)=3$，这是因为 $9$ 是质数 $3$ 的 $2$ 次幂。

因此我们又得出了一个结论，对于一个数 $x$，如果它不是质数且它是一个质数的二次幂，则 $f(x)$ 等于哪个质数，否则 $f(x)=1$。时间复杂度 $\mathcal{O}(b)$。

#include <fstream>
#include <vector>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 1e7 + 5;
 
ifstream cin("gcd.in");
ofstream cout("gcd.out");
 
LL g[kMaxN], a, b, ans;
bool f[kMaxN];
vector<LL> p;
 
void prime(LL n) {
  for (LL i = 2; i <= n; i++) {
    if (!f[i]) {
      p.push_back(i);
      g[i] = i;
    }
    for (LL j : p) {
      if (i * j > n) {
        break;
      }
      f[i * j] = 1;
      g[i * j] = i % j == 0 && g[i] != 1 ? j : 1;
      if (i % j == 0) {
        break;
      }
    }
  }
}
 
int main() {
  cin >> a >> b;
  prime(b);
  for (LL i = a; i <= b; i++) {
    ans += g[i];
  }
  cout << ans << '\n';
  return 0;
}

包含

若 $a\mathrm{and}b=b$，则称 $b\in a$，其中 $\mathrm{and}$ 表示按位与。给定 $n$ 个数，第 $i$ 个数为 $x_i$，组成可重集 $S=\{x_1,x_2,\cdots ,x_n\}$。又有 $m$ 个询问，每次询问给出 $y$，判断是否存在 $y\in x$ 且 $x\in S$。

---

在二进制上考虑，对于一个数 $x$，将 $x$ 的若干个二进制位 $1$ 给改成 $0$，所组成的 $y$，满足 $y\in x$。所以我们可以枚举将 $x$ 的哪些二进制位 $1$ 给改成 $0$，但是数量过于庞大，我们需要思考其它方式。

由于 $1\le x_i\le 10^6$，这代表着我们可以通过预处理处理出任意 $y$ 是否被任意的 $x_i$ 包含。将 $1$ 改成 $0$ 的数量过于庞大，但是询问的数很小，只有 $10^6$，因此我们可以认为假设两个数 $x_1,x_2$ 都可以经过修改变成 $y$，那么它们就可以合为一体。

详细的说，就是令 $f_i$ 表示为 $i$ 是否满足条件，如果此时 $f_i=1$，那么我们枚举 $i$ 的 $1$ 位，将其改为 $0$，假设更改后的数为 $j$，则标记 $f_j=1$。你肯定要问这不就只能删掉一个 $1$ 吗？但是我们的 $i$ 是倒序枚举的，这使一个数可以被去掉多次二进制位，因此题目解决成功。该算法的时间复杂度为 $\mathcal{O}(n{\log }_{2}v)$，其中 $v$ 为值域。

#include <fstream>
 
using namespace std;
 
const int kMaxN = 1e6 + 5;
 
ifstream cin("include.in");
ofstream cout("include.out");
 
int f[kMaxN], n, m, x;
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  while (n--) {
    cin >> x;
    f[x] = 1;
  }
  for (int i = 1e6; i >= 1; i--) {
    if (f[i]) {
      for (int j = 0; (1 << j) <= i; j++) {
        if (i & (1 << j)) {
          f[i - (1 << j)] = 1;
        }
      }
    }
  }
  while (m--) {
    cin >> x;
    cout << (f[x] ? "yes" : "no") << '\n';
  }
  return 0;
}

前缀

有一个仅包含小写字母的字符串 $s$，现在牛牛将 $s$ 变成了一个无限循环串。对于字符串 $t$，若某字符串的至少一个子序列为 $t$。则称它是一个「含 $t$ 序列串」。对于给定的 $t$，他想要知道 $s$ 的一个最短前缀满足它是一个「含 $t$ 序列串」，它的长度有多长？答案对 $998244353$ 取模。

---

采用暴力。对于不包含数字的串，我们暴力进行匹配，最坏时间复杂度达到了 $\mathcal{O}(n\times |s|\times |t|)$，但是通过了 $30$ 分。不可以总司令没有分。

移动

有 $n$ 道闸门，牛牛初始在第 $1$ 道闸门，此时时刻为 $1$。有 $m$ 条信息，第 $i$ 条信息为 $(a_i,b_i,c_i)$ 的格式，表示第 $a_i$ 道闸门会在 $[b_i,c_i]$ 的时刻内闭合，此时牛牛不能在这道闸门下。求到达第 $n$ 道闸门的最小时间，无解输出 $-1$。

---

采用贪心，让牛牛只能等待或前进。时间复杂度 $\mathcal{O}(n+m)$。这种很明显就可以 Hack 掉的错误解法成功拿到了 $85$ 分。

总结

• 排名：$4$；
• 比赛分数：$315/400$；
• 情况：相比 2024.10.21 模拟赛，不错；
• 问题：问题不大。