liuchuo – 第231页 – 我不管，反正我最萌～

蓝桥杯 ADV-136 算法提高大数加法

问题描述
　　输入两个正整数a,b，输出a+b的值。
输入格式
　　两行，第一行a，第二行b。a和b的长度均小于1000位。
输出格式
　　一行，a+b的值。
样例输入
4
2
样例输出
6

分析：用两个指针一起从后往前加两个字符串，用carry变量表示进位，如果最后还有进位就还要再加1.

include <iostream>
using namespace std;
int main() {
    string a, b;
    cin >> a >> b;
    char ans[1001];
    int p = a.length() - 1;
    int q = b.length() - 1;
    int carry = 0;
    int i = 0;
    while(p != -1 && q != -1) {
        int ta = a[p] - '0';
        int tb = b[q] - '0';
        if(ta + tb + carry >= 10) {
            ans[i++] = (char)(ta + tb + carry - 10 + '0');
             carry = 1;
        } else {
            ans[i++] = (char)(ta + tb + carry + '0');
            carry = 0;
        }
        p--;
        q--;
    }
    while(p != -1) {
        int ta = a[p] - '0';
        if(ta + carry >= 10) {
            ans[i++] = (char)(ta + carry - 10 + '0');
            carry = 1;
        } else {
            ans[i++] = (char)(ta + carry + '0');
            carry = 0;
        }
        p--;
    }
    while(q != -1) {
        int tb = b[q] - '0';
        if(tb + carry >= 10) {
            ans[i++] = (char)(tb + carry - 10 + '0');
            carry = 1;
        } else {
            ans[i++] = (char)(tb + carry + '0');
            carry = 0;
        }
        q--;
    }
    if(carry == 1) {
        ans[i] = '1';
    }
    for(; i >= 0; i--) {
        cout << ans[i];
    }
    return 0;
}

include <iostream>

using namespace std;

int main() {

string a, b;

cin >> a >> b;

char ans[1001];

int p = a.length() - 1;

int q = b.length() - 1;

int carry = 0;

int i = 0;

while(p != -1 && q != -1) {

int ta = a[p] - '0';

int tb = b[q] - '0';

if(ta + tb + carry >= 10) {

ans[i++] = (char)(ta + tb + carry - 10 + '0');

carry = 1;

} else {

ans[i++] = (char)(ta + tb + carry + '0');

carry = 0;

}

p--;

q--;

}

while(p != -1) {

int ta = a[p] - '0';

if(ta + carry >= 10) {

ans[i++] = (char)(ta + carry - 10 + '0');

carry = 1;

} else {

ans[i++] = (char)(ta + carry + '0');

carry = 0;

}

p--;

}

while(q != -1) {

int tb = b[q] - '0';

if(tb + carry >= 10) {

ans[i++] = (char)(tb + carry - 10 + '0');

carry = 1;

} else {

ans[i++] = (char)(tb + carry + '0');

carry = 0;

}

q--;

}

if(carry == 1) {

ans[i] = '1';

}

for(; i >= 0; i--) {

cout << ans[i];

}

return 0;

}

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

}