信息学奥赛一本通——基础篇¶
全部题解：https://blog.csdn.net/u011815404/article/details/79324003
评测系统最好使用C语言中的scanf，因为关了同步也没用。
第一部分 C++语言¶
第一章 C++语言入门¶
第五节 数据输入和输出¶
getchar()函数接收从键盘输入的单个字符数据，通常把输入的字符赋予一个字符变量。只接受单个字符，输入的数字也按字符处理。输入多于一个字符，只接受第一个字符。
char ch = getchar();
第五章 数组¶
memset函数包含在头文件<string.h>内。
第三节 字符类型和字符数组¶
scanf以空格作为分隔读取，会自动跳过多余的空格，比如字符串let us go，如果写
char ch[200];
scanf("%s", ch);
则只读取let。如果想读取一整行，那么就使用函数gets()，相当于C++里面的getline()函数。
一般使用fegts()来进行替换，需要传入三个参数：
char *fgets(char *str, int n, FILE *stream);
一般时候的用法是：
char ch[200];
fgets(ch, 200, stdin);
但是注意，在OJ里面最好少使用fgets()，比如1130题目使用fgets会报错。
另外，fgets()会把空格应读入。
**在OJ里面gets()是首选。
相应的还有puts()函数，会自动输出一个空格。下面语句等价。gets()和puts()都在<stdio.h>里。
printf("%s\n", ch);
puts(ch);
比如例5.16，去掉多余的空格，首尾不存在空格。比如输入是：
Hello world. This is c language.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char ch[200];
int main()
{
while (scanf("%s", ch) != EOF) { //这里还可以写成scanf("%s", ch) == 1
printf("%s ", ch);
}
return 0;
}
字符串处理函数
第六章 函数¶
第二节 递归算法¶
第二部分¶
第二章 数据排序¶
第三章 递推算法¶
例3.3和《算法问题实战策略》的第八章的“动态规划”的P175，计算铺设方法的个数TILING2是一致的。
当n=1时，只有一种情况，当n=2的时候，存在两种排列方式，当n=3的时候，发现取决于第一块的摆放：如果第一块竖放，则相当于解决如何摆放剩余两块的情况，如果第一个横放，那么变成最后一块如何摆放，于是得出结论：x_n=x_{n-1}+x_{n-2}。其实就是斐波那契数列。
这道题的扩展就是《算法问题实战策略》的P180 非对称铺设 ASYMTILING。
非对称铺设只需要考虑奇数和偶数的情况，然后做相应的处理。
例3.4 昆虫繁殖 这道题目还是很典型的，需要正确计算卵和成虫，另外，题目问的是z月后，问的是第z+1个月的数量，注意问法。另外，这道题目明确指出2个月后长成成虫，其实这个也可以变成一个变量，修改的只是递推关系式里面的计算成虫数量的部分。还有一点是数据类型是long long
第四章 递归算法¶
第五章 搜索与回溯算法¶
《算法竞赛入门经典》7.4节也提到了素数环。邝斌的搜索专题。
回溯框架一：
void search(int k)
{
for (int i = 1; i <= n; ++i) {
if (/* 满足搜索条件*/ ) {
//保存结果
if (/* 到达终点 */) //输出结果
else search(k + 1);
/* 恢复保存结果之前的状态 */
}
}
}
典型应用：
- UVA-524 素数环（输出超级严格）
- 一本通-1317：【例5.2】组合的输出（也可以参考《算法竞赛进阶指南》的递归实现）
- 一本通-1318：【例5.3】自然数的拆分（可以和POJ 2229结合起来）
- 一本通-1213：八皇后问题
- 一本通-1220：单词接龙（比较难做的搜索题，也是洛谷-P1019）
- 一本通-1221：分成互质组（思路巧妙的DFS）
**例5.6**设有A、B、C、D、E五人从事J1、J2、J3、J4、J5五项工作，每人只能从事一项，他们的效益如图5-3所示。
解析：这道问题就是抽象版的八皇后，每个人选择某一个位置，五个人的位置不能在同一行和同一列，验证可以加个计数器cnt，总的数量就是A_5^5=120种。
设输入的数据是人数n，接下来是一个5\times 5的矩阵，第i行的第j个数代表第i个人做第j份工作的收益。
Input
5
13 11 10 4 7
13 10 10 8 5
5 9 7 7 4
15 12 10 11 5
10 11 8 8 4
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <set>
#include <algorithm>
using namespace std;
int n;
vector<vector<int> > gird(15, vector<int>(15));
// int direction[8][2] = {{-2, 1}, {-1, 2}, {2, 1}, {1, 2}, {-1, -2}, {-2, -1}, {1, -2}, {2, -1}};
// int direction[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
int res = 0;
vector<int> d(10);
int cnt = 0;
bool canPlace(int row, int col)
{
for (int i = 0; i < row; ++i) {
if (d[i] == col) return false;
}
return true;
}
void DFS(int row)
{
for (int col = 0; col < n; ++col) {
if (canPlace(row, col)) {
d[row] = col;
if (row == n - 1) {
++cnt;
int sum = 0;
for (int i = 0; i < n; ++i) sum += gird[i][d[i]];
res = max(res, sum);
}
else DFS(row + 1);
}
}
}
int main()
{
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> gird[i][j];
}
}
DFS(0);
cout << res << endl;
cout << "count = " << cnt << endl;
return 0;
}
例5.7选书 学校放寒假时，信息学竞赛辅导老师有A、B、C、D、E五本书，要分给参加培训的张、王、刘、孙、李五位同学，每人只能选一本书。老师事先让每个人将自己喜欢的书填写在如下的表格中。然后根据他们填写的表来分配书本，希望设计一个程序帮助老师求出所有可能的分配方案，使每个学生都满意。
仍然是抽象版的八皇后问题。
输入数据第一行是n代表人数，接下来n行，对应表中是y的为1，其他为0.
5
0 0 1 1 0
1 1 0 0 1
0 1 1 0 0
0 0 0 1 0
0 1 0 0 1
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <set>
#include <algorithm>
using namespace std;
int n;
vector<vector<int> > gird(15, vector<int>(15));
// int direction[8][2] = {{-2, 1}, {-1, 2}, {2, 1}, {1, 2}, {-1, -2}, {-2, -1}, {1, -2}, {2, -1}};
// int direction[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
int res = 0;
vector<int> d(10);
bool canPlace(int row, int col)
{
for (int i = 0; i < row; ++i) {
if (d[i] == col) return false;
}
return true;
}
void DFS(int row)
{
for (int col = 0; col < n; ++col) {
if (gird[row][col] && canPlace(row, col)) {
d[row] = col;
if (row == n - 1) {
++res;
for (int i = 0; i < n; ++i) {
cout << (i + 1) << " : " << (char)('A' + d[i]) << endl;
}
}
else DFS(row + 1);
}
}
}
int main()
{
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> gird[i][j];
}
}
DFS(0);
cout << "total = " << res << endl;
return 0;
}
发现结果输出为1，这个很好验证，因为第四个同学只有一种选择，依次推导发现只有一种选择。
1 : C
2 : A
3 : B
4 : D
5 : E
total = 1
第六章 贪心算法¶
详细见《基础算法——贪心》的总结，包含基础贪心和区间贪心的方法。
第七章 分治算法¶
第八章 广度优先算法¶
例8.1，假设输入的形式是，第一行为边的条数n，接下来n行每行两个字符，代表相连的两个点。
12
A B
A C
A D
A F
C D
C E
B F
F H
D G
G E
E H
F H
#include <bits/stdc++.h>
using namespace std;
int n = 8;
int target = 7;
vector<bool> used(8, false);
vector<int> pre(8, -1);
vector<vector<int> > grid(8, vector<int>(8));
void printPath(int pos)
{
if (pos == -1) return;
printPath(pre[pos]);
if (pre[pos] != -1) cout << " -> " << (char)('A' + pos);
else cout << (char)('A' + pos);
}
void BFS()
{
queue<int> q;
q.push(0);
used[0] = true;
while (!q.empty()) {
int from = q.front(); q.pop();
if (from == 7) {
printPath(from);
cout << endl;
return;
}
for (int i = 0; i < n; ++i) {
if (grid[from][i] && !used[i]) {
q.push(i);
used[i] = true;
pre[i] = from;
}
}
}
}
int main()
{
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int edgeNum; cin >> edgeNum;
char startPoint, endPoint;
for (int i = 0; i < edgeNum; ++i) {
cin >> startPoint >> endPoint;
grid[startPoint - 'A'][endPoint - 'A'] = 1;
grid[endPoint - 'A'][startPoint - 'A'] = 1;
}
BFS();
return 0;
}
A -> F -> H
第九章 动态规划¶
一般来说，采用动态规划解决的问题，必须满足最优化原理和无后效性原则。
最优化原理
通俗理解是：子问题的局部最优将导致整个问题的最优解，即问题具有最优子结构。
无后效性原则
某阶段的状态一旦确定，则此后过程的演变不再受此前各种状态及决策的影响。