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

蓝桥杯 ALGO-10 算法训练集合运算

问题描述
给出两个整数集合A、B，求出他们的交集、并集以及B在A中的余集。
输入格式
第一行为一个整数n，表示集合A中的元素个数。
第二行有n个互不相同的用空格隔开的整数，表示集合A中的元素。
第三行为一个整数m，表示集合B中的元素个数。
第四行有m个互不相同的用空格隔开的整数，表示集合B中的元素。
集合中的所有元素均为int范围内的整数，n、m<=1000。
输出格式
第一行按从小到大的顺序输出A、B交集中的所有元素。
第二行按从小到大的顺序输出A、B并集中的所有元素。
第三行按从小到大的顺序输出B在A中的余集中的所有元素。
样例输入
5
1 2 3 4 5
5
2 4 6 8 10
样例输出
2 4
1 2 3 4 5 6 8 10
1 3 5
样例输入
4
1 2 3 4
3
5 6 7
样例输出
1 2 3 4 5 6 7
1 2 3 4

分析：1.利用map，第一个集合的元素标记为1，第二个集合的元素累加2
2.判断，值为1的为余集，有值的为交集，值为3的为并集，且map自带排序功能~

#include <iostream>
#include <map>
using namespace std;
int main() {
    int n, m, t;
    map<int, int> a;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &t);
        a[t] = 1;
    }
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%d", &t);
        a[t] += 2;
    }
    for (map<int, int>::iterator i = a.begin(); i != a.end(); i++)
        if (i->second == 3) cout << i->first << ' ';
    cout << endl;
    for (map<int, int>::iterator i = a.begin(); i != a.end(); i++)
        cout << i->first << ' ';
    cout << endl;
    for (map<int, int>::iterator i = a.begin(); i != a.end(); i++)
        if (i->second == 1) cout << i->first << ' ';
    cout << endl;
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

int n, m, t;

map<int, int> a;

scanf("%d", &n);

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

scanf("%d", &t);

a[t] = 1;

}

scanf("%d", &m);

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

scanf("%d", &t);

a[t] += 2;

}

for (map<int, int>::iterator i = a.begin(); i != a.end(); i++)

if (i->second == 3) cout << i->first << ' ';

cout << endl;

for (map<int, int>::iterator i = a.begin(); i != a.end(); i++)

cout << i->first << ' ';

cout << endl;

for (map<int, int>::iterator i = a.begin(); i != a.end(); i++)

if (i->second == 1) cout << i->first << ' ';

cout << endl;

return 0;

}

蓝桥杯 ADV-149 算法提高特殊的质数肋骨

问题描述
农民约翰母牛总是产生最好的肋骨。你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。农民约翰确定他卖给买方的是真正的质数肋骨，是因为从右边开始切下肋骨，每次还剩下的肋骨上的数字都组成一个质数。
例如有四根肋骨的数字分别是：7 3 3 1，那么全部肋骨上的数字 7331是质数；三根肋骨 733是质数；二根肋骨 73 是质数；当然,最后一根肋骨 7 也是质数。7331 被叫做长度 4 的特殊质数。
写一个程序对给定的肋骨的数目 N (1<=N<=8),求出所有的特殊质数。数字1不被看作一个质数。
输入格式
单独的一行包含N。
输出格式
按顺序输出长度为 N 的特殊质数,每行一个。
样例输入
4
样例输出
2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

分析：从第一位数字开始搜索，如果发现数字是素数，就继续搜索，否则在此处剪枝～

#include <algorithm>
#include <map>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
int n;
bool is(int x){
    if(x == 1 || x ==0) return  false;
    for(int i = 2; i*i <= x; i++)
        if(x % i == 0) return false;
    return true;
}
void dfs(int num, int level){
    if(level == n){
        cout << num << endl;
    }else{
        for(int i = 0; i <= 9; i++){
            if(is(num*10+i)){
                dfs(num * 10 + i, level+1);
            }
        }
    }
}
int main() {
    cin >> n;
    dfs(0,0);
    return 0;
}

#include <algorithm>

#include <map>

#include <cmath>

#include <iostream>

#include <vector>

using namespace std;

int n;

bool is(int x){

if(x == 1 || x ==0) return false;

for(int i = 2; i*i <= x; i++)

if(x % i == 0) return false;

return true;

}

void dfs(int num, int level){

if(level == n){

cout << num << endl;

}else{

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

if(is(num*10+i)){

dfs(num * 10 + i, level+1);

}

int main() {

cin >> n;

dfs(0,0);

return 0;

}

蓝桥杯 ADV-63 算法提高利息计算

问题描述
编制程序完成下述任务：接受两个数，一个为用户一年期定期存款金额，一个为按照百分比格式表示的利率；程序计算一年期满后本金与利息总额。说明：（1）存款金额以人民币元为单位，可能精确到分；（2）输入利率时不需要输入百分号，例如一年期定期存款年利率为2.52%，用户输入2.52即可；（3）按照国家法律，存款利息所得需缴纳20% 的所得税，计算结果时所得税部分应扣除。
输入格式
输入一行，包含两个实数，分别表示本金和年利率。
输出格式
输出一行，包含一个实数，保留到小数点后两位，表示一年后的本金与利息和。
样例输入
10000 2.52
样例输出
10201.60

#include <iostream>
using namespace std;
int main() {
    double m, r;
    cin >> m >> r;
    printf("%.2f", m + 0.8 * 0.01 * m * r);
    return 0;
}

#include <iostream>

using namespace std;

int main() {

double m, r;

cin >> m >> r;

printf("%.2f", m + 0.8 * 0.01 * m * r);

return 0;

}

蓝桥杯 ALGO-5 算法训练最短路

问题描述
给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。
输入格式
第一行两个整数n, m。
接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。
输出格式
共n-1行，第i行表示1号点到i+1号点的最短路。
样例输入
3 3
1 2 -1
2 3 -1
3 1 2
样例输出
-1
-2
数据规模与约定
对于10%的数据，n = 2，m = 2。
对于30%的数据，n <= 5，m <= 10。
对于100%的数据，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保证从任意顶点都能到达其他所有顶点。

分析：1.n个点，m条有向边，含有负边
1.外层循环n-1次，内层循环m次，进行松弛
3.添加check变量判断本轮是否进行松弛了，如果未进行松弛则可以提前退出循环（否则会超时）
4.处理有向边时，注意u[i]和v[i]的顺序不要颠倒~

#include <iostream>
using namespace std;
int main() {
    int dis[20001] = {0}, u[200001], v[200001],w[200001];
    int n, m, inf = 99999999;
    fill(dis+2,dis+20001,inf);
    scanf("%d %d", &n, &m);
    for(int i = 1;  i <= m; i++)
        scanf("%d %d %d",&u[i], &v[i], &w[i]);
    for(int k = 1; k <= n - 1; k++){
        int  check = 0;
        for(int i = 1; i <= m; i++){
            if(dis[v[i]] > dis[u[i]] + w[i]){
                dis[v[i]] = dis[u[i]] + w[i];
                check = 1;
            }
        }
        if(check == 0) break;
    }
    for(int i = 2; i <= n; i++)
        printf("%d\n",dis[i]);
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int dis[20001] = {0}, u[200001], v[200001],w[200001];

int n, m, inf = 99999999;

fill(dis+2,dis+20001,inf);

scanf("%d %d", &n, &m);

for(int i = 1; i <= m; i++)

scanf("%d %d %d",&u[i], &v[i], &w[i]);

for(int k = 1; k <= n - 1; k++){

int check = 0;

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

if(dis[v[i]] > dis[u[i]] + w[i]){

dis[v[i]] = dis[u[i]] + w[i];

check = 1;

}

if(check == 0) break;

}

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

printf("%d\n",dis[i]);

return 0;

}

蓝桥杯 ADV-207 算法提高最长字符序列

问题描述
设x(i), y(i), z(i)表示单个字符，则X={x(1)x(2)……x(m)}，Y={y(1)y(2)……y(n)}，Z={z(1)z(2)……z(k)},我们称其为字符序列，其中m,n和k分别是字符序列X，Y，Z的长度，括号()中的数字被称作字符序列的下标。
如果存在一个严格递增而且长度大于0的下标序列{i1,i2……ik}，使得对所有的j=1,2,……k，有x(ij)=z(j)，那么我们称Z是X的字符子序列。而且，如果Z既是X的字符子序列又是Y的字符子序列，那么我们称Z为X和Y的公共字符序列。
在我们今天的问题中，我们希望计算两个给定字符序列X和Y的最大长度的公共字符序列，这里我们只要求输出这个最大长度公共子序列对应的长度值。
举例来说，字符序列X=abcd，Y=acde，那么它们的最大长度为3，相应的公共字符序列为acd。
输入格式
输入一行，用空格隔开的两个字符串
输出格式
输出这两个字符序列对应的最大长度公共字符序列的长度值
样例输入
aAbB aabb
样例输出
2
数据规模和约定
输入字符串长度最长为100，区分大小写。

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    string a, b;
    cin >> a >> b;
    int dp[110][100] = {0};
    for (int i = 1; i <= a.length(); i++) {
        for (int j = 1; j <= b.length(); j++) {
            if (a[i - 1] == b[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
        }
    }
    cout << dp[a.length()][b.length()];
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

string a, b;

cin >> a >> b;

int dp[110][100] = {0};

for (int i = 1; i <= a.length(); i++) {

for (int j = 1; j <= b.length(); j++) {

if (a[i - 1] == b[j - 1])

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

else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);

}

cout << dp[a.length()][b.length()];

return 0;

}

蓝桥杯 ALGO-28 算法训练星际交流

问题描述
人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。
火星人用一种非常简单的方式来表示数字——掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为1，2，3……。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。
一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指——拇指、食指、中指、无名指和小指分别编号为1，2，3，4和5，当它们按正常顺序排列时，形成了5位数12345，当你交换无名指和小指的位置时，会形成5位数12354，当你把五个手指的顺序完全颠倒时，会形成54321，在所有能够形成的120个5位数中，12345最小，它表示1；12354第二小，它表示2；54321最大，它表示120。下表展示了只有3根手指时能够形成的6个 3位数和它们代表的数字：
三进制数
123
132
213
231
312
321
代表的数字
1
2
3
4
5
6
现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。
输入格式
包括三行，第一行有一个正整数N，表示火星人手指的数目（1 <= N <= 10000）。第二行是一个正整数M，表示要加上去的小整数（1 <= M <= 100）。下一行是1到N这N个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。
输出格式
只有一行，这一行含有N个整数，表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开，不能有多余的空格。
样例输入
5
3
1 2 3 4 5
样例输出
1 2 4 5 3
数据规模和约定
对于30%的数据，N<=15；
对于60%的数据，N<=50；
对于全部的数据，N<=10000；

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int n, m, a[10001];
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    for(int i = 0; i < m; i++)
        next_permutation(a,a+n);
    for(int i = 0; i < n; i++)
        cout << a[i] << " ";
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int n, m, a[10001];

cin >> n >> m;

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

cin >> a[i];

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

next_permutation(a,a+n);

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

cout << a[i] << " ";

return 0;

}