在我的不懈努力之下，通过神秘的瞪眼法在 00:00 过了这道题，当了 1 分钟的（并列）rank 1
斩获红名表现分。
（然后 B 就差点坠机了）
1
2
3
4
5
|
auto solve() {
i64 a;
std::cin >> a;
std::cout << 2 * a << endl;
}
|
笑点解析：
- 把计算 $l$ 的个数看成计算 $(l, r)$ 的个数对着样例哈气了 30 分钟；
- 因为「别 tm define int long long」于是没开 long long，wa 了一发。
唉唉，天罚。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
auto solve() {
i64 n, k, x;
std::cin >> n >> k >> x;
i64 ssum = 0;
std::vector<i64> b(n);
for (auto& x : b) {
std::cin >> x;
ssum += x;
}
if (ssum * k < x) {
std::cout << 0 << endl;
return;
}
i64 sum = 0;
i64 base = x / ssum;
x %= ssum;
rgs::reverse(b);
i64 cur = 0;
while (cur < n * k and sum < x) {
sum += b[(cur++) % n];
}
std::cerr << cur << endl;
std::cout << n * k - (base * n + cur) + 1 << endl;
}
|
典中典之置换环。
某位 louisdlee 指出：「这种题都做过 114514 遍了。」
赛时手写了一个 DSU，赛后直接套模板。
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
|
auto solve() {
int n;
std::cin >> n;
std::vector<int> p(n);
for (auto& x : p) {
std::cin >> x;
x--;
}
DSU dsu(n);
for (int i = 0; i < n; i++) {
dsu.merge(i, p[i]);
}
std::set<int> st;
int ans = 0;
for (int i = 0; i < n; i++) {
int x;
std::cin >> x;
x--;
int fa = dsu.find(x);
if (not st.count(fa)){
st.insert(fa);
ans += dsu.size(x);
}
std::cout << ans << " \n"[i == n - 1];
}
}
|
神秘背包&组合数学。
这次抄到模板了😋
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
|
std::vector<i64> fact(maxn), inv_fact(maxn);
auto power(i64 a, i64 b) {
i64 res = 1;
while (b) {
if (b & 1) res = res * a % modn;
a = a * a % modn;
b >>= 1;
}
return res;
}
void pre() {
fact[0] = inv_fact[0] = 1;
for (int i = 1; i < maxn; i++) {
fact[i] = fact[i - 1] * i % modn;
}
inv_fact[maxn - 1] = power(fact[maxn - 1], modn - 2);
for (int i = maxn - 2; i > 0; i--) {
inv_fact[i] = inv_fact[i + 1] * (i + 1) % modn;
}
}
auto solve() {
std::array<int, 26> c = {};
i64 sum = 0;
for (auto& x : c) {
std::cin >> x;
sum += x;
}
if (sum == 0) {
std::cout << 1 << endl;
return;
}
i64 cnte = sum / 2, cnto = (sum + 1) / 2;
std::vector<i64> dp(cnto + 1);
dp[0] = 1;
for (auto x : c) {
if (x == 0)
continue;
for (int i = cnte; i >= x; i--) {
if (dp[i - x]) {
dp[i] = (dp[i] + dp[i - x]) % modn;
}
}
}
i64 k = dp[cnte];
if (k == 0) {
std::cout << 0 << endl;
return;
}
i64 num = fact[cnte] * fact[cnto] % modn;
i64 dinv = 1;
for (auto x : c) {
if (x == 0)
continue;
dinv = dinv * inv_fact[x] % modn;
}
i64 ans = k * num % modn;
ans = ans * dinv % modn;
std::cout << ans << endl;
}
|
总结
唉唉。