T1：角谷猜想
模拟
代码实现
n = int(input())
while n > 1:
if n%2 == 1:
n = n*3+1
else:
n //= 2
print(n, end=' ')
T2：屏幕比例
约分
代码实现
// py
import math
x, y = map(int, input().split('*'))
g = math.gcd(x, y)
x //= g
y //= g
print('%d:%d' % (x, y))
// C++
#include <bits/extc++.h>
using std::cin;
using std::cout;
using std::gcd;
int read() {
int x = 0;
char c;
while (c < '0' or c > '9') c = getchar();
while ('0' <= c and c <= '9') {
x = x*10+(c-'0');
c = getchar();
}
return x;
}
int main() {
int x = read(), y = read();
int g = gcd(x, y);
x /= g;
y /= g;
cout << x << ':' << y << '\n';
return 0;
}
T3：最大子串
方法一：
枚举起点和终点，有 \(O(n^2)\) 种可能性。对于每个序列我们可以遍历其所有数，求出序列的数字和。总复杂度：\(O(n^3)\)
方法二：
引入 \(s\) 数组，表示前缀和，s[i] 表示前 \(i\) 个数之和。于是起点为 \(i\)，终点为 \(j\) 的数字和就是 \(s[j] - s[i-1]\)。总复杂度：\(O(n^2)\)
方法三：
定下终点，因为我们求的是最大子段和，其实只需要考虑 \(i \leqslant j\) 的情况下最小的 \(s[i-1]\)。总复杂度: \(O(n)\)
代码实现
#include <bits/extc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::min;
using std::max;
using std::vector;
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, n) cin >> a[i];
vector<int> s(n+1);
rep(i, n) s[i+1] = s[i]+a[i];
int ans = 0;
int mn = 0;
for (int i = 1; i <= n; ++i) {
int now = s[i]-mn;
ans = max(ans, now);
mn = min(mn, s[i]);
}
cout << ans << '\n';
return 0;
}