比赛链接：https://atcoder.jp/contests/abc172/tasks
给出一个正整数 $a$，计算 $a + a^2 + a^3$ 。($1 \le a \le 10$)
#include <bits/stdc++.h> using namespace std; int main() { int a; cin >> a; cout << a + a * a + a * a * a; }
给出两个等长的字符串 $s$ 和 $t$，每次可以替换 $s$ 中的一个字符，问使 $s$ 和 $t$ 相等至少要替换多少字符。
不同的字符是一定要替换的。
#include <bits/stdc++.h> using namespace std; int main() { string s, t; cin >> s >> t; int cnt = 0; for (int i = 0; i < s.size(); i++) if (s[i] != t[i]) ++cnt; cout << cnt << "\n"; }
有两摞书，一摞有 $n$ 本，从上至下每本需阅读 $a_i$ 分钟，一摞有 $m$ 本，从上至下每本需阅读 $b_i$ 分钟，问最多能在 $k$ 分钟内读多少本书。
计算两摞书阅读时长的前缀和，枚举从第一摞书中读多少本，余下的时间用二分或双指针查找能在第二摞书中读多少本。
二分
#include <bits/stdc++.h> using ll = long long; using namespace std; int main() { int n, m, k; cin >> n >> m >> k; ll pre_a[n + 1] = {}; for (int i = 0; i < n; i++) { int x; cin >> x; pre_a[i + 1] = pre_a[i] + x; } ll pre_b[m + 1] = {}; for (int i = 0; i < m; i++) { int x; cin >> x; pre_b[i + 1] = pre_b[i] + x; } int ans = 0; for (int i = 0; i < n + 1; i++) { ll ex = k - pre_a[i]; if (ex >= 0) { int j = upper_bound(pre_b, pre_b + m + 1, ex) - pre_b - 1; ans = max(ans, i + j); } } cout << ans << "\n"; }
双指针
#include <bits/stdc++.h> using ll = long long; using namespace std; int main() { int n, m, k; cin >> n >> m >> k; ll pre_a[n + 1] = {}; for (int i = 0; i < n; i++) { int x; cin >> x; pre_a[i + 1] = pre_a[i] + x; } ll pre_b[m + 1] = {}; for (int i = 0; i < m; i++) { int x; cin >> x; pre_b[i + 1] = pre_b[i] + x; } int ans = 0; for (int i = 0, j = m; i < n + 1; i++) { ll ex = k - pre_a[i]; if (ex >= 0) { while (j >= 0 and pre_b[j] > ex) --j; ans = max(ans, i + j); } } cout << ans << "\n"; }
设 $f_{(x)}$ 为 $x$ 正因子的个数。计算 $\sum_{i = 1}^n i \times f_{(i)}$ 。
筛得每个数的因子个数，求和即可。
#include <bits/stdc++.h> using ll = long long; using namespace std; const int N = 1e7 + 10; ll f[N]; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) for (int j = i; j <= n; j += i) ++f[j]; ll ans = 0; for (int i = 1; i <= n; i++) ans += i * f[i]; cout << ans << "\n"; }
代码一简化而得
#include <bits/stdc++.h> using ll = long long; using namespace std; int main() { int n; cin >> n; ll ans = 0; for (int i = 1; i <= n; i++) for (int j = i; j <= n; j += i) ans += j; cout << ans << "\n"; }
给出 $n, m$，计算有多少对大小为 $n$ 的数列 $a, b$ 满足：
\begin{equation} A_m^n ( \sum_{i = 0}^n (-1)^{i} C_n^i A_{m - i}^{n - i}) \nonumber \end{equation}
$A_m^n$，$m$ 个数排 $n$ 个位置，即合法的 $a$ 的个数
$\sum$，对于每个合法的 $a$ 来说，合法的 $b$ 的个数
#include <bits/stdc++.h> using ll = long long; using namespace std; const int N = 5e5 + 10; const int mod = 1e9 + 7; ll fac[N]; ll binpow(ll a, ll b) { ll res = 1; while (b > 0) { if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; } void init() { fac[0] = 1; for (int i = 1; i < N; i++) fac[i] = fac[i - 1] * i % mod; } ll inv(ll a) { return binpow(a, mod - 2); } ll A(ll n, ll m) { return fac[n] * inv(fac[n - m]) % mod; } ll C(ll n, ll m) { return fac[n] * inv(fac[m]) % mod * inv(fac[n - m]) % mod; } int main() { init(); int n, m; cin >> n >> m; ll sum = 0; for (int i = 0; i <= n; i++) { sum += binpow(-1, i) * C(n, i) * A(m - i, n - i) % mod; sum = (sum + mod) % mod; } cout << A(m, n) * sum % mod << "\n"; }
原文：https://www.cnblogs.com/Kanoon/p/13202280.html