柳婼の blog – 第119页 – 我不管，反正我最萌～

蓝桥杯 ADV-208 算法提高矩阵相乘

问题描述
　　小明最近在为线性代数而头疼，线性代数确实很抽象（也很无聊），可惜他的老师正在讲这矩阵乘法这一段内容。
　　当然，小明上课打瞌睡也没问题，但线性代数的习题可是很可怕的。
　　小明希望你来帮他完成这个任务。

　　现在给你一个ai行aj列的矩阵和一个bi行bj列的矩阵，
　　要你求出他们相乘的积（当然也是矩阵）。
　　(输入数据保证aj=bi,不需要判断)
输入格式
　　输入文件共有ai+bi+2行，并且输入的所有数为整数（long long范围内）。
　　第1行：ai 和 aj
　　第2~ai+2行：矩阵a的所有元素
　　第ai+3行：bi 和 bj
　　第ai+3~ai+bi+3行：矩阵b的所有元素
输出格式
　　输出矩阵a和矩阵b的积（矩阵c)
　　（ai行bj列）
样例输入
2 2
12 23
45 56
2 2
78 89
45 56
样例输出
1971 2356
6030 7141

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int a, b;
    cin >> a >> b;
    vector<vector<long long int> > A(a, vector<long long int>(b));
    for(int i = 0; i < a; i++)
        for(int j = 0; j < b; j++)
            cin >> A[i][j];
    int c, d;
    cin >> c >> d;
    vector<vector<long long int> > B(c, vector<long long int>(d));
    for(int i = 0; i < c; i++)
        for(int j = 0; j < d; j++)
            cin >> B[i][j];
    vector<vector<long long int> > C(a, vector<long long int>(d));
    for(int i = 0; i < a; i++) {
        for(int j = 0; j < d; j++) {
            C[i][j] = 0;
            for(int k = 0; k < b; k++)
                C[i][j] += A[i][k] + B[k][j];
            cout << C[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

int a, b;

cin >> a >> b;

vector<vector<long long int> > A(a, vector<long long int>(b));

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

for(int j = 0; j < b; j++)

cin >> A[i][j];

int c, d;

cin >> c >> d;

vector<vector<long long int> > B(c, vector<long long int>(d));

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

for(int j = 0; j < d; j++)

cin >> B[i][j];

vector<vector<long long int> > C(a, vector<long long int>(d));

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

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

C[i][j] = 0;

for(int k = 0; k < b; k++)

C[i][j] += A[i][k] + B[k][j];

cout << C[i][j] << " ";

}

cout << endl;

}

return 0;

}

蓝桥杯 ADV-197 算法提高 P1001

　　当两个比较大的整数相乘时，可能会出现数据溢出的情形。为避免溢出，可以采用字符串的方法来实现两个大数之间的乘法。
具体来说，首先以字符串的形式输入两个整数，每个整数的长度不会超过8位，然后把它们相乘的结果存储在另一个字符串当中
（长度不会超过16位），最后把这个字符串打印出来。例如，假设用户输入为：62773417和12345678，
则输出结果为：774980393241726.
输入：
　　62773417 12345678
输出：
　　774980393241726

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main() {
    string a, b;
    cin >> a >> b;
    int lena = a.length();
    int lenb = b.length();
    char d[20][20];
    char c[20];
    for (int i = 0; i <= 19; i++) {
        for (int j = 0; j <= 19; j++) {
            d[i][j] = '0';
        }
        c[i] = '0';
    }
    
    int temp = 0;
    int k = 0;
    int cou = 0;
    int t = 0;
    for (int i = lenb - 1; i >= 0; i--) {
        k = 0;
        for (int j = lena - 1; j >= 0; j--) {
            t = ((b[i] - '0') * (a[j] - '0'));
            temp = temp + t * pow(10, k++);
        }
        k = 0;
        while(temp != 0) {
            d[cou][k++] = (temp % 10) + '0';
            temp = temp / 10;
        }
        cou++;
    }
    
    for (int i = 0; i <= 18; i++) {
        for (int j = 0; j <= i; j++) {
            c[i] = (c[i] - '0' + d[j][i - j] - '0') % 10 + '0';
            temp = temp + (d[j][i - j] - '0');
        }
        temp = temp / 10;
        c[i + 1] = temp + '0';
    }
    
    int flag = 0;
    for (int i = 19; i >= 0; i--) {
        if (c[i] != '0') {
            flag = i;
            break;
        }
    }
    for (int i = flag; i >= 0; i--)
        cout << c[i];
    return 0;
}

#include <iostream>

#include <string>

#include <cmath>

using namespace std;

int main() {

string a, b;

cin >> a >> b;

int lena = a.length();

int lenb = b.length();

char d[20][20];

char c[20];

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

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

d[i][j] = '0';

}

c[i] = '0';

}

int temp = 0;

int k = 0;

int cou = 0;

int t = 0;

for (int i = lenb - 1; i >= 0; i--) {

k = 0;

for (int j = lena - 1; j >= 0; j--) {

t = ((b[i] - '0') * (a[j] - '0'));

temp = temp + t * pow(10, k++);

}

k = 0;

while(temp != 0) {

d[cou][k++] = (temp % 10) + '0';

temp = temp / 10;

}

cou++;

}

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

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

c[i] = (c[i] - '0' + d[j][i - j] - '0') % 10 + '0';

temp = temp + (d[j][i - j] - '0');

}

temp = temp / 10;

c[i + 1] = temp + '0';

}

int flag = 0;

for (int i = 19; i >= 0; i--) {

if (c[i] != '0') {

flag = i;

break;

}

for (int i = flag; i >= 0; i--)

cout << c[i];

return 0;

}

蓝桥杯 ADV-188 算法提高排列数

问题描述
　　0、1、2三个数字的全排列有六种，按照字母序排列如下：
　　012、021、102、120、201、210
　　输入一个数n
　　求0~9十个数的全排列中的第n个（第1个为0123456789）。
输入格式
　　一行，包含一个整数n
输出格式
　　一行，包含一组10个数字的全排列
样例输入
1
样例输出
0123456789
数据规模和约定
　　0 < n <= 10!

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    string s = "0123456789";
    int n;
    cin >> n;
    int cnt = 1;
    do {
        if(cnt == n) {
            cout << s;
            break;
        }
        cnt++;
    }while(next_permutation(s.begin(), s.end()));
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

string s = "0123456789";

int n;

cin >> n;

int cnt = 1;

do {

if(cnt == n) {

cout << s;

break;

}

cnt++;

}while(next_permutation(s.begin(), s.end()));

return 0;

}

蓝桥杯 ADV-187 算法提高勾股数

问题描述
　　勾股数是一组三个自然数，a < b < c，以这三个数为三角形的三条边能够形成一个直角三角形
　　输出所有a + b + c <= 1000的勾股数
　　a小的先输出；a相同的，b小的先输出。
输出格式
　　每行为一组勾股数，用空格隔开
样例输出
例如，结果的前三行应当是
3 4 5
5 12 13
6 8 10

#include <iostream>
using namespace std;
int main() {
    for(int i = 1; i <= 333; i++) {
        for(int j = i+1; j <= 666; j++) {
            for(int k = j+1; k <= 999; k++) {
                if(i + j + k <= 1000 && i*i + j*j == k*k)
                    cout << i << " " << j << " " << k << endl;
            }
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

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

for(int j = i+1; j <= 666; j++) {

for(int k = j+1; k <= 999; k++) {

if(i + j + k <= 1000 && i*i + j*j == k*k)

cout << i << " " << j << " " << k << endl;

}

return 0;

}

蓝桥杯 ADV-184 算法提高素数求和

问题描述
　　输入一个自然数n，求小于等于n的素数之和
样例输入
2
样例输出
2
数据规模和约定
　　测试样例保证 2 <= n <= 2,000,000

#include <iostream>
using namespace std;
int v[2000001];
int main() {
    int n;
    cin >> n;
    for(int i = 2; i * i <= n; i++) {
        if(v[i] == 1)
            continue;
        for(int j = i * i; j <= n; j = j + i)
                v[j] = 1;
    }
    long long int cnt = 0;
    for(int i = 2; i <= n ; i++) {
        if(v[i] == 0) {
            cnt += i;
        }
    }
    cout << cnt;
    return 0;
}

#include <iostream>

using namespace std;

int v[2000001];

int main() {

int n;

cin >> n;

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

if(v[i] == 1)

continue;

for(int j = i * i; j <= n; j = j + i)

v[j] = 1;

}

long long int cnt = 0;

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

if(v[i] == 0) {

cnt += i;

}

cout << cnt;

return 0;

}

蓝桥杯 ADV-182 算法提高前10名

问题描述
　　数据很多，但我们经常只取前几名，比如奥运只取前3名。现在我们有n个数据，请按从大到小的顺序，输出前10个名数据。
输入格式
　　两行。
　　第一行一个整数n，表示要对多少个数据
　　第二行有n个整数，中间用空格分隔。表示n个数据。
输出格式
　　一行，按从大到小排列的前10个数据，每个数据之间用一个空格隔开。
样例输入
26
54 27 87 16 63 40 40 22 61 6 57 70 0 42 11 50 13 5 56 7 8 86 56 91 68 59
样例输出
91 87 86 70 68 63 61 59 57 56
数据规模和约定
　　10<=n<=200,各个整数不超出整型范围

#include <iostream>
#include <algorithm>
using namespace std;
int cmp1(int a, int b) {return a > b;}
int main() {
    int n;
    cin >> n;
    int *a = new int[n];
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a+n, cmp1);
    for(int i = 0; i < 10; i++)
        cout << a[i] << " ";
    delete [] a;
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

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

int main() {

int n;

cin >> n;

int *a = new int[n];

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

cin >> a[i];

}

sort(a, a+n, cmp1);

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

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

delete [] a;

return 0;

}