【思路】由于完全平方公式\(a^2 - b^2 = (a+b)(a-b)=c\)，假设 $ d $ 可以拆分成这样的平方差，\(c + b ^2 = a ^2\)。
假设\(a + b\) 都大于 \(c\) 了，而\(a - b\)又不可能小于1，所以\(a\)和\(b\)不能大于\(c\)。这样我们就可以缩小遍历的范围了。
答案：78
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int sum = 0;
for (int i = 1; i <= 2021; i++) {
for (int j = 0; j <= i; j++) {
int k = i + j * j;
int sq = sqrt(k);
if (sq * sq == k) {
sum++;
break;
}
}
}
cout << sum << endl;
return 0;
}
问题描述(哈夫曼编码)
【思路】本题考察的是哈夫曼编码，要使得最终编码的长度最少，那么就尽可能地使数量最多的字母长度最短，越靠近树的根节点数值越大，然后每个子分支的边从左到右分别为0和1，从根节点依次数下来就是某个字母对应的编码，再求出所有编码所用的字母数。
答案：219
01最短路问题
问题描述
小蓝住在 LQ 城，今天他要去小乔家玩。
LQ 城可以看成是一个 n 行 m 列的一个方格图。
小蓝家住在第 1 行第 1 列，小乔家住在第 n 行第 m 列。
小蓝可以在方格图内走，他不愿意走到方格图外。
城市中有的地方是风景优美的公园，有的地方是熙熙攘攘的街道。小蓝很喜欢公园，不喜欢街道。他把方格图中的每一格都标注了一个属性，或者是喜欢的公园，标为1，或者是不喜欢的街道标为2。小蓝和小乔住的地方都标为了1。
小蓝每次只能从一个方格走到同一行或同一列的相邻方格。他想找到一条路径，使得不连续走两次标为 2 的街道，请问在此前提下他最少要经过几次街道？
输入格式
输入的第一行包含两个整数 n, m，用一个空格分隔。
接下来 n 行，每行一个长度为 m 第数字串，表示城市的标注。
输出格式
输出一行包含一个整数，表示答案。如果没有满足条件的方案，输出 -1。
样例输入
3 4
1121
1211
2211
样例输出
2
样例输入
3 4
1122
1221
2211
样例输出
-1
样例输入
5 6
112121
122221
221212
211122
111121
样例输出
5
评测用例规模与约定
对于 50% 的评测用例，2 <= n, m <= 20。
对于所有评测用例，2 <= n, m <= 300。
【思路】题目的意思是走到终点的之前不能连续经过两个\(2\)，而且最终要统计经过的\(2\)的个数。
2-->2 inf
2-->1 0
1-->1 0
1-->2 1
可以发现这里面只有0和1两种距离，可以采用双端队列\(BFS\)来写，也可采用深搜剪枝。
\(01BFS\)，双端队列做法
include <iostream>
#include <cstring>
#include <deque>
#define x first
#define y second
using namespace std;
using T = pair<int, int>;
const int N = 305, M = N * N;
const int inf = 0x3f3f3f3f;
int res = inf;
int g[N][N];
bool st[N][N];
int dist[N][N];
int n, m;
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, 1, -1};
int bfs() {
memset(dist, 0x3f, sizeof dist);
deque<T> q;
q.push_back({0, 0});
dist[0][0] = 0;
while (q.size()) {
auto t = q.front();
q.pop_front();
for (int i = 0; i < 4; i++) {
int nx = t.x + dx[i], ny = t.y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m)
continue;
if (g[t.x][t.y] == 2 && g[nx][ny] == 2)
continue;
if (g[nx][ny] == 1 && dist[nx][ny] > dist[t.x][t.y]) {
dist[nx][ny] = dist[t.x][t.y] + 0;
q.push_front({nx, ny});
//cout << " 下一个为1" << endl;
}
if (g[nx][ny] == 2 && dist[nx][ny] > dist[t.x][t.y] + 1) { // 只有距离变小才能入队
dist[nx][ny] = dist[t.x][t.y] + 1;
q.push_back({nx, ny});
//cout << " 下一个为2" << endl;
}
}
}
if (dist[n - 1][m - 1] == 0x3f3f3f3f)
return -1;
return dist[n - 1][m - 1];
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (int j = 0; j < m; j++)
g[i][j] = s[j] - '0';
}
cout << bfs();
return 0;
}
\(dfs\)深搜
#include <iostream>
#include <cstring>
#include <deque>
#define x first
#define y second
using namespace std;
using T = pair<int, int>;
const int N = 305, M = N * N;
const int inf = 0x3f3f3f3f;
//int res = inf;
int g[N][N];
bool st[N][N];
int dist[N][N];
int n, m;
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, 1, -1};
void dfs(int x, int y, int cnt) { // 经过 2 的个数
if (x == n - 1 && y == m - 1) {
res = min(res, cnt);
return;
}
st[x][y] = true;
// 从x y向四个方向扩展
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m)
continue;
if (st[nx][ny])
continue;
if (g[x][y] == 2 && g[nx][ny] == 2)
continue; // 不能走连续的2
dfs(nx, ny, g[nx][ny] == 2 ? cnt + 1 : cnt);
}
st[x][y] = false;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (int j = 0; j < m; j++)
g[i][j] = s[j] - '0';
}
dfs(0, 0, 0);
if (res == inf)
puts("-1");
else
cout << res << endl;
cout << bfs();
return 0;
}