闲着无聊做做，看看退役选手还能写出来些啥。
题解 memo，保持更新。（反正应该没几天就腻了）
CCPC 威海
Codeforeces Gym: http://codeforces.com/gym/103428
A. Goodbye, Ziyin
签到，输入保证是一棵树，那么这棵树有超过 3 度的节点就不能构成有根二叉树了，剩下就数一下度数为 1 和 2 的节点数，他们做根都合法。读进来扫两遍，复杂度 $\mathcal{O}(n)$。
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
| #include <iostream>
using namespace std;
const int SIZE = 1e6 + 10;
int deg[SIZE], cnt[SIZE];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
bool exceeded = false;
for (int i = 0; i < n - 1; i++) {
int x, y;
cin >> x >> y;
cnt[x]++, cnt[y]++;
}
for (int i = 1; i <= n; i++) {
deg[cnt[i]]++;
if (cnt[i] > 3 && deg[cnt[i]]) {
exceeded = true;
break;
}
}
if (exceeded) {
cout << "0\n";
} else {
cout << deg[1] + deg[2] << '\n';
}
}
|
D. Period
输入只有小写字母，改成 # 之后构不成新的循环节，所以看插入 # 之后剩几个循环节即可。
考虑不跨过中心线的循环节，可知循环次数至少为 3（也就是子串至少出现 3 次），那破坏任何一个位置循环都会被打破，此时无法构成循环节，故这种情况统统不考虑；对于跨过中心线的循环节，只要此时不修改前缀和后缀重合的部分，这个循环节就不会被破坏。
找循环节可以用 kmp 求出来 border，也就是前缀和后缀匹配的长度，然后剔除掉所有不合法的情况，在距离上二分一下当前位置为 # 之后，前面还有几个 border 不会被破坏即可。kmp $\mathcal{O}(|s|)$，合法 border 数量大概就 $\mathcal{O}(\log\frac{|s|}{2})$个，所以最后总复杂度就是 $\mathcal{O}(|s| + q\log\log |s|)$。
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
| #include <algorithm>
#include <iostream>
#include <queue>
#include <string>
using namespace std;
vector<int> get_next(const string& s) {
int j = -1;
vector<int> nxt{-1};
for (int i = 0; i < s.size(); i++) {
while (j != -1 && s[i] != s[j]) j = nxt[j];
nxt.push_back(++j);
}
return nxt;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
string s;
cin >> s;
auto nxt = get_next(s);
int sz = s.size();
int border = sz;
deque<int> borders;
while (nxt[border] != 0) {
border = nxt[border];
if (2 * border < sz) {
borders.push_front(border);
}
}
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int t;
cin >> t;
auto p = upper_bound(borders.begin(), borders.end(), min(t - 1, sz - t));
cout << p - borders.begin() << '\n';
}
}
|
G. Desserts
意义不明的数数题，感觉像是为了平衡难度硬凑的。
每个甜点的分发都是独立的，那任意甜点 $a$ 分给某些队伍 $k$ 就是简单的 $\binom{k}{a}$，所以针对某个 $k$，合法的数量就是 $\prod_{i=1}^n\binom{k}{a_i}$。
针对每个 $k$ 拆一下式子，答案变成了：
$$
\text{ans}_k = \prod_{i=1}^n\binom{k}{a_i} = \frac{(k!)^n}{\prod_{i=1}^n{a_i!}{\prod_{i=1}^n{(k-a_i)!}}}
$$
$(k!)^n$ 直接快速幂一下，然后 $\prod_{i=1}^n{a_i!}$ 读进来的时候就可以预处理掉。而根据限制 $0\le a_i\le 10^5, \sum_{i=1}^n a_i\le10^5$ 可知 $a_i$ 的种类就是 $\sqrt{\sum_{i=1}^n a_i}$ 级别的，时间复杂度是够的，搞个 unordered_map 算一下数量就行。
然后这个题就做完了，总复杂度 $\mathcal{O}(m\sqrt{\sum a}\log n)$，就是独立分析一下，默写几个板子就做完了。
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
| #include <iostream>
#include <unordered_map>
using namespace std;
using ll = long long;
const int MOD = 998244353;
const int SIZE = 1e5 + 10;
ll fact[SIZE], inv[SIZE];
ll bp(ll a, ll x) {
ll ans = 1;
while (x) {
if (x & 1) {
ans = ans * a % MOD;
}
a = a * a % MOD;
x >>= 1;
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
fact[0] = 1;
for (int i = 1; i < SIZE; i++) {
fact[i] = fact[i - 1] * i % MOD;
}
inv[SIZE - 1] = bp(fact[SIZE - 1], MOD - 2);
for (int i = SIZE - 2; i >= 0; i--) {
inv[i] = inv[i + 1] * (i + 1) % MOD;
}
int n, m;
cin >> n >> m;
ll total = 1;
unordered_map<int, int> rec;
for (int i = 0; i < n; i++) {
int a;
cin >> a;
total = total * inv[a] % MOD;
rec[a]++;
}
for (int i = 1; i <= m; i++) {
ll ans = bp(fact[i], n) * total % MOD;
for (auto [a, t] : rec) {
if (i < a) {
ans = 0;
break;
}
ans = ans * bp(inv[i - a], t) % MOD;
}
cout << ans << '\n';
}
}
|
J. Circular Billiard Table
根据题目，台球在桌子里滚动和碰撞不损失能量，那小球绕一定圈数过后肯定能绕出来。单纯靠反弹的话，两次相邻碰撞点构成的圆心角也是不会变的，那就是看小球能在圆里撞几圈。
图上比划一下就能得出来圆心角大小是 $2\beta$，假设小球撞 $n$ 次就能出来，那肯定对某个系数 $w$ 满足 $n2\beta|360w$，此时 $n$ 和 $w$ 都是最小的。
凑这个 $w$ 非常简单，先把 $\beta=\frac{a}{b}$ 带入上面那个式子，化简成最简分数一下得到 $n=\frac{180b’}{a’}$，发现凑个 $w=a’$ 就整除了，答案就是 $180b’$，也就是说这个 $w$ 啥用没有，读进来 __gcd 一下然后除一下就是答案了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include <iostream>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin >> T;
while (T--) {
ll a, b;
cin >> a >> b;
ll g = __gcd(b * 180, a);
cout << b * 180 / g - 1 << '\n';
}
}
|