liuchuo

蓝桥杯 ADV-16 算法提高和最大子序列

问题描述
对于一个给定的长度为N的整数序列A，它的“子序列”的定义是：A中非空的一段连续的元素（整数）。你要完成的任务是，在所有可能的子序列中，找到一个子序列，该子序列中所有元素的和是最大的（跟其他所有子序列相比）。程序要求你输出这个最大值。
输入格式
输入文件的第一行包含一个整数N，第二行包含N个整数，表示A。
其中
1 <= N <= 100000
-10000 <= A[i] <= 10000
输出格式
输出仅包含一个整数，表示你算出的答案。
样例输入
5
3 -2 3 -5 4
样例输入
4

分析：sum为某一段和，sum=0 从0号开始向前，遇到一个数字，若该数字加起来不会让sum变成负数，则加上它，若加起来变成负数的话，就丢掉前面所有的数字，置为0，用maxn记录sum出现过最大的数字即可～

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int n, a[100005] = {0}, sum = 0, maxn = 0;
    scanf("%d", &n);
    for (int i = 0; i <= n; i++) {
        scanf("%d", &a[i]);
        if (sum + a[i] >= 0) sum = sum + a[i];
        else sum = 0;
        maxn = max(maxn, sum);
    }
    cout << maxn;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n, a[100005] = {0}, sum = 0, maxn = 0;

scanf("%d", &n);

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

scanf("%d", &a[i]);

if (sum + a[i] >= 0) sum = sum + a[i];

else sum = 0;

maxn = max(maxn, sum);

}

cout << maxn;

return 0;

}

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

问题描述
给定一个矩阵A,一个非负整数b和一个正整数m，求A的b次方除m的余数。
其中一个nxn的矩阵除m的余数得到的仍是一个nxn的矩阵，这个矩阵的每一个元素是原矩阵对应位置上的数除m的余数。
要计算这个问题，可以将A连乘b次，每次都对m求余，但这种方法特别慢，当b较大时无法使用。下面给出一种较快的算法(用A^b表示A的b次方)：
若b=0，则A^b%m=I%m。其中I表示单位矩阵。
若b为偶数，则A^b%m=(A^(b/2)%m)^2%m，即先把A乘b/2次方对m求余，然后再平方后对m求余。
若b为奇数，则A^b%m=(A^(b-1)%m)*a%m，即先求A乘b-1次方对m求余，然后再乘A后对m求余。
这种方法速度较快，请使用这种方法计算A^b%m，其中A是一个2×2的矩阵，m不大于10000。
输入格式
输入第一行包含两个整数b, m，第二行和第三行每行两个整数，为矩阵A。
输出格式
输出两行，每行两个整数，表示A^b%m的值。
样例输入
2 2
1 1
0 1
样例输出
1 0
0 1

分析：1.按照题目要求即可，和快速幂算法类似
2.注意当相乘次数为0时，输出单位矩阵（题目要求）,（但是后台测试数据给的是0 0 0 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;
}

#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;

}

比如不加 \mathrm 的 ABCDEFGabcdefg如下所示： $ABCDEFGabcdefg$

加了 \mathrm{ABCDEFGabcdefg} 如下所示： $\mathrm{ABCDEFGabcdefg}$

蓝桥杯 ADV-16 算法提高和最大子序列

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

米家自动洗手机（套装）说明书

洛菲键盘说明书

LaTeX公式打出U上面一个小圈表示去心领域的符号：\mathring{U}

LaTeX（TeX）中\mathrm{}的作用含义