#暴力 #深度优先搜索 #质数
> 警告，本篇题解十分暴力，请正解党理性观看。
## 试题 A : 平方序列
兄弟们，炒鸡大暴力能过！
想不到正解，于是我们直接双重循环。为了不会死循环，我们加一个小小的优化：如果 $y^2-x^2>x^2-2019^2$，也就是 $y$ 已经很大了，再枚举已经没有意义的时候时，我们就直接 `break` 掉第二层循环。
```cpp
#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 背包枚举所有的质数，倒着遍历转移，从 $dp_{j-i}$ 转移至 $dp_{j}$。千万要注意边界处理和 `long long ` ！
```cpp
#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，往四个方向拓展。注意标记数组的清空。
```cpp
#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$。
```cpp
#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$。
```cpp
#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$ 代的，那么在允许的情况下可以尝试一下暴力哟。