AgOH

Codeforces Round #824 (Div. 2) 题解

字数统计: 341阅读时长: 1 min
2022/10/04

A. Working Week

直接输出 \(n/3-2\) 即可。

B. Tea with Tangerines

找到最小一片橘子皮,设其大小为 \(x\),则其他橘子皮(设大小为 \(y\))对答案的贡献为 \(\lceil \cfrac{y}{2x-1} \rceil - 1\)

C. Phase Shift

遍历字符串中的每个字母 \(\texttt{c}\),若已知其前方字母则直接输出,否则贪心地选择尽量小、没有后项、且与 \(\texttt{c}\) 连接后不会成一个大小小于 \(26\) 的环的字母作为其前方字母。使用两个哈希表维护一个字母的前后项,判环可以使用并查集维护。

D. Meta-set

一个 Meta-set 中必定包括两个好牌组,且两个好牌组只能有一张重复的牌,我们称这张重复的牌为“中心牌”,则若某张牌出现在了 \(x\) 个好牌组中,以其为中心牌的 Meta-set 即有 \(x(x-1)\) 个。

考虑如何获取 \(x\) 值,我们只需要遍历每个牌对,并求出这两张牌的补集,并将补集的 \(x\) 值加一即可。这个过程可以使用哈希表来维护。

CATALOG
  1. 1. A. Working Week
  2. 2. B. Tea with Tangerines
  3. 3. C. Phase Shift
  4. 4. D. Meta-set