2024/10/23 模拟赛总结

\(100+55+30+0=185\)，T4 没有 -1 唐完了

#A. GCD

把 \(1\sim 50\) 的 \(f\) 打表输出，可以找到规律：若 \(x\) 为 \(p^k(k\in\mathbb{N}^+,p\in\mathcal{P})\)，则 \(f(x)=p\)，否则 \(f(x)=1\)

于是可以筛出所有质数并枚举指数

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 1e7 + 5;

LL a, b, ans, f[kMaxN], pr[kMaxN >> 1], tot;
bitset<kMaxN> vis;

int main() {
  freopen("gcd.in", "r", stdin), freopen("gcd.out", "w", stdout);
  vis[0] = vis[1] = 1;
  for (int i = 2; i < kMaxN; i++) {
    if (!vis[i]) {
      pr[++tot] = i;
    }
    for (int j = 1; j <= tot && i * pr[j] < kMaxN; j++) {
      vis[i * pr[j]] = 1;
      if (i % pr[j] == 0) {
        break;
      }
    }
  }
  fill(f, f + kMaxN, 1);
  for (LL i = 1; i <= tot; i++) {
    for (LL j = pr[i]; j < kMaxN; j *= pr[i]) {
      f[j] = pr[i];
    }
  }
  cin >> a >> b;
  for (int i = a; i <= b; i++) {
    ans += f[i];
  }
  cout << ans << '\n';
  return 0;
}

#B. 包含

一个简单的可行性 dp，赛时写个 01 trie 被卡到 \(55\) 了

倒序枚举每个数，其删掉任意一位后一定也可行，于是直接枚举那一位转移即可

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 1e6 + 5;

int n, m, x;
bitset<kMaxN> f;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  freopen("include.in", "r", stdin), freopen("include.out", "w", stdout);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> x, f[x] = 1;
  }
  for (int i = kMaxN - 1; i; i--) {
    if (f[i]) {
      for (int j = 0; j < 20; j++) {
        if (i & (1 << j)) {
          f[i - (1 << j)] = 1;
        }
      }
    }
  }
  for (; m; m--) {
    cin >> x, cout << (f[x] ? "yes" : "no") << '\n';
  }
  return 0;
}

#C. 前缀

不想写高精qwq

#D. 移动

自古 T4 出唐题，古有 原地立正 \(75\)，今有横冲直撞 \(90\) 分

对于 \(n \le 10\) 枚举下一个走哪里，\(O(3^n)\) DFS 即可

否则一直往前冲，如果前面有障碍则等它升起再走，否则原地不动，如果当前闸门降下也不管，就呆着，不输出 -1

#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 1e5 + 2;

int n, m, ans;
vector<pair<int, int>> f[kMaxN];
unordered_map<int, int> b[kMaxN];

void DFS(int x, int t) {
  if (ans) {
    return;
  }
  if (x > n) {
    ans = t;
    return;
  }
  if (b[x + 1][t + 1] == 0) {
    DFS(x + 1, t + 1);
  }
  if (b[x][t + 1] == 0) {
    DFS(x, t + 1);
  }
  if (x && b[x - 1][t + 1] == 0) {
    DFS(x - 1, t + 1);
  }
}
void Solve() {
  for (int i = 1, x, y, z; i <= m; i++) {
    cin >> x >> y >> z;
    for (int j = y; j <= z; j++) b[x][j] = y;
  }
  DFS(0, 0), cout << ans << '\n', exit(0);
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  freopen("move.in", "r", stdin), freopen("move.out", "w", stdout);
  cin >> n >> m;
  (n <= 10 && (Solve(), 0)), ans = 1;
  for (int i = 1, x, y, z; i <= m; i++) {
    cin >> x >> y >> z, f[x].push_back({y, z});
  }
  for (int i = 1; i <= n; i++, ans++) {
    for (auto [x, y] : f[i]) {
      if (ans < x) {
        break;
      } else if (ans > y) {
        continue;
      } else {
        ans = y + 1;
      }
    }
  }
  cout << ans << '\n';
  return 0;
}