蓝桥杯 – 第29页 – 柳婼の blog

蓝桥杯 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;

}

蓝桥杯 ADV-68 算法提高企业奖金发放

企业发放的奖金根据利润提成。利润低于或等于10万元时，奖金可提10%；利润高于10万元，低于20万元时，
低于10万元的部分按10%提成，高于10万元的部分，可提成7.5%；20万到40万之间时，高于20万元的部分，可提成5%；
40万元到60万元之间时高于40万元的部分，可提成3%；60万到100万之间时，高于60万元的部分，可提成1.5%；
高于100万元时，超过100万元的部分按1%提成。从键盘输入当月利润，求应发放奖金总数？
（保留两位小数）利润的大小在double以内
样例输入
210000
样例输出
18000.00

#include <iostream>
#include <cstdio>
using namespace std;
int main() {
    double a;
    cin >> a;
    double b = 0;
    int s[6] = {1000000, 600000, 400000, 200000, 100000, 0};
    double t[6] = {0.01, 0.015, 0.03, 0.05, 0.075, 0.1};
    for(int i = 0; i < 6; i++) {
        if(a - s[i] >= 0) {
            b += (a - s[i]) * t[i];
            a = s[i];
        }
    }
    printf("%.2f", b);
    return 0;
}

#include <iostream>

#include <cstdio>

using namespace std;

int main() {

double a;

cin >> a;

double b = 0;

int s[6] = {1000000, 600000, 400000, 200000, 100000, 0};

double t[6] = {0.01, 0.015, 0.03, 0.05, 0.075, 0.1};

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

if(a - s[i] >= 0) {

b += (a - s[i]) * t[i];

a = s[i];

}

printf("%.2f", b);

return 0;

}

蓝桥杯 ADV-62 算法提高夺宝奇兵(动态规划)

[题目描述]
　　在一座山上,有很多很多珠宝,它们散落在山底通往山顶的每条道路上,不同道路上的珠宝的数目也各不相同.下图为一张藏宝地图:

　　7
　　3 8
　　8 1 0
　　2 7 4 4
　　4 5 2 6 5

　　”夺宝奇兵”从山下出发,到达山顶,如何选路才能得到最多的珠宝呢?在上图所示例子中,按照5->7->8->3->7的顺序,将得到最大值30

[输入]
　　第一行正整数N(100>=N>1),表示山的高度
　　接下来有N行非负整数,第i行有i个整数(1<=i<=N),表示山的第i层上从左到右每条路上的珠宝数目

[输出]
　　一个整数,表示从山底到山顶的所能得到的珠宝的最大数目.
[样例输入]
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
[样例输出]
30
分析：经典的动态规划之数字三角形问题~~将输入存储入二维数组后，从上到下遍历，对于最左边的一列，等于a[i][j] += a[i-1][j];对于最右边的一列，a[i][j] += a[i-1][j-1];对于其他的中间列，等于a[i][j] += max(a[i-1][j-1], a[i-1][j]);最后看最后一行的最大值是多少，即可找到这样一条最大数目珠宝的路径~

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

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int a[101][101];

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

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

cin >> a[i][j];

}

int ans = 0;

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

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

if(j == 0)

a[i][j] += a[i-1][j];

else if(j == i)

a[i][j] += a[i-1][j-1];

else

a[i][j] += max(a[i-1][j-1], a[i-1][j]);

}

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

ans = ans > a[n-1][i] ? ans : a[n-1][i];

}

cout << ans;

return 0;

}

蓝桥杯 ADV-157 算法提高现代诗如蚯蚓

问题描述
　　现代诗如蚯蚓
　　断成好几截都不会死
　　字符串断成好几截
　　有可能完全一样
　　请编写程序
　　输入字符串
　　输出该字符串最多能断成多少截完全一样的子串
输入格式
　　一行，一个字符串
输出格式
　　一行，一个正整数表示该字符串最多能断成的截数
样例输入
abcabcabcabc
样例输出
4
样例说明
　　最多能断成四个”abc”，也就是abc重复四遍便是原串
　　同时也能断成两个”abcabc”
　　最坏情况是断成一个原串”abcabcabcabc”
数据规模和约定
　　字符串长度<=1000
分析：字串从长度为1试探到长度为len/2，判断该字串是否是重复的字串。保留长度最短的那个值，就可以求得最多能断开的个数~~~

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

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

cin >> s;

int len = s.length();

int ans = len;

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

if(len % i != 0)

continue;

int flag = 0;

string t1, t2;

t1 = s.substr(0, i);

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

t2 = s.substr(j, i);

if(t2 != t1) {

flag = 1;

break;

}

t1 = t2;

}

if(flag == 0)

ans = ans < i ? ans : i;

}

cout << len / ans;

return 0;

}

蓝桥杯 ADV-15 算法提高最大乘积

问题描述
　　对于n个数，从中取出m个数，如何取使得这m个数的乘积最大呢？
输入格式
　　第一行一个数表示数据组数
　　每组输入数据共2行：
　　第1行给出总共的数字的个数n和要取的数的个数m，1<=n<=m<=15，
　　第2行依次给出这n个数，其中每个数字的范围满足:a[i]的绝对值小于等于4。
输出格式
　　每组数据输出1行，为最大的乘积。
样例输入
1
5 5
1 2 3 4 2
样例输出
48
分析：负数要想选择，必须两个两个的选择。正数只需要一个一个选择就好~所以把数组按照从小到大排序，这样负数就在最左边，正数就在最右边啦~当还可以选择两个或者两个以上数字的时候~比较两个左边的数字相乘会不会比右边的数字相乘的结果大~如果大的话，那就选左边那两个负数~如果只能选择一个数字了，或者左边两个数的乘积不比右边两个数的乘积大~那么就选择最右边那个最大数字就好~相乘得到结果~~

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int cnt;
    cin >> cnt;
    for(int i = 0; i < cnt; i++) {
        int n, m;
        cin >> n >> m;
        int *a = new int [n];
        int ans = 1;
        for(int j = 0; j < n; j++) {
            cin >> a[j];
        }
        sort(a, a+n);
        int p = 0, q = n - 1;
        while(p <= n-1 && q >= 0 && m > 0) {
            if((a[p] * a[p+1] > a[q] * a[q-1]) && m >= 2) {
                ans = ans * (a[p] * a[p+1]);
                p += 2;
                m -= 2;
            } else {
                ans = ans * (a[q]);
                q--;
                m--;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int cnt;

cin >> cnt;

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

int n, m;

cin >> n >> m;

int *a = new int [n];

int ans = 1;

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

cin >> a[j];

}

sort(a, a+n);

int p = 0, q = n - 1;

while(p <= n-1 && q >= 0 && m > 0) {

if((a[p] * a[p+1] > a[q] * a[q-1]) && m >= 2) {

ans = ans * (a[p] * a[p+1]);

p += 2;

m -= 2;

} else {

ans = ans * (a[q]);

q--;

m--;

}

cout << ans << endl;

}

return 0;

}