这两年，技术研究得越来越多，但算法基本是没学了
让我本就不强的算法能力更是雪上加霜
于是我就打算趁着暑假的时间，每天做一道算法题
也不是为了比赛之类的，只是觉得现在确实缺算法方面的能力
顺便也当练练C++了，我C++熟练度也不够
需要写在前面的是，我的代码会有很多封装，这样性能肯定不是最佳的
而且因为每天要干的事情也是挺多的，所以文章不会讲得很细，就当是个过程记录吧
为了简化文章结构，做个合订本
<0x01> 马的遍历
题目描述
有一个 $n \times m$ 的棋盘，在某个点 $(x, y)$ 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。
输入格式
输入只有一行四个整数，分别为 $n, m, x, y$。
输出格式
一个 $n \times m$ 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 $-1$）。
样例
样例输入
3 3 1 1
样例输出
0 3 2
3 -1 1
2 1 4
数据规模与约定
对于全部的测试点，保证 $1 \leq x \leq n \leq 400$，$1 \leq y \leq m \leq 400$。
分析
这个题目是一道搜索相关的题目
搜索的话，基本上就是DFS深度优先和BFS广度优先
本题需要计算马到棋盘的每一格最少需要走几步
使用DFS的话马容易一条路走到黑，虽然也是能解决问题的
而选择BFS的话，相当于同时放出好几匹马，更快得出最少步数
因为走不到的地方要标-1，所以地图初始化所有标记为-1
代码
#include <iostream>
#include <queue>
#include <vector>
// 为了更好的可读性，这里封装了一个Map类型
class Map
{
int n;
int m;
std::vector<std::vector<int>> mat;
public:
// 负责访问内容
int &At(int x, int y)
{
return mat[y][x];
}
// 运算符重载
std::vector<int> &operator[](int index)
{
return mat[index];
}
void ShowMap()
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
std::cout << mat[j][i] << " ";
}
std::cout << "\n";
}
}
// 复制构造函数，防止C++整花活
Map(const Map &c)
{
n = c.n;
m = c.m;
mat.resize(m);
for (int i = 0; i < m; i++)
{
mat[i].resize(n);
for (int j = 0; j < n; j++)
{
mat[i][j] = c.mat[i][j];
}
}
}
// 正常的构造函数
Map(int n, int m)
{
this->n = n;
this->m = m;
mat.resize(m);
for (int i = 0; i < m; i++)
{
mat[i].resize(n);
for (int j = 0; j < n; j++)
{
mat[i][j] = -1;
}
}
}
};
// BSF状态结构
class State
{
public:
int px;
int py;
int step = 0;
State(int px, int py, int step, Map map)
{
this->px = px;
this->py = py;
this->step = step;
}
};
// 马的移动
int dx[] = {-1, 1, 2, 2, -1, 1, -2, -2};
int dy[] = {-2, -2, -1, 1, 2, 2, -1, 1};
// 地图大小
int MaxX = 0;
int MaxY = 0;
// 出界判断
bool IsOutBorder(int x, int y)
{
if (x < 0 || y < 0)
{
return true;
}
if (x >= MaxX || y >= MaxY)
{
return true;
}
return false;
}
// BFS函数
void BFS(Map map, int x, int y)
{
// 使用std库中的队列来处理
std::queue<State> q;
// 初始化第一个状态
map.At(x, y) = 0;
q.push(State(x, y, 0, map));
// 进入BFS循环
while (!q.empty())
{
// 获取队列顶部对象
State temp = q.front();
q.pop();
// 生成下面可能的8个状态
for (int i = 0; i < 8; i++)
{
// 临时的位置
int tx = temp.px + dx[i];
int ty = temp.py + dy[i];
// 判断是否出界
if (IsOutBorder(tx, ty))
{
continue;
}
// 判断这个位置是否有马走过
if (map.At(tx, ty) != -1)
{
continue;
}
int ts = temp.step + 1;
// 向全局地图中添加标记
map.At(tx, ty) = ts;
// 向队列中添加新的状态
q.push(State(tx, ty, ts, map));
}
}
// 最后，输出答案
map.ShowMap();
}
// main入口，负责读取与启动
int main(int argc, char **argv)
{
int x, y;
std::cin >> MaxX >> MaxY >> x >> y;
BFS(Map(MaxX, MaxY), x - 1, y - 1);
return 0;
}
遇到的坑
主要也就是最后输出的时候矩阵反了
因为题目给的样例答案也是沿对角线对称的，一开始还真没发现
<0x02> 小A的糖果
题目描述
小 A 有 $n$ 个糖果盒，第 $i$ 个盒中有 $a_i$ 颗糖果。 小 A 每次可以从其中一盒糖果中吃掉一颗，他想知道，要让任意两个相邻的盒子中糖的个数之和都不大于 $x$，至少得吃掉几颗糖。
输入格式
输入的第一行是两个用空格隔开的整数，代表糖果盒的个数 $n$ 和给定的参数 $x$。 第二行有 $n$ 个用空格隔开的整数，第 $i$ 个整数代表第 $i$ 盒糖的糖果个数 $a_i$。
输出格式
输出一行一个整数，代表最少要吃掉的糖果的数量。
样例 #1
样例输入 #1
3 3
2 2 2
样例输出 #1
1
样例 #2
样例输入 #2
6 1
1 6 1 2 0 4
样例输出 #2
11
样例 #3
样例输入 #3
5 9
3 1 4 1 5
样例输出 #3
0
提示
样例输入输出 1 解释
吃掉第 2 盒中的一个糖果即可。
样例输入输出 2 解释
第 2 盒糖吃掉 $6$ 颗，第 4 盒吃掉 $2$ 颗，第 6 盒吃掉 $3$ 颗。
数据规模与约定
- 对于 $30%$ 的数据，保证 $n \leq 20$，$a_i, x \leq 100$。
- 对于 $70%$ 的数据，保证 $n \leq 10^3$，$a_i, x \leq 10^5$。
- 对于 $100%$ 的数据，保证 $2 \leq n \leq 10^5$，$0 \leq a_i, x \leq 10^9$。
分析
这是来自贪心题单的题，那么就是用贪心算法
怎么贪心呢
因为每次考虑的都是相邻的两个盒子，而且要用贪心
所以应该每次就只用考虑这两个盒子就可以了
每次计算中，只有第二个盒子会参与下一次的计算
既然是要算吃得最少的数目，那么应该要先吃第二个盒子的糖
这样就可以保证每个相邻的盒子中的糖满足条件且吃的糖的数量是最少的
代码
#include <iostream>
#include <vector>
int main()
{
// 读入
int n;
int x;
std::cin >> n >> x;
std::vector<int> list;
list.resize(n);
for (int i = 0; i < n; i++)
{
std::cin >> list[i];
}
// 解题
size_t ans = 0;
for (int i = 0; i < n - 1; i++)
{
// 按前面分析的思路解题
int temp = list[i] + list[i + 1];
if (temp > x)
{
// 计算满足条件要吃几颗
int d = temp - x;
ans += d;
// 如果第二个盒子糖果不足
if (list[i + 1] < d)
{
list[i] -= d - list[i + 1];
list[i + 1] = 0;
}
// 否则就直接减去
else
{
list[i + 1] -= d;
}
}
}
std::cout << ans;
return 0;
}
遇到的坑
经典最后答案爆数值范围了
最开始ans是int类型，然后提交上去发现有两个数据点过不了
下载下来一看输出就明白了，答案超21亿了
于是把int改成size_t这样就过了
(size_t在64位系统中是unsigned long long)
<0x03> A-B 数对
题目描述
给出一串正整数数列以及一个正整数 $C$，要求计算出所有满足 $A - B = C$ 的数对的个数（不同位置的数字一样的数对算不同的数对）。
输入格式
输入共两行。 第一行，两个正整数 $N,C$。 第二行，$N$ 个正整数，作为要求处理的那串数。
输出格式
一行，表示该串正整数中包含的满足 $A - B = C$ 的数对的个数。
样例
样例输入
4 1
1 1 2 3
样例输出
3
数据规模与约定
对于 $75%$ 的数据，$1 \leq N \leq 2000$。 对于 $100%$ 的数据，$1 \leq N \leq 2 \times 10^5$，$0 \leq a_i <2^{30}$，$1 \leq C < 2^{30}$。 2017/4/29 新添数据两组
分析
我的思路有点抽象，这道题是在二分的题单里的
因为对于已知B的情况，则A=B+C，这个A是固定的
本来我是打算对输入数列排序，然后求连续的B有几个
通过二分求出A的位置上下界，然后上下界相减求出A有几个
两个数字相乘加入到总的结果中，如此反复，最后求出答案
然后我就想，既然这样，为什么不在输入时维护一个数组，保存某数有几个
这种数据结构更进一步不就是哈希表嘛
于是这个题就很简单了
通过哈希表，建立键值对(数, 数的个数)
然后就是每个B计算A=B+C，两个数的个数相乘即可
唯一的坏处是没练习怎么写二分
代码
#include <iostream>
#include <map>
int main()
{
// 读入
int n;
size_t c;
std::cin >> n >> c;
std::map<size_t, int> numInfo;
// 处理
for (int i = 0; i < n; i++)
{
int t;
std::cin >> t;
numInfo[t]++;
}
// 解题
size_t ans = 0;
for (auto &it : numInfo)
{
size_t temp = c + it.first;
if (numInfo.find(temp) != numInfo.end())
{
// 强转保平安
ans += (size_t)numInfo[temp] * (size_t)it.second;
}
}
std::cout << ans;
}
遇到的坑
又是经典答案爆int范围了，但这里是在最后的乘法
两个int相乘返回的也是int，如果乘出来的值超过范围，也是会爆的
所以int强转size_t解决
<0x04> 数楼梯
偶然发现居然有道很久之前写的题没有AC，那就写这题了
洛谷的P1255
题目描述
楼梯有 $N$ 阶，上楼可以一步上一阶，也可以一步上二阶。
编一个程序，计算共有多少种不同的走法。
输入格式
一个数字，楼梯数。
输出格式
输出走的方式总数。
样例
样例输入
4
样例输出
5
数据规模与约定
- 对于 $60%$ 的数据，$N \leq 50$；
- 对于 $100%$ 的数据，$1 \le N \leq 5000$。
分析
思路应该是不难的
现在有4层楼梯，每次上一层或者两层
那先走个一层，这样还有3层楼梯
3层也能上一层或者两层，那这次上两层…
如此类推，我们可以得到一个决策树
4
├── 3
| ├── 2
| | ├── 1 ── 0
| | └── 0
| └── 1 ── 0
└── 2
├── 1 ── 0
└── 0
我们可以发现存在一些相同的子树
这些相同的子树带来的走法是一样的
所以要求4层楼梯有几种走法，可以先求3层有几种，2层有几种…
求到最后就是只有1层楼梯和2层楼梯有几种走法，这两种情况的答案是显然的
更进一步，我们可以得到一个递推式：$f(n) = f(n-1) + f(n-2), f(1) = 1, f(2) = 2$
对于这样的递推式，一般可以用递归的方式来解决
因为$f(n)$的值仅与$n$有关，所以对于每次求值，没必要完整计算一遍整个递推式
我们可以用一个list去暂存我们已经计算好的值
在计算新的值的过程中，如果发现有些值已经计算过了，直接用就可以
这样可以大大提高运行速度
代码
#include <iostream>
#include <vector>
// 数据量会非常大，所以要有高精度计算
class BigInteger
{
public:
BigInteger() : digits(1, 0)
{
}
BigInteger(const std::string &number)
{
for (int i = number.size() - 1; i >= 0; --i)
{
if (isdigit(number[i]))
{
digits.push_back(number[i] - '0');
}
}
}
// 有加法就够了
BigInteger operator+(const BigInteger &other) const
{
BigInteger result;
result.digits.clear();
int carry = 0;
size_t maxSize = std::max(digits.size(), other.digits.size());
for (size_t i = 0; i < maxSize || carry; ++i)
{
int sum = carry;
if (i < digits.size())
sum += digits[i];
if (i < other.digits.size())
sum += other.digits[i];
result.digits.push_back(sum % 10);
carry = sum / 10;
}
return result;
}
// 重载输出流
friend std::ostream &operator<<(std::ostream &os, const BigInteger &number)
{
for (int i = number.digits.size() - 1; i >= 0; --i)
{
os << number.digits[i];
}
return os;
}
// 判零用
bool IsZero()
{
if (digits.size() == 1)
{
return true;
}
return false;
}
private:
std::vector<int> digits;
};
// 初始化全局缓存的答案
BigInteger ans[5001] = {BigInteger()};
// 解题
BigInteger Step(int n)
{
// 边界条件
if (n == 1)
{
return BigInteger("1");
}
if (n == 2)
{
return BigInteger("2");
}
// 已经计算出来的就直接返回
if (!ans[n].IsZero())
{
return ans[n];
}
// 递归计算
return Step(n - 1) + Step(n - 2);
}
int main()
{
// 打表计算所有的答案
for (int i = 1; i < 5001; i++)
{
ans[i] = Step(i);
}
// 读入
int n;
std::cin >> n;
// 直接就能输出了
std::cout << ans[n];
return 0;
}
遇到的坑
本来以为是没啥问题的题，很快就写出了算法
然后跑评测，能过一半的数据
我就纳闷啊，把输入输出下载下来一看，输入到没啥，输出倒是老长一串数字
那这数字size_t都扛不住，要上高精度计算了
所以这道题看似考递推递归，实际上考的是高精度计算
然后本来想逃课用C#的BigIntager的，但不知道为什么，洛谷的评测机上面没有BigIntager这个类
所以最后就写了个高精度计算，也就用到个加法，问题不大