Code – 第230页

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

}

取消c++所设置的cout中setprecision输出的格式

C++11中可以这样写：

std::cout << std::defaultfloat;

1	std::cout << std::defaultfloat;

C++11以前是这样写的：

std::cout.unsetf(std::ios_base::floatfield);

1	std::cout.unsetf(std::ios_base::floatfield);

蓝桥杯 ADV-94 算法提高复数归一化

编写函数Normalize，将复数归一化，即若复数为a+bi，归一化结果为a/sqrt(a*a+b*b) + i*b/sqrt(a*a+b*b) 。使用结构体指针类型作为函数参数可能是必要的。其中实部和虚部由键盘输入，输出为归一化结果，如果归一化结果的实部或虚部为小数的要求保留一位小数。
样例输入:（格式说明：3 4 分别为以空格隔开的实数的实部和虚部）
3 4
样例输出:
0.6+0.8i
样例输入:
2 5
样例输出:
0.4+0.9i
分析：没什么好分析的耶。。

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
int main() {
    double a, b;
    double p, q;
    cin >> a >> b;
    p = a / sqrt(a * a + b * b);
    q = b / sqrt(a * a + b * b);
    cout << setprecision(1) << p;
    if(q > 0) {
        cout << "+";
        cout << setprecision(1) << q;
        cout.unsetf(ios_base::floatfield);
        cout << "i";
    } else if(q < 0) {
        cout << setprecision(1) << q;
        cout.unsetf(ios_base::floatfield);
        cout << "i";
    }
    return 0;
}

#include <iostream>

#include <cmath>

#include <iomanip>

using namespace std;

int main() {

double a, b;

double p, q;

cin >> a >> b;

p = a / sqrt(a * a + b * b);

q = b / sqrt(a * a + b * b);

cout << setprecision(1) << p;

if(q > 0) {

cout << "+";

cout << setprecision(1) << q;

cout.unsetf(ios_base::floatfield);

cout << "i";

} else if(q < 0) {

cout << setprecision(1) << q;

cout.unsetf(ios_base::floatfield);

cout << "i";

}

return 0;

}