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

蓝桥杯 ALGO-55 算法训练矩阵加法

问题描述
给定两个N×M的矩阵，计算其和。其中：
N和M大于等于1且小于等于100，矩阵元素的绝对值不超过1000。
输入格式
输入数据的第一行包含两个整数N、M，表示需要相加的两个矩阵的行数和列数。接下来2*N行每行包含M个数，其中前N行表示第一个矩阵，后N行表示第二个矩阵。
输出格式
你的程序需要输出一个N*M的矩阵，表示两个矩阵相加的结果。注意，输出中每行的最后不应有多余的空格，否则你的程序有可能被系统认为是Presentation　　Error
样例输入
2 2
1 2
3 4
5 6
7 8
样例输出
6 8
10 12

#include <iostream>
using namespace std;
int main() {
    int n, m, t, a[150][150];
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++) {
            cin >> a[i][j];

        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++) {
            cin >> t;
            a[i][j] += t;

        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++) {
            if(j != m - 1) cout << a[i][j] << ' ';
            else cout << a[i][j] << endl;

        }
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m, t, a[150][150];

cin >> n >> m;

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

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

cin >> a[i][j];

}

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

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

cin >> t;

a[i][j] += t;

}

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

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

if(j != m - 1) cout << a[i][j] << ' ';

else cout << a[i][j] << endl;

}

return 0;

}

蓝桥杯 ALGO-26 算法训练麦森数

问题描述
形如2P-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数，2P-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。
任务：从文件中输入P（1000<P<3100000），计算2P-1的位数和最后500位数字（用十进制高精度数表示）
输入格式
文件中只包含一个整数P（1000<P<3100000）
输出格式
第一行：十进制高精度数2P-1的位数。
第2-11行：十进制高精度数2P-1的最后500位数字。（每行输出50位，共输出10行，不足500位时高位补0）
不必验证2P-1与P是否为素数。
样例输入
1279
样例输出
386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087

分析：1.快速幂二分求2^p，用字符串模拟乘法，注意，每次只保留后505数字即可（全部保留超时）
2.求位数直接公式 log10(2^p)+1 = p*log(2)+1 即可
3.取后500位时，直接在前面先加上500位0，再取后500位，这样可省去判断过程~

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
string mul(string s1, string s2) {
    if (s1.length() > 505) s1 = s1.substr(s1.length() - 505);
    if (s2.length() > 505) s1 = s2.substr(s2.length() - 505);
    vector<int> v(s1.length() + s2.length(), 0);
    reverse(s1.begin(), s1.end());
    reverse(s2.begin(), s2.end());
    for (int i = 0; i < s1.length(); i++) {
        for (int j = 0; j < s2.length(); j++) {
            int t = (s1[i] - '0') * (s2[j] - '0') + v[i + j];
            v[i + j] = t % 10;
            v[i + j + 1] += t / 10;
        }
    }
    int i;
    for (i = v.size() - 1; v[i] == 0; i--);
    string ans(i + 1, '0');
    for (int j = 0; j <= i; j++)
        ans[j] = v[i - j] + '0';
    return ans;

}
string f(int p) {
    if (p == 1) return "2";
    if (p % 2 == 1) return mul(f(p - 1), "2");
    string s = f(p / 2);
    return mul(s, s);
}

string cut(string s, int index) {
    if (s[index] != 0) {
        s[index] = s[index] - 1;
        return s;
    } else {
        s[index] = '9';
        return cut(s, index - 1);
    }
}
int main() {
    int p;
    cin >> p;
    string s = f(p);
    string ans = cut(s, s.length() - 1);
    cout << (int) (p * log10(2)) + 1 << endl;
    string add(500, '0');
    ans = add + ans;
    ans = ans.substr(ans.length() - 500);
    for (int i = 0; i < 500; i++) {
        cout << ans[i];
        if ((i + 1) % 50 == 0) cout << endl;
    }
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

#include <string>

#include <cmath>

using namespace std;

string mul(string s1, string s2) {

if (s1.length() > 505) s1 = s1.substr(s1.length() - 505);

if (s2.length() > 505) s1 = s2.substr(s2.length() - 505);

vector<int> v(s1.length() + s2.length(), 0);

reverse(s1.begin(), s1.end());

reverse(s2.begin(), s2.end());

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

for (int j = 0; j < s2.length(); j++) {

int t = (s1[i] - '0') * (s2[j] - '0') + v[i + j];

v[i + j] = t % 10;

v[i + j + 1] += t / 10;

}

int i;

for (i = v.size() - 1; v[i] == 0; i--);

string ans(i + 1, '0');

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

ans[j] = v[i - j] + '0';

return ans;

}

string f(int p) {

if (p == 1) return "2";

if (p % 2 == 1) return mul(f(p - 1), "2");

string s = f(p / 2);

return mul(s, s);

}

string cut(string s, int index) {

if (s[index] != 0) {

s[index] = s[index] - 1;

return s;

} else {

s[index] = '9';

return cut(s, index - 1);

}

int main() {

int p;

cin >> p;

string s = f(p);

string ans = cut(s, s.length() - 1);

cout << (int) (p * log10(2)) + 1 << endl;

string add(500, '0');

ans = add + ans;

ans = ans.substr(ans.length() - 500);

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

cout << ans[i];

if ((i + 1) % 50 == 0) cout << endl;

}

return 0;

}

蓝桥杯 ADV-235 算法提高阶乘差

问题描述
给定n和m以及p，保证n>=m，求(n!-m!)对p取余的结果。
输入格式
一行三个正整数n,m,p。
输出格式
一行一个非负整数表示结果。
样例输入
3 2 10
样例输出
4
数据规模和约定
n,m<=20，p<=10000.

分析：先取余再相减，减完为了避免出现负数的情况，加上p再取余~

#include <iostream>
using namespace std;
int n, m, p;
int f(int n){
    int ans = 1;
    for(int i = 1; i <= n; i++)
        ans = ans * i % p;
    return ans;
}
int main() {
    cin >> n >> m >> p;
    cout << (f(n)-f(m) + p) % p;
    return 0;
}

#include <iostream>

using namespace std;

int n, m, p;

int f(int n){

int ans = 1;

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

ans = ans * i % p;

return ans;

}

int main() {

cin >> n >> m >> p;

cout << (f(n)-f(m) + p) % p;

return 0;

}

蓝桥杯 ADV-221 算法提高 7-1用宏求球的体积

问题描述
使用宏实现计算球体体积的功能。用户输入半径，系统输出体积。不能使用函数，pi=3.1415926,结果精确到小数点后五位。
样例输入
一个满足题目要求的输入范例。
例：
1.0
样例输出
与上面的样例输入对应的输出。
例：

数据规模和约定
输入数据中每一个数的范围。
数据表示采用double类型。

#include <iostream>
using namespace std;
#define PI 3.1415926
int main() {
    double r;
    cin >> r;
    printf("%.5f", 4 * r * r * r * PI / 3);
    return 0;
}

#include <iostream>

using namespace std;

#define PI 3.1415926

int main() {

double r;

cin >> r;

printf("%.5f", 4 * r * r * r * PI / 3);

return 0;

}

蓝桥杯 ADV-234 算法提高字符串跳步

问题描述
给定一个字符串，你需要从第start位开始每隔step位输出字符串对应位置上的字符。
输入格式
第一行一个只包含小写字母的字符串。
第二行两个非负整数start和step，意义见上。
输出格式
一行，表示对应输出。
样例输入
abcdefg
2 2
样例输出
ceg
数据规模和约定
start从0开始计数。
字符串长度不超过100000。
提示
读入上有问题，可以参照字符串进位。
尝试不要出现以下代码：for (int i = 0; i < (int) S.size(); ++i)

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s;
    int star, step;
    cin >> s >>  star >> step;
    for(int i = 0; star+ i * step <= s.size(); i++) 
        cout << s[star + i * step];
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

int star, step;

cin >> s >> star >> step;

for(int i = 0; star+ i * step <= s.size(); i++)

cout << s[star + i * step];

return 0;

}

蓝桥杯 ALGO-25 算法训练 Car的旅行路线

问题描述
又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第I个城市中高速铁路了的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。
那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题，于是她来向你请教。
找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。
输入格式
的第一行有四个正整数s，t，A，B。
S表示城市的个数，t表示飞机单位里程的价格，A，B分别为城市A，B的序号，(1<=A，B<=S)。
接下来有S行，其中第I行均有7个正整数xi1，yi1，xi2，yi2，xi3，yi3，Ti，这当中的(xi1，yi1)，(xi2，yi2)，(xi3，yi3)分别是第I个城市中任意三个机场的坐标，T I为第I个城市高速铁路单位里程的价格。
输出格式
共有n行，每行一个数据对应测试数据，保留一位小数。
样例输入
1
1 10 1 3
1 1 1 3 3 1 30
2 5 7 4 5 2 1
8 6 8 8 11 6 3
样例输出
47.55
数据规模和约定
0<S<=100，

分析：1.每个城市的四个机场相互有铁路联通，非同一城市的机场相互有航线，所以n个城市有4*n个机场
2.给出三个矩形的定点，通过向量垂直判断直角点，再通过中点坐标公式计算出另外一个点，把四个机场点的相互到达所需花费记录起来
3.把每两个不同城市机场之间的花费记录起来
4.得到一个4n*4n的邻接矩阵表示每个点到其他点的花费，用迪杰斯特拉算法循环扫描四次，{s1,s2,s3,s4}到{e1,e2,e3,e4}之间的最短路径，共16条中取最小即可～

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
struct node {
    int x, y, id;
};
vector<node> nodes(1);
int n, flyprice, beginn, endn, inf = 99999;
double e[500][500];
double w(int x1, int y1, int x2, int y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
bool h(int x1, int y1, int x2, int y2, int x3, int y3) {
    return !((x1 - x2) * (x1 - x3) + (y1 - y2) * (y1 - y3));
}
double f(int m) {
    double dis[500];
    bool book[500] = {0};
    fill(dis, dis + 500, inf);
    for (int i = 0; i < 500; i++) dis[i] = inf;
    dis[m] = 0;
    for (int i = 1; i <= n * 4 - 1; i++) {
        int minn = inf, u = -1;
        for (int j = 1; j <= n * 4; j++) {
            if (book[j] == false && dis[j] < minn) {
                minn = dis[j];
                u = j;
            }
        }
        if (u == -1) break;
        book[u] = true;
        for (int k = 1; k <= n * 4; k++) {
            if (e[u][k] < inf && dis[k] > e[u][k] + dis[u]) {
                dis[k] = e[u][k] + dis[u];
            }
        }
    }
    return min(min(dis[endn * 4 - 3], dis[endn * 4 - 2]), min(dis[endn * 4 - 1], dis[endn * 4]));
}
int main() {
    fill(e[0], e[0] + 500 * 500, inf);
    scanf("%d %d %d %d", &n, &flyprice, &beginn, &endn);
    for (int i = 1; i <= n; i++) {
        int x1, y1, x2, y2, x3, y3, x4, y4, t;
        scanf("%d %d %d %d %d %d %d", &x1, &y1, &x2, &y2, &x3, &y3, &t);
        if (h(x1, y1, x2, y2, x3, y3)) {
            x4 = x2 + x3 - x1;
            y4 = y2 + y3 - y1;
        } else if (h(x2, y2, x1, y1, x3, y3)) {
            x4 = x1 + x3 - x2;
            y4 = y1 + y3 - y2;
        } else {
            x4 = x1 + x2 - x3;
            y4 = y1 + y2 - y3;
        }
        e[(i - 1) * 4 + 1][(i - 1) * 4 + 2] = e[(i - 1) * 4 + 2][(i - 1) * 4 + 1] = w(x1, y1, x2, y2) * t;
        e[(i - 1) * 4 + 1][(i - 1) * 4 + 3] = e[(i - 1) * 4 + 3][(i - 1) * 4 + 1] = w(x1, y1, x3, y3) * t;
        e[(i - 1) * 4 + 1][(i - 1) * 4 + 4] = e[(i - 1) * 4 + 4][(i - 1) * 4 + 1] = w(x1, y1, x4, y4) * t;
        e[(i - 1) * 4 + 2][(i - 1) * 4 + 3] = e[(i - 1) * 4 + 3][(i - 1) * 4 + 2] = w(x2, y2, x3, y3) * t;
        e[(i - 1) * 4 + 2][(i - 1) * 4 + 4] = e[(i - 1) * 4 + 4][(i - 1) * 4 + 2] = w(x2, y2, x4, y4) * t;
        e[(i - 1) * 4 + 3][(i - 1) * 4 + 4] = e[(i - 1) * 4 + 4][(i - 1) * 4 + 3] = w(x3, x3, x4, y4) * t;
        nodes.push_back({x1, y1, i});
        nodes.push_back({x2, y2, i});
        nodes.push_back({x3, y3, i});
        nodes.push_back({x4, y4, i});
    }
    for (int i = 1; i <= n * 4; i++) {
        for (int j = i + 1; j <= n * 4; j++) {
            if (nodes[i].id != nodes[j].id) {
                e[i][j] = e[j][i] = flyprice * w(nodes[i].x, nodes[i].y, nodes[j].x, nodes[j].y);
            }
        }
    }
    double ans = inf;
    for (int i = 3; i >= 0; i--)
        ans = min(ans, f(beginn * 4 - i));
    printf("%.1f\n", ans);
    return 0;
}

#include <iostream>

#include <vector>

#include <cmath>

using namespace std;

struct node {

int x, y, id;

};

vector<node> nodes(1);

int n, flyprice, beginn, endn, inf = 99999;

double e[500][500];

double w(int x1, int y1, int x2, int y2) {

return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));

}

bool h(int x1, int y1, int x2, int y2, int x3, int y3) {

return !((x1 - x2) * (x1 - x3) + (y1 - y2) * (y1 - y3));

}

double f(int m) {

double dis[500];

bool book[500] = {0};

fill(dis, dis + 500, inf);

for (int i = 0; i < 500; i++) dis[i] = inf;

dis[m] = 0;

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

int minn = inf, u = -1;

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

if (book[j] == false && dis[j] < minn) {

minn = dis[j];

u = j;

}

if (u == -1) break;

book[u] = true;

for (int k = 1; k <= n * 4; k++) {

if (e[u][k] < inf && dis[k] > e[u][k] + dis[u]) {

dis[k] = e[u][k] + dis[u];

}

return min(min(dis[endn * 4 - 3], dis[endn * 4 - 2]), min(dis[endn * 4 - 1], dis[endn * 4]));

}

int main() {

fill(e[0], e[0] + 500 * 500, inf);

scanf("%d %d %d %d", &n, &flyprice, &beginn, &endn);

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

int x1, y1, x2, y2, x3, y3, x4, y4, t;

scanf("%d %d %d %d %d %d %d", &x1, &y1, &x2, &y2, &x3, &y3, &t);

if (h(x1, y1, x2, y2, x3, y3)) {

x4 = x2 + x3 - x1;

y4 = y2 + y3 - y1;

} else if (h(x2, y2, x1, y1, x3, y3)) {

x4 = x1 + x3 - x2;

y4 = y1 + y3 - y2;

} else {

x4 = x1 + x2 - x3;

y4 = y1 + y2 - y3;

}

e[(i - 1) * 4 + 1][(i - 1) * 4 + 2] = e[(i - 1) * 4 + 2][(i - 1) * 4 + 1] = w(x1, y1, x2, y2) * t;

e[(i - 1) * 4 + 1][(i - 1) * 4 + 3] = e[(i - 1) * 4 + 3][(i - 1) * 4 + 1] = w(x1, y1, x3, y3) * t;

e[(i - 1) * 4 + 1][(i - 1) * 4 + 4] = e[(i - 1) * 4 + 4][(i - 1) * 4 + 1] = w(x1, y1, x4, y4) * t;

e[(i - 1) * 4 + 2][(i - 1) * 4 + 3] = e[(i - 1) * 4 + 3][(i - 1) * 4 + 2] = w(x2, y2, x3, y3) * t;

e[(i - 1) * 4 + 2][(i - 1) * 4 + 4] = e[(i - 1) * 4 + 4][(i - 1) * 4 + 2] = w(x2, y2, x4, y4) * t;

e[(i - 1) * 4 + 3][(i - 1) * 4 + 4] = e[(i - 1) * 4 + 4][(i - 1) * 4 + 3] = w(x3, x3, x4, y4) * t;

nodes.push_back({x1, y1, i});

nodes.push_back({x2, y2, i});

nodes.push_back({x3, y3, i});

nodes.push_back({x4, y4, i});

}

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

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

if (nodes[i].id != nodes[j].id) {

e[i][j] = e[j][i] = flyprice * w(nodes[i].x, nodes[i].y, nodes[j].x, nodes[j].y);

}

double ans = inf;

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

ans = min(ans, f(beginn * 4 - i));

printf("%.1f\n", ans);

return 0;

}