Code – 第229页

蓝桥杯 ADV-146 算法提高计算器

【问题描述】
　　王小二的计算器上面的LED显示屏坏掉了，于是他找到了在计算器维修与应用系学习的你来为他修计算器。
　　屏幕上可以显示0~9的数字，其中每个数字由7个小二极管组成，各个数字对应的表示方式如图所示：

　　为了排除电路故障，现在你需要计算，将数字A变为数字B需要经过多少次变换？
　　注意：现在将其中每段小二极管的开和关都定义为一次变换。例如数字1变为2是5次操作。

【输入格式】
　　第一行为一个正整数L，表示数码的长度。
　　接下来两行是两个长度为L的数字A和B，表示要把数字A变成数字B（数字可以以0开头）。
【输出格式】
　一行一个整数，表示这些小二极管一共要变换多少次。
【样例输入1】
3
101
025
【样例输出1】
12
【样例输入2】
8
19920513
20111211
【样例输出2】
27
【数据范围】
L<=100

#include <iostream>
using namespace std;
int main() {
    int a[10][10] = {
        {0, 4, 3, 3, 4, 3, 2, 3, 1, 2},
        {4, 0, 5, 3, 2, 5, 6, 1, 5, 4},
        {3, 5, 0, 2, 5, 4, 3, 4, 2, 3},
        {3, 3, 2, 0, 3, 2, 3, 2, 2, 1},
        {4, 2, 5, 3, 0, 3, 4, 3, 3, 2},
        {3, 5, 4, 2, 3, 0, 1, 4, 2, 1},
        {2, 6, 3, 3, 4, 1, 0, 5, 1, 2},
        {3, 1, 4, 2, 3, 4, 5, 0, 4, 3},
        {1, 5, 2, 2, 3, 2, 1, 4, 0, 1},
        {2, 4, 3, 1, 2, 1, 2, 3, 1, 0}
    };
    int n;
    cin >> n;
    string s, m;
    cin >> s >> m;
    int cnt = 0;
    for(int i = 0; i < n; i++) {
        cnt += a[s[i] - '0'][m[i] - '0'];
    }
    cout << cnt;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a[10][10] = {

{0, 4, 3, 3, 4, 3, 2, 3, 1, 2},

{4, 0, 5, 3, 2, 5, 6, 1, 5, 4},

{3, 5, 0, 2, 5, 4, 3, 4, 2, 3},

{3, 3, 2, 0, 3, 2, 3, 2, 2, 1},

{4, 2, 5, 3, 0, 3, 4, 3, 3, 2},

{3, 5, 4, 2, 3, 0, 1, 4, 2, 1},

{2, 6, 3, 3, 4, 1, 0, 5, 1, 2},

{3, 1, 4, 2, 3, 4, 5, 0, 4, 3},

{1, 5, 2, 2, 3, 2, 1, 4, 0, 1},

{2, 4, 3, 1, 2, 1, 2, 3, 1, 0}

};

int n;

cin >> n;

string s, m;

cin >> s >> m;

int cnt = 0;

for(int i = 0; i < n; i++) {

cnt += a[s[i] - '0'][m[i] - '0'];

}

cout << cnt;

return 0;

}

问题描述
　　大家都知道”超级玛丽”是一个很善于跳跃的探险家，他的拿手好戏是跳跃，但它一次只能向前跳一步或两步。有一次，他要经过一条长为n的羊肠小道，小道中有m个陷阱，这些陷阱都位于整数位置，分别是a1,a2,….am，陷入其中则必死无疑。显然，如果有两个挨着的陷阱，则玛丽是无论如何也跳过不去的。
　　现在给出小道的长度n，陷阱的个数及位置。求出玛丽从位置1开始，有多少种跳跃方法能到达胜利的彼岸（到达位置n）。
输入格式
　　第一行为两个整数n,m
　　第二行为m个整数，表示陷阱的位置
输出格式
　　一个整数。表示玛丽跳到n的方案数
样例输入
4 1
2
样例输出
1
数据规模和约定
　　40>=n>=3,m>=1
　　n>m;
　　陷阱不会位于1及n上

分析：和leetcode上面那道爬楼梯问题类似，但是要注意的是，爬楼梯是爬n的长度，而这里是从1出发到n，只要走n-1的长度，所以是初始化v[1] = 1, v[2]处如果没陷阱就是1，有陷阱就是0，然后根据状态转移方程v[i] = v[i-1] + v[i-2];求得v[n]的值即为种类个数~~~

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> v(n+1, -1);
    for(int i = 0; i < m; i++) {
        int temp;
        cin >> temp;
        v[temp] = 0;
    }
    v[1] = 1;
    v[2] = v[2] == 0 ? v[2] : 1;
    for(int i = 3; i <= n; i++) {
        if(v[i] != 0)
            v[i] = v[i-1] + v[i-2];
    }
    cout << v[n];
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

int n, m;

cin >> n >> m;

vector<int> v(n+1, -1);

for(int i = 0; i < m; i++) {

int temp;

cin >> temp;

v[temp] = 0;

}

v[1] = 1;

v[2] = v[2] == 0 ? v[2] : 1;

for(int i = 3; i <= n; i++) {

if(v[i] != 0)

v[i] = v[i-1] + v[i-2];

}

cout << v[n];

return 0;

}

蓝桥杯 ADV-166 算法提高聪明的美食家

问题描述
　　如果有人认为吃东西只需要嘴巴，那就错了。
　　都知道舌头有这么一个特性，“由简入奢易，由奢如简难”（据好事者考究，此规律也适合许多其他情况）。具体而言，如果是甜食，当你吃的食物不如前面刚吃过的东西甜，就很不爽了。
　　大宝是一个聪明的美食家，当然深谙此道。一次他来到某小吃一条街，准备从街的一头吃到另一头。为了吃得爽，他大费周章，得到了各种食物的“美味度”。他拒绝不爽的经历，不走回头路而且还要爽歪歪（爽的次数尽量多）。
输入格式
　　两行数据。
　　第一行Z为一个整数n，表示小吃街上小吃的数量
　　第二行为n个整数，分别表示n种食物的“美味度”
输出格式
　　一个整数，表示吃得爽的次数
样例输入
10
3 18 7 14 10 12 23 41 16 24
样例输出
6
数据规模和约定
　　美味度为0到100的整数
　　n<1000
分析：求最长不降子序列~用动态规划解决~建立一个与序列等长的数组b~b[i]表示当前i处能够构成的最长不降子序列的长度~
所以说当前b[i]的值为前面所有数字比i处数字小的长度的最大值+1~
最后返回整个b数组中的最大值~~

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int *a = new int [n];
    int *b = new int [n];
    for(int i = 0; i < n; i++)
        cin >> a[i];
    b[0] = 1;
    int ans = 1;
    for(int i = 0; i < n; i++) {
        int maxvalue = 0;
        for(int j = i-1; j >= 0; j--) {
            if(a[i] >= a[j])
                maxvalue = max(maxvalue, b[j]);
        }
        b[i] = maxvalue + 1;
        ans = max(ans, b[i]);
    }
    cout << ans;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int *a = new int [n];

int *b = new int [n];

for(int i = 0; i < n; i++)

cin >> a[i];

b[0] = 1;

int ans = 1;

for(int i = 0; i < n; i++) {

int maxvalue = 0;

for(int j = i-1; j >= 0; j--) {

if(a[i] >= a[j])

maxvalue = max(maxvalue, b[j]);

}

b[i] = maxvalue + 1;

ans = max(ans, b[i]);

}

cout << ans;

return 0;

}

蓝桥杯 ADV-150 算法提高周期字串

问题描述
　　右右喜欢听故事，但是右右的妈妈总是讲一些“从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事，讲的什么呢？从前有座山……”这样循环的故事来搪塞右右。
　　我们定义，如果一个字符串是以一个或者一个以上的长度为k的重复字符串所连接成的，那么这个字符串就叫做周期为k的串。
　　例如:
　　字符串’abcabcabcabc’周期为3，因为它是由4个循环’abc’组成的。它同样是以6为周期（两个重复的’abcabc’）和以12为周期（一个循环’abcabcabcabc’）。
　　右右现在想给他的朋友大灰狼转述妈妈讲的故事，请帮他写一个程序，可以测定一个字符串的最小周期。
输入格式
　　一个最大长度为100的无空格的字符串。
输出格式
　　一个整数，表示输入的字符串的最小周期。
样例输入
HaHaHa
样例输出
2
样例输入
Return0
样例输出
7
分析：从长度为1一直到长度为len/2判断是否满足周期~不满足的话就说明周期是字符串本身的长度~~

#include <iostream>
#include <string>
using namespace std;
int main() {
	string s;
	int len = s.length();
	for(int i = 1; i <= len / 2; i++) {
		int flag = 0;
		if(len % i != 0)
			continue;
		string t1 = s.substr(0, i);
		string t2;
		for(int j = i; j < len; j = j + i) {
			t2 = s.substr(j, i);
			if(t1 != t2) {
				flag = 1;
				break;
			}
		}
		if(flag == 0) {
			cout << i;
			return 0;
		}
	}
	cout << len;
	return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

int len = s.length();

for(int i = 1; i <= len / 2; i++) {

int flag = 0;

if(len % i != 0)

continue;

string t1 = s.substr(0, i);

string t2;

for(int j = i; j < len; j = j + i) {

t2 = s.substr(j, i);

if(t1 != t2) {

flag = 1;

break;

}

if(flag == 0) {

cout << i;

return 0;

}

cout << len;

return 0;

}

蓝桥杯 ADV-167 算法提高快乐司机（贪心算法）

问题描述
　　”嘟嘟嘟嘟嘟嘟
　　喇叭响
　　我是汽车小司机
　　我是小司机
　　我为祖国运输忙
　　运输忙”
　　这是儿歌“快乐的小司机”。话说现在当司机光有红心不行，还要多拉快跑。多拉不是超载，是要让所载货物价值最大，特别是在当前油价日新月异的时候。司机所拉货物为散货，如大米、面粉、沙石、泥土……
　　现在知道了汽车核载重量为w，可供选择的物品的数量n。每个物品的重量为gi,价值为pi。求汽车可装载的最大价值。（n<10000,w<10000,0<gi<=100,0<=pi<=100)
输入格式
　　输入第一行为由空格分开的两个整数n w
　　第二行到第n+1行，每行有两个整数，由空格分开，分别表示gi和pi
输出格式
　　最大价值（保留一位小数）
样例输入
5 36
99 87
68 36
79 43
75 94
7 35
样例输出
71.3
解释：
先装第5号物品，得价值35，占用重量7
再装第4号物品，得价值36.346,占用重量29
最后保留一位小数，得71.3
分析：贪心算法，因为可以装取一部分的货物，所以每次选择(价值/数量)最大的那个货物即可~~先按照除得的单价从大到小排序，然后按照能装载的最大限度从左到右依次装载货物，直到装不下为止~~

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct node {
    int a;
    int b;
    double c;
};
int cmp1(node t1, node t2) {
    return t1.c > t2.c;
}
int main() {
    int n, w;
    cin >> n >> w;
    node *arr = new node [n];
    for(int i = 0; i < n; i++) {
        cin >> arr[i].a >> arr[i].b;
        arr[i].c =arr[i].b *1.0 / arr[i].a;
    }
    sort(arr, arr+n, cmp1);
    double ans = 0.0;
    int j = 0;
    while(w > 0) {
        if(arr[j].a < w) {
            w = w - arr[j].a;
            ans = ans + arr[j].b;
        } else {
            ans = ans + w * 1.0 / arr[j].a * arr[j].b;
            w = 0;
        }
        j++;
    }
    printf("%.1f", ans);
    return 0;
}

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

struct node {

int a;

int b;

double c;

};

int cmp1(node t1, node t2) {

return t1.c > t2.c;

}

int main() {

int n, w;

cin >> n >> w;

node *arr = new node [n];

for(int i = 0; i < n; i++) {

cin >> arr[i].a >> arr[i].b;

arr[i].c =arr[i].b *1.0 / arr[i].a;

}

sort(arr, arr+n, cmp1);

double ans = 0.0;

int j = 0;

while(w > 0) {

if(arr[j].a < w) {

w = w - arr[j].a;

ans = ans + arr[j].b;

} else {

ans = ans + w * 1.0 / arr[j].a * arr[j].b;

w = 0;

}

j++;

}

printf("%.1f", ans);

return 0;

}

蓝桥杯 ADV-66 算法提高阮小二买彩票

问题描述
　　在同学们的帮助下，阮小二是变的越来越懒了，连算账都不愿意自己亲自动手了，每天的工作就是坐在电脑前看自己的银行账户的钱是否有变多。可是一段时间观察下来，阮小二发现自己账户的钱增长好慢啊，碰到节假日的时候连个铜板都没进，更郁闷的是这些天分文不进就算了，可恨的是银行这几天还有可能“落井下石”(代扣个人所得税)，看着自己账户的钱被负增长了，阮小二就有被割肉的感觉(太痛苦了！)，这时阮小二最大的愿望无疑是以最快的速度日进斗金，可什么方法能够日进斗金呢？抢银行(老本行)？不行，太危险，怕有命抢没命花；维持现状？受不了，搂钱太慢了！想来想去，抓破脑袋之后，终于想到了能快速发家致富的法宝—-买彩票，不但挣了钱有命花，运气好的话，可以每天中他个几百万的，岂不爽哉！抱着这种想法，阮小二开始了他的买彩票之旅。想法是“好的”（太天真了OR 太蠢了），可是又发现自己的数学功底太差，因为不知道数字都有哪些组合排列？那现在就请同学们写个递归程序，帮助阮小二解决一下这个问题吧！
输入格式
　　不超过6位数的正整数N，注意：构成正整数N的数字可重复
输出格式
　　组成正整数N的所有位数的全排列，这些排列按升序输出，每个排列占一行。

注意：输出数据中不能有重复的排列
样例输入
123
样例输出
123
132
213
231
312
321
样例输入
3121
样例输出
1123
1132
1213
1231
1312
1321
2113
2131
2311
3112
3121
3211
样例输入
4003
样例输出
0034
0043
0304
0340
0403
0430
3004
3040
3400
4003
4030
4300

分析：用next_permutation(s.begin(), s.end())输出s字符串的全排列~~在头文件<algorithm>里面~~~//要不是你因为好用，谁愿意记住辣么长的单词- -||

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    string s;
    cin >> s;
    int len = s.length();
    sort(s.begin(), s.end());
    do {
        cout << s << endl;
    }while(next_permutation(s.begin(), s.end()));
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

string s;

cin >> s;

int len = s.length();

sort(s.begin(), s.end());

do {

cout << s << endl;

}while(next_permutation(s.begin(), s.end()));

return 0;

}

分类： Code

蓝桥杯 ADV-146 算法提高计算器

蓝桥杯 ADV-165 算法提高超级玛丽（动态规划、递推）

蓝桥杯 ADV-166 算法提高聪明的美食家

蓝桥杯 ADV-150 算法提高周期字串

蓝桥杯 ADV-167 算法提高快乐司机（贪心算法）

蓝桥杯 ADV-66 算法提高阮小二买彩票