目录

XCPC 2021 补题 memo

闲着无聊做做,看看退役选手还能写出来些啥。

题解 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
38
#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';
  }
}