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

蓝桥杯 ALGO-38 算法训练接水问题

问题描述
学校里有一个水房，水房里一共装有m 个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为1。现在有n 名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从1 到n 编号，i 号同学的接水量为wi。接水开始时，1 到m 号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学j 完成其接水量要求wj 后，下一名排队等候接水的同学k 马上接替j 同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即 j 同学第x 秒结束时完成接水，则k 同学第x+1 秒立刻开始接水。若当前接水人数n’不足m，则只有n’个龙头供水，其它m−n’个龙头关闭。现在给出n 名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。
输入格式
第1 行2 个整数n 和m，用一个空格隔开，分别表示接水人数和龙头个数。第2 行n 个整数w1、w2、……、wn，每两个整数之间用一个空格隔开，wi 表示i 号同学的接水量。
输出格式
输出只有一行，1 个整数，表示接水所需的总时间。
样例输入
5 3
4 4 1 2 1
样例输出
4
样例输入
8 4
23 71 87 32 70 93 80 76
样例输出
163
输入输出样例 1 说明
第1 秒，3 人接水。第1 秒结束时，1、2、3 号同学每人的已接水量为1，3 号同学接完
水，4 号同学接替3 号同学开始接水。
第2 秒，3 人接水。第2 秒结束时，1、2 号同学每人的已接水量为2，4 号同学的已接
水量为1。
第3 秒，3 人接水。第3 秒结束时，1、2 号同学每人的已接水量为3，4 号同学的已接
水量为2。4 号同学接完水，5 号同学接替4 号同学开始接水。
第4 秒，3 人接水。第4 秒结束时，1、2 号同学每人的已接水量为4，5 号同学的已接
水量为1。1、2、5 号同学接完水，即所有人完成接水。
总接水时间为4 秒。
数据规模和约定
1 ≤ n ≤ 10000，1 ≤m≤ 100 且m≤ n；
1 ≤ wi ≤ 100。

分析：1.每次同学接水，都走到需要排队时间最少的队伍前，每次有同学排队，需最少排队时间的队都在变化
2.用优先队列，每次取出队头，把要进来的同学的排队时间加上，然后丢到队尾
3.最后，队伍最长的，就是接水总时间~

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
    priority_queue<int, vector<int>, greater<int> > q;
    int n, m, ans;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int t;
        scanf("%d", &t);
        if (i <= m) q.push(t);
        else {
            int a = q.top();
            q.pop();
            q.push(a + t);
        }
    }
    while (!q.empty()) {
        ans = q.top();
        q.pop();
    }
    cout << ans;
    return 0;
}

#include <iostream>

#include <vector>

#include <queue>

using namespace std;

int main() {

priority_queue<int, vector<int>, greater<int> > q;

int n, m, ans;

cin >> n >> m;

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

int t;

scanf("%d", &t);

if (i <= m) q.push(t);

else {

int a = q.top();

q.pop();

q.push(a + t);

}

while (!q.empty()) {

ans = q.top();

q.pop();

}

cout << ans;

return 0;

}

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

}