一 、杂题（第一天）
1.成绩统计
题目描述
小蓝给学生们组织了一场考试，卷面总分为 100 分，每个学生的得分都是一个 0 到 100 的整数。如果得分至少是 60 分，则称为及格。如果得分至少为 85 分，则称为优秀。请计算及格率和优秀率，用百分数表示，百分号前的部分四舍五入保留整数。
https://www.lanqiao.cn/courses/17812/learning/?id=821087&compatibility=false
输入描述
输入的第一行包含一个整数 n (1≤n≤10^4^)，表示考试人数。
接下来 n 行，每行包含一个 0 至 100 的整数，表示一个学生的得分。
输出描述
输出两行，每行一个百分数，分别表示及格率和优秀率。百分号前的部分 四舍五入保留整数。
输入输出样例
示例
输入
7
80
92
56
74
88
100
0输出
71%
43%运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main(){
// 关闭输入输出缓存，使效率提升
ios::sync_with_stdio(false);
// 解除cin和cout的默认绑定，来降低IO的负担使效率提升
cin.tie(NULL); cout.tie(NULL);
int n=0;
cin>> n;
int temp=n;
int sssCount=0,sCount=0;
while(temp--){
int num;
cin>> num;
if(num>=85) ++sssCount;
if(num>=60) ++sCount;
}
cout<<setprecision(0)<<fixed<<1.0*sCount/n*100<<"%\n"<<1.0*sssCount/n*100<<"%\n";
return 0;
}
推荐题解：
#include<bits/stdc++.h>
using namespace std;
signed main(){
int n , x , cnt1 = 0 , cnt2 = 0;
cin >> n;
for(int i = 1 ; i <= n ; i ++){
cin >> x;
if(x >= 60) cnt1 ++ ;
if(x >= 85) cnt2 ++ ;
}
cout << setprecision(0) << fixed << (1.0 * cnt1 / n * 100) << "%\n" << (1.0 * cnt2 / n * 100) << "%\n";
return 0;
}2 排列字母
问题描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小蓝要把一个字符串中的字母按其在字母表中的顺序排列。
例如，LANQIAO 排列后为 AAILNOQ。
又如，GOODGOODSTUDYDAYDAYUP 排列后为 AADDDDDGGOOOOPSTUUYYY。
请问对于以下字符串，排列之后字符串是什么？
WHERETHEREISAWILLTHEREISAWAY
运行限制
- 最大运行时间：1s
- 最大运行内存: 512M
#include <iostream>
#include <string>
#include <algorithm>
//#include <bits/stdc++.h>
using namespace std;
int main(){
string s = "WHERETHEREISAWILLTHEREISAWAY" ;
sort(s.begin(),s.end());
cout<<s<<endl;
return 0;
}
推荐题解：
#include<bits/stdc++.h>
using namespace std;
int main(){
string s = "WHERETHEREISAWILLTHEREISAWAY";
//直接排序
sort(s.begin(), s.end());
cout<<s<<endl;
return 0;
}3 纸张尺寸
问题描述
在 ISO 国际标准中定义了 A0 纸张的大小为 1189mm ×× 841mm, 将 A0 纸 沿长边对折后为 A1 纸, 大小为 841mm ×× 594mm, 在对折的过程中长度直接取 下整 (实际裁剪时可能有损耗)。将 A1 纸沿长边对折后为 A2 纸, 依此类推。
输入纸张的名称, 请输出纸张的大小。
输入格式
输入一行包含一个字符串表示纸张的名称, 该名称一定是 A0、A1、A2、 A3、A4、A5、A6、A7、A8、A9 之一。
输出格式
输出两行，每行包含一个整数，依次表示长边和短边的长度。
样例输入1
A0样例输出1
1189
841样例输入 2
A1样例输出 2
841
594运行限制
- 最大运行时间：1s
- 最大运行内存: 512M
#include <iostream>
using namespace std;
int main()
{
// 关闭输入输出缓存，使效率提升
ios::sync_with_stdio(false);
// 解除cin和cout的默认绑定，来降低IO的负担使效率提升
cin.tie(NULL); cout.tie(NULL);
char a;
int i;
cin>>a>>i;
int lenght = 1189;
int weiht = 841;
while(i--){
int tem = weiht;
weiht = lenght/2; //宽
lenght = tem; //长
// lenght /= 2;
// if()swap(lenght,weiht);
}
cout<<lenght<<endl<<weiht<<endl;
return 0;
}
推荐题解：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
char c; int x;
//先输入字符A，再输入纸张类型x
cin >> c >> x;
//维护a,b
int a = 1189, b = 841;
while(x--) {
a /= 2;
if(a < b)swap(a, b);
}
cout<<a<<endl;
cout<<b<<endl;
return 0;
}4 迷宫
#include <iostream>
#include <string>
#include <set>
using namespace std;
string map[10] = {
"UDDLUULRUL",
"UURLLLRRRU",
"RRUURLDLRD",
"RUDDDDUUUU",
"URUDLLRRUU",
"DURLRLDLRL",
"ULLURLLRDU",
"RDLULLRDDD",
"UUDDUDUDLL",
"ULRDLUURRR",
};
bool isSuccess(int i, int j, set<pair<int, int> >& path) {
//判断终止条件
if ((i < 0 || i >= 10 || j < 0 || j >= 10) || map[i][j] == 'Y') { //可以出去
return true;
}
if (map[i][j] == 'N' || path.find(make_pair(i, j)) != path.end()) { //遇到死路或者路径重复
return false;
}
else {
//把走过的点加入路径
path.insert(make_pair(i, j));
}
//单层搜索的逻辑
switch (map[i][j]) {
case 'U':
return isSuccess(i - 1, j, path);
break;
case 'D':
return isSuccess(i + 1, j, path);
break;
case 'L':
return isSuccess(i, j - 1, path);
break;
case 'R':
return isSuccess(i, j + 1, path);
break;
}
}
int main() {
set<pair<int, int> > path; //表示路径，集合查找比vector更快
int count = 0; //多少人能出去
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
//判断map[i][j]是不是可以出去,如果可以出去，把沿途路径设置为Y ,如果出不去把沿途路径设置为N
path.clear();
if (isSuccess(i, j, path)) {
count++;
for (set<pair<int, int> >::iterator it = path.begin(); it != path.end(); it++) {
map[it->first][it->second] = 'Y';
}
}
else {
for (set<pair<int, int> >::iterator it = path.begin(); it != path.end(); it++) {
map[it->first][it->second] = 'N';
}
}
}
}
cout << count << endl;
return 0;
}5 星期一
思路:
用Excel
在一个格子里输入日期1901年1月1日，另一个格子输入2000年12月31日，然后两个格子相减得36524天，除以7得5217.7周。再看1901年1月1日是星期几。用Excel点1901年1月1日这一格的“设置单元格式-数字-日期-星期三”，点击“确定”，得“星期二”，即1901年1月1日是星期二，36524是5217周多几天，最后几天没有星期一，说明答案就是5217。
也可以直接利用Excel“单元格格式”对话框得出2000年12月31日刚好是星期天，从星期二至星期天之间没有星期一。
用Python
填空题遇到字符、大数字、日期问题，Python是首选。
直接用datetime库求解，强烈推荐!第4行可以输出某个日期是星期几。
from datetime import *
dt1 = datetime(1901,1,1)
dt2 = datetime(2000,12,31)
print(dt1.weekday( )) #打印出1，表示周二。注意:周一是0，周日是6
td = dt2- dt1
print(td.days//7)
答案：5217用C++
#include <iostream>
using namespace std;
int res;
//先判断润年
bool is_r(int n){
if((n % 4 == 0 && n % 100 != 0)|| n % 400 == 0) //满足其中之一的条件（1）能被4整除，但不能被100整除（2）能被400整除
return true;
return false;
}
int main() {
for(int i = 1901 ; i <= 2000 ; i++)
if(is_r(i)) res += 366;
else res += 365;
int x = res / 7;
cout << x << endl ;
return 0;
}6 乘积尾零
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
如下的 10行数据，每行有 10 个整数，请你求出它们的乘积的末尾有多少个零？
5650 4542 3554 473 946 4114 3871 9073 90 4329
2758 7949 6113 5659 5245 7432 3051 4434 6704 3594
9937 1173 6866 3397 4759 7557 3070 2287 1453 9899
1486 5722 3135 1170 4014 5510 5120 729 2880 9019
2049 698 4582 4346 4427 646 9742 7340 1230 7683
5693 7015 6887 7381 4172 4341 2909 2027 7355 5649
6701 6645 1671 5978 2704 9926 295 3125 3878 6785
2066 4247 4800 1578 6652 4616 1113 6205 3264 2915
3966 5291 2904 1285 2193 1428 2265 8730 9436 7074
689 5510 8243 6114 337 4096 8199 7313 3685 211 ·题解
直接连乘:几千位的大数然后统计末尾的0
num = data.split()
s=1
for i in num:
s=s*int(i)
cnt =0
while s%10==0:
s //=10
cnt += 1
print(cnt)·题解
10=2*5，统计5的个数，就是尾零的个数。
#include <bits/stdc++.h>
using namespace std;
int main(){
int cnt2=0, cnt5=0;
for (int i=1;i<=10;i++){
for (int j=1; j<=10; j++){
int x;
cin>>x ;
while (x%2==0) cnt2++,x/=2; //可以拆成 y * 2^cnt2
while (x%5==O) cnt5++,x/=5; //可以拆成 x * 5^cnt5
}
}
cout<<min(cnt2, cnt5)<<’\n’;
return 0;
}7 平方和
用python
sum = 0
for i in range( 1,2020):
s = str(i)
if '2' in s or '0' in s or '1' in s or '9' in s:
sum += i*i
print( sum )用C++
#include<bits/stdc++.h>
using namespace std;
int main(){
long long sum= 0;
for(int i = 1; i <=2019; i++){
int t = i;
while(t){
if(t%10==2 || t%10==0 || t%10==1 || t%10==9){ //t的个位数是2 0 1 9的
sum += i*i ;
break;
}
t/= 10;
}
}
cout <<sum;
return 0;
}
//解法2
#include <iostream>
#include <string>
using namespace std;
int main(){
long long int sum=0,i;
for(i=1;i<=2019;i++){
string a=to_string(i);
if(a.find("2")!=-1 || a.find("0")!=-1 || a.find("1")!=-1 || a.find("9")!=-1)
sum+=i*i;
}
cout<<sum;
return 0;
}
//在Visual Studio 2019可以运行，提交OJ也可以，但是Dev-C++会报错to_string(i)这个函数
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main() {
long long sum = 0;
for (int i = 1; i <= 2019; i++) {
string s = to_string(i);//由于to_string是c++11里面的，而dev没有c++11的环境，我们只需找到工具->编译选项,添加-std=c++11
if ((find(s.begin(),s.end(),'2') != s.end()) || (find(s.begin(), s.end(), '0') != s.end())
|| (find(s.begin(), s.end(), '1') != s.end()) || (find(s.begin(), s.end(), '9') != s.end())) {
sum += i * i;
}
}
cout << sum;
return 0;
}13 付账问题
示例
输入
5 2333
666 666 666 666 666输出
0.0000运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
//付账问题2018年第九届蓝桥杯C/C++大学A组，Java大学A组 //题目链接:lanqiao0J 174
//#include <bits/stdc++.h>
#include<iostream>
#include<array>
#include<algorithm>
#include<cmath> //sqrt的头文件
#include<iomanip> //setprecision(4)的头文件
using namespace std;
const int M = 5e5;
array<long long, M>a;
int main() {
int n;
long long s;
cin>>n>>s;
for (int i = 0; i < n; i++) cin>>a[i];
sort(a.begin(), a.begin()+n); //排序，从小到大double avg =1.O*s/n;//平均值
double avg = 1.0 * s / n; //平均值
double sum = 0.0;
for (int i = 0; i < n; i++) {
if (a[i] * (n - i) < s) { //需要把钱全拿出的人:钱不够当前的平均数的
sum += (a[i] - avg) * (a[i] - avg);
s -= a[i];
}
//更新剩余钱数
else { //不用把钱全拿出的人:非常有钱，不管怎么平均都够
double cur_avg = 1.0 * s / (n - i);//更新平均出钱数
sum += (cur_avg - avg) * (cur_avg - avg) * (n - i);
break;
}
}
//printf("%.4lf", sqrt(sum / n));
cout << setprecision(4) << fixed << sqrt(sum / n) << endl;
return 0;
}14 蜂巢
//蜂巢2022年第十三届省赛Java大学A组、研究生组，Python大学B组、C组 lanqiaoOJ 2134
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll xdir[] = {-2,-1,1,2,1,-1} ; //横向
ll ydir[] = { 0,1,1,0,-1,-1}; //纵向
void walk(ll d,ll q, ll &x, ll &y){ //d表示方向，q表示距离
x += xdir[d]*q;
y += ydir[d]* q; //引用传参，返回坐标值(x, y)
}
int main(){
ll d1, p1, q1, d2, p2,q2;
cin>>d1>>p1>>q1>>d2>>p2>>q2;
ll x1 = 0, y1 = 0; //计算起点坐标(x1，y1)
walk(d1,p1,x1, y1) ; //先走第1个方向
walk((d1 + 2) % 6,q1,x1, y1);//再走第2个方向ll x2= 0,y2 = 0;
ll x2 = 0, y2 = 0; //计算终点坐标(x2，y2)
walk(d2,p2,x2,y2);
walk((d2+ 2)% 6,q2,x2,y2);
ll dx = abs(x1 - x2),dy = abs(y1 - y2);
if (dx >= dy) cout << (dx+dy)/2; //先横走，再斜着走
else cout << dy ; //一直斜着走就行了
}题目的地址（想做哪道题就替换中间的2134）：https://www.lanqiao.cn/problems/2134/learning/
二、枚举题和二分法（第二天）
枚举的思想:将问题的所有可能成为答案的解一一列举，然后根据问题所给出的条件判断此解是否合适，如果合适就保留，反之则舍弃。
枚举解题的要素:
- 1.确定枚举解的范围，以及判断条件
- 2.选取合适枚举方法，进行逐一枚举，此时应注意能否覆盖所有的可能的解3.在枚举时使用判断条件检验，留下所有符合要求的解。
枚举的步骤:
- 1.根据题目确定枚举的范围，并选取合适的枚举方式，不能遗漏任何一个真正解，同时避免重复。
- 2.为了提高解决问题的效率，看题目是否存在优化，将可能成为解的答案范围尽可能缩小。
- 3.根据问题找到合理、准确描述、易编码的验证条件。
- 4.枚举并判断是否符合第3步确定的的条件，并保存符合条件的解。
- 5.按要求输出枚举过程中留下的符合条件的解。
1 特殊时间
#include <iostream>
using namespace std;
int main()
{
// 请在此输入您的代码
//年：**** A行
//月**日** B行
//时**分** C行
//年份无论闰年平年没有影响。从月份入手，分两种情况:
// 零开头：01 02两种 所以第二行是0111或0222 共有2*4*4=32种
// 一开头：10 11 12
// 10： 1000（×） 1011（√） 4*1*4=16种
// 11: 11*1—— 1101（√） 1111（×）1121（√）1131（×）1141..无 2种 2*4*4=32种
// 111*—— 1110（√） 1111（×）1112（√） 4*2*4=32种
// 1113（3种）1114（3种）1115（3种）4*3*3=36种
// 1116、1117、1118、 1119 （2种） 4*4*2=32种
// 12： 1211 （√） 1222（√） 4*2*4=32种
// 总数为:4*4*(2+1+2+2+2+2)+4*3*3=212;
cout<<4*4*(2+1+2+2+2+2)+4*3*3<<endl;
return 0;
}
推荐题解：
#include<bits/stdc++.h>
using namespace std;
int day_per_month[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
//检查日期D是否合法
bool check_D(int D){
int month = D / 100;
int day = D % 100;
if(month < 1 || month > 12)return false;
if(day < 1 || day > day_per_month[month])return false;
return true;
}
//检查时刻H是否合法
bool check_H(int H){
int h = H / 100;
int m = H % 100;
if(h < 0 || h > 23)return false;
if(m < 0 || m > 59)return false;
return true;
}
int main(){
int ans = 0;
//枚举第一个数字
for(int a = 0; a <= 9; a++){
//枚举第二个数字
for(int b = 0; b <= 9; b++)if(a != b){
//合法数量
int N_Y = 4, N_D = 0, N_H = 0;
int A[4] = {a, a, a, a};
//枚举四种情况aaab、aaba、abaa、baaa
for(int i = 0; i < 4; i++){
A[i] = b;
int number = 0;
for(int j = 0; j < 4; j++)
number = number * 10 + A[j];
N_D += check_D(number);
N_H += check_H(number);
A[i] = a;
}
ans += N_Y * N_D * N_H;
}
}
cout<<ans<<endl;
return 0;
}2 卡片
比较容易的模拟，我们从1开始枚举，每次检查剩下的卡片能不能拼出这个数字就好。
我们是怎么把一个数在10进制下每个位置的数字求出来呢?
很简单对吧，先对10取模，个位上的数字就求出来了，再除以10，原本十位上的数字就变到了个位上，再对10取模..依次进行下去就求出来了。把当前拼的这个数每一位都拆出来，看看那个数字的卡片还够不够，不够的话就说明拼不了，这时候退出循环，所以最多拼到上一个数。
最终答案:3181。
#include <iostream>
using namespace std;
int main(){
// 关闭输入输出缓存，使效率提升
ios::sync_with_stdio(false);
// 解除cin和cout的默认绑定，来降低IO的负担使效率提升
cin.tie(NULL); cout.tie(NULL);
int i;
int arr[10];
for(i=0;i<10;i++){
arr[i]=2021;//记录0-9这10张卡片的数量，开始都是2021张
}
for(i=1;;i++){ //由于不知道到i的边界值，省略，会一直执行
int x=i; //用x来存放每一个i的值，防止i值的改变
while(x){
if(arr[x%10]==0){//当有一张卡片的数量剩余为0张的时候，输出前一个i的值，也就是i-1，并退出
cout<<i-1;
exit(0);
}
arr[x%10]--; //每一张卡片数量减少1
x/=10;
}
}
return 0;
}
推荐题解：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int num[10];
bool check(int x){
while(x){
int now = x % 10;
if(num[now] > 0) num[now]--;
else return false;
x /= 10;
}
return true;
}
int main(){
for(int i = 0;i < 10;i++) num[i] = 2021;
for(int i = 1;;i++){
if(!check(i)){
cout << i - 1 << endl;
break;
}
}
return 0;
}3 约数个数
解题思路
简单枚举题，解法有很多。
当1200000时，我们称为1200000的约数。
由于1200000很小，所以可以直接用最最最朴素的做法:枚举1～1200000的所有数，计算这当中有多少个可以被1200000整出的数。
最后的答案为96.
#include <iostream>
#include <math.h>
using namespace std;
int main(){
int count=0;
for(int i=1;i<sqrt(1200000);i++){
if(1200000%i==0) count++;
}
cout<<2*count;
return 0;
}4 第几个幸运数字
【解题思路】暴力枚举。这个系列的数可以表示为3^i^×5^i^×7^k^，枚举所有不超过范围的i、j、k组合。代码中最小的3^50^肯定超过
59084709587505。
#include<bits/stdc++.h>
using namespace std;
int main(void){
long long n = 59084709587505;
int cnt = 0;
for(int i=0;pow(3,i)<n;i++)
for(int j=0 ; pow(5,j)<n;j++)
for(int k=O ; pow(7, k)<n;k++)
if(pow(3, i)*pow(5,j)*pow(7,k)<=n)
cnt++;
cout<<cnt-1; //1906-1=1905，幸运数字不包括1
return 0;
}课程例1 手写排列组合代码
从{1,2,3,4}中选3个的排列，有24种。最简单直接无技巧的手写排列:
【优缺点】简单且效果很好，但是非常笨拙。如果写5个以上的数的排列组合,代码冗长无趣。
#include <bits/stdc++.h>
using namespace std;
int main(){
int s[] = {1,2,3,4};
for(int i=0 ; i<4 ;i++) //循环3次，选3个数
for(int j=0; j<4;j++)
if(j!=i) //每个循环的数不同
for(int k=0; k<4 ;k++)
if (k!=j && k!=i) //每个循环的数不同
printf("%d%d%d\n" ,s[i],s[j],s[k]);
return 0;
}
include <bits/stdc++.h>
using namespace std;
int main(){
int s[] ={1,2,3,4} ;
for(int i=0 ; i<4; i++)//循环3次，选3个数
for(int j=i+1 ; j<4 ; j++)//让第2个数比第1个大
for(int k=j+1 ; k<4 ;k++)//让第3个数比第3个大
printf("%d%d%d\n",s[i],s[j],s[k]);
return 0;
}课程例2 手写子集代码:二进制法
#include<bits/stdc++.h>
using namespace std;
int a[] = {1,2,3,4,5,6,7,8,9,10,11，12,13,14};
void print_subset(int n){
for(int i=0 ; i<(1<<n) ; i++) {
//i: 0~2^n，每个i的二进制数对应一个子集。一次打印一个子集，最后得到所有子集
for(int j=0 ;j<n; j++) //打印一个子集，即打印i的二进制数中所有的1
if(i& (1<<j)) //从i的最低位开始，逐个检查每一位，如果是1，打印
cout<<a[j]<<"";
cout<<" \n" ;
}
}
int main(){
int n=3;
print_subset(n);
//打印前n个元素a[0]~a[n-1]的所有子集
}课程例3 C++枚举技术:排列
#include bits/stdc++.h>
using namespace std;
int main(){
string s="bca";
sort(s.begin(), s.end()); //字符串内部排序，得到最小的排列"abc"
do{
cout<<s<<"\n";
}while(next_permutation(s.begin(), s.end()) );
return 0;
}5 排列序数
题目描述
如果用abcd这4个字母组成一个串，有4!=24种，如果把它们排个序，每个串都对应一个序号:
abcd 0
abdc 1
acbd 2
acdb 3
adbc 4
adcb 5
bacd 6
badc 7
bcad 8
bcda 9
bdac 10
bdca 11
cabd 12
cadb 13
cbad 14
cbda 15
cdab 16
cdba 17
⋯⋯
先对输入的串s排序，然后用next_permutation()输出全排列，当全排列与初始的串相等时结束。
#include <bits/stdc++.h>
using namespace std;
int main(){
string s, olds;
cin>>s;
olds=s ;//用olds记录最初的串int cnt = 0;
sort(s. begin () , s.end() );
//字符串内部排序，得到最小的排列
do{
if(s == olds){
cout<<cnt<<endl;
break ;
}
cnt++;
} while(next_permutation(s.begin() , s.end()) ) ;
return 0;
}6 火星人
【题目描述】给出N个数的排列，输出这个排列后面的第M个排列。
【输入描述】第一行有一个正整数 N ，1 ≤ N ≤ 10000。第二行是一个正整数 M。下一行是 1 到 N个整数的一个排列，用空格隔开。
【输出描述】输出一行，这一行含有 N 个整数，表示原排列后面第M个排列。每两个相邻的数中间用一个空格分开，不能有多余的空格。
【输入样例】
5
3
1 2 3 4 5【输出样例】
1 2 4 5 3#include <bits/stdc++.h>
using namespace std;
int a[100000];
int main(){
int n,m; cin >> n >> m;
for(int i=1;i<=n;++i) cin >> a[i];
for(int i=1;i<=m;++i) next_permutation(a+1,a+n+1);
for(int i=1;i<=n;++i) cout <<a[i]<<" ";
return 0;
}尺取法（双指针、two pointers）
7 回文判定
【题目描述】给定一个长度为 n 的字符串 S。请你判断字符串 S是否回文。
【输入描述】输入仅1行包含一个字符串S。1≤|S|≤106，保证S只包含大小写、字母。
【输出描述】若字符串S为回文串，则输出Y，否则输出N
反向扫描的两个指针i、j，指针i从左向右扫描，指针j从右向左扫描，在中间i < j处相遇并停止。
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
cin>>s;
int i=0,j=s.size()-1;
while(i<j){
if(s[i]!=s[j]){
cout<<"N"<<endl;
}
}
cout<<"Y"<<endl;
return 0;
}课程例4 找指定和的整数对
【问题描述】输入n个整数，放在数组a[]中。找出其中的两个数，它们之和等于整数m。
尺取法：
（1）对数组从小到大排序；
（2）i和j分别指向头和尾，i和j向中间移动:
- a[i] + a[j] > m，让j减1：大的变小
- a[i] + a[j] < m，让i加1：小的变大
- 直至a[i] + a[j] = m
课程例5 美丽的区间
很直接的滑动窗口，求窗口内的区间和，满足大于S的最小长度。i指针在前，j指针在后，计算两个指针之间的区间和。当i指针到达末尾时，结束计算。计算复杂度为O(n)。
#include <bits/stdc++.h>
using namespace std;
int a[100010];
int main() {
int n,S; cin>>n>>S;
for (int i=0; i<n; ++i) cin>>a[i];
int sum= 0, ans=1e8;
for (int i=0，j=0; i<n;) {
if(sum<S){
sum+=a[i]; //i作为快指针往前走
i++;
}
else{
ans=min(i-j, ans);
sum-=a[j]; //j往前走
j++;
}
}
if (ans==1e8) cout<<0;
else cout<<ans;
return 0;
}三、递归与递推（第三天）
1 数的计算
#include <iostream>
using namespace std;
int res = 1; // 用来记录满足条件的数的个数
void f(int n) {
if (n == 1) return; // 如果 n 为 1，满足条件的数的个数是 1
for (int i = 1; i <= n / 2; i++) { // 枚举左边加的数
res++; // 新得到一个数，满足条件的数的个数加 1
f(i); // 递归调用 f(i)，计算新得到的数下满足条件的数的个数
}
}
int main() {
int n;
cin >> n;
f(n); // 计算满足条件的数的个数
cout << res; // 输出结果
return 0;
}2 数的划分
#include<bits/stdc++.h>
using namespace std;
int n,k,res;
void fun(int last,int sum,int cur){ //从last位置开始，划分的和sum；划分的段数cur
if(cur==k) {
if(sum==n) {
res++;
}
return;
}
else if(k>0) {
//sum+i*(k-cur)<=n 有人判断条件是这个，但是我不是很能想到。
for(int i=last;i<=n-sum;i++){
fun(i,sum+i,cur+1);
}
}
}
int main(){
cin>>n>>k;
fun(1,0,0);
cout<<res<<"\n";
return 0;
}
//解题思路
#include<bits/stdc++.h>
using namespace std;
int f(int n,int m) {
if (m == 0 || m == 0||n<m) {
return 0;
}
if (n == 1 || n == m) {
return 1;
}
else{
return f(n - m , m) + f(n - 1 , m- 1);
}
}
int main(){
int n , k;
cin >> n >> k;
cout << f(n , k) << '\n';
return 0;
}
3 耐摔指数？（动态规划）
#include <iostream>
using namespace std;
int b[105], c[105];
int main(void) {
int n, i = 0;
cin >> n;
i = 0;
while (c[i] < n) {
i++;
b[i] = i + b[i - 1];
c[i] = c[i - 1] + b[i - 1] + 1;
}
cout << i << '\n';
return 0;
}例1 斐波那契数列
递推式: f(n)= f(n-1)+ f(n-2)
打印第20个数:
#include<bits/stdc++.h>
using namespace std;
int fib[25];
int main(){
fib[1]=fib[2]=1;
for(int i=3;i<=20;i++) fib[i]= fib[i-1]+fib[i-2];
for(int i=1;i<=20;i++) cout <<fib[i]<<" ";
}
递归过程
#include<bits/stdc++.h>
using namespace std;
int cnt=0; //统计执行了多少次递归
int fib (int n){ //递归函数
cnt ++;
if (n==1 || n==2) return 1; //到达终止条件，即最小问题
return fib (n-1) + fib (n-2);//递归调用自己2次，复杂度约O(2n)
}
int main(){
cout << fib(20); //计算第20个斐波那契数
cout <<" cnt="<<cnt; //递归了cnt=13529次
}
- 递推和递归两种代码，结果一样，计算量差别巨大：
- 递推代码：一个for循环，计算20次。
- 递归代码：计算第20个斐波那契数，共计算cnt = 13529次。
- 为什么斐波那契的递归代码如此低效？
改进：记忆化
- 递归的过程中做了重复工作，例如fib(3)计算了2次，其实只算1次就够了。
- 为避免递归时重复计算，在子问题得到解决时，就保存结果，再次需要这个结果时，直接返回保存的结果，不继续递归下去。
- 这种存储已经解决的子问题结果的技术称为“记忆化（Memoization）”。
- 记忆化是递归的常用优化技术。
- 动态规划也常常用递归写代码
- 记忆化也是动态规划的关键技术。
#include<bits/stdc++.h>
using namespace std;
int cnt=0; //统计执行了多少次递归
int data[25]; //存储斐波那契数
int fib (int n){
cnt++;
if (n==1 || n==2){data[n]=1; return data[n];}
if(data[n]!=0) return data[n];
//记忆化搜索：已经算过，不用再算，直接返回结果
data[n] = fib (n-1) + fib (n-2); //继续递归
return data[n];
}
int main(){
cout << fib(20); //计算第20个斐波那契数
cout <<" cnt="<<cnt; //递归了cnt=37次。
}
例2：自写排列算法（递归）
#include<bits/stdc++.h>
using namespace std;
int a[20]={1,2,3,4,5,6,7,8,9,10,11,12,13};
bool vis[20]; //记录第i个数是否用过
int b[20]; //生成的一个全排列
void dfs(int s,int t){
if(s==t) { //递归结束，产生一个全排列
for(int i=0; i<t; ++i) cout<<b[i]<<" ";//输出一个排列
cout<<"\n";
return;
}
for(int i=0;i<t;i++)
if(!vis[i]){
vis[i]=true;
b[s]=a[i];
dfs(s+1,t);
vis[i]=false;
}
}
int main(){
int n=3;
dfs(0,n); //前n个数的全排列
return 0;
}从小到大打印n个数中任意m个数的排列（大概率会考）
#include<bits/stdc++.h>
using namespace std;
int a[20]={1,2,3,4,5,6,7,8,9,10,11,12,13};
bool vis[20];
int b[20];
void dfs(int s,int t){
if(s==3) { //改为s=3
for(int i=0; i<3; ++i) cout<<b[i]<<" "; //改为i<3
cout<<“\n";
return;
}
for(int i=0;i<t;i++)
if(!vis[i]){
vis[i]=true;
b[s]=a[i];
dfs(s+1,t);
vis[i]=false;
}
}
int main(){
int n=4;
dfs(0,n); //前n个数的全排列
return 0;
}例3 自写组合算法(递归)
以3个数{1, 2, 3}为例，把上面的代码与需要打印的数列结合
#include<bits/stdc++.h>
using namespace std;
int a[]={1,2,3,4,5,6,7,8,9,10};
int vis[10];
void dfs(int k) {
if (k == 3) {
for(int i=0;i<3;i++)
if(vis[i]) cout<<a[i];
cout<<"-";
}
else {
vis[k] = 0; //不选中第k个数
dfs(k + 1); //继续搜下一个数
vis[k] = 1; //选这个数
dfs(k + 1); //继续搜下一个数
}
}
int main() {
dfs(0); //从第一个数开始
return 0;
}
class Solution {
vector<vector<int>>result;
vector<int>path;
void dfs(vector<int>& nums, vector<bool>used) {
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); ++i) {
if (used[i] == true) { //已经被用过了，就不能再用了
continue;
}
path.push_back(nums[i]);
used[i] = true;
dfs(nums, used);
used[i] = false;
path.pop_back();
}
return;
}
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<bool>used(nums.size(), false);
dfs(nums, used);
return result;
}
};
int main() {
Solution s;
vector<int> nums{ 1,2,3 };
vector<vector<int>>result = s.permute(nums);
for (int i = 0; i < result.size(); i++) {
for (int j = 0; j < result[i].size(); j++) {
cout << result[i][j] << " ";
}
cout << endl;
}
system("pause");
return 0;
}例4 五星填数
步骤：
- 定义五星。（数据结构）
- 第一步：写出10个数的全排列。（算法）
- 第二步：判断每个直线上的数字和是不是相等。（逻辑）（
- v[1]+v[3]+v[6]+v[9]
- v[1]+v[4]+v[8]+v[10]
- v[2]+v[3]+v[4]+v[5]
- v[2]+v[6]+v[7]+v[10]
- v[5]+v[7]+v[8]+v[9]）
- 第三步：剔除旋转、镜像相同的解。（思维）（旋转：一个解旋转5次，都相同；镜像：再乘以2。所以任意一种组合经过镜像和旋转都有10种不同的组合满足判断。最后结果除以10即可。）
#include <bits/stdc++.h>
using namespace std;
int main() {
int sum = 0;
int v[12] = {0,1,2,3,4,5,6,8,9,10,12};
do {
int t = v[1]+v[3]+v[6]+v[9];
if(t==v[1]+v[4]+v[8]+v[10] && t==v[2]+v[3]+v[4]+v[5] &&
t==v[2]+v[6]+v[7]+v[10] && t==v[5]+v[7]+v[8]+v[9])
sum++;
} while(next_permutation(v+1, v+11));
cout << sum/10;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int v[12] = {0,1,2,3,4,5,6,8,9,10,12};
int sum = 0;
void dfs(int s,int t) {
if(s == t) { // 结束，输出一个全排列
int t = v[1]+v[3]+v[6]+v[9];
if(t==v[1]+v[4]+v[8]+v[10] && t==v[2]+v[3]+v[4]+v[5] &&
t==v[2]+v[6]+v[7]+v[10] && t==v[5]+v[7]+v[8]+v[9])
sum++;
}
else
for(int i=s; i<=t; i++) {
swap(v[s],v[i]);
dfs(s+1,t);
swap(v[s],v[i]);
}
}
int main() {
dfs(1,10); //求从第1个数到第10个数的全排列。
cout << sum/10;
return 0;
}例5 加减乘除四种运算：
思路：用上一次讲过的permutations()函数，生成所有的排列，检查是否合法
运行时间极长：13个数的排列：13! = 6,227,020,800 （需要半小时）？
#include<bits/stdc++.h>
using namespace std;
int a[20]={1,2,3,4,5,6,7,8,9,10,11,12,13};
bool vis[20];
int b[20];
int ans=0;
void dfs(int s,int t){
if(s==12) {
if(b[9]*b[10] == b[11]) ans++;
return;
}
if(s==3 && b[0]+b[1]!=b[2]) return; //剪枝
if(s==6 && b[3]-b[4]!=b[5]) return; //剪枝
if(s==9 && b[6]*b[7]!=b[8]) return; //剪枝
for(int i=0;i<t;i++)
if(!vis[i]){
vis[i]=true;
b[s]=a[i];
dfs(s+1,t);
vis[i]=false;
}
}
int main(){
int n=13;
dfs(0,n); //前n个数的全排列
cout<<ans;
return 0;
}
例6 生成格雷码 ？
#include <bits/stdc++.h>
using namespace std;
int n;
unsigned long long K;
string s;
void gray(int t,unsigned long long k){
if(t==0) return;
gray(t-1,k/2);
if(k%4==2||k%4==1) s+='1';
else s+='0';
}
int main(){
cin>>n>>K;
gray(n,K);
cout<<s;
return 0;
}四、深度优先搜索和广度优先搜索
例1 DFS：搜索和输出所有路径
路径有很多条，需要记录每条路径然后打印，这个代码使用了“输出最短路径的简单方法”：每到一个点，就在这个点上记录从起点到这个点的路径。p[][]记录路径，p[i][j]用字符串记录了从起点到点(i, j)的完整路径。第20行把新的点(nx, ny)加入到这个路径。这种“简单方法”浪费空间，适用于小图。
#include<bits/stdc++.h>
using namespace std;
char mp[10][10]; //地图
string p[10][10]; //记录从起点到点path[i][j]的路径
int d[4][2] = {{-1,0},{0,-1},{1,0},{0,1}}; //左、上、右、下。左上角坐标是(0, 0)
int Wy, Hx, num=0; //Wy行，Hx列。用num统计路径数量
int sx,sy,tx,ty; //起点和终点
void dfs(int x, int y){
for(int i = 0; i < 4; i++) { //左、上、右、下，4个方向顺时针深搜
int nx=x+d[i][0], ny=y+d[i][1]; //一个邻居点
if(nx>=Hx || nx<0 || ny <0 || ny>=Wy) continue; //不在地图内
if(mp[nx][ny] == '*') { //遇到终点
num++;
char t[4]; sprintf(t,"%d%d",nx,ny); //记录路径
cout<<num<<": "<<p[x][y]+"->"+t<<"\n"; //打印路径
continue; //不退出，继续找下一个路径
}
if( mp[nx][ny] == '.'){
mp[nx][ny] = '#'; //保存现场。这个点在这次更深的dfs中不能再用
char t[4];sprintf(t,"%d%d",nx,ny);
p[nx][ny]=p[x][y]+"->"+t; //记录路径
dfs(nx, ny);
mp[nx][ny] = '.'; //恢复现场。回溯之后，这个点可以再次用
}
}
}
int main(){
cin >> Wy >> Hx; //Wy行，Hx列
for (int y = 0; y < Wy; y++) { //有Hx列
for (int x = 0; x < Hx; x++) { //一次读入一行
cin >> mp[x][y];
if(mp[x][y]=='@') {sx=x; sy=y;} //读起点
if(mp[x][y]=='*') {tx=x; ty=y;} //读终点
}
}
cout<<"from "<<sx<<sy<<" to "<<tx<<ty<<"\n";
char t[4];
sprintf(t,"%d%d", sx,sy);
p[sx][sy] = t; //开始记录路径
dfs(sx, sy); //搜索并打印所有路径
//cout<<num; //打印路径总数
return 0;
}搜所有的路径，应该用DFS；如果只搜最短路径，应该用BFS。在一张图上，从起点到终点的所有路径数量是一个天文数字，读者可以用上面的代码试试一个8×8的图，看看路径总数是多少。但是搜最短的路径就比较简单，并不需要把所有路径搜出来之后再比较得到最短路，用BFS可以极快地搜到最短路。DFS适合用来处理暴力搜所有情况的题目
例2 全球变暖
https://www.lanqiao.cn/problems/178/learning/
题目描述
你有一张某海域 NxN 像素的照片，”.”表示海洋、”#”表示陆地，如下所示：
.......
.##....
.##....
....##.
..####.
...###.
.......其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
.......
.......
.......
.......
....#..
.......
.......请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
输入描述
第一行包含一个整数 N (1≤N≤1000)N (1≤N≤1000)。
以下 N 行 N 列代表一张海域照片。
照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。
输出一个整数表示答案。
输入输出样例
示例
输入
7
.......
.##....
.##....
....##.
..####.
...###.
.......输出
1运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
连通性判断
连通性问题，计算步骤：
- 遍历一个连通块（找到这个连通块中所有的’#‘，标记已经搜过，不用再搜）；
- 再遍历下一个连通块……；
- 遍历完所有连通块，统计有多少个连通块。
什么岛屿不会被完全淹没？
- 若岛中有个陆地（称为高地），它周围都是陆地，那么这个岛不会被完全淹没。
- 用DFS搜出有多少个岛（连通块），检查这个岛有没有高地，统计那些没有高地的岛（连通块）的数量，就是答案。
- 计算复杂度：每个像素点只用搜一次且必须至少搜一次，共N2个点，DFS的复杂度是O(N2)，不可能更好了。
DFS判断连通性的步骤
- 从图上任意一个点u开始遍历，标记u已经搜过。
- 递归u的所有符合连通条件的邻居点。
- 递归结束，找到了与u连通的所有点，这是一个连通块。
- 不与u连通的、其他没有访问到的点，继续用上述步骤处理，找到所有的连通块。
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
char mp[N][N]; //地图
int vis[N][N]={0}; //标记是否搜过
int d[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}}; //四个方向 上下右左
int flag; //用于标记这个岛中是否被完全淹没
void dfs(int x, int y){
vis[x][y] = 1; //标记这个'#'被搜过。注意为什么放在这里
if( mp[x][y+1]=='#' && mp[x][y-1]=='#' &&
mp[x+1][y]=='#' && mp[x-1][y]=='#' )
flag = 1; //上下左右都是陆地，这是一个高地，不会淹没
for(int i = 0; i < 4; i++){ //继续DFS周围的陆地
int nx = x + d[i][0], ny = y + d[i][1];
if(vis[nx][ny]==0 && mp[nx][ny]=='#') //注意为什么要判断vis[][]
dfs(nx,ny); //继续DFS未搜过的陆地，目的是标记它们
}
}
int main(){
int n; cin >> n;
for (int i = 0; i < n; i++) cin >> mp[i];
int ans = 0 ;
for(int i = 0; i < n; i++) //DFS所有像素点
for(int j = 0; j < n; j++)
if(mp[i][j]=='#' && vis[i][j]==0){
flag = 0; //假设这个岛被淹
dfs(i,j); //找这个岛中有没有高地，如果有,置flag=1
if(flag == 0) ans++; //这个岛确实被淹了，统计被淹没岛的数量
}
cout<<ans<<endl;
return 0;
}DFS：剪枝的技术
- 可行性剪枝：对当前状态进行检查，如果当前条件不合法就不再继续，直接返回。
- 搜索顺序剪枝：搜索树有多个层次和分支，不同的搜索顺序会产生不同的搜索树形态。
- 最优性剪枝：在最优化问题的搜索过程中，如果当前花费的代价已超过前面搜索到的最优解，那么本次搜索已经没有继续进行下去的意义，停止对当前分支的搜索。
- 排除等效冗余：搜索的不同分支，最后的结果是一样的，那么只搜一个分支就够了。
- 记忆化搜索：在递归的过程中，有许多分支被反复计算，会大大降低算法的执行效率。将已经计算出来的结果保存起来，以后需要用到的时候直接取出结果，避免重复运算，从而提高了算法的效率。
例3 剪格子
- 思路：先求所有格子的和sum，然后用DFS找一个联通区域，看这个区域的和是否为sum/2。
- 剪枝：如果DFS到的部分区域的和已经超过sum/2，就不用继续DFS了。
- 这种格子DFS搜索题，是蓝桥杯的常见考题。
#include<bits/stdc++.h>
using namespace std;
const int N=15;
int n, m;
int a[N][N], vis[N][N]; //格子是否被访问过
int sum, ans=100000;
int d[4][2] = { {1,0},{0,-1},{0,1},{-1,0} }; //4个方向
void dfs(int x, int y, int c, int s) {
if (2*s>sum) return; //剪枝（感觉还可以if (2*s>sum && c>ans) return;）
if (2*s==sum) {
if (c<ans && vis[0][0]) ans = c; //左上角格子最少数量
return;
}
vis[x][y]=1;
for (int k=0; k<4; k++) {
int tx=x+d[k][0], ty=y+d[k][1];
if (tx>=0 && tx<n && ty>=0 && ty<m && !vis[tx][ty])
dfs(tx,ty,c+1,s+a[x][y]);
}
vis[x][y]=0;
}
int main() {
cin>>m>>n;
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
cin>>a[i][j], sum+=a[i][j]; //求所有格子的和
dfs(0,0,0,0);
cout<<(ans==100000 ? 0 : ans);
return 0;
}BFS原理
- BFS搜索的原理：“逐层扩散”。从起点出发，按层次从近到远，逐层先后搜索。
- 编码：用队列实现。
- 应用：BFS一般用于求最短路径问题，BFS的特点是逐层搜索，先搜到的层离起点更近。
BFS的特点：逐层扩散。
- 往BFS的队列中加入邻居结点时，按距离起点远近的顺序加入：先加入距离起点为1的邻居结点，加完之后，再加入距离为2的邻居结点，等等
- 搜完一层，才会继续搜下一层。
- 最短路径：从起点开始，沿着每一层逐步往外走，每多一层，路径长度就增加1。所有长度相同的最短路径都是从相同的层次扩散出去的。搜到第一个到达终点的路径，就是最短路径。
- 应用场合：点和点直接的距离是1，即边长是1。
例4 迷宫
【题目描述】下图给出了一个迷宫的平面图，其中标记为1的为障碍，标记为0的为可以通行的地方。
010000
000100
001001
110000迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这个它的上、下、左、右四个方向之一。对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫，一共10步。其中D、U、L、R分别表示向下、向上、向左、向右走。对于下面这个更复杂的迷宫（30行50列），请找出一种通过迷宫的方式，其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。请注意在字典序中D<L<R<U。
01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000题目求字典序最小的最短路径
在每次扩散下一层（往BFS的队列中加入下一层的结点）时，按字典序“D<L<R<U”的顺序加下一层的结点，那么第一个搜到的最短路径就是字典序最小的。
计算复杂度：每个点只搜一次，即进入队列和出队列一次。复杂度O(n)，n是迷宫内结点的总数。
BFS能用于解决1千万个点的最短路问题。
- 在每个点上记录它的前驱点
- 从终点一步步回溯到起点，得到一条完整路径。
//注意本题是填空题。下面代码直接提交到oj，“答案错误”。自己运行得到答案后，再把答案提交到OJ。
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y; //坐标
string path; //path,记录从起点(0,0)到这个点(x,y)的完整路径
};
char mp[31][51]; //存地图
char k[4]={'D','L','R','U'}; //4个方向，按字典序（行数是x，列数是y）
int dir[4][2]={{1,0},{0,-1},{0,1},{-1,0}};
int vis[30][50]; //标记。vis=1: 已经搜过，不用再搜
void bfs(){
node start;
start.x=0; start.y=0; start.path=""; //定义起点
vis[0][0]=1; //标记起点被搜过
queue<node>q;
q.push(start); //把第一个点放进队列，开始BFS
while(!q.empty()){
node now = q.front(); q.pop(); //取出队首，弹走队首
if(now.x==29 && now.y==49){ //第一次遇到终点，就是字典序最小的最短路径
cout << now.path; //打印完整路径
return;
}
for(int i=0;i<4;i++){ //扩散4个方向的邻居结点
node next;
next.x = now.x + dir[i][0];
next.y = now.y + dir[i][1];
if(next.x<0||next.x>=30||next.y<0||next.y>=50) continue; //越界了
if(vis[next.x][next.y]==1 || mp[next.x][next.y]=='1')
continue; //vis=1:已经搜过; mp=1:是障碍
vis[next.x][next.y]=1; //标记被搜过
next.path = now.path + k[i]; //记录完整路径：复制上一个点的路径，加上这一步
q.push(next);
}
}
}
int main(){
for(int i=0;i<30;i++) cin >> mp[i]; //读题目给的地图数据
bfs();
}例5 全球变暖
BFS：连通性判断、BFS用三种队列实现
https://www.lanqiao.cn/problems/178/learning/
题目描述
你有一张某海域 NxN 像素的照片，”.”表示海洋、”#”表示陆地，如下所示：
.......
.##....
.##....
....##.
..####.
...###.
.......其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
.......
.......
.......
.......
....#..
.......
.......请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
输入描述
第一行包含一个整数 N (1≤N≤1000)N (1≤N≤1000)。
以下 N 行 N 列代表一张海域照片。
照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。
输出一个整数表示答案。
输入输出样例
示例
输入
7
.......
.##....
.##....
....##.
..####.
...###.
.......输出
1运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
连通性判断
连通性问题，计算步骤：
- 遍历一个连通块（找到这个连通块中所有的’#‘，标记已经搜过，不用再搜）；
- 再遍历下一个连通块……；
- 遍历完所有连通块，统计有多少个连通块。
什么岛屿不会被完全淹没？
- 若岛中有个陆地（称为高地），它周围都是陆地，那么这个岛不会被完全淹没。
- 用DFS搜出有多少个岛（连通块），检查这个岛有没有高地，统计那些没有高地的岛（连通块）的数量，就是答案。
- 计算复杂度：每个像素点只用搜一次且必须至少搜一次，共N2个点，DFS的复杂度是O(N2)，不可能更好了。
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
char mp[N][N];
int vis[N][N];
int d[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}}; //四个方向
int flag;
void bfs(int x, int y) {
queue<pair<int, int>> q;
q.push({x, y});
vis[x][y] = 1; //标记这个'#'被搜过
while (q.size()) {
pair<int, int> t = q.front();
q.pop();
int tx = t.first, ty = t.second;
if( mp[tx][ty+1]=='#' && mp[tx][ty-1]=='#' &&
mp[tx+1][ty]=='#' && mp[tx-1][ty]=='#' )
flag = 1; //上下左右都是陆地，不会淹没
for (int i = 0; i < 4; i++) { //扩展(tx,ty)的4个邻居
int nx = tx + d[i][0], ny = ty + d[i][1];
if(vis[nx][ny]==0 && mp[nx][ny]=='#'){ //把陆地放进队列
vis[nx][ny] = 1; //注意：这一句必不可少
q.push({nx, ny});
}
}
}
}
int main() {
int n; cin >> n;
for (int i = 0; i < n; i++) cin >> mp[i];
int ans = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (mp[i][j] == '#' && vis[i][j]==0) {
flag = 0;
bfs(i, j);
if(flag == 0) //这个岛全部被淹
ans++; //统计岛的数量
}
cout << ans << endl;
return 0;
}
搜索习题
青蛙跳杯子102，发现环108，合根植物110，填字母游戏113，机器人塔118，四平方和122，取球博弈123，
卡片换位125、生命之树131，穿越雷区141、长草149、小朋友崇拜圈182，剪格子211，版本分支223，
迷宫与陷阱229，调手表230，分考场237，最长子序列244，九宫重排261，网络寻路263，危险系数264，
约数倍数选卡片265，字母阵列621，魔方状态643，算式649，凑平方数653，方格填数664，完美正方形685，
五星填数687，生成回文数691，走迷宫1216，N皇后问题1508，最少操作数1509。
https://www.lanqiao.cn/problems/178/learning/
1 跳蚱蜢
这是一道典型的 BFS 题目，求最少跳跃，也是最短路径问题。
1. 建模
直接让蚱蜢跳到空盘有点麻烦，因为有很多蚱蜢在跳，跳晕了。如果反过来看，让空盘跳，跳到蚱蜢的位置，就简单多了，只有一个空盘在跳。
题目给的是一个圆圈，不好处理，用一个建模技巧“化圆为线”，把圆形转换为线形。把空盘看成 0，那么有 9 个数字 {0,1,2,3,4,5,6,7,8}，一个圆圈上的 9 个数字，拉直成了一条线上的 9 个数字，这条线的首尾两个数字处理成相连的。
这一题是八数码问题，八数码是经典的 BFS 问题。八数码问题有 9 个数字{0, 1, 2, 3, 4, 5, 6, 7, 8}，共有 9！= 362880 种排列，不算多。
本题的初始状态是“012345678”，目标状态是“087654321”。从初始状态“012345678”跳一次，有 4 种情况：“102345678”、 “210345678”、 “812345670”、 “712345608”。然后从这 4 种状态继续跳到下一种状态，一直跳到目标状态为止。
用 BFS 扩展每一层。每一层就是蚱蜢跳了一次，扩展到某一层时发现了终点“087654321”，这一层的深度就是蚱蜢跳跃的最少次数。
#include<iostream>
#include<set>
#include<queue>
//#include <chrono>
using namespace std;
//using namespace chrono;
struct state {
state() {};
state(string s, int count) :s(s), count(count) {};
string s;
int count;
};
set<string>HashTable;
int main() {
//auto m_alivetime = steady_clock::now();
state startState("012345678", 0);
HashTable.insert(startState.s);
queue<state>Q;
Q.push(startState);
while (!Q.empty()) {
state now = Q.front(); Q.pop();
if (now.s == "087654321") {
cout << now.count << endl;
break;
}
//找到‘0’的位置
int zeroIndex = now.s.find('0', 0); //0-8位置的其中一个
for (int i = zeroIndex - 2; i <= zeroIndex + 2; i++) { //4种跳法
// if(zeroIndex>=2&&zeroIndex<=6)
int k = (i + 9) % 9; //需要换的位置
string nextState = now.s;
swap(nextState[zeroIndex], nextState[k]);
if (HashTable.find(nextState) != HashTable.end() || k == zeroIndex) {
continue;
}
HashTable.insert(nextState);
Q.push(state(nextState, now.count + 1));
}
}
//auto res = steady_clock::now() - m_alivetime;
//milliseconds millsec = duration_cast<milliseconds>(res); //类型转换
//cout << millsec.count()<<"ms" << endl; //返回的是有多少个毫秒
system("pause");
return 0;
}
#include<bits/stdc++.h>
using namespace std;
struct node{
node(){}
node(string ss, int tt){s = ss, t = tt;}
string s;
int t;
};
int cnt = 0; //统计计算了多少次
map<string, bool> mp;
queue<node> q;
void solve(){
while(!q.empty()){
node now = q.front();
q.pop();
string s = now.s;
int step = now.t;
if(s == "087654321"){ //到目标了
cout << step << endl; //输出跳跃步数
cout << cnt << endl; //计算了 1451452 次
break;
}
int i;
for(i = 0 ; i < 10 ; i++) //找到盘子的位置
if(s[i] == '0') break;
for(int j = i - 2 ; j <= i + 2 ; j++){ //4种跳法
int k = (j + 9) % 9;
if(k == i) continue; //这是当前状态，不用检查
string news = s;
char tmp = news[i];
news[i] = news[k];
news[k] = tmp; //跳到一种情况
cnt ++;
if(!mp[news]){ //判重：这个情况没有出现过
mp[news] = true;
q.push(node(news, step + 1));
}
}
}
}
int main(){
string s = "012345678";
q.push(node(s, 0));
mp[s] = true;
solve();
return 0;
}2 七段码（并查集）
解题思路
我们可以把每个二极管看成一条边，并把相邻的边相连，那么这样题目就可以转换为：
有多少种选边方案，使得选出来的边构成的图只有一个联通快。
于是现在只要枚举选边方案，再判断联通块的个数是否为 11 即可。
- 枚举选边方案可以采用状压（当然直接
dfs搜索也行）：用二进制 1、0 分别表示二进制位所对应的边是选还是不选，复杂度为 2^7^。 - 求联通块的个数可以采用
bfs（也可以采用并查集等方法）：从任意一个选中的边出发将所有能到达的选中的边全部打上标记；若标记覆盖了所有选中的边则联通快只有一个（满足条件），反之不止一个联通块（不满足条件）。
最后的答案为 80。
#include<bits/stdc++.h>
using namespace std;
int ans , g[7][7] , vis[7] , flag[7];
void bfs(int x){
queue<int>que;
que.push(x);
vis[x] = true; //记录这个灯被用过
while(!que.empty()){
int u = que.front();
que.pop();
for(int i = 0 ; i <= 6 ; i ++){
if(g[u][i] && flag[i] && !vis[i]){ //g[u][i]表示与他相邻的灯，flag[i]表示被点亮，!vis[i]表示没被访问过
vis[i] = true;
que.push(i);
}
}
}
}
bool check(int x){
for(int i = 0 ; i <= 6 ; i ++) flag[i] = vis[i] = false; //初始化
int cnt = 0;
for(int i = 6 ; ~i ; i --) if(x >> i & 1) flag[i] = true; //记录哪些灯被点亮
for(int i = 0 ; i <= 6 ; i ++){ //检查这些点亮的是不是形成一个连通块
if(flag[i] && !vis[i]){
bfs(i);
cnt ++ ;
}
}
return cnt == 1; //如果连通块超过两个，就表示不能全部连通
}
signed main(){
g[0][1] = g[0][5] = 1;
g[1][0] = g[1][2] = g[1][6] = 1;
g[2][1] = g[2][3] = g[2][6] = 1;
g[3][2] = g[3][4] = 1;
g[4][3] = g[4][5] = g[4][6] = 1;
g[5][0] = g[5][4] = g[5][6] = 1;
g[6][1] = g[6][2] = g[6][4] = g[6][5] = 1;
for(int i = 0 ; i < (1 << 7) ; i ++){
if(check(i)) {
ans ++ ;
}
}
cout << ans << '\n';
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int e[10][10] = {0};
int s[8] = {0}, vis[8] = {0};
int ans = 0;
void init() {
for (int i = 1; i <= 7; i++) s[i] = i;
}
int find_set(int x){ //用“路径压缩”优化的查询
if(x != s[x]) s[x] = find_set(s[x]); //路径压缩
return s[x];
}
void merge_set(int x, int y){ //合并
x = find_set(x); y = find_set(y);
if(x != y) s[x] = s[y]; //y成为x的父亲，x的集是y
}
void check(){
init();
for (int i = 1; i <= 7; i++)
for(int j=1;j<=7;j++)
if (e[i][j] && vis[i] && vis[j]) merge_set(i, j);
int flag = 0;
for (int j = 1; j <= 7; j++)
if (vis[j] && s[j] == j) flag++;
if (flag == 1) ans++;
}
void dfs(int k) { //深搜到第k个灯
if (k == 8) check(); //检查连通性
else {
vis[k] = 1; //点亮这个灯
dfs(k + 1); //继续搜下一个灯
vis[k] = 0; //关闭这个灯
dfs(k + 1); //继续搜下一个灯
}
}
int main() {
//a b c d e f g 字符用数字表示
//1 2 3 4 5 6 7
e[1][2] = e[1][6] = 1;
e[2][1] = e[2][3] = e[2][7] = 1;
e[3][2] = e[3][4] = e[3][7] = 1;
e[4][3] = e[4][5] = 1;
e[5][4] = e[5][6] = e[5][7] = 1;
e[6][1] = e[6][5] = e[6][7] = 1;
e[7][2] = e[7][3] = e[7][5] = e[7][6] = 1;
dfs(1); //从第一个灯开始深搜
cout << ans ;
return 0;
}
五、二分法
例1 猜数游戏的代码
#include<bits/stdc++.h>
using namespace std;
int a[1000];
int bin_search(int *a, int n, int x){ //在数组a中找数字x，返回位置
int left = 0, right = n;
while (left < right) {
int mid = left+ (right-left)/2;
if (a[mid] >= x) right = mid;
else left = mid+1;
cout<<a[mid]<<" "; //打印猜数的过程
}
return left;
}
int main(){
int n = 100;
for(int i=0;i<n;i++) a[i]=i+1; //赋值，数字1~100
int test = 54; //猜54这个数
int pos = bin_search(a,n,test);
cout<<"\n"<<"test="<<a[pos];
return 0;
}非线性方程的求根问题
搜索法和二分法
二分法复杂度
例2 跳石头（整数二分例题）
示例
输入
25 5 2
2
11
14
17
21输出
4运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
#include<cstdio>
int len,n,m; //起点到终点的距离，起点与终点间可以放多少块石头，要抽取多少石头
int stone[50005];
bool check(int d){ //检查距离d是否合适
int num=0; //num记录搬走石头的数量
int pos=0; //当前站立的石头
for(int i=1;i<n;++i)
if(stone[i]-pos < d) num++; //第i块石头搬走
else pos = stone[i]; //第i块石头不能搬走
if(num <= m) return true; //要移动的石头比m少，满足条件
else return false; //要移动的石头比m多，不满足条件
}
int main(){
scanf("%d%d%d",&len,&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&stone[i]);
int L=0,R=len,mid;
while(L<R){
mid = L+(R-L)/2;
if(check(mid)) L = mid+1; //满足条件，说明mid小了，调大一点
else R = mid-1; //不满足条件，说明mid大了，调小一点
}
if(!check(L)) L -= 1;
printf("%d\n",L);
return 0;
}例3 青蛙过河
- 往返累计2x次相当于单向走2x次。跳跃能力越大，越能保证可以通过2x次。
- 用二分法找到一个最小的满足条件的跳跃能力。
- 设跳跃能力为mid，每次能跳多远就跳多远，用二分法检查mid是否合法。
#include<bits/stdc++.h>
using namespace std;
int h[1000005];
int n,x;
bool check(int mid){
long long sum=0;
for(int i=0;i<mid-1;i++) sum+=h[i]; //mid-1个石头的总高度
for(int i=0, j=mid-1;j<n;i++,j++) { //青蛙位置i，目标位置j
sum += h[j];
if(sum < 2*x) return false;
sum -= h[i];
}
return true;
}
int main(){
cin>>n>>x;
for(int i=1;i<n;i++) cin>>h[i];
int left=0, right=n;
while(left<right){
int mid=(left+right)/2;
if(check(mid)) right = mid;
else left = mid+1;
}
cout<<right;
return 0;
}
例4 一元三次方程求解
【暴力法】本题数据范围小，可以用暴力法模拟。一元三次方程有3个解，用暴力法，在根的范围[-100,100]内一个个试。答案只要求3个精度为2位小数的实数，那么只需要试200*100 = 20000次就行了。判断一个数是解的方法：如果函数值是连续变化的，且函数值在解的两边分别是大于0和小于0，那么解就在它们中间。例如函数值f(i)和f(j)分别大于、小于0，那么解就在[i, j]内。
【二分法】如果题目要“精确到小数点后6位”，上面的暴力法需要计算200*106次，超时了。二分法：题目给了一个很好的条件：根与根之差的绝对值大于等于1。
在每个[i, i+1]小区间内做二分查找。
#include <bits/stdc++.h>
using namespace std;
double a,b,c,d;
double y(double x){ return a*x*x*x+b*x*x+c*x+d;}
int main(){
scanf("%lf%lf%lf%lf",&a,&b,&c,&d); //输入
for (int i=-100;i<100;i++){ //题目说“根与根之差的绝对值≥1”，分为200个小区间
double left = i, right =i+1;
double y1 = y(left), y2 = y(right);
if(y1 == 0) printf("%.2lf ",left); //判断左端点。一个小坑
if(y1*y2 < 0){ //小区间内有根
for(int j = 0; j<100; j++){ //在小区间内二分100次
double mid=(left+right)/2;
if(y(mid)*y(right) <= 0)
left = mid;
else
right = mid;
}
printf("%.2lf ",right);
}
}
return 0;
}其他题目：
2 解立方根
解题思路
可以使用二分查找来求解。因为 N 最大为 10^5^，所以最大的立方根也就在 10左右。
我们可以对立方根 x进行二分，根据 x^3^ 与 N 的大小关系来缩小搜索区间。当区间足够小的时候，输出区间左端点即为答案。
注意在实现时，为了保证精度，需要将搜索区间的左右端点设置为实数。
#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
#define double long double
const double eps = 1e-12;
int main(){
int T = 1;
cin >> T;
while (T--) {
double n;
cin >> n;
double l = 0, r = 100000, res = 0;
while (l <= r) //二分法查找答案
{
double mid = (l + r) / 2;
if (fabs(mid * mid * mid - n) <= eps)//满足精度
{
res = mid;
break;
}
if (mid * mid * mid > n) r = mid - 0.0001;
else if (mid * mid * mid < n) l = mid + 0.0001, res = mid; //当满足条件不满足精度时返回一个近似值
}
cout << setprecision(3) << fixed << res << endl; //setprecision(3)函数用来保留有效数字，fixed用来防止浮点数科学计数法
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
double n;
scanf("%d",&t);
while(t--){
scanf("%lf",&n);
double l=0,r=100000,res;
while(r-l>1e-5){
double mid=(l+r)/2;
if(mid*mid*mid>=n) r=mid-0.0001;
else l=mid+0.0001,res=mid;
}
printf("%.3lf\n",res);
}
}
//自己的方法可通过示例
#include <bits/stdc++.h>
using namespace std;
int main(){
// 关闭输入输出缓存，使效率提升
ios::sync_with_stdio(false);
// 解除cin和cout的默认绑定，来降低IO的负担使效率提升
cin.tie(NULL); cout.tie(NULL);
int T; double x;
cin>>T;
while(T--){
cin>>x;
cout<<setprecision(3)<<fixed<<pow(1.0*x,0.333333333333333333)<<endl;
}
return 0;
}3 分巧克力
解题思路
先试试暴力法：把边长从 1 开始到最大边长 d，每个值都试一遍，一直试到刚好够分的最大边长为止。编码：边长初始值 d = 1，然后 d = 2, 3, 4, ⋯⋯一个个试。
下面是 C++ 的代码实现，请大家自己写一遍作为练习。
#include<bits/stdc++.h>
using namespace std;
int h[100010],w[100010];
int n,k;
bool check(int d){ //检查够不够分
int num=0;
for(int i=0;i<n;i++) num += (h[i]/d)*(w[i]/d);
if(num>=k) return true; //够分
else return false; //不够分
}
int main(){
cin >>n>>k;
for(int i=0;i<n;i++) cin>>h[i]>>w[i];
int d=1; //正方形边长
while(1){
if(check(d)) d++; //边长从1开始，一个个地暴力试
else break;
}
cout << d-1;
return 0;
}
//自己写的
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n,k;
cin>>n>>k;
int lenght[100010],wight[100010];
for(int i=0;i<n;i++){
cin>>lenght[i]>>wight[i];
}
int i=2;
for(;;i++){
int count=0;
for(int j=0;i<n;j++){
count+=(lenght[j]/i) *(wight[j]/i);
}
if(count<=k){
cout<<i<<endl;
break;
}
}
return 0;
}暴力法的复杂度：n 个长方形，长方形的最大边长 d。第 16 行 check()一次的计算量是 O(n)，需要做 d 次 check()，总复杂度 O(n×d)，而 n 和 d 的最大值是 105，超时。
一个个试边长 d 太慢了，现在使用二分，按前面的“猜数游戏”的方法猜 d 的取值。暴力法需要做 d 次 check()，现在用二分法，只需要做 O(logd)次 check()。
具体操作是：
- 第一次：开始时 d 的范围是 1~D，试试中间值 D/2，如果这个值大了，就把范围缩小为 0 ~ D/2，如果这个值小了，就把范围缩小为 D/2 ~ D；
- 第二次，取新的中间值 D/4 或 3D/4，再试⋯⋯
- ⋯⋯
直到找到合适的值为止。
#include<bits/stdc++.h>
using namespace std;
int n,k;
const int N=100010;
int h[N],w[N];
bool check(int d){
int num=0;
for(int i=0;i<n;i++) num += (h[i]/d)*(w[i]/d);
if(num>=k) return true; //够分
else return false; //不够分
}
int main(){
cin >> n >> k;
for(int i=0;i<n;i++) cin>>h[i]>>w[i];
int L=1, R=N; //D的初值是R=100010
//第一种写法：
while(L<R) {
int mid=(L+R+1)>>1; //除2，向右取整
if(check(mid)) L=mid; //新的搜索区间是右半部分，R不变，调整L=mid
else R=mid-1; //新的搜索区间是左半部分，L不变，调整R=mid–1
}
cout << L;
//第二种写法：
/* while(L<R) {
int mid=(L+R)>>1; //除2，向左取整
if(check(mid)) L=mid+1; //新的搜索区间是右半部分，R不变，更新L=mid+1
else R=mid; //新的搜索区间是左半部分，L不变，更新R=mid
}
cout << L-1; */
return 0;
}
六、贪心算法
【算法优点】
- 容易理解：生活常见
- 操作简单：在每一步都选局部最优
- 效率高：复杂度常常是O(1)的
【算法缺点】
- 缺点：局部最优不一定是全局最优
常见贪心问题
1 活动安排问题（区间调度问题）有很多电视节目，给出它们的起止时间。有些节目时间冲突。问能完整看完的电视节目最多有多少？
解题的关键在于选择什么贪心策略，才能安排尽量多的活动。由于活动有开始时间和结束时间，考虑三种贪心策略：
（1）最早开始时间。
（2）最早结束时间。
（3）用时最少。
三种贪心策略：
（1）最早开始时间：错误，因为如果一个活动迟迟不终止，后面的活动就无法开始。
（2）最早结束时间：合理，一个尽快终止的活动，可以容纳更多的后续活动。
（3）用时最少：错误。
2 区间覆盖问题 给定一个长度为n的区间，再给出m条线段的左端点（起点）和右端点（终点）。问最少用多少条线段可以将整个区间完全覆盖。
贪心策略： 尽量找出更长的线段。
解题步骤是：
（1）把每个线段按照左端点递增排序。
（2）设已经覆盖的区间是[L, R]，在剩下的线段中，找所有左端点小于等于R，且右端点最大的线段，把这个线段加入到已覆盖区间里，并更新已覆盖区间的[L, R]值。
（3）重复步骤（2），直到区间全部覆盖。
3 最优装载问题有n种药水，体积都是V，浓度不同。把它们混合起来，得到浓度不大于w%的药水。问怎么混合，才能得到最大体积的药水？注意一种药水要么全用，要么都不用，不能只取一部分。
贪心策略：要求配置浓度不大于w%的药水，
贪心思路：尽量找浓度小的药水。
先对药水按浓度从小到大排序，药水的浓度不大于w%就加入，如果药水的浓度大于w%，计算混合后总浓度，不大于w%就加入，否则结束判断。
4 多机调度问题
有n个独立的作业，由m台相同的机器进行加工。 作业i的处理时间为ti，每个作业可在任何一台机器上加工处理，但不能间断、拆分。 要求给出一种作业调度方案，在尽可能短的时间内，由m台机器加工处理完成这n个作业。
贪心策略：最长处理时间的作业优先，即把处理时间最长的作业分配给最先空闲的机器。让处理时间长的作业得到优先处理，从而在整体上获得尽可能短的处理时间。
例1 翻硬币
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
string startStr,endStr;
cin>>startStr>>endStr;
int count=0;
for(int i=0; i<startStr.size(); i++){
if(startStr[i]!=endStr[i] ){
if(i+1<startStr.size()){
startStr[i+1]= startStr[i+1]=='*'? 'o':'*';
count++;
}
else
cout<<-1;
}
}
cout<<count<<endl;
return 0;
}例2 快乐司机
【题目描述】话说现在当司机光有红心不行，还要多拉快跑。多拉不是超载，是要让所载货物价值最大，特别是在当前油价日新月异的时候。司机所拉货物为散货，如大米、面粉、沙石、泥土⋯现在知道了汽车核载重量为w，可供选择的物品的数量n。每个物品的重量为gi, 价值为pi。求汽车可装载的最大价值。（n<10000,w<10000,0<gi≤100,0≤pi≤100)。
【输入描述】输入第一行为由空格分开的两个整数n,w。第二行到第n+1行，每行有两个整数，由空格分开，分别表示gi和pi。
【输出描述】最大价值（保留一位小数）。
#include<bits/stdc++.h>
using namespace std;
double sum;
struct object{
double wg;
double va;
double scale;
}ct[10000];
bool guize(object a,object b){
return a.scale>b.scale;
};
int main(){
int n,w;
cin>>n>>w;
for(int i=0;i<n;i++) {
cin>>ct[i].wg>>ct[i].va;
ct[i].scale=ct[i].va/ct[i].wg;
}
sort(ct,ct+n,guize);
for(int i=0;i<n;i++){
if(w>=ct[i].wg){
sum+=ct[i].va;
w-=ct[i].wg;
} else{
sum+=w*ct[i].scale;
break;
}
} printf("%.1lf",sum);
return 0;
}例3 旅行家的预算？
题目描述
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离 D1、汽车油箱的容量 C（以升为单位）、每升汽油能行驶的距离 D2、出发点每升汽油价格 P 和沿途油站数 N（N 可以为零），油站 i 离出发点的距离 Di、每升汽油价格 Pi（i=1，2，⋯N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出 No Solution。
输入描述
第一行，D1，C，D2，P，N。
接下来有 N 行。
第 i+1行，两个数字，油站 i 离发点的距离 Di 和每升汽油价格 Pi。
输出描述
输出所需最小费用，计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出 No Solution。
输入输出样例
示例 1
输入
275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2输出
26.95#include <iostream>
#include <string>
using namespace std;
int main(){
double D1,C,D2,P;
int N;
cin>>D1>>C>>D2>>P>>N;
double * value = new double[N+1]; //记录第i个加油站的每升汽油价格 P
double * over = new double[N+1](); //记录到第i个加油站的时候还可以走多少公里
double * way = new double[N+2]; //记录第i个点离出发点的距离
//初始化
value[0] = P;
way[0] = 0;
double MAX = C*D2; //记录装满油的最大行驶距离
bool flag = false; //判断是否无解
for(int i = 1; i<=N; i++){
cin>>way[i]>>value[i];
if(way[i] - way[i-1]>MAX){
flag = true; //无解
}
}
if(flag){
cout<<"No Solution"<<endl;
return 0;
}
way[N+1] = D1;//终点是最后一个加油站
int i = 0;//记录当前到达的加油站
int j = 1;// 记录向后找到的比自己便宜的加油站的编号
double cost = 0;//记录费用
while(i!=N+1){//直到终点才停止
double s = 0;//记录到比自己便宜的加油站的距离
while((s<=MAX)&&(j<=N)&&(value[i] <= value[j])){ //查找比自己便宜的加油站
j++;
s = s + way[j] - way[j-1];
}
if(s<=MAX){ //是否可以一步j加油站或不中途不加油到J
if(over[i]>=way[j]-way[i]){ //在i点加不加油
over[j] = over[i]-way[j]+way[i];//在i点不加油因为够油到j点
}else{ //在i点加油到刚刚好到j点
cost = cost + (way[j]-way[i]-over[i])/D2 * value[i];
over[j] = 0; //到j点时刚刚没油
}
}else{ //到不lJ或没有找到比当前便宜的点，即在当前加满油
cost = cost + (MAX - over[i])/D2 * value[i];
j = i+1;
over[j] = MAX - (way[j] - way[i]);//记录到下一个加油站的时候还可以走多远
}
i = j;
}
printf("%.2f",cost);
return 0;
}例4 防御力
#include <bits/stdc++.h>
using namespace std;
struct nodea{int id,w;} a[100005];// A的道具//id是道具，w是这个道具的增加量
struct nodeb{int id,w;} b[100005]; // B的道具
bool cmp1(nodea a,nodea b){
if(a.w != b.w) return a.w < b.w; //先对A的增加量排序，从小到大
else return a.id < b.id; //再按字典序id排序
}
bool cmp2(nodeb a,nodeb b){ //先对B的增加量排序，从大到小
if(a.w != b.w) return a.w > b.w;
else return a.id < b.id;
}
int main(){
int n1,n2; cin >> n1 >> n2;
for(int i = 1; i <= n1; i++) cin >> a[i].w, a[i].id = i;
for(int i = 1; i <= n2; i++) cin >> b[i].w, b[i].id = i;
sort(a+1,a+n1+1,cmp1);
sort(b+1,b+n2+1,cmp2);
string s; cin >> s;
int idx1 = 1, idx2 = 1;
for(int i=0;i<s.length();i++){
if(s[i]=='1'){cout << "B"; cout << b[idx1++].id << "\n";}
else {cout << "A"; cout << a[idx2++].id << "\n";}
}
cout << "E" << "\n";
return 0;
}
// ConsoleApplication2.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
using namespace std;
using namespace chrono;
//DWORD WINAPI ThreadProc(LPVOID lpParam);
//
//int main(){
// steady_clock::time_point begin = steady_clock::now(); //计算初始时间
// Sleep(1000); //休眠2000ms s（秒）、ms（毫秒）、μs（微秒）、ns（纳秒）1s = 1000ms，1 ms = 1000μs，1μs = 1000ns
//
// steady_clock::time_point end = steady_clock::now(); //计算终止时间
// auto length = end - begin;
// cout << "扫描过程耗时: " << length.count() / 10000 << " 毫秒" << endl;
//
//
// HANDLE hThread;
// DWORD dwThreadId;
// char lpFolderPath[200] = R"(C:\Windows\)";
// WIN32_FIND_DATA FindFileData;
// HANDLE hFind;
// ULONGLONG ullTotalSize = 0;
// strcat(lpFolderPath, "*.*");
//
// hFind = FindFirstFile(lpFolderPath, &FindFileData);
// if (hFind == INVALID_HANDLE_VALUE) {
// printf("FindFirstFile failed (%d)\n", GetLastError());
// return 0;
// }
//
// do{
// if (FindFileData.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY){
// continue;
// }
//
// ULONGLONG ullFileSize = FindFileData.nFileSizeHigh;
// ullFileSize <<= sizeof(FindFileData.nFileSizeLow) * 8;
// ullFileSize |= FindFileData.nFileSizeLow;
// ullTotalSize += ullFileSize;
// } while (FindNextFile(hFind, &FindFileData) != 0);
//
// FindClose(hFind);
//
// printf("Total size of files in %s is %llu bytes.\n", lpFolderPath, ullTotalSize);
//
// hThread = CreateThread(NULL, 0, ThreadProc, &lpFolderPath, 0, &dwThreadId);
// if (hThread == NULL){
// printf("CreateThread failed (%d)\n", GetLastError());
// return 0;
// }
//
// WaitForSingleObject(hThread, INFINITE);
//
// CloseHandle(hThread);
//
// return 0;
//}
//
//DWORD WINAPI ThreadProc(LPVOID lpParam){
// LPCTSTR lpFolderPath = (LPCTSTR)lpParam;
// WIN32_FIND_DATA FindFileData;
// HANDLE hFind;
// ULONGLONG ullTotalSize = 0;
//
// hFind = FindFirstFile(lpFolderPath, &FindFileData);
// if (hFind == INVALID_HANDLE_VALUE) {
// printf("FindFirstFile failed (%d)\n", GetLastError());
// return 0;
// }
//
// do{
// if (FindFileData.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY){
// continue;
// }
//
// ULONGLONG ullFileSize = FindFileData.nFileSizeHigh;
// ullFileSize <<= sizeof(FindFileData.nFileSizeLow) * 8;
// ullFileSize |= FindFileData.nFileSizeLow;
// ullTotalSize += ullFileSize;
// } while (FindNextFile(hFind, &FindFileData) != 0);
//
// FindClose(hFind);
// printf("Total size of files in %s is %llu bytes.\n", lpFolderPath, ullTotalSize);
// return 0;
//}
void listFiles(const char * dir);
int main(){
/*char dir[200] = R"(C:\Windows\)";*/
//cout << "Enter a directory (ends with \'\\\'): ";
//cin.getline(dir, 200);
//strcat(dir, "*.*"); // 在要遍历的目录后加上通配符
string dir = R"(C:\Windows\)" ;
dir += "*.*";
listFiles(dir.c_str());
return 0;
}
void listFiles(const char * dir){
intptr_t handle;
_finddata_t findData;
handle = _findfirst(dir, &findData); // 查找目录中的第一个文件
if (handle == -1){
cout << "Failed to find first file!\n";
return;
}
do{
if (findData.attrib & _A_SUBDIR
&& strcmp(findData.name, ".") == 0
&& strcmp(findData.name, "..") == 0
) // 是否是子目录并且不为"."或".."
cout << findData.name << "\t<dir>\n";
else
cout << findData.name << "\t" << findData.size << endl;
} while (_findnext(handle, &findData) == 0); // 查找目录中的下一个文件
cout << "Done!\n";
_findclose(handle); // 关闭搜索句柄
}
//可用的遍历
#include <windows.h>
#include <tchar.h>
#include <iostream>
using namespace std;
BOOL EnumFiles(LPCTSTR lpszPath, LPCTSTR lpszType){
TCHAR szPath[MAX_PATH] = { 0 };
_stprintf(szPath, _T("%s\\%s"), lpszPath, lpszType);
WIN32_FIND_DATA FindData = { 0 };
HANDLE hFind = FindFirstFile(szPath, &FindData);
if (hFind == INVALID_HANDLE_VALUE) return FALSE;
do{
if ((FindData.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY) > 0) {
if (_tcscmp(FindData.cFileName, _T(".")) == 0 || _tcscmp(FindData.cFileName, _T("..")) == 0) continue;
//文件夹
cout << "文件夹：";
}
else
{
//文件
cout << "文件：";
}
wcout << FindData.cFileName<<" " << FindData.nFileSizeLow << endl;
} while (FindNextFile(hFind, &FindData));
return TRUE;
}
int WINAPI _tWinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPTSTR lpCmdLine, int nCmdShow){
EnumFiles(_T("C:\\Windows"), _T("*.*"));
return 0;
}
int _tmain(int argc, TCHAR* argv[]){
EnumFiles(_T("C:\\Windows"), _T("*.*"));
return 0;
}