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

蓝桥杯 ALGO-45 算法训练调和数列问题

问题描述
输入一个实数x，求最小的n使得，1/2+1/3+1/4+…+1/(n+1)>=x。
输入的实数x保证大于等于0.01，小于等于5.20，并且恰好有两位小数。你的程序要能够处理多组数据，即不停地读入x，如果x不等于0.00，则计算答案，否则退出程序。
输出格式为对于一个x，输出一行n card(s)。其中n表示要计算的答案。
输入格式
分行输入x的具体数值
输出格式
分行输出n的数值，格式为n card(s)
样例输入
1.00
3.71
0.04
5.19
0.00
样例输入
3 card(s)
61 card(s)
1 card(s)
273 card(s)

#include <iostream>
using namespace std;
int main() {
    double x, ans = 0;
    cin >> x;
    if(x != 0){
        for(int i = 1; ; i++){
            ans += 1.0 / (i+1);
            if(ans >= x){
                printf("%d card(s)\n",i);
                return main();
            }
        }
    } else{
        return 0;
    }
}

#include <iostream>

using namespace std;

int main() {

double x, ans = 0;

cin >> x;

if(x != 0){

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

ans += 1.0 / (i+1);

if(ans >= x){

printf("%d card(s)\n",i);

return main();

}

} else{

return 0;

}

蓝桥杯 ALGO-86 算法训练矩阵乘法

问题描述
输入两个矩阵，分别是m*s，s*n大小。输出两个矩阵相乘的结果。
输入格式
第一行，空格隔开的三个正整数m,s,n（均不超过200）。
接下来m行，每行s个空格隔开的整数，表示矩阵A（i，j）。
接下来s行，每行n个空格隔开的整数，表示矩阵B（i，j）。
输出格式
m行，每行n个空格隔开的整数，输出相乘後的矩阵C（i，j）的值。
样例输入
2 3 2
1 0 -1
1 1 -3
0 3
1 2
3 1
样例输出
-3 2
-8 2

提示
矩阵C应该是m行n列，其中C(i,j)等于矩阵A第i行行向量与矩阵B第j列列向量的内积。
例如样例中C(1,1)=(1,0,-1)*(0,1,3) = 1 * 0 +0*1+(-1)*3=-3

#include <iostream>
#include <vector>
using namespace std;
vector<int> f(vector<int> v, int k, int m) {
    vector<int> ans(5);
    if (k == 0) {
        ans[1] = ans[4] = 1;
        ans[2] = ans[3] = 0;
    } else {
        if (k % 2 == 0) {
            vector<int> t = f(v, k / 2, m);
            ans[1] = (t[1] * t[1] + t[2] * t[3]) % m;
            ans[2] = (t[1] * t[2] + t[2] * t[4]) % m;
            ans[3] = (t[3] * t[1] + t[4] * t[3]) % m;
            ans[4] = (t[3] * t[2] + t[4] * t[4]) % m;
        } else {
            vector<int> t = f(v, k - 1, m);
            ans[1] = (t[1] * v[1] + t[2] * v[3]) % m;
            ans[2] = (t[1] * v[2] + t[2] * v[4]) % m;
            ans[3] = (t[3] * v[1] + t[4] * v[3]) % m;
            ans[4] = (t[3] * v[2] + t[4] * v[4]) % m;
        }
    }
    return ans;
}

int main() {
    int k, m, a, b, c, d;
    vector<int> v(5), ans;
    cin >> k >> m >> v[1] >> v[2] >> v[3] >> v[4];
    ans = f(v, k, m);
    printf("%d %d\n%d %d\n", ans[1], ans[2], ans[3], ans[4]);
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

vector<int> f(vector<int> v, int k, int m) {

vector<int> ans(5);

if (k == 0) {

ans[1] = ans[4] = 1;

ans[2] = ans[3] = 0;

} else {

if (k % 2 == 0) {

vector<int> t = f(v, k / 2, m);

ans[1] = (t[1] * t[1] + t[2] * t[3]) % m;

ans[2] = (t[1] * t[2] + t[2] * t[4]) % m;

ans[3] = (t[3] * t[1] + t[4] * t[3]) % m;

ans[4] = (t[3] * t[2] + t[4] * t[4]) % m;

} else {

vector<int> t = f(v, k - 1, m);

ans[1] = (t[1] * v[1] + t[2] * v[3]) % m;

ans[2] = (t[1] * v[2] + t[2] * v[4]) % m;

ans[3] = (t[3] * v[1] + t[4] * v[3]) % m;

ans[4] = (t[3] * v[2] + t[4] * v[4]) % m;

}

return ans;

}

int main() {

int k, m, a, b, c, d;

vector<int> v(5), ans;

cin >> k >> m >> v[1] >> v[2] >> v[3] >> v[4];

ans = f(v, k, m);

printf("%d %d\n%d %d\n", ans[1], ans[2], ans[3], ans[4]);

return 0;

}

蓝桥杯 ADV-135 算法提高三角形面积

问题描述
由三角形的三边长，求其面积。
提示：由三角形的三边a,b,c求面积可以用如下的公式：
s=（a+b+c）/2
面积=

输入格式
由空格分开的三个整数。
输出格式
一个实数，保留两位小数。
样例输入
3 4 5
样例输出
6.00
数据规模和约定
输入的三条边一定能构成三角形，不用进行判定。a,b,c小于1000

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int a, b, c;
    cin >> a >> b >> c;
    double s = (a + b + c) / 2.0;
    printf("%.2f", sqrt(s * (s - a) * (s - b) * (s - c)));
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int a, b, c;

cin >> a >> b >> c;

double s = (a + b + c) / 2.0;

printf("%.2f", sqrt(s * (s - a) * (s - b) * (s - c)));

return 0;

}

蓝桥杯 ADV-121 算法提高高精度加法

问题描述
在C/C++语言中，整型所能表示的范围一般为-231到231（大约21亿）,即使long long型，一般也只能表示到-263到263。要想计算更加规模的数，就要用软件来扩展了，比如用数组或字符串来模拟更多规模的数及共运算。
现在输入两个整数，请输出它们的和。
输入格式
两行，每行一个整数，每个整数不超过1000位
输出格式
一行，两个整数的和。
样例输入
15464315464465465
482321654151
样例输出
15464797786119616
数据规模和约定
每个整数不超过1000位

分析：1.模拟竖式加法，依次从往左加
2.如果刚开始两位数字位数不一样，短的用0补上，最后一次加法，如果有进位也要加上～

#include <iostream>
#include <string>
using namespace std;
string add(string s1, string s2) {
    int len1 = s1.length(), len2 = s2.length();
    if (len1 < len2) {
        string t(len2 - len1, '0');
        s1 = t + s1;
    } else if (len2 < len1) {
        string t(len1 - len2, '0');
        s2 = t + s2;
    }
    string ans = s1;
    int car = 0;
    for (int i = s1.length() - 1; i >= 0; i--) {
        ans[i] = (s1[i] - '0' + s2[i] - '0' + car) % 10 + '0';
        car = (s1[i] - '0' + s2[i] - '0' + car) / 10;
    }
    if (car) ans = (char) (car + '0') + ans;
    return ans;
}
int main() {
    string s1, s2;
    cin >> s1 >> s2;
    cout << add(s1, s2);
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

string add(string s1, string s2) {

int len1 = s1.length(), len2 = s2.length();

if (len1 < len2) {

string t(len2 - len1, '0');

s1 = t + s1;

} else if (len2 < len1) {

string t(len1 - len2, '0');

s2 = t + s2;

}

string ans = s1;

int car = 0;

for (int i = s1.length() - 1; i >= 0; i--) {

ans[i] = (s1[i] - '0' + s2[i] - '0' + car) % 10 + '0';

car = (s1[i] - '0' + s2[i] - '0' + car) / 10;

}

if (car) ans = (char) (car + '0') + ans;

return ans;

}

int main() {

string s1, s2;

cin >> s1 >> s2;

cout << add(s1, s2);

return 0;

}

蓝桥杯 ALGO-93 算法训练反置数

问题描述
一个整数的“反置数”指的是把该整数的每一位数字的顺序颠倒过来所得到的另一个整数。如果一个整数的末尾是以0结尾，那么在它的反置数当中，这些0就被省略掉了。比如说，1245的反置数是5421，而1200的反置数是21。请编写一个程序，输入两个整数，然后计算这两个整数的反置数之和sum，然后再把sum的反置数打印出来。要求：由于在本题中需要多次去计算一个整数的反置数，因此必须把这部分代码抽象为一个函数的形式。
输入格式：输入只有一行，包括两个整数，中间用空格隔开。
输出格式：输出只有一行，即相应的结果。
输入输出样例
样例输入
435 754
样例输出
199

#include <iostream>
using namespace std;
int re(int n){
    int ans = 0;
    while(n){
        ans = ans * 10 + n % 10;
        n /= 10;
    }
    return ans;
}
int main() {
    int a, b;
    cin >> a >> b;
    cout << re(re(a)+re(b));
    return 0;
}

#include <iostream>

using namespace std;

int re(int n){

int ans = 0;

while(n){

ans = ans * 10 + n % 10;

n /= 10;

}

return ans;

}

int main() {

int a, b;

cin >> a >> b;

cout << re(re(a)+re(b));

return 0;

}

蓝桥杯 ALGO-52 算法训练排列问题

问题描述
求一个0～N-1的排列（即每个数只能出现一次），给出限制条件（一张N*N的表，第i行第j列的1或0，表示为j-1这个数不能出现在i-1这个数后面，并保证第i行第i列为0），将这个排列看成一个自然数，求从小到大排序第K个排列。
数据规模和约定
N<=10，K<=500000
输入格式
第一行为N和K,接下来的N行，每行N个数，0表示不能，1表示能
输出格式
所求的排列
样例输入
3 2
0 1 1
1 0 0
0 1 0
样例输出
1 0 2
解释：
对于N=3的没有任何限制的情况
第一：0 1 2
第二：0 2 1
第三：1 0 2
第四：1 2 0
第五：2 0 1
第六：2 1 0
根据题目所给的限制条件由于2不能出现在1后面，0不能出现在2后面
第一：0 2 1
第二：1 0 2
第三：2 1 0

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int n, k, t, a[10], index[10], cnt = 1;
    vector<pair<int, int> > v;
    cin >> n >> k;
    for (int i = 0; i < n; i++) 
        a[i] = i;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> t;
            if (t == 0 && i != j) {
                v.push_back({i, j});
            }
        }
    }
    do {
        int flag = 0;
        for (int i = 0; i < n; i++)
            index[a[i]] = i;
        for (int i = 0; i < v.size(); i++) {
            if (index[v[i].second] - index[v[i].first] == 1) {
                flag = 1;
                break;
            }
        }
        if (flag == 0) {
            if (cnt == k) {
                for (int i = 0; i < n; i++)
                    cout << a[i] << ' ';
                break;
            } else {
                cnt++;
            }

        }

    } while (next_permutation(a, a + n));
    return 0;
}

#include <iostream>

#include <cmath>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

int n, k, t, a[10], index[10], cnt = 1;

vector<pair<int, int> > v;

cin >> n >> k;

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

a[i] = i;

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

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

cin >> t;

if (t == 0 && i != j) {

v.push_back({i, j});

}

do {

int flag = 0;

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

index[a[i]] = i;

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

if (index[v[i].second] - index[v[i].first] == 1) {

flag = 1;

break;

}

if (flag == 0) {

if (cnt == k) {

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

cout << a[i] << ' ';

break;

} else {

cnt++;

}

} while (next_permutation(a, a + n));

return 0;

}