填空题
卡片
直接模拟。
展开代码
#include <bits/stdc++.h>
using ll = long long;
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
std::map<char, int> mp;
for (int i = 0; i <= 9; i++) {
mp[i + '0'] = 2021;
}
for (int i = 1; ; i++) {
for (char j : std::to_string(i)) {
if (mp[j] > 0) {
mp[j] -= 1;
} else {
std::cout << i - 1 << '\n';
std::exit(0);
}
}
}
return 0;
}
直线
分类讨论：水平、竖直或者是斜着（记下斜率 \(k\) 和截距 \(b\)），注意到给定坐标情况下，使用 std::atan2(y, x) 计算斜率 \(k = \dfrac{y}{x}\)；直线方程使用两点式：
从而解出截距 \(b = \dfrac{x_0y_1-x_1y_0}{x_1-x_0}\)。
展开代码
#include <bits/stdc++.h>
using ll = long long;
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
std::vector<std::pair<int, int>> p;
const int n = 20, m = 21;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
p.emplace_back(i, j);
}
}
std::set<std::pair<double, double>> s;
std::set<int> kind[2]{};
int t = p.size();
for (int i = 0; i < t; i++) {
int x_0 = p[i].first, y_0 = p[i].second;
for (int j = i + 1; j < t; j++) {
int f = 0;
int x_1 = p[j].first, y_1 = p[j].second;
if (x_0 == x_1) kind[0].insert(x_0), f++;
if (y_0 == y_1) kind[1].insert(y_0), f++;
if (f == 0) {
double k = std::atan2(y_1 - y_0, x_1 - x_0);
double t = 1. * (x_0 * y_1 - x_1 * y_0) / (x_1 - x_0);
s.emplace(k, t);
}
}
}
std::cout << kind[0].size() + kind[1].size() + s.size() << '\n';
return 0;
}
货物摆放
即求有多少可重排列，使得 \(n = 2021041820210418 = 2\times3^3\times17\times131\times2857\times5882453 = pqr\)。由隔板法，答案为 \(3!{8 + 3 - 1 \choose 3 - 1} = 2430\)。
路径
\(n = 2000\)，在本机使用 Floyd 跑出结果之后交。
展开代码
#include <bits/stdc++.h>
using ll = long long;
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
// std::cout << 10266837 << '\n';
// return 0;
const int N = 2021 + 10;
ll g[N][N]{};
for (int i = 1; i <= 2021; i++) {
for (int j = 1; j <= 2021; j++) {
if (std::abs(i - j) <= 21) {
g[i][j] = g[j][i] = 1ll * i * j / std::__gcd(i, j);
} else {
g[i][j] = g[j][i] = 0x3f3f3f3f;
}
}
}
for (int k = 1; k <= 2021; k++) {
for (int i = 1; i <= 2021; i++) {
for (int j = 1; j <= 2021; j++) {
g[i][j] = std::min(g[i][j], g[i][k] + g[k][j]);
}
}
}
std::cout << g[1][2021] << '\n';
return 0;
}
回路计数
即求哈密顿回路数，状压即可。
展开代码
#include <bits/stdc++.h>
using ll = long long;
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
// std::cout << "881012367360" << '\n';
// return 0;
const int n = 21;
static std::array<std::array<int, n>, n> g{};
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (std::__gcd(i + 1, j + 1) == 1) {
g[i][j] = g[j][i] = 1;
}
}
}
static std::array<std::array<ll, n>, 1 << n> f{};
f[1][0] = 1;
for (int i = 1; i < 1 << n; i++) {
for (int j = 0; j < n; j++) {
if ((i >> j & 1) && f[i][j]) { // `j` selected
for (int k = 0; k < n; k++) {
if (((i ^ (1 << j)) >> k & 1) && g[k][j]) {
f[i][j] += f[i ^ (1 << j)][k];
}
}
}
}
}
std::cout << std::accumulate(f.back().begin(), f.back().end(), 0ll) << '\n';
return 0;
}
空间
\(1 \mathrm{Byte} = 8 \mathrm{bit}s\)，因此答案为 \(\dfrac{256\times1024^2\times8}{32} = 67108864\)。
相乘
即求 \(2021x \equiv 999999999 \bmod 1000000007\)，\(x \equiv 999999999 \times 2021 ^ {-1}\) 求得 \(x = 17812964\)。
mod = 1000000007
x = pow(2021, mod - 2, mod) * 999999999 % mod
print(x)
编程题
砝码称重
同 01 背包，只是转移到左右。可使用 std::bitset 的 operator<< 实现。
展开代码
#include <bits/stdc++.h>
using ll = long long;
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
std::bitset<100010> f;
f[0] = 1;
for (int i : a) f |= f << i;
for (int i : a) f |= f >> i;
f[0] = 0;
std::cout << f.count() << '\n';
return 0;
}
特别注意如果使用 01 背包写法，想在一个循环里完成，需要开两维。
核心代码
int B = 100000;
std::vector<std::vector<int>> f(2, std::vector<int>(2 * B + 10, 0));
f[0][0 + B] = 1;
for (int i = 1; i <= n; i++) {
int w = a[i - 1];
for (int j = -m + B; j <= m + B; j++) {
f[i & 1][j] = f[~i & 1][j];
if (j - w >= -m + B) f[i & 1][j] |= f[~i & 1][j - w];
if (j + w <= +m + B) f[i & 1][j] |= f[~i & 1][j + w];
}
}
int ans = 0;
for (int i = 1 + B; i <= m + B; i++) {
ans += f[n & 1][i];
}
异或数列
容易发现平局当且仅当 \(\bigoplus\limits_{i=1}^n X_n = 0\)：记下每一位的次数，从高到低按位贪心，可见如果当前位为偶数则必然不会栽在这个位上。
话接上文，如果当前为出现次数 \(c = 1\)，则先手胜利；若为其他奇数，后手可以选择一个 \(c \ne 1\) 的数来反转，因此当 \(n - c \equiv 0 \bmod 2\) 时先手胜利，否则后手胜利。
展开代码
#include <bits/stdc++.h>
using ll = long long;
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int test = 1;
std::cin >> test;
void solve();
while (test--) solve();
return 0;
}
void solve() {
int n;
std::cin >> n;
std::array<int, 30> cnt{};
int s = 0;
for (int i = 0; i < n; i++) {
int x;
std::cin >> x;
for (int i = 20; ~i; i--) if (x >> i & 1) cnt[i] += 1;
s ^= x;
}
if (!s) {
std::cout << "0\n";
return;
}
for (int i = 20; ~i; i--) if (cnt[i] & 1) {
if (cnt[i] == 1) std::cout << "1\n";
else if ((n - cnt[i]) & 1) std::cout << "-1\n";
else std::cout << "1\n";
break;
}
}
左孩子右兄弟
用 \(f_u\) 表示 \(u\) 节点对应的答案，可见 \(f_u\) 至少是 \(u\) 的儿子数量，另有 \(\mathop\max\limits_{v \in u}\{f_v\}\)。
展开代码
#include <bits/stdc++.h>
using ll = long long;
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int n;
std::cin >> n;
std::vector<std::vector<int>> g(n + 1);
for (int i = 1; i < n; i++) {
int u;
std::cin >> u;
g[u].push_back(i + 1);
}
std::vector<int> f(n + 1);
std::function<void(int)> dfs = [&](int u) -> void {
f[u] = g[u].size();
int max = 0;
for (int v : g[u]) dfs(v), max = std::max(max, f[v]);
f[u] += max;
};
dfs(1);
std::cout << f[1] << '\n';
return 0;
}
括号序列
既考虑左括号又考虑右括号很麻烦，不如分开考虑，最终的方案数相乘即可。如对于序列 \())((\)，可以只添加左括号使之成为：\(\color{red}{((}\)\())((\) 或 \(\color{red}{(}\)\()\)\(\color{red}{(}\)\()((\)；只添加右括号时，要转换为上面的问题，将序列反转再翻转：\())((\)，方案是一样的。因此最终答案为 \(4\)。接下来只需解决放左括号的方案数。
将原始序列按照右括号分成若干片段，研究某一段还需要放多少左括号。用 \(f_{i, j}\) 表示前缀 \(i\) 放置 \(j\) 个左括号使之合法（这里指的是左括号不少于右括号数量）的方案数。如果 \(s_i = \tt `('\)，方案数同 \(f_{i - 1, j - 1}\)；否则 \(f_{i, j} = \sum\limits_{k = 0}^{j + 1} f_{i - 1, k} = f_{i, j - 1} + f_{i - 1, j + 1}\)。最终答案即为前缀 \(i\) 放置至少 \(j'\) 个左括号使之合法的方案数。按照定义即使得 \(f_{n, j'} \ge 0\) 的最小 \(j'\)。
展开代码
#include <bits/stdc++.h>
using ll = long long;
const int mod = 1000000007, N = 5002;
ll f[N][N];
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
std::string s;
std::cin >> s;
int n = s.size();
f[0][0] = 1;
for (int i = 1; i <= n; i++) {
if (s[i - 1] == '(') {
for (int j = 1; j <= n; j++) {
f[i][j] = f[i - 1][j - 1];
}
} else {
f[i][0] = (f[i - 1][0] + f[i - 1][1]) % mod;
for (int j = 1; j <= n; j++) {
f[i][j] = (f[i - 1][j + 1] + f[i][j - 1]) % mod;
}
}
}
ll l = -1;
for (int i = 0; i <= n; i++) {
if (f[n][i]) {
l = f[n][i];
break;
}
}
for (auto &si : s) {
si ^= '(' ^ ')';
}
std::reverse(s.begin(), s.end());
for (int i = 0; i <= n + 1; i++) {
for (int j = 0; j <= n + 1; j++) {
f[i][j] = 0;
}
}
f[0][0] = 1;
for (int i = 1; i <= n; i++) {
if (s[i - 1] == '(') {
for (int j = 1; j <= n; j++) {
f[i][j] = f[i - 1][j - 1];
}
} else {
f[i][0] = (f[i - 1][0] + f[i - 1][1]) % mod;
for (int j = 1; j <= n; j++) {
f[i][j] = (f[i - 1][j + 1] + f[i][j - 1]) % mod;
}
}
}
ll r = -1;
for (int i = 0; i <= n; i++) {
if (f[n][i]) {
r = f[n][i];
break;
}
}
std::cout << l * r % mod << '\n';
return 0;
}
时间显示
不考虑毫秒，直接 /= 1000，接着直接分解各位。
展开代码
#include <bits/stdc++.h>
using ll = long long;
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int test = 1;
std::cin >> test;
void solve();
while (test--) solve();
return 0;
}
void solve() {
ll x;
std::cin >> x;
x /= 1000;
ll h = 24, m = 60, s = 60;
x %= h * m * s;
std::cout << std::fixed << std::setw(2) << std::setfill('0');
std::cout << x / (m * s) << ':';
std::cout << std::fixed << std::setw(2) << std::setfill('0');
std::cout << x % (m * s) / m << ':';
std::cout << std::fixed << std::setw(2) << std::setfill('0');
std::cout << x % s << '\n';
}
iostream sucks~
杨辉三角形
看到数据范围 \(10^9\)，大概率也是二分或者有结论。尝试二分的话，得寻找单调性，杨辉三角最明显的单调性莫过于每一条斜线了（自上而下）。注意到杨辉三角对称，不妨按照 \({n \choose n / 2}\) 来找。注意组合数容易爆精度，只要大于 \(x\) 就直接返回，反正需要的也只是 \(\ge x\) 的单调性而已。因为 \(10^9 \leq {30 \choose 15}\)。
展开代码
#include <bits/stdc++.h>
using ll = long long;
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int test = 1;
std::cin >> test;
void solve();
while (test--) solve();
return 0;
}
int x;
ll binom(int n, int m) {
ll res = 1;
for (int i = n, j = 1; j <= m; i--, j++) {
res = res * i / j;
if (res > x) {
return res;
}
}
return res;
}
void solve() {
std::cin >> x;
for (int i = 16;; i--) {
int l = 2 * i, r = std::max(x, l);
while (l < r) {
int mid = (l + r) / 2;
if (binom(mid, i) >= x) r = mid;
else l = mid + 1;
}
if (binom(r, i) == x) {
std::cout << 1ll * (r + 1) * r / 2 + i + 1 << '\n';
return;
}
}
__builtin_unreachable();
}
双向排序
注意到有许多步骤，是不需要的：例如 \(x \leq y\) 时 \([1, x], [1, y]\) 中就不需要跑 \([1, x]\)，另一个方向也类似。另外如果第一次操作为 \([x, n]\) 是不需要跑的。
接下来问题转变为两种操作交替时，该如何减少操作次数。观察下面的操作：
\(1. 0, 3\), \([\underline{3, 2, 1}, 4, 5, 6, 7]\)
\(2. 1, 4\), \([3, 2, 1, \underline{4, 5, 6, 7}]\)
\(3. 0, 5\), \([\underline{5, 4, 3, 2, 1}, 6, 7]\)
在这里，前两次操作没有交集，这两次结果被第三次覆盖了，相当于直接从初始状态到第三步。
下面要解决的问题就只有放置了，由于任意相邻两步必有交，因此只能放那些与自己无关的区间，例如 \(0, 5\) 就可以将答案数组置为 \([0, 0, 0, 0, 0, \underline{6, 7}]\)；再下一步 \(1, 2\)，可以将答案置为 \([5, 0, 0, 0, 0, 6, 7]\), ... 以此类推。
注意如果所有操作区间的并不为 \([1, n]\)，还需要按照最后一次操作种类填满。
展开代码
#include <bits/stdc++.h>
using ll = long long;
const int N = 100010;
int stk[N][2], ans[N];
int top;
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int n, m;
std::cin >> n >> m;
while (m--) {
int p, q;
std::cin >> p >> q;
if (p == 0) {
while (top && stk[top][0] == 0)
q = std::max(q, stk[top --][1]);
while (top >= 2 && stk[top - 1][1] <= q)
top -= 2;
stk[++top][0] = p, stk[top][1] = q;
} else if (top) {
while (top && stk[top][0] == 1)
q = std::min(q, stk[top --][1]);
while (top >= 2 && stk[top - 1][1] >= q)
top -= 2;
stk[++top][0] = p, stk[top][1] = q;
}
}
int k = n, l = 1, r = n;
for (int i = 1; i <= top; i++) {
if (stk[i][0] == 0) {
while (l <= r && r > stk[i][1])
ans[r--] = k--;
} else {
while (l <= r && l < stk[i][1])
ans[l++] = k--;
}
if (l > r)
break;
}
if (top & 1) {
while (l <= r) ans[l++] = k--;
} else {
while (l <= r) ans[r--] = k--;
}
std::copy(ans + 1, ans + n + 1, std::ostream_iterator<int> {std::cout, " "});
return 0;
}
最少砝码
实际上为平衡三进制最少需要多少底数。实际上有，\(n\) 位平衡三进制，每一位都包含 \(1, z\)，可以表示 \([-\dfrac{3^n - 1}{2}, \dfrac{3^n - 1}{2}]\) 内的所有数，即需要 \(\log_3(2 n + 1)\) 个数。
展开代码
#include <bits/stdc++.h>
using ll = long long;
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int test = 1;
std::cin >> test;
void solve();
while (test--) solve();
return 0;
}
void solve() {
ll x;
std::cin >> x;
auto y = std::log(2 * x + 1) / std::log(3);
std::cout << (int)(std::ceil(y) + .5) << '\n';
}