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

蓝桥杯 ADV-226 算法提高 9-3摩尔斯电码

问题描述
摩尔斯电码破译。类似于乔林教材第213页的例6.5，要求输入摩尔斯码，返回英文。请不要使用”zylib.h”，只能使用标准库函数。用’ * ‘表示’ . ‘，中间空格用’ | ‘表示，只转化字符表。
摩尔斯码定义见：http://baike.baidu.com/view/84585.htm?fromId=253988。
提示
清橙进行评测时，输入是以EOF结尾的，而不是换行符。（EOF不是一个字符，“以EOF结尾”是一种通俗但不严谨的说法。）因此可以通过以下方式之一获取输入：
1. 一次读入整行字符串，再进行后续解析。
2. 使用getchar或scanf一次读入一个字符，通过它们的返回值判断输入结束。

样例输出

#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main() {
    map<string,char> m;
    m["*-"] = 'a';
    m["-***"] = 'b';
    m["-*-*"] = 'c';
    m["-**"] = 'd';
    m["*"] = 'e';
    m["**-*"] = 'f';
    m["--*"] = 'g';
    m["****"] = 'h';
    m["**"] = 'i';
    m["*---"] = 'j';
    m["-*-"] = 'k';
    m["*-**"] = 'l';
    m["--"] = 'm';
    m["-*"] = 'n';
    m["---"] = 'o';
    m["*--*"] = 'p';
    m["--*-"] = 'q';
    m["*-*"] = 'r';
    m["***"] = 's';
    m["-"] = 't';
    m["**-"] = 'u';
    m["***-"] = 'v';
    m["*--"] = 'w';
    m["-**-"] = 'x';
    m["-*--"] = 'y';
    m["--**"] = 'z';
    string s;
    vector<string> v;
    cin >> s;
    s += '|';
    for(int i = 0; i < s.length(); i++){
        string t;
        for(; s[i] != '|'; i++)
            t += s[i];
        v.push_back(t);
    }
    for(int i = 0; i < v.size(); i++)
        cout << m[v[i]];
    return 0;
}

#include <iostream>

#include <vector>

#include <map>

using namespace std;

int main() {

map<string,char> m;

m["*-"] = 'a';

m["-***"] = 'b';

m["-*-*"] = 'c';

m["-**"] = 'd';

m["*"] = 'e';

m["**-*"] = 'f';

m["--*"] = 'g';

m["****"] = 'h';

m["**"] = 'i';

m["*---"] = 'j';

m["-*-"] = 'k';

m["*-**"] = 'l';

m["--"] = 'm';

m["-*"] = 'n';

m["---"] = 'o';

m["*--*"] = 'p';

m["--*-"] = 'q';

m["*-*"] = 'r';

m["***"] = 's';

m["-"] = 't';

m["**-"] = 'u';

m["***-"] = 'v';

m["*--"] = 'w';

m["-**-"] = 'x';

m["-*--"] = 'y';

m["--**"] = 'z';

string s;

vector<string> v;

cin >> s;

s += '|';

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

string t;

for(; s[i] != '|'; i++)

t += s[i];

v.push_back(t);

}

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

cout << m[v[i]];

return 0;

}

蓝桥杯 ALGO-23 算法训练一元三次方程求解

问题描述
有形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d 均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。要求三个实根。。
输入格式
四个实数：a，b，c，d
输出格式
由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位
样例输入
1 -5 -4 20
样例输出
-2.00 2.00 5.00
数据规模和约定
|a|，|b|，|c|，|d|<=10

分析：1.若 x1<x2，且f(x1)*f(x2)<0，则在(x1，x2)之间一定有一个根
2.找到一个区间内的根，二分逼近，找到误差很小的近似根，可认为是根
3.题目描述每个根间隔最少为1，从-100到100遍历，遇到整数根直接输出，否则判断是否在其右侧间并查找~

#include <iostream>
using namespace std;
double a, b, c, d;
double f(double x) {
    return a * x * x * x + b * x * x + c * x + d;
}
double find(double x, double y) {
    if (y - x < 0.0001) return x;
    double mid = (x + y) / 2;
    if (f(mid) * f(x) > 0) return find(mid, y);
    else return find(x, mid);
}
int main() {
    cin >> a >> b >> c >> d;
    for (int i = -100; i <= 100; i++) {
        if (f(i) == 0) printf("%.2f ", i * 1.0);
        else if (f(i) * f(i + 1) < 0) printf("%.2f ", find(i, i + 1));
    }
    return 0;
}

#include <iostream>

using namespace std;

double a, b, c, d;

double f(double x) {

return a * x * x * x + b * x * x + c * x + d;

}

double find(double x, double y) {

if (y - x < 0.0001) return x;

double mid = (x + y) / 2;

if (f(mid) * f(x) > 0) return find(mid, y);

else return find(x, mid);

}

int main() {

cin >> a >> b >> c >> d;

for (int i = -100; i <= 100; i++) {

if (f(i) == 0) printf("%.2f ", i * 1.0);

else if (f(i) * f(i + 1) < 0) printf("%.2f ", find(i, i + 1));

}

return 0;

}

蓝桥杯 ALGO-37 算法训练 Hankson的趣味题

问题描述
Hanks 博士是BT (Bio-Tech，生物技术) 领域的知名专家，他的儿子名叫Hankson。现在，刚刚放学回家的Hankson 正在思考一个有趣的问题。今天在课堂上，老师讲解了如何求两个正整数c1 和c2 的最大公约数和最小公倍数。现在Hankson 认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数a0,a1,b0,b1，设某未知正整数x 满足： 1． x 和a0 的最大公约数是a1； 2． x 和b0 的最小公倍数是b1。 Hankson 的“逆问题”就是求出满足条件的正整数x。但稍加思索之后，他发现这样的 x 并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的x 的个数。请你帮助他编程求解这个问题。
输入格式
输入第一行为一个正整数n，表示有n 组输入数据。
接下来的n 行每行一组输入数据，为四个正整数a0，a1，b0，b1，每两个整数之间用一个空格隔开。输入数据保证a0 能被a1 整除，b1 能被b0 整除。
输出格式
输出共n 行。每组输入数据的输出结果占一行，为一个整数。
对于每组数据：若不存在这样的 x，请输出0；若存在这样的 x，请输出满足条件的x 的个数；
样例输入
2
41 1 96 288
95 1 37 1776
样例输出
6
2
样例说明
第一组输入数据，x 可以是9、18、36、72、144、288，共有6 个。
第二组输入数据，x 可以是48、1776，共有2 个。
数据规模和约定
对于 50%的数据，保证有1≤a0，a1，b0，b1≤10000 且n≤100。
对于 100%的数据，保证有1≤a0，a1，b0，b1≤2,000,000,000 且n≤2000。

分析：暴力枚举，判断计数即可，注意，因子是成对出现的，枚举到sqrt(即可)，x=sqrt(b1)只要判断一次即可~

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
using namespace std;
int main() {
    int a0, a1, b0, b1, k;
    cin >> k;
    while (k--) {
        int ans = 0;
        scanf("%d %d %d %d", &a0, &a1, &b0, &b1);
        for (int i = 1; i * i <= b1; i++) {
            if(b1 % i == 0){
                int n = i;
                if (gcd(a0, n) == a1 && b0 * n == b1 * gcd(b0, n))
                    ans++;
                if(i != b1 / i) {
                    n = b1 / i;
                    if (gcd(a0, n) == a1 && b0 * n == b1 * gcd(b0, n))
                        ans++;
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

#include <string>

#include <cmath>

int gcd(int a, int b) {

if (b == 0) return a;

return gcd(b, a % b);

}

using namespace std;

int main() {

int a0, a1, b0, b1, k;

cin >> k;

while (k--) {

int ans = 0;

scanf("%d %d %d %d", &a0, &a1, &b0, &b1);

for (int i = 1; i * i <= b1; i++) {

if(b1 % i == 0){

int n = i;

if (gcd(a0, n) == a1 && b0 * n == b1 * gcd(b0, n))

ans++;

if(i != b1 / i) {

n = b1 / i;

if (gcd(a0, n) == a1 && b0 * n == b1 * gcd(b0, n))

ans++;

}

printf("%d\n",ans);

}

return 0;

}

蓝桥杯 ADV-224 算法提高 9-1九宫格

问题描述
九宫格。输入1-9这9个数字的一种任意排序，构成3*3二维数组。如果每行、每列以及对角线之和都相等，打印1。否则打印0。
样例输出
与上面的样例输入对应的输出。
例：

数据规模和约定
输入1-9这9个数字的一种任意排序。

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
int main() {
    int a[10], ans = 1;
    for (int i = 1; i <= 9; i++)
        cin >> a[i];
    if (a[1] + a[2] + a[3] != 15) ans = 0;
    if (a[4] + a[5] + a[6] != 15) ans = 0;
    if (a[7] + a[8] + a[9] != 15) ans = 0;
    if (a[1] + a[4] + a[7] != 15) ans = 0;
    if (a[2] + a[5] + a[8] != 15) ans = 0;
    if (a[3] + a[6] + a[9] != 15) ans = 0;
    if (a[1] + a[5] + a[9] != 15) ans = 0;
    if (a[7] + a[5] + a[3] != 15) ans = 0;
    cout << ans;
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <cmath>

using namespace std;

int main() {

int a[10], ans = 1;

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

cin >> a[i];

if (a[1] + a[2] + a[3] != 15) ans = 0;

if (a[4] + a[5] + a[6] != 15) ans = 0;

if (a[7] + a[8] + a[9] != 15) ans = 0;

if (a[1] + a[4] + a[7] != 15) ans = 0;

if (a[2] + a[5] + a[8] != 15) ans = 0;

if (a[3] + a[6] + a[9] != 15) ans = 0;

if (a[1] + a[5] + a[9] != 15) ans = 0;

if (a[7] + a[5] + a[3] != 15) ans = 0;

cout << ans;

return 0;

}

蓝桥杯 ADV-225 算法提高 9-2 文本加密

问题描述
先编写函数EncryptChar,按照下述规则将给定的字符c转化（加密）为新的字符：”A”转化”B”，”B”转化为”C”，… …”Z”转化为”a”，”a”转化为”b”,… …, “z”转化为”A”，其它字符不加密。编写程序，加密给定字符串。
样例输出
与上面的样例输入对应的输出。
例：

数据规模和约定
输入数据中每一个数的范围。
例：50个字符以内无空格字符串。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cctype>
#include <map>
using namespace std;
string encrypt(string s) {
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == 'Z') s[i] = 'a';
        else if (s[i] == 'z') s[i] = 'A';
        else if (isalpha(s[i])) s[i]++;
    }
    return s;
}
int main() {
    string s;
    cin >> s;
    cout << encrypt(s);
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

#include <cctype>

#include <map>

using namespace std;

string encrypt(string s) {

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

if (s[i] == 'Z') s[i] = 'a';

else if (s[i] == 'z') s[i] = 'A';

else if (isalpha(s[i])) s[i]++;

}

return s;

}

int main() {

string s;

cin >> s;

cout << encrypt(s);

return 0;

}

蓝桥杯 ADV-65 算法提高格子位置

问题描述
输入三个自然数N，i，j （1<=i<=N，1<=j<=N），输出在一个N*N格的棋盘中，与格子（i，j）同行、同列、同一对角线的所有格子的位置。
输入格式
输入共三行，分别输入自然数N，i，j。其中保证N<=24且1<=i<=N，1<=j<=N。
输出格式
输出共四行。第一行为与格子（i，j）同行的所有格子的位置，第二行为与格子（i，j）同列的所有格子的位置，第三行为从左上到右下对角线上的格子的位置，第四行为从左下到右上对角线上的格子的位置。
样例输入
4
2
3
样例输出
(2,1) (2,2) (2,3) (2,4)
(1,3) (2,3) (3,3) (4,3)
(1,2) (2,3) (3,4)
(4,1) (3,2) (2,3) (1,4)
输入输出样例解释
n=4，i=2，j=3表示了棋盘中的第二行第三列的格子，如下图：

(2,1) (2,2) (2,3) (2,4) {同一行上格子的位置}
(1,3) (2,3) (3,3) (4,3) {同列列上格子的位置}
(1,2) (2,3) (3,4) {左上到右下对角线上的格子的位置}
(4,1) (3,2) (2,3) (1,4) {左下到右上对角线上的格子的位置}

#include <iostream>
using namespace std;
int main() {
    int n, x, y, i, j;
    cin >> n >> x >> y;
    for (i = 1; i <= n; i++)
        printf("(%d,%d)", x, i);
    printf("\n");
    for (i = 1; i <= n; i++)
        printf("(%d,%d)", i, y);
    printf("\n");
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i - x == j - y)
                printf("(%d,%d)", i, j);
        }
    }
    printf("\n");
    for (int i = n; i >= 1; i--) {
        for (int j = 1; j <= n; j++) {
            if (i - x == -1 * (j - y))
                printf("(%d,%d)", i, j);
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, x, y, i, j;

cin >> n >> x >> y;

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

printf("(%d,%d)", x, i);

printf("\n");

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

printf("(%d,%d)", i, y);

printf("\n");

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

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

if (i - x == j - y)

printf("(%d,%d)", i, j);

}

printf("\n");

for (int i = n; i >= 1; i--) {

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

if (i - x == -1 * (j - y))

printf("(%d,%d)", i, j);

}

return 0;

}