P8690 填空问题

警告，本篇题解十分暴力，请正解党理性观看。

试题 A : 平方序列

兄弟们，炒鸡大暴力能过！

想不到正解，于是我们直接双重循环。为了不会死循环，我们加一个小小的优化：如果 $y^{2} - x^{2} > x^{2} - 201 9^{2}$ ，也就是 $y$ 已经很大了，再枚举已经没有意义的时候时，我们就直接 break 掉第二层循环。

#include <iostream>
 
using namespace std;
 
int main() {
  for (int i = 2020; ; ++i) {  // 枚举x
    for (int j = i + 1; ; ++j) {  // 枚举y
      if (i * i - 2019 * 2019 == j * j - i * i) {  // 如果搜到了解
        cout << i + j << '\n';
        return 0;
      }
      if (i * i - 2019 * 2019 < j * j - i * i) {  // 如果不用搜了
        break;
      }
    }
  }
  return 0;
}

我的 $12$ 代 i9 开 O2 最快 $0$ 毫秒！！！

试题 B : 质数拆分

秉承着不暴力不快活的原则，干脆懒得写质数筛了，枚举所有的数，然后用 isPrime 函数判断是否是质数，加入 vector。然后直接 01 背包枚举所有的质数，倒着遍历转移，从 $d p_{j - i}$ 转移至 $d p_{j}$ 。千万要注意边界处理和 long long ！

#include <iostream>
#include <vector>
 
using namespace std;
using ll = long long;
 
ll dp[2020];
vector<ll> v;
 
bool isPrime(ll x) {  // 判断x是否是质数
  for (ll i = 2; i * i <= x; ++i) {
    if (!(x % i)) {
      return 0;
    }
  }
  return 1;
}
 
int main() {
  for (ll i = 2; i <= 2019; ++i) {  // 「暴力筛」
    if (isPrime(i)) {
      v.push_back(i);
    }
  }
  dp[0] = 1;
  for (ll i : v) {  // 01背包
    for (ll j = 2019; j >= i; --j) {
      dp[j] += dp[j - i];
    }
  }
  cout << dp[2019] << '\n';
  return 0;
}

开 O2 最快 $1$ 毫秒！

试题 C : 拼接

暴力 dfs，直接将所有 $x = y$ 的点全部扫一遍，跑 dfs，往四个方向拓展。注意标记数组的清空。

#include <iostream>
 
using namespace std;
 
const int kMaxN = 8, kD[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
 
int ans;
bool f[kMaxN][kMaxN];
 
void dfs(int x, int y) {
  if (!x || y == 7) {  // 满足条件
    return ++ans, void();
  }
  for (auto i : kD) {  // 拓展
    int nx = x + i[0], ny = y + i[1];
    if (nx < 0 || nx > 7 || ny <= nx || ny > 7 || f[nx][ny]) {  // 判断是否满足条件
      continue;
    }
    f[nx][ny] = 1, dfs(nx, ny), f[nx][ny] = 0;  // 标记、搜索并回溯
  }
}
 
int main() {
  for (int i = 0; i <= 7; ++i) { 
    fill(f[0], f[0] + kMaxN * kMaxN, 0);  // 清空标记数组
    f[i][i] = 1, dfs(i, i);  // 进行搜索
  }
  cout << ans << '\n';
  return 0;
}

试题 D: 求值

又到了喜闻乐见的暴力时间！

我们直接暴力穷举每一个数，然后在枚举所有小于等于这个数的数，算出一共有多少个因数后再判断是否等于 $100$ 。

#include <iostream>
 
using namespace std;
 
int main() {
  for (int i = 1; ; ++i) {  // 没有边界的枚举
    int s = 0;
    for (int j = 1; j <= i; ++j) {  // 算出一共有多少个因数
      s += i % j == 0;
    }
    if (s == 100) { 
      cout << i << '\n';
      return 0;
    }
  }
  return 0;
}

吸氧 $1420$ 毫秒，有点失望，考场中的低代 CPU 慎用。

试题 E: 路径计数

暴力 dfs，将边给标成 $0 - 5$ ，然后跑 dfs。注意步数最少是 $4$ 。

#include <iostream>
 
using namespace std;
 
const int kD[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
 
int ans;
bool f[8][8];
 
void dfs(int x, int y, int s) {
  if (!x && !y && s >= 4) {  // 如果回到了起点并且步数不小于4
    return ++ans, void();
  }
  for (auto i : kD) {
    int nx = x + i[0], ny = y + i[1];
    if (s < 12 && nx >= 0 && nx <= 5 && ny >= 0 && ny <= 5 && !f[nx][ny]) {  // 判断是否满足条件
      f[nx][ny] = 1, dfs(nx, ny, s + 1), f[nx][ny] = 0;  // 标记、搜索并回溯
    }
  }
}
 
int main() {
  dfs(0, 0, 0);
  cout << ans << '\n';
  return 0;
}

就这样，本篇题解就结束了。在比赛中，如果大家也遇到了类似的题目，一定要 Ctrl+Shift+Esc 打开任务管理器，查看 CPU 的情况。如果 CPU 是 $10 - 13$ 代的，那么在允许的情况下可以尝试一下暴力哟。

Haokee Note

Explorer