暴力
“暴力”是指，不用任何策略就能够解决问题。比如问
1
+
2
+
⋯
+
100
1+2+\\dots+100
1+2+⋯+100 的值，for(int i=1;i<=100;i++ 就是暴力。但当我们需要解决更复杂的问题时，暴力往往会超时，就需要使用其他的算法了。
今天就来讲讲 CSP-J 考纲中的几种基本算法：（方括号内的是难度）
- 【3】贪心法
- 【3】递推法
- 【4】递归法
- 【4】二分法
- 【4】倍增法
今天讲简单的，先不讲倍增，下次一起讲分治。
贪心
“贪心”是一种基本的算法。它的核心是：在每一步选择中都采取 当前状态下 的最优解。但是，贪心能造成局部最优，不一定造成全局最优。一般情况下，贪心的局部最优解可以导致全局最优解。
什么时候要使用贪心？关键：当前选择不依赖后续选择，也不会被之前选择影响。
最优子结构
- 问题的最优解包含其子问题的最优解；
- 可以通过一系列局部最优选择构建局部最优解。
无后效性
- 作出选择后，不会回头重新考虑之前的决策；
- 过去的决策只影响当前装袋，不影响未来选择。
例题
P13158 [GCJ 2017 Qualification] Oversized Pancake Flipper
题目描述
去年，Infinite House of Pancakes 推出了一种新型煎饼。这种煎饼的一面（“开心面”）上有用巧克力豆做成的笑脸，另一面（“空白面”）则什么都没有。
你是当班的主厨。煎饼被排成一排在加热面上烹饪。为了进一步提升效率，餐厅最近给你配备了一个超大号煎饼翻转器，每次可以同时翻转恰好
K
K
K 个连续的煎饼。也就是说，在这
K
K
K 个煎饼的范围内，每个开心面朝上的煎饼会变为空白面朝上，反之亦然；煎饼的左右顺序不会改变。
你不能用翻转器翻转少于
K
K
K 个煎饼，即使是在煎饼排的两端（因为加热面两侧有凸起的边界）。例如，你可以翻转最左边的
K
K
K 个煎饼，但不能只翻转最左边的
K
−
1
K-1
K−1 个煎饼。
你的学徒厨师还在学习工作，他刚刚用老式的单煎饼翻转器翻转了一些单独的煎饼，然后带着翻转器跑去洗手间了，正好在顾客即将参观厨房之前。现在你只剩下超大号煎饼翻转器，你需要尽快使用它，使所有正在烹饪的煎饼都开心面朝上，这样顾客才能满意地离开。
给定当前煎饼的状态，计算至少需要使用多少次超大号煎饼翻转器，才能让所有煎饼都开心面朝上；或者说明无法做到这一点。
输入格式
输入的第一行包含测试用例的数量
T
T
T。接下来有
T
T
T 组测试用例。每组测试用例包含一行，包括一个字符串
S
S
S 和一个整数
K
K
K。
S
S
S 表示煎饼的排列：每个字符为 +（表示该煎饼初始为开心面朝上）或 -（表示该煎饼初始为空白面朝上）。
输出格式
对于每组测试用例，输出一行，格式为 Case #x: y，其中
x
x
x 是测试用例编号（从 1 开始），
y
y
y 是所需使用超大号煎饼翻转器的最小次数，或者如果无法做到则输出 IMPOSSIBLE。
输入 #1
3
—+-++- 3
+++++ 4
-+-+- 4
输出 #1
Case #1: 3
Case #2: 0
Case #3: IMPOSSIBLE
说明/提示
数据范围
-
1
≤
T
≤
100
1 \\leq T \\leq 100
1≤T≤100。 -
S
S
S 中每个字符均为 + 或 -。 -
2
≤
K
≤
S
2 \\leq K \\leq S
2≤K≤S 的长度。
例题解析
很明显这是一道贪心。
为什么呢？对于从左到右的每个煎饼，一旦我们决定是否翻转它所在的位置，这个决定就是最终的。
翻转第
i
i
i 个煎饼也不会影响已经处理过的左边部分，（让当前煎饼变成开心面）能导致局部最优。
思路
从左到右遍历，每遇到一个反面，就将他反转。反转时记录步数。最后扫一遍，如果还有反面的煎饼，说明不可能实现，输出 IMPOSSIBLE。
代码
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main() {
int T;
cin>>T;
for(int t=1;t<=T;t++) {
string s;
int K;
cin>>s>>K;
int n=s.length(),cnt=0;
vector<char> arr(s.begin(),s.end());
bool pos=true;
for(int i=0;i<n;i++) {
if(arr[i]=='-') {
if(i+K>n) {
pos=false;
break;
}
++cnt;
for(int j=i;j<i+K;j++)
arr[j]=='+'?arr[j]='-':arr[j]='+';
//反转
}
}
if(pos==false)
cout<<"Case #"<<t<<": IMPOSSIBLE\\n";
else {
bool all=true;
for(char c:arr) if(c=='-') {
all=false; break;
}
if(all) cout<<"Case #"<<t<<": "<<cnt<<endl;
else cout<<"Case #"<<t<<": IMPOSSIBLE\\n";
}
}
return 0;
}
//elseif123
递归
在学习递归之前，我常听到：
很多人都因为递归学不会而放弃了！
递归确实很重要，那我们详细讲一讲。其实不要把递归想得太复杂、太难，这是一个比较有趣的算法。在学习递归前，你需要先学会函数。
递归是指函数不断调用自己以解决复杂的问题。递归需要的两个部分：
-
递归出口（什么时候跳出递归）；
-
递归式（如何递归）。
先看入门例题。
例题
B2153 求阶乘的和
题目描述
给定正整数
n
n
n，求不大于
n
n
n 的正整数的阶乘的和（即求
1
!
+
2
!
+
3
!
+
⋯
+
n
!
1!+2!+3!+\\dots+n!
1!+2!+3!+⋯+n!），输出阶乘的和。
阶乘定义为
n
!
=
n
×
(
n
−
1
)
×
(
n
−
2
)
×
⋯
×
1
n!=n\\times (n-1)\\times (n-2)\\times \\cdots \\times 1
n!=n×(n−1)×(n−2)×⋯×1。例如，
5
!
=
5
×
4
×
3
×
2
×
1
=
120
5! = 5 \\times 4 \\times 3 \\times 2 \\times 1=120
5!=5×4×3×2×1=120。
输入格式
输入一行，包含一个正整数
n
(
1
<
n
<
12
)
n(1 < n < 12)
n(1<n<12)。
输出格式
输出一行，表示阶乘的和。
输入 #1
5
输出 #1
153
例题解析
思路
先看看怎么计算阶乘。阶乘是每一个教练都要讲的入门题。
观察
5
5
5 的阶乘：
5
×
4
×
3
×
2
×
1
5\\times 4\\times 3 \\times 2\\times 1
5×4×3×2×1。怎么拆分它使得我们能够运用递归的思路？经过观察，我们也发现
5
5
5 的阶乘为
5
×
4
!
5\\times 4!
5×4!。就是单拎出来第一个数，后面的数就是
(
n
−
1
)
(n-1)
(n−1) 的阶乘。这就是递归式了。
那么这个递归的出口是什么？当计算到
1
1
1 的时候，递归的出口就是返回
1
1
1，因为
1
!
=
1
1!=1
1!=1。
递归代码：
int jc(int x) {//计算 x 的阶乘
if(x==1) return 1;//递归出口
else
return x*jc(x–1);//递归式
}
最后再暴力地 for(int i=1;i<=n;i++) 将结果相加即可。
注意，对于这道题，更推荐暴力。因为 递归会调用栈空间，效率反而不如暴力。
代码
递归代码
#include<iostream>//本人不推荐使用万能头
using namespace std;
int jc(int x) {
if(x==1) return 1;
return x*jc(x–1);
}
int main() {
int n,ans=0;
cin>>n;
for(int i=1;i<=n;i++)
ans+=jc(i);
cout<<ans;
return 0;
}
暴力代码（AC记录）
#include<iostream>
using namespace std;
int n,ans=0;
int main() {
cin>>n;
for(int i=1;i<=n;i++) {
int jc=1;
for(int j=i;j>=1;j—)
jc*=j;
ans+=jc;
}
cout<<ans;
return 0;
}
此外斐波那契数列也是入门好题，这里不再赘述。
深入地“递归”
上文讲到的递归只是皮毛，来看看递归实际的用处。
在上面的例子中，我们知道递归的本质是将问题拆分成个体和一个整体，再将整体逐个拆为个体，如果你是入门者，可能还没有感觉，那么请看下文。
二叉树的中序遍历：左子树 -> 根 -> 右子树。
来通过递归实现中序遍历。
// 递归中序遍历
void f(TreeNode* root, vector<int>& result) {
if (root == nullptr) return;
f(root->left, result); // 左
result.push_back(root->val); // 中
f(root->right, result); // 右
}
前序、后序同理，只需调换顺序即可。
推荐问题：汉诺塔问题(hanoi)，请读者自行查阅。
递推
递推和递归差不多，唯一的区别在于 递归往后推，递推往前推，考试也不会问“这是递归还是递推”，递归的应用也更多。
所以这里不再赘述递推，感兴趣的读者可以自己查阅资料。
二分
什么是二分？二分（二分查找/二分法）是一种在有序数据集合中快速查找目标元素的算法。其核心思想为，每次将搜索区间减半，通过比较中间元素与目标值，排除一半不可能的区域。
二分模板：
while(l < r) {
int mid = l + (r – l + 1) / 2; // 找最大可行解
if(check(mid))
l = mid; // 可行，尝试更大的
else
r = mid – 1; // 不可行，减小
}
cout << l << endl;
请务必记熟。感觉 CSP-J 挺看重二分的。
例题
P1873 [COCI 2011/2012 #5] EKO / 砍树
题目描述
伐木工人 Mirko 需要砍
M
M
M 米长的木材。对 Mirko 来说这是很简单的工作，因为他有一个漂亮的新伐木机，可以如野火一般砍伐森林。不过，Mirko 只被允许砍伐一排树。
Mirko 的伐木机工作流程如下：Mirko 设置一个高度参数
H
H
H（米），伐木机升起一个巨大的锯片到高度
H
H
H，并锯掉所有树比
H
H
H 高的部分（当然，树木不高于
H
H
H 米的部分保持不变）。Mirko 就得到树木被锯下的部分。例如，如果一排树的高度分别为
20
,
15
,
10
20,15,10
20,15,10 和
17
17
17，Mirko 把锯片升到
15
15
15 米的高度，切割后树木剩下的高度将是
15
,
15
,
10
15,15,10
15,15,10 和
15
15
15，而 Mirko 将从第
1
1
1 棵树得到
5
5
5 米，从第
4
4
4 棵树得到
2
2
2 米，共得到
7
7
7 米木材。
Mirko 非常关注生态保护，所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助 Mirko 找到伐木机锯片的最大的整数高度
H
H
H，使得他能得到的木材至少为
M
M
M 米。换句话说，如果再升高
1
1
1 米，他将得不到
M
M
M 米木材。
输入格式
第
1
1
1 行
2
2
2 个整数
N
N
N 和
M
M
M，
N
N
N 表示树木的数量，
M
M
M 表示需要的木材总长度。
第
2
2
2 行
N
N
N 个整数表示每棵树的高度。
输出格式
1
1
1 个整数，表示锯片的最高高度。
输入输出样例 #1
输入 #1
4 7
20 15 10 17
输出 #1
15
输入输出样例 #2
输入 #2
5 20
4 42 40 26 46
输出 #2
36
说明/提示
对于
100
%
100\\%
100% 的测试数据，
1
≤
N
≤
10
6
1\\le N\\le10^6
1≤N≤106，
1
≤
M
≤
2
×
10
9
1\\le M\\le2\\times10^9
1≤M≤2×109，树的高度
≤
4
×
10
5
\\le 4\\times 10^5
≤4×105，所有树的高度总和
>
M
>M
>M。
例题解析
这是一个典型的二分答案问题，因为：
答案具有单调性：锯片高度 H 越高，得到的木材越少
可验证性：对于给定的 H，可以快速计算能得到的木材总量
答案范围确定：H 在 [0, max(tree_heights)] 之间
二分搜索策略
左边界 left = 0（锯片高度为 0 时，得到所有木材）
右边界 right = max_height（锯片高度等于最高树时，得到 0 木材）
对于每个 mid，计算 f(mid)
如果 f(mid) >= M：说明高度可以更高，在右半部分搜索
如果 f(mid) < M：说明高度太高了，在左半部分搜索
计算木材总量
对于每棵树高度 tree[i]：
如果 tree[i] > H，则得到 tree[i] – H 米木材
如果 tree[i] <= H，则得到 0 米木材
代码
#include<iostream>
#include<vector>
using namespace std;
int n,m,maxx;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin>>n>>m;
vector<long long> q(n);
for(int i=0;i<n;i++) {
int val;
cin>>val;
q[i]=val,maxx=max(maxx,val);
}
int l=0,r=maxx,mid;
while(l<r) {
mid=l+(r–l+1)/2;
long long tot=0;
for(int i=0;i<n;i++)
tot+=(q[i]–mid>=0?q[i]–mid:0);
if(tot >= m)
l = mid;
else
r = mid – 1;
}
cout<<l<<endl;
return 0;
}
例题2
P1020 [NOIP 1999 提高组] 导弹拦截
题目描述
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
一行，若干个整数，中间由空格隔开。
输出格式
两行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入输出样例 #1
输入 #1
389 207 155 300 299 170 158 65
输出 #1
6
2
说明/提示
对于前
50
%
50\\%
50% 数据，满足导弹的个数不超过
10
4
10^4
104 个。该部分数据总分共
100
100
100 分。可使用
O
(
n
2
)
\\mathcal O(n^2)
O(n2) 做法通过。 对于后
50
%
50\\%
50% 的数据，满足导弹的个数不超过
10
5
10^5
105 个。该部分数据总分也为
100
100
100 分。请使用
O
(
n
log
n
)
\\mathcal O(n\\log n)
O(nlogn) 做法通过。
对于全部数据，满足导弹的高度为正整数，且不超过
5
×
10
4
5\\times 10^4
5×104。
此外本题开启 spj，每点两问，按问给分。
NOIP1999 提高组 第一题
例题 2 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 100005;
int missiles[MAXN];
int tails1[MAXN]; // 用于最长不上升
int tails2[MAXN]; // 用于最长上升
int main() {
int n = 0;
while (cin >> missiles[n]) {
n++;
}
if (n == 0) {
cout << "0\\n0\\n";
return 0;
}
// 第一问：最长不上升子序列
int len1 = 0;
for (int i = 0; i < n; i++) {
int h = missiles[i];
// 二分查找第一个小于 h 的位置
int left = 0, right = len1;
while (left < right) {
int mid = left + (right – left) / 2;
if (tails1[mid] < h) {
right = mid;
} else {
left = mid + 1;
}
}
// 插入或替换
tails1[left] = h;
if (left == len1) {
len1++;
}
}
// 第二问：最长上升子序列
int len2 = 0;
for (int i = 0; i < n; i++) {
int h = missiles[i];
// 二分查找第一个大于等于 h 的位置
int left = 0, right = len2;
while (left < right) {
int mid = left + (right – left) / 2;
if (tails2[mid] >= h) {
right = mid;
} else {
left = mid + 1;
}
}
// 插入或替换
tails2[left] = h;
if (left == len2) {
len2++;
}
}
cout << len1 << "\\n" << len2 << "\\n";
return 0;
}
