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

蓝桥杯 ADV-170 算法提高数字黑洞

问题描述
任意一个四位数，只要它们各个位上的数字是不全相同的，就有这样的规律：
1)将组成该四位数的四个数字由大到小排列，形成由这四个数字构成的最大的四位数；
2)将组成该四位数的四个数字由小到大排列，形成由这四个数字构成的最小的四位数(如果四个数中含有0，则得到的数不足四位)；
3)求两个数的差，得到一个新的四位数(高位零保留)。
重复以上过程，最后一定会得到的结果是6174。
比如：4312 3087 8352 6174，经过三次变换，得到6174
输入格式
一个四位整数，输入保证四位数字不全相同
输出格式
一个整数，表示这个数字经过多少次变换能得到6174
样例输入
4312
样例输出
3

#include <iostream>
#include <algorithm>
using namespace std;
int cmp1(int a, int b) {return a > b;}
int cmp2(int a, int b) {return a < b;}
int main() {
    int a[4];
    string s;
    cin >> s;
    for(int i = 0; i < 4; i++) {
        a[i] = s[i] - '0';
    }
    int res = a[0] * 1000 + a[1] * 100 + a[2] * 10 + a[3];
    int cnt = 0;
    while(res != 6174) {
        cnt++;
        sort(a, a+4, cmp1);
        int big = a[0] * 1000 + a[1] * 100 + a[2] * 10 + a[3];
        sort(a, a+4, cmp2);
        int small = a[0] * 1000 + a[1] * 100 + a[2] * 10 + a[3];
        res = big - small;
        a[0] = res / 1000;
        a[1] = res / 100 - res / 1000 * 10;
        a[2] = res / 10 - res / 100 * 10;
        a[3] = res % 10;
    }
    cout << cnt;
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int cmp1(int a, int b) {return a > b;}

int cmp2(int a, int b) {return a < b;}

int main() {

int a[4];

string s;

cin >> s;

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

a[i] = s[i] - '0';

}

int res = a[0] * 1000 + a[1] * 100 + a[2] * 10 + a[3];

int cnt = 0;

while(res != 6174) {

cnt++;

sort(a, a+4, cmp1);

int big = a[0] * 1000 + a[1] * 100 + a[2] * 10 + a[3];

sort(a, a+4, cmp2);

int small = a[0] * 1000 + a[1] * 100 + a[2] * 10 + a[3];

res = big - small;

a[0] = res / 1000;

a[1] = res / 100 - res / 1000 * 10;

a[2] = res / 10 - res / 100 * 10;

a[3] = res % 10;

}

cout << cnt;

return 0;

}

蓝桥杯 ADV-120 算法提高 6-17复数四则运算

设计复数库，实现基本的复数加减乘除运算。
输入时只需分别键入实部和虚部，以空格分割，两个复数之间用运算符分隔；输出时按a+bi的格式在屏幕上打印结果。参加样例输入和样例输出。
注意考虑特殊情况，无法计算时输出字符串”error”。
样例输入
2 4 * -3 2
样例输出
-14-8i
样例输入
3 -2 + -1 3
样例输出
2+1i
分析：除法的时候有点麻烦，结果要变成浮点型，因为测试用例的答案是统一输出一位有效数字的。。所以0.123输出0.1 1.000输出1。。。我用了cout的setprecision控制输出的有效数字个数~

#include <iostream>
#include <iomanip>
using namespace std;

void add(int a, int b, int m, int n);
void min(int a, int b, int m, int n);
void multi(int a, int b, int m, int n);
void div1(int a, int b, int m, int n);

int main() {
    int a,b,m,n;
    char c;
    cin >> a >> b;
    cin >> c;
    cin >> m >> n;
    switch(c) {
        case '+': add(a, b, m, n); break;
        case '-': min(a, b, m, n); break;
        case '*': multi(a, b, m, n); break;
        case '/': div1(a, b, m, n); break;
    }
    return 0;
}

void add(int a, int b, int m, int n) {
    int l, r;
    l = a + m;
    r = b + n;
    if (l != 0){
        if (r != 0) {
            if (r > 0)
                cout << l << "+" << r << "i";
            else
                cout << l << r << "i";
        }
        else {
            cout << l;
        }
    }
    else {
        if (r != 0) {
            cout << r << "i";
        }
        else {
            cout << 0;
        }
    }
}

void min(int a, int b, int m, int n) {
    int l, r;
    l = a - m;
    r = b - n;
    if (l != 0) {
        if (r != 0) {
            if (r > 0)
                cout << l << "+" << r << "i";
            else
                cout << l << r << "i";
        }
        else {
            cout << l;
        }
    }
    else {
        if (r != 0) {
            cout << r << "i";
        }
        else {
            cout << 0;
        }
    }
}

void multi(int a, int b, int m, int n) {
    int l, r;
    l = a * m - b * n;
    r = a * n + b * m;
    if (l != 0) {
        if (r != 0) {
            if (r > 0)
                cout << l << "+" << r << "i";
            else
                cout << l << r << "i";
        }
        else {
            cout << l;
        }
    }
    else {
        if (r != 0) {
            cout << r << "i";
        }
        else {
            cout << 0;
        }
    }
}

void div1(int a, int b, int m, int n) {
    if (m == 0 && n == 0) {
        cout << "error";
    } else {
        double l, r;
        l = (double)(a * m + b * n) / (m * m + n * n);
        r = (double)(b * m - a * n) / (m * m + n * n);
        
        if (l != 0) {
            if (r != 0) {
                if (r > 0) {
                    cout << setprecision(1) << l << "+" << r << endl;
                }
                else {
                    cout << setprecision(1) << l  << r << "i" << endl;
                }
            }
            else {
                cout << setprecision(1) << l << endl;
            }
        } else {
            if (r != 0) {
                cout << setprecision(1) << r << "i" << endl;
            }
            else {
                cout << 0;
            }
        }
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

#include <iostream>

#include <iomanip>

using namespace std;

void add(int a, int b, int m, int n);

void min(int a, int b, int m, int n);

void multi(int a, int b, int m, int n);

void div1(int a, int b, int m, int n);

int main() {

int a,b,m,n;

char c;

cin >> a >> b;

cin >> c;

cin >> m >> n;

switch(c) {

case '+': add(a, b, m, n); break;

case '-': min(a, b, m, n); break;

case '*': multi(a, b, m, n); break;

case '/': div1(a, b, m, n); break;

}

return 0;

}

void add(int a, int b, int m, int n) {

int l, r;

l = a + m;

r = b + n;

if (l != 0){

if (r != 0) {

if (r > 0)

cout << l << "+" << r << "i";

else

cout << l << r << "i";

}

else {

cout << l;

}

else {

if (r != 0) {

cout << r << "i";

}

else {

cout << 0;

}

void min(int a, int b, int m, int n) {

int l, r;

l = a - m;

r = b - n;

if (l != 0) {

if (r != 0) {

if (r > 0)

cout << l << "+" << r << "i";

else

cout << l << r << "i";

}

else {

cout << l;

}

else {

if (r != 0) {

cout << r << "i";

}

else {

cout << 0;

}

void multi(int a, int b, int m, int n) {

int l, r;

l = a * m - b * n;

r = a * n + b * m;

if (l != 0) {

if (r != 0) {

if (r > 0)

cout << l << "+" << r << "i";

else

cout << l << r << "i";

}

else {

cout << l;

}

else {

if (r != 0) {

cout << r << "i";

}

else {

cout << 0;

}

void div1(int a, int b, int m, int n) {

if (m == 0 && n == 0) {

cout << "error";

} else {

double l, r;

l = (double)(a * m + b * n) / (m * m + n * n);

r = (double)(b * m - a * n) / (m * m + n * n);

if (l != 0) {

if (r != 0) {

if (r > 0) {

cout << setprecision(1) << l << "+" << r << endl;

}

else {

cout << setprecision(1) << l << r << "i" << endl;

}

else {

cout << setprecision(1) << l << endl;

}

} else {

if (r != 0) {

cout << setprecision(1) << r << "i" << endl;

}

else {

cout << 0;

}

蓝桥杯 ADV-193 算法提高盾神与条状项链

问题描述
　　有一天，盾神捡到了好多好多五颜六色的珠子！他心想这些珠子这么漂亮，可以做成一条项链然后送给他心仪的女生~于是他用其中一些珠子做成了长度为n的项链。当他准备把项链首尾相接的时候，土方进来了。
　　“哇这么恶心的项链你也做得出来！！！”
　　盾神自知审美不是他的长项，于是他很谦虚地请教土方，怎么才能把项链做得漂亮。
　　“这个嘛~首先你要在这里加上一个这种颜色的珠子，然后在这里去掉这个珠子，然后……，最后你看看是不是漂亮很多咧~”土方一下子说出了m个修改步骤。
　　盾神觉得这个用人工做太麻烦了，于是交给了你。
输入格式
　　第一行两个数，分别为n，m。
　　第二行n个数，表示盾神一开始的项链。第i个数表示第i颗珠子的颜色。
　　接下来m行，为以下形式之一：
　　ADD P Q：表示在颜色为P的珠子前面加上一个颜色为Q的珠子。
　　DEL P：表示把颜色为P的珠子去掉，如果它不在端点处，则需要把它旁边的两颗珠子连起来。例如某时刻项链状态为1 4 5 8，则执行DEL 4会变成1 5 8，执行DEL 1会变成4 5 8。
　　输入保证在每次操作之前，项链有颜色为P的珠子，且任意时刻珠子颜色互不相同。
输出格式
　　第一行为一个数len，为做完所有操作后，项链的长度。
　　第二行len个数，表示此时项链的状态。第i个数表示第i颗珠子的颜色。
样例输入
10 5
1 2 3 4 5 6 7 8 9 10
DEL 5
ADD 7 5
DEL 10
ADD 4 20
ADD 20 12
样例输出
11
1 2 3 12 20 4 6 5 7 8 9
数据规模和约定
　　表示颜色的数字不超过10^5的正数，1<=n<=10^4，1<=m<=10^4。

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> v(n);
    for(int i = 0; i < n; i++) {
        cin >> v[i];
    }
    for(int i = 0; i < m; i++) {
        string s;
        cin >> s;
        if(s == "DEL") {
            int p;
            cin >> p;
            for(vector<int>::iterator it = v.begin(); it != v.end(); it++) {
                if(*it == p) {
                    v.erase(it);
                    break;
                }
            }
        }
        if(s == "ADD") {
            int p, q;
            cin >> p >> q;
            for(vector<int>::iterator it = v.begin(); it != v.end(); it++) {
                if(*it == p) {
                    v.insert(it, q);
                    break;
                }
            }
        }
    }
    cout << v.size() << endl;
    for(int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

int n, m;

cin >> n >> m;

vector<int> v(n);

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

cin >> v[i];

}

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

string s;

cin >> s;

if(s == "DEL") {

int p;

cin >> p;

for(vector<int>::iterator it = v.begin(); it != v.end(); it++) {

if(*it == p) {

v.erase(it);

break;

}

if(s == "ADD") {

int p, q;

cin >> p >> q;

for(vector<int>::iterator it = v.begin(); it != v.end(); it++) {

if(*it == p) {

v.insert(it, q);

break;

}

cout << v.size() << endl;

for(int i = 0; i < v.size(); i++) {

cout << v[i] << " ";

}

return 0;

}

蓝桥杯 ALGO-29 算法训练校门外的树（区间处理）

问题描述
　　某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。
　　由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
输入格式
　　输入文件的第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
输出格式
　　输出文件包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。
样例输入
500 3
150 300
100 200
470 471
样例输出
298
数据规模和约定
　　对于20%的数据，区域之间没有重合的部分；
　　对于其它的数据，区域之间有重合的情况。

#include <iostream>
#include <vector>
using namespace std;
int main() {
	int l, m;
	cin >> l >> m;
	vector<int> v(l+1, 1);
	for(int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		for(int j = a; j <= b; j++) {
			v[j] = 0;
		}
	}
	int cnt = 0;
	for(int i = 0; i < l+1; i++) {
		if(v[i] == 1)
			cnt++;
	}
	cout << cnt;
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

int l, m;

cin >> l >> m;

vector<int> v(l+1, 1);

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

int a, b;

cin >> a >> b;

for(int j = a; j <= b; j++) {

v[j] = 0;

}

int cnt = 0;

for(int i = 0; i < l+1; i++) {

if(v[i] == 1)

cnt++;

}

cout << cnt;

return 0;

}

蓝桥杯 ALGO-11 算法训练瓷砖铺放（递归/动态规划）

问题描述
　　有一长度为N(1<=Ｎ<=10)的地板，给定两种不同瓷砖：一种长度为1，另一种长度为2，数目不限。要将这个长度为N的地板铺满，一共有多少种不同的铺法？
　　例如，长度为4的地面一共有如下5种铺法：
　　4=1+1+1+1
　　4=2+1+1
　　4=1+2+1
　　4=1+1+2
　　4=2+2
　　编程用递归的方法求解上述问题。
输入格式
　　只有一个数N，代表地板的长度
输出格式
　　输出一个数，代表所有不同的瓷砖铺放方法的总数
样例输入
4
样例输出
5

分析：用动态规划的方法解：

#include <iostream>
#include <vector>
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<int> v(n+1);
	v[0] = 1, v[1] = 1;
	for(int i = 2; i <= n; i++) {
		v[i] = v[i-1] + v[i-2];
	}
	cout << v[n];
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

int n;

cin >> n;

vector<int> v(n+1);

v[0] = 1, v[1] = 1;

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

v[i] = v[i-1] + v[i-2];

}

cout << v[n];

return 0;

}

蓝桥杯ADV-17算法提高统计单词数

问题描述
　　统计输入英文文章段落中不同单词（单词有大小写之分,　　但统计时忽略大小写）各自出现的次数。输入段落中所含单词的总数不超过100，最长单词的长度不超过20个字母.
输入格式
　　一个包含若干句子的段落, 每个句子由若干英文单词组成. 除空格,　　逗号和句号外, 这些输入的句子中不含其他非字母字符, 并且, 逗号和句号紧跟在它前面的英文单词后面, 中间没有空格. 段落最后一个字符是回车符,　　表示输入结束.
输出格式
　　若段落中共有M个不同的英文单词，则按照其在段落中出现的先后顺序输出M行，各行的格式为:　　单词中所有字母均用大写形式输出（最长的单词顶格输出，它前面没有多余的空格;　　其余单词与其右对齐）+冒号+N个*号+该单词在段落中的出现次数N
样例输入
This is a test. This test is easy. This is a test. This test is easy.

样例输出
THIS:****4
IS:****4
A:**2
TEST:****4
EASY:**2
分析：本来想用map映射做的，结果发现必须要根据单词出现的次序排列，而不是按照字典序排列。。所以不能用map了。。所以用了pair类型的vector存储~~虽然题目中说保证逗号和句号之后紧跟空格，结果测试用例骗人。。逗号和句号后面还是有一个空格的。。所以要多加个continue的判断，防止把空格记入单词数里面~还有就是输出的时候是大写字符，要把小写转换成大写再存储进去呢~~

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
typedef pair<string, int> p;
int main() {
    string str;
    vector<p> v;
    getline(cin, str);
    string s;
    int flag2 = 0;
    int maxlen = 0;
    for(int i = 0; i < str.length(); i++) {
        if(flag2 == 1 && str[i] == ' ')
            continue;
        if(str[i] == '.' || str[i] == ' ' || str[i] == ',' ) {
            flag2 = 1;
            int len = s.length();
            maxlen = maxlen > len ? maxlen : len;
            for(int j = 0; j < len; j++) {
                if(s[j] >= 'a' && s[j] <= 'z') {
                    s[j] = s[j] - 32;
                }
            }
            int flag = 0;
            for(int i = 0; i < v.size(); i++) {
                if(v[i].first == s) {
                    v[i].second++;
                    flag = 1;
                }
            }
            if(flag == 0) {
                p temp = make_pair(s, 1);
                v.push_back(temp);
            }
            s = "";
        } else {
            flag2 = 0;
            s += str[i];
        }
    }
    for(int i = 0; i < v.size(); i++) {
        string temp = v[i].first;
        int len = maxlen - temp.length();
        for(int k = 0; k < len; k++) {
            cout << " ";
        }
        cout << v[i].first << ":";
        for(int j = 0; j < v[i].second; j++) {
            cout << "*";
        }
        cout << v[i].second << endl;
    }
    return 0;
}

#include <iostream>

#include <cstdio>

#include <vector>

using namespace std;

typedef pair<string, int> p;

int main() {

string str;

vector<p> v;

getline(cin, str);

string s;

int flag2 = 0;

int maxlen = 0;

for(int i = 0; i < str.length(); i++) {

if(flag2 == 1 && str[i] == ' ')

continue;

if(str[i] == '.' || str[i] == ' ' || str[i] == ',' ) {

flag2 = 1;

int len = s.length();

maxlen = maxlen > len ? maxlen : len;

for(int j = 0; j < len; j++) {

if(s[j] >= 'a' && s[j] <= 'z') {

s[j] = s[j] - 32;

}

int flag = 0;

for(int i = 0; i < v.size(); i++) {

if(v[i].first == s) {

v[i].second++;

flag = 1;

}

if(flag == 0) {

p temp = make_pair(s, 1);

v.push_back(temp);

}

s = "";

} else {

flag2 = 0;

s += str[i];

}

for(int i = 0; i < v.size(); i++) {

string temp = v[i].first;

int len = maxlen - temp.length();

for(int k = 0; k < len; k++) {

cout << " ";

}

cout << v[i].first << ":";

for(int j = 0; j < v[i].second; j++) {

cout << "*";

}

cout << v[i].second << endl;

}

return 0;

}