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

蓝桥杯 ADV-156 算法提高分分钟的碎碎念(动态规划)

问题描述
　　以前有个孩子，他分分钟都在碎碎念。不过，他的念头之间是有因果关系的。他会在本子里记录每一个念头，并用箭头画出这个念头的来源于之前的哪一个念头。翻开这个本子，你一定会被互相穿梭的箭头给搅晕，现在他希望你用程序计算出这些念头中最长的一条因果链。
　　将念头从1到n编号，念头i来源于念头from[i]，保证from[i]<i，from[i]=0表示该念头没有来源念头，只是脑袋一抽，灵光一现。
输入格式
　　第一行一个正整数n表示念头的数量
　　接下来n行依次给出from[1]，from[2]，…，from[n]
输出格式
　　共一行，一个正整数L表示最长的念头因果链中的念头数量
样例输入
8
0
1
0
3
2
4
2
4
样例输出
3
样例说明
　　最长的因果链有：
　　1->2->5 (from[5]=2,from[2]=1,from[1]=0)
　　1->2->7 (from[7]=2,from[2]=1,from[1]=0)
　　3->4->6 (from[6]=4,from[4]=3,from[3]=0)
　　3->4->8 (from[8]=4,from[4]=3,from[3]=0)
数据规模和约定
　　1<=n<=1000
分析：建立一个与from数组等长的数组dp，dp[i]表示当前序号能满足构成的最长的长度，dp[i]的值可以由dp[from[i]]+1得到~

#include <iostream>
#include <cstdio>
using namespace std;
int main() {
	int n;
	scanf("%d", &n);
	int *dp = new int[n+1];
	int *from = new int[n+1];
	for(int i = 1; i <= n; i++) {
		scanf("%d", &from[i]);
	}
	dp[0] = 0;
	int maxvalue = 0;
	for(int i = 1; i <= n; i++) {
		dp[i] = dp[from[i]] + 1;
		maxvalue = max(maxvalue, dp[i]);
	}
	cout << maxvalue;
	delete [] dp;
	delete [] a;
}

#include <iostream>

#include <cstdio>

using namespace std;

int main() {

int n;

scanf("%d", &n);

int *dp = new int[n+1];

int *from = new int[n+1];

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

scanf("%d", &from[i]);

}

dp[0] = 0;

int maxvalue = 0;

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

dp[i] = dp[from[i]] + 1;

maxvalue = max(maxvalue, dp[i]);

}

cout << maxvalue;

delete [] dp;

delete [] a;

}

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

}

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

问题描述
　　大家都知道”超级玛丽”是一个很善于跳跃的探险家，他的拿手好戏是跳跃，但它一次只能向前跳一步或两步。有一次，他要经过一条长为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;

}