发现这个38所很喜欢大整数加减法，连着两题是吧
A. 加油
题意：
说实话，这题题意感觉很抽象，读半天没读懂。最后去根据样例猜出来的，实际就是一个类 fibonacci 问题
数据范围：$0 < n < 100$
题解：
注意到这里 fib[1] = 1, fib[2] = 2, fib[3] = 3。
可以理解为初始为 fib[1] = 1, fib[i] = fib[i - 1] + fib[i - 2], i >= 2
因为 fib[93] > 2^63 - 1，会爆 signed long long。
这里如果使用C++，则考虑使用大整数加法，要么就是用 Python 解千愁，贴一个 Python 代码。
代码：
1
2
3
4
5
6
|
n = int(input())
x = [0, 1, 2]
for i in range(3, n + 1):
x.append(x[i - 1] + x[i - 2])
print(x[n])
|
B. 整数最小和
题意：
给定一个由大小写字母和数字以及+、-符号组成的字符串。
这里考虑一个合法整数为：
- 正数：以任意数字字符开始的串，直到遇到一个非数字字符
- 负数：以
-开始的，紧接着至少一个数字字符，直到遇到一个非数字字符。
求所有合法整数之和的最小值。
数据范围：字符串长度 $\leq$ 1000
题解：
要求的是可能的和的最小值，那么对于负数，就尽可能往后取，对于正数就是一个一个作为一个数。
这样正数之和最小，负数的绝对值之和最大，两者相加最小。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
char s[N];
int n;
vector<int> add(vector<int>& A, vector<int>& B) {
int c = 0;
vector<int> C;
reverse(A.begin(), A.end());
reverse(B.begin(), B.end());
for (int i = 0; i < A.size() || i < B.size(); ++i) {
if (i < A.size()) c += A[i];
if (i < B.size()) c += B[i];
C.push_back(c % 10);
c /= 10;
}
while (c > 0) C.push_back(c % 10), c /= 10;
reverse(C.begin(), C.end());
return C;
}
vector<int> sub(vector<int>& A, vector<int>& B) {
reverse(A.begin(), A.end());
reverse(B.begin(), B.end());
for(int i = 0; i < A.size(); ++i) {
int c = A[i];
if(i < B.size()) c -= B[i];
if(c < 0) A[i + 1] -= 1, c += 10;
A[i] = c;
}
while(A.size() > 1 && A.back() == 0) A.pop_back();
reverse(A.begin(), A.end());
return A;
}
int main()
{
scanf("%s", s + 1);
n = strlen(s + 1);
vector<int> A;
int positive = 0;
for (int i = 1; i <= n; ++i) {
if (s[i] == '-' && i + 1 <= n && isdigit(s[i + 1])) {
vector<int> B;
int j = i + 1;
while (j <= n && isdigit(s[j])) {
B.push_back(s[j] - '0');
j += 1;
}
A = add(A, B);
i = j - 1;
} else if (isdigit(s[i])) {
int j = i;
while (j <= n && isdigit(s[j])) {
positive += (s[j] - '0');
j += 1;
}
i = j - 1;
}
}
vector<int> B;
while (positive > 0) B.push_back(positive % 10), positive /= 10;
reverse(B.begin(), B.end());
if (B.size() < A.size()) {
printf("-");
} else if (B.size() == A.size()) {
for (int i = 0; i < A.size(); ++i) {
if (A[i] != B[i]) {
if (A[i] > B[i]) {
printf("-");
} else {
swap(A, B);
}
break;
}
}
} else {
swap(A, B);
}
vector<int> res = sub(A, B);
for (auto u: res) printf("%d", u);
printf("\n");
return 0;
}
|
C. 整除
题意：
给定一个整数 $m$ ，以及一个包含 $n$ 个整数的数组 $a$。
问 $a$ 中是否存在连续一段，这段整数之和是 $m$ 的倍数。
数据范围：$1\leq m\leq 10^8, 1\leq n\leq 1000, 1\leq a_i\leq 400000$
题解：
考虑 $a$ 的前缀和对 $m$ 取模的值 $value$ ，如果 $value$ 在之前出现过，说明存在连续的一段数之和为 $m$ 的倍数。
用一个 $set$ 存储出现过的前缀和，要特判 0 或者将 0 事先就添加到 $set$ 中去。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m;
int a[N];
set<int> S;
void solve() {
S.clear();
int sum = 0;
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = 1; i <= n; ++i) {
sum = (sum + a[i]) % m;
if (sum == 0 || S.count(sum)) {
puts("1");
return ;
}
S.insert(sum);
}
puts("0");
}
int main()
{
while (~scanf("%d%d", &n, &m)) {
solve();
}
return 0;
}
|