蓝桥杯必刷题
目录
题目描述
设有 N×N 的方格图 (N≤9)，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 0。如下图所示（见样例）:
A
0 0 0 0 0 0 0 0
0 0 13 0 0 6 0 0
0 0 0 0 7 0 0 0
0 0 0 14 0 0 0 0
0 21 0 0 0 4 0 0
0 0 15 0 0 0 0 0
0 14 0 0 0 0 0 0
0 0 0 0 0 0 0 0
B
某人从图的左上角的 A 点出发，可以向下行走，也可以向右走，直到到达右下角的 B 点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字 0）。
此人从 A 点到 B 点共走两次，试找出 2 条这样的路径，使得取得的数之和为最大。
输入格式
输入的第一行为一个整数 N（表示 N×N 的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的 0 表示输入结束。
输出格式
只需输出一个整数，表示 2 条路径上取得的最大的和。
输入输出样例
输入
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
输出
67
01背包问题：
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8#include <iostream>
using namespace std;
int n,m;
int ti[1005];
int jia[1005];
int ans[1005][1005];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>ti[i]>>jia[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ans[i][j]=ans[i-1][j]; //不选i
if(j>=ti[i]){
ans[i][j]=max(ans[i-1][j],ans[i-1][j-ti[i]]+jia[i]);
} //当总背包体积大于该物品体积时可以选
}
}
cout<<ans[n][m];
return 0;
}
完全背包问题：
有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行两个整数vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
10
#include <iostream>
using namespace std;
int n,m;
int ti[1005];
int jia[1005];
int ans[1005][1005];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>ti[i]>>jia[i];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(j>=ti[i]){
ans[i][j]=max(ans[i-1][j],ans[i][j-ti[i]]+jia[i]);
}else{
ans[i][j]=ans[i-1][j]; //不选i
}
}
}
cout<<ans[n][m];
return 0;
}
传纸条：
题目描述
小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排坐成一个 m 行 n 列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标 (1,1)，小轩坐在矩阵的右下角，坐标 (m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。
在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。
还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用 0 表示），可以用一个 [0,100] 内的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度之和最大。现在，请你帮助小渊和小轩找到这样的两条路径。
输入格式
第一行有两个用空格隔开的整数 m 和 n，表示班里有 m 行 n 列。
接下来的 m 行是一个 m×n 的矩阵，矩阵中第 i 行 j列的整数表示坐在第 i 行 j 列的学生的好心程度。每行的 nn 个整数之间用空格隔开。
输出格式
输出文件共一行一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。
输入输出样例
输入 #1复制
3 3
0 3 9
2 8 5
5 7 0
输出
34说明/提示
【数据范围】
对于 30% 的数据，满足 1≤m,n≤10。
对于 1100% 的数据，满足1≤m,n≤50。
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int m,n;
int dp[55][55][55][55];
int zhi[55][55];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>m>>n;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
cin>>zhi[i][j];
}
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
for(int l=1;l<=m;l++){
for(int r=1;r<=n;r++){
if(i==l&&j==r){
continue;
}
dp[i][j][l][r]=max(max(dp[i-1][j][l-1][r],dp[i-1][j][l][r-1]),max(dp[i][j-1][l-1][r],dp[i][j-1][l][r-1]))+zhi[i][j]+zhi[l][r];
}
}
}
}
cout<<dp[m][n-1][m-1][n];
return 0;
}
独木桥
题目背景
战争已经进入到紧要时间。你是运输小队长，正在率领运输部队向前线运送物资。运输任务像做题一样的无聊。你希望找些刺激，于是命令你的士兵们到前方的一座独木桥上欣赏风景，而你留在桥下欣赏士兵们。士兵们十分愤怒，因为这座独木桥十分狭窄，只能容纳 11 个人通过。假如有 2 个人相向而行在桥上相遇，那么他们 22 个人将无法绕过对方，只能有 11 个人回头下桥，让另一个人先通过。但是，可以有多个人同时呆在同一个位置。
题目描述
突然，你收到从指挥部发来的信息，敌军的轰炸机正朝着你所在的独木桥飞来！为了安全，你的部队必须撤下独木桥。独木桥的长度为 LL，士兵们只能呆在坐标为整数的地方。所有士兵的速度都为 1，但一个士兵某一时刻来到了坐标为 0 或 L+1 的位置，他就离开了独木桥。
每个士兵都有一个初始面对的方向，他们会以匀速朝着这个方向行走，中途不会自己改变方向。但是，如果两个士兵面对面相遇，他们无法彼此通过对方，于是就分别转身，继续行走。转身不需要任何的时间。
由于先前的愤怒，你已不能控制你的士兵。甚至，你连每个士兵初始面对的方向都不知道。因此，你想要知道你的部队最少需要多少时间就可能全部撤离独木桥。另外，总部也在安排阻拦敌人的进攻，因此你还需要知道你的部队最多需要多少时间才能全部撤离独木桥。
输入格式
第一行共一个整数 L，表示独木桥的长度。桥上的坐标为 1,2,⋯,L。
第二行共一个整数 N，表示初始时留在桥上的士兵数目。
第三行共有 N 个整数，分别表示每个士兵的初始坐标。
输出格式
共一行，输出 22个整数，分别表示部队撤离独木桥的最小时间和最大时间。2 个整数由一个空格符分开。
输入输出样例
输入 #1复制
4
2
1 3
输出 #1复制
2 4说明/提示
对于 100% 的数据，满足初始时，没有两个士兵同在一个坐标，1\1≤L≤5×103，0≤N≤5×103，且数据保证 N≤L。
#include <iostream>
#include <algorithm>
using namespace std;
int l,n;
int a[5005];
int ansx,ansd;
int xiao,da;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>l>>n;
if(l==0 || n==0){
cout<<0<<' '<<0;
return 0;
}
xiao=1e8;
for(int i=1;i<=n;i++){
cin>>a[i];
int y=max(a[i]-1,l-a[i]);
ansd=max(ansd,y);
int x=min(a[i]-1,l-a[i]);
ansx=max(ansx,x);
}
cout<<ansx+1<<' '<<ansd+1;
return 0;
}幂次方：
题目描述
任何一个正整数都可以用 22 的幂次方表示。例如 137=2^7+2^3+2^0137=27+23+20。
同时约定方次用括号来表示，即 ab 可表示为a(b)。
由此可知，137137 可表示为 2(7)+2(3)+2(0)2(7)+2(3)+2(0)
进一步：
7= 2+2+20 ( 2 用 2 表示)，并且 3=2+20。
所以最后 137137 可表示为 2(2(2)+2+2(0))+2(2+2(0))+2(0)。
又如 1315=210+28+25+2+1
所以 13151315 最后可表示为 2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)。
输入格式
一行一个正整数 n。
输出格式
符合约定的 n 的 0,2 表示（在表示中不能有空格）。
输入输出样例
输入
1315输出
2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)说明/提示
【数据范围】
对于 100% 的数据，1≤n≤2×104。
#include <iostream>
using namespace std;
int a[16];
int n;
void dayin(int x){
int k=0;
for(k=14;k>=0;k--){
if(a[k]<=x){
break;
}
}
if(k==0){
cout<<"2(0)";
}else if(k==1){
cout<<"2";
}else{
cout<<"2(";
dayin(k);
cout<<")";
}
if(a[k]<x){
cout<<"+";
dayin(x-a[k]);
}
}
int main(){
cin>>n;
a[0]=1;
for(int i=1;i<=14;i++){
a[i]=2*a[i-1];
}
dayin(n);
return 0;
}
车站：
题目描述
火车从始发站（称为第 1 站）开出，在始发站上车的人数为 a，然后到达第 2 站，在第 2 站有人上、下车，但上、下车的人数相同，因此在第 2 站开出时（即在到达第 3 站之前）车上的人数保持为 a 人。从第 3 站起（包括第 3 站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第 (n−1) 站），都满足此规律。现给出的条件是：共有 n个车站，始发站上车的人数为 a ，最后一站下车的人数是 m（全部下车）。试问 x 站开出时车上的人数是多少？
输入格式
输入只有一行四个整数，分别表示始发站上车人数 a，车站数 n，终点站下车人数 m 和所求的站点编号 x。
输出格式
输出一行一个整数表示答案：从 x 站开出时车上的人数。
输入输出样例
输入
5 7 32 4
输出
13
说明/提示
对于全部的测试点，保证1≤a≤20，1≤x≤n≤20，1≤m≤2×104。
#include <iostream>
using namespace std;
int a,n,m,x;
int as[25];
int bs[25];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>a>>n>>m>>x; //起始a，n个车站，m下车
as[1]=as[2]=1;
as[3]=2;
for(int i=4;i<=20;i++){
as[i]=as[i-1]+as[i-2]-1;
}
bs[1]=bs[2]=bs[3]=0;
bs[4]=1;
for(int i=4;i<=20;i++){
bs[i]=bs[i-1]+bs[i-2]+1;
}
int b=0;
for(int i=1;i<=20;i++){
if(as[n-1]*a+bs[n-1]*i==m){
b=i;
break;
}
}
cout<<as[x]*a+bs[x]*b;
return 0;
}
拼数：
题目描述
设有 n 个正整数 a1…an，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。
输入格式
第一行有一个整数，表示数字个数 n。
第二行有 n 个整数，表示给出的 n 个整数 ai。
输出格式
一个正整数，表示最大的整数
输入输出样例
输入 #1复制
3
13 312 343
输出
34331213
输入
4
7 13 4 246输出
7424613说明/提示
对于全部的测试点，保证 1≤n≤20，11≤ai≤109。
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string s[21];int n;
bool cmp(string a,string b) { // &表示引用
return (a+b > b+a);
}
int main(void) {
cin >> n;
for(int i=1;i<=n;++i) cin >> s[i];
sort(s+1,s+n+1,cmp);
for (int i=1;i<=n;++i) cout << s[i];
return 0;
}#include <iostream>
#include <algorithm>
using namespace std;
int n;
string a[25];
bool b[25];
bool check(string a,string b){
if(a.compare(b)!=-1){
return true;
}else{
return false;
}
}
void kuaipai(string a[],int l,int r){
if(l>=r){
return;
}
string k=a[r];
int i=l,j=r;
while(i<j){
while(i<j&&a[i]<=k) i++;
a[j]=a[i];
while(i<j&&a[j]>=k) j--;
a[i]=a[j];
}
a[i]=k;
kuaipai(a,i+1,r);
kuaipai(a,l,i-1);
}
int main(){
cin>>n;
if(n==0){
cout<<0;
return 0;
}
string c="";
for(int i=0;i<n;i++){
cin>>a[i];
c+=a[i]+'0';
}
int len=c.size();
kuaipai(a,0,n-1);
string ans;
for(int i=n-1;i>=0;i--){
ans+=a[i];
}
cout<<ans;
return 0;
}
排序：
小蓝最近学习了一些排序算法，其中冒泡排序让他印象深刻。
在冒泡排序中，每次只能交换相邻的两个元素。
小蓝发现，如果对一个字符串中的字符排序，只允许交换相邻的两个字符， 则在所有可能的排序方案中，冒泡排序的总交换次数是最少的。
例如，对于字符串 lanlan 排序，只需要 11 次交换。对于字符串 qiao 排序，总共需要 44 次交换。
小蓝找到了很多字符串试图排序，他恰巧碰到一个字符串，需要 100次交 换，可是他忘了吧这个字符串记下来，现在找不到了。
请帮助小蓝找一个只包含小写英文字母且没有字母重复出现的字符串，对 该串的字符排序，正好需要 100 次交换。如果可能找到多个，请告诉小蓝最短的那个。如果最短的仍然有多个，请告诉小蓝字典序最小的那个。
运行限制
- 最大运行时间：1s
#include <iostream>
using namespace std;
int main()
{
//考虑冒泡排序的复杂度，对于拥有N个字母的字符串，最多需要交换N*(N-1)/2次（完全乱序时）
//易知N=15时，有15*14/2=105，即满足100次交换所需的最短字符串有15个字母。
//要求字典序最小，那么显然要取a~o这15个字典序最小的字母
/*
逆向思考，目标字符串经过100次交换后，得到正序字符串abcdefghijklmno，而完全逆序的字符串onmlkjihgfedcba变成正序字符串需要105次交换，那么将完全逆序的字符串交换5次后，便能得到答案。
而要求字典序最小，那么将j交换5次提到字符串最前面，就得到了最小的情况
*/
printf("jonmlkihgfedcba");
return 0;
}数字三角形：
题目描述
上图给出了一个数字三角
形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。
路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。
输入描述
输入的第一行包含一个整数 (1≤N≤100)，表示三角形的行数。
下面的 NN 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。
输出描述
输出一个整数，表示答案。
输入输出样例
示例
输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出
27
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int a[105][105];
int n;
int dp[105][105];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
cin>>a[i][j];
}
}
int floge=0;
dp[1][1]=a[1][1];
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];
}
}
cout<<max(dp[n][(n+1)/2],dp[n][(n+2)/2]);
return 0;
}递增序列：
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
对于一个字母矩阵，我们称矩阵中的一个递增序列是指在矩阵中找到两个字母，它们在同一行，同一列，或者在同一 4545 度的斜线上，这两个字母从左向右看、或者从上向下看是递增的。
例如，如下矩阵中
LANN
QIAO
有LN、LN、AN、AN、IO、AO、LQ、AI、NO、NO、AQ、IN、ANLN、LN、AN、AN、IO、AO、LQ、AI、NO、NO、AQ、IN、AN 等 13 个 递增序列。注意当两个字母是从左下到右上排列时，从左向右看和从上向下看 是不同的顺序。
对于下面的 30行 50 列的矩阵，请问总共有多少个递增序列？
VLPWJVVNNZSWFGHSFRBCOIJTPYNEURPIGKQGPSXUGNELGRVZAG
SDLLOVGRTWEYZKKXNKIRWGZWXWRHKXFASATDWZAPZRNHTNNGQF
ZGUGXVQDQAEAHOQEADMWWXFBXECKAVIGPTKTTQFWSWPKRPSMGA
BDGMGYHAOPPRRHKYZCMFZEDELCALTBSWNTAODXYVHQNDASUFRL
YVYWQZUTEPFSFXLTZBMBQETXGXFUEBHGMJKBPNIHMYOELYZIKH
ZYZHSLTCGNANNXTUJGBYKUOJMGOGRDPKEUGVHNZJZHDUNRERBU
XFPTZKTPVQPJEMBHNTUBSMIYEGXNWQSBZMHMDRZZMJPZQTCWLR
ZNXOKBITTPSHEXWHZXFLWEMPZTBVNKNYSHCIQRIKQHFRAYWOPG
MHJKFYYBQSDPOVJICWWGGCOZSBGLSOXOFDAADZYEOBKDDTMQPA
VIDPIGELBYMEVQLASLQRUKMXSEWGHRSFVXOMHSJWWXHIBCGVIF
GWRFRFLHAMYWYZOIQODBIHHRIIMWJWJGYPFAHZZWJKRGOISUJC
EKQKKPNEYCBWOQHTYFHHQZRLFNDOVXTWASSQWXKBIVTKTUIASK
PEKNJFIVBKOZUEPPHIWLUBFUDWPIDRJKAZVJKPBRHCRMGNMFWW
CGZAXHXPDELTACGUWBXWNNZNDQYYCIQRJCULIEBQBLLMJEUSZP
RWHHQMBIJWTQPUFNAESPZHAQARNIDUCRYQAZMNVRVZUJOZUDGS
PFGAYBDEECHUXFUZIKAXYDFWJNSAOPJYWUIEJSCORRBVQHCHMR
JNVIPVEMQSHCCAXMWEFSYIGFPIXNIDXOTXTNBCHSHUZGKXFECL
YZBAIIOTWLREPZISBGJLQDALKZUKEQMKLDIPXJEPENEIPWFDLP
HBQKWJFLSEXVILKYPNSWUZLDCRTAYUUPEITQJEITZRQMMAQNLN
DQDJGOWMBFKAIGWEAJOISPFPLULIWVVALLIIHBGEZLGRHRCKGF
LXYPCVPNUKSWCCGXEYTEBAWRLWDWNHHNNNWQNIIBUCGUJYMRYW
CZDKISKUSBPFHVGSAVJBDMNPSDKFRXVVPLVAQUGVUJEXSZFGFQ
IYIJGISUANRAXTGQLAVFMQTICKQAHLEBGHAVOVVPEXIMLFWIYI
ZIIFSOPCMAWCBPKWZBUQPQLGSNIBFADUUJJHPAIUVVNWNWKDZB
HGTEEIISFGIUEUOWXVTPJDVACYQYFQUCXOXOSSMXLZDQESHXKP
FEBZHJAGIFGXSMRDKGONGELOALLSYDVILRWAPXXBPOOSWZNEAS
VJGMAOFLGYIFLJTEKDNIWHJAABCASFMAKIENSYIZZSLRSUIPCJ
BMQGMPDRCPGWKTPLOTAINXZAAJWCPUJHPOUYWNWHZAKCDMZDSR
RRARTVHZYYCEDXJQNQAINQVDJCZCZLCQWQQIKUYMYMOVMNCBVY
ABTCRRUXVGYLZILFLOFYVWFFBZNFWDZOADRDCLIRFKBFBHMAXX
运行限制
- 最大运行时间：1s
- 最大运行内存: 128M
#include <iostream>
#include <cmath>
using namespace std;
int ans;
char a[35][55];
int main(){
for(int i=0;i<30;i++){
for(int j=0;j<50;j++){
cin>>a[i][j];
}
}
for(int i=0;i<30;i++){
for(int j=0;j<50;j++){
for(int x=0;x<30;x++){
for(int y=0;y<50;y++){
if(i==x && j==y){
continue;
}
int c=abs(i-x);
if(i==x && a[i][j]<a[x][y] && y>j){
ans++;
}
if(j==y && a[i][j]<a[x][y] && x>i) {
ans++;
}
if(i+j==x+y && x>i && a[i][j]!=a[x][y]){
ans++;
}
if(j+c==y && x>i&&a[i][j]<a[x][y]){
ans++;
}
}
}
}
}
cout<<ans;
return 0;
}
- 点赞
- 收藏
- 关注作者
评论（0）