0

XCPC 2021 补题 memo

 2 years ago
source link: https://blog.lxdlam.com/post/8697249c/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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

题解 memo，保持更新。（反正应该没几天就腻了）

CCPC 威海

Codeforeces Gym: http://codeforces.com/gym/103428

A. Goodbye, Ziyin!

签到，输入保证是一棵树，那么这棵树有超过 3 度的节点就不能构成有根二叉树了，剩下就数一下度数为 1 和 2 的节点数，他们做根都合法。读进来扫两遍，复杂度 O(n)\mathcal{O}(n)O(n)。

#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 O(∣s∣)\mathcal{O}(|s|)O(∣s∣)，合法 border 数量大概就 O(log⁡∣s∣2)\mathcal{O}(\log\frac{|s|}{2})O(log2∣s∣​)个，所以最后总复杂度就是 O(∣s∣+qlog⁡log⁡∣s∣)\mathcal{O}(|s| + q\log\log |s|)O(∣s∣+qloglog∣s∣)。

#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

意义不明的数数题，感觉像是为了平衡难度硬凑的。

每个甜点的分发都是独立的，那任意甜点 aaa 分给某些队伍 kkk 就是简单的 (ka)\binom{k}{a}(ak​)，所以针对某个 kkk，合法的数量就是 ∏i=1n(kai)\prod_{i=1}^n\binom{k}{a_i}∏i=1n​(ai​k​)。

针对每个 kkk 拆一下式子，答案变成了：

ansk=∏i=1n(kai)=(k!)n∏i=1nai!∏i=1n(k−ai)! \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)!}}} ansk​=i=1∏n​(ai​k​)=∏i=1n​ai​!∏i=1n​(k−ai​)!(k!)n​

(k!)n(k!)^n(k!)n 直接快速幂一下，然后 ∏i=1nai!\prod_{i=1}^n{a_i!}∏i=1n​ai​! 读进来的时候就可以预处理掉。而根据限制 0≤ai≤105,∑i=1nai≤1050\le a_i\le 10^5, \sum_{i=1}^n a_i\le10^50≤ai​≤105,∑i=1n​ai​≤105 可知 aia_iai​ 的种类就是 ∑i=1nai\sqrt{\sum_{i=1}^n a_i}∑i=1n​ai​​ 级别的，时间复杂度是够的，搞个 unordered_map 算一下数量就行。

然后这个题就做完了，总复杂度 O(m∑alog⁡n)\mathcal{O}(m\sqrt{\sum a}\log n)O(m∑a​logn)，就是独立分析一下，默写几个板子就做完了。

#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β2\beta2β，假设小球撞 nnn 次就能出来，那肯定对某个系数 www 满足 n2β∣360wn2\beta|360wn2β∣360w，此时 nnn 和 www 都是最小的。

凑这个 www 非常简单，先把 β=ab\beta=\frac{a}{b}β=ba​ 带入上面那个式子，化简成最简分数一下得到 n=180b′a′n=\frac{180b'}{a'}n=a′180b′​，发现凑个 w=a′w=a'w=a′ 就整除了，答案就是 180b′180b'180b′，也就是说这个 www 啥用没有，读进来 __gcd 一下然后除一下就是答案了。

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

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK