CF R 682 Engineer Artem [*2000]

  • https://codeforces.com/problemset/problem/1438/C

考虑奇偶性，显然如果一个偶数与奇数相邻，必然他们不相等。

直接考虑黑白染色，黑点改为奇数，白点改为偶数即可。

时间复杂度 O(tnm)O(tnm)。

https://codeforces.com/contest/1438/submission/117497127

Edu CF R 89 Two Divisors [*2000]

  • http://codeforces.com/problemset/problem/1366/D

考虑将每个数质因数分解，再来构造。

如果被分出来的两个因数 d1,d2d_1,d_2 满足 gcd⁡(d1,d2)=1\gcd(d_1,d_2)\not=1，那么他们的和会为 d×(d1d,d2d)d\times(\frac{d_1}{d},\frac{d_2}{d})，其中 dd 为 xx 的一个约数，这显然不可取。

所以，我们就有了一个构造方法，当 x=pkx\not =p^k 时，其中 p∈primep\in\text{prime}，无解，而其余情况，固定 xx 的任意一个质因子 dd，输出 xdk\frac{x}{d^k}，其中 xx 可被分解为 a×dk(a≡0(modd))a\times d^k(a\not \equiv 0\pmod d)。

时间复杂度：线性筛 O(107)O(10^7)，单次回答 O(log⁡x)O(\log x)，总时间复杂度 O(107+nlog⁡x)O(10^7+n\log x)。

http://codeforces.com/contest/1366/submission/117498343

CF R 223 Sereja and Brackets [*2000]

  • https://codeforces.com/problemset/problem/380/C

数据范围 10610^6，考虑 log⁡\log 级别数据结构。

考虑用线段树维护，对于每一段区间，维护三个值，靠左的右括号个数 ll，靠右的左括号个数 rr 以及当前匹配的括号个数 ansans。

pushup 时，直接考虑处理每一段接起来后中间可合并的括号。

时间复杂度：建树 O(nlog⁡n)O(n\log n)，询问 O(mlog⁡n)O(m\log n)，总时间复杂度 O((n+m)log⁡n)O((n+m)\log n)。

https://codeforces.com/problemset/submission/380/117713290

Edu CF R 46 We Need More Bosses [*2100]

  • https://codeforces.com/contest/1000/problem/E

显然有一个结论是，在同一个边双连通分量的点之间的答案为 00。

所以直接对边双缩点，在缩出来的树上求直径即可。

时间复杂度：O(n+m)O(n+m)。

https://codeforces.com/contest/1000/submission/117848026

Edu CF R 46 One Occurrence [*2400]

  • https://codeforces.com/problemset/problem/1000/F

大力莫队，O(nn)O(n\sqrt{n}) 过 5×1055\times 10^5 不是梦。

这个做法很卡，但还是过了。

考虑怎样维护答案，我们考虑求出出现个数为 11 的数，并用一个栈维护。

加入很好做，删除呢？

考虑记录出每个数所在栈的位置，把这个数踢出去的同时，把栈顶丢到这个数所在的位置。

这样，对于每一次询问，直接求栈顶的值即可。

时间复杂度：O(qn)O(q\sqrt{n})。

https://codeforces.com/contest/1000/submission/117852388

CF R 723 Kill Anton [*2200]

  • https://codeforces.com/problemset/problem/1526/D

有一个结论，就是答案串必然由连续的字母段组成。

所以，大力枚举连续字母段的组成，即 A、N、T、O 的一个排列。

剩下的，显然要考虑如何配对，又有一个结论，即在前面的字符匹配在原串中前面的相同字符，这样排队一定是最优的。

那么，对组成的序列编号后，对应编号，求逆序对即可。

时间复杂度 O(24nlog⁡n)O(24n\log n)。

https://codeforces.com/contest/1526/submission/117721441

CF R 643 Guess Divisors Count [*2600]

  • https://codeforces.com/problemset/problem/1355/F

精辟乱搞。

显然问出正确答案不切实际，考虑如何问出近似答案。

考虑尽量询问多的约数，所以开一个队列，尽量询问多的约数并统计答案。

在询问了 2222 次之后，我们可以乐观估计，小于 850850 的素因数已被询问出来，考虑剩下的数（以下 pp 表示任意大于 850850 的素数）：

  • 11：此时 d=ansd=ans；
  • pp：此时 2×d=ans2\times d=ans；
  • p2p^2：此时 3×d=ans3\times d=ans；
  • p1×p2p_1\times p_2，此时 4×d=ans4\times d=ans；
  • p1×p2×p3p_1\times p_2\times p_3，此时你会发现，8503×2>109850^3\times 2>10^9，这说明 ans=8ans=8.

考虑对求出的 dd 做一定的调整，如何调整呢？乘以 22 即可，此时发现会完全符合条件。

https://codeforces.com/contest/1355/submission/117991144

ARC 103 B Robot Arms [*2677]

  • https://atcoder.jp/contests/arc103/tasks/arc103_b

首先考虑如何判无解，容易发现，如果 xi+yix_i+y_i 的奇偶性有不同的，显然不可能有解。

考虑接下来如何构造，发现 m≤40m\le 40 很有学问，考虑二进制分解一下。

倍增构造，步长设为 2k2^k 幂，每次选择距目标点较远的坐标来跳，容易发现这是一定可行的。

https://atcoder.jp/contests/arc103/submissions/23176829

ARC 103 D Distance Sums [*2836]

  • https://atcoder.jp/contests/arc103/tasks/arc103_d

考虑如何求 DiD_i，显然有一个 DP 式子：

Dson=Dfa−sizson+(n−sizson)D_{son}=D_{fa}-siz_{son}+(n-siz_{son})

变形一下，得：

Dfa=Dson+2×sizson−nD_{fa}=D_{son}+2\times siz_{son}-n

那么，我们只要知道 DsonD_{son} 与其他常量就可以推出 DfaD_{fa}。

钦定重心为根，显然此时叶子节点的值最大，从大到小对给定的 DD 排序，根据每一个点的 DD 推出他的父亲。

我们只满足了父子之间的关系，所以我们还要在构造完之后跑一遍 DD 的值，以使得是对的。

https://atcoder.jp/contests/arc103/submissions/23177106

ARC 091 D Strange Nim [*2395]

  • https://atcoder.jp/contests/arc091/tasks/arc091_d

考虑博弈论，显然可以设 f(i,j))f(i,j)) 为大小为 ii 的石子，且 jj 为常数 kk 的胜负情况。

如果你很牛逼或者善于打表，那么你可以得到一个结果：

f(i,j)={0a<kaka≡0(modk)f(a−⌊ak⌋−1,k)a≡0(modk)f(i,j)=\begin{cases}0 & a<k\\\frac{a}{k} & a\equiv 0 \pmod k\\f(a-\lfloor \frac{a}{k}\rfloor-1,k) & a\not\equiv 0\pmod k \end{cases}

那么，于是你直接暴力模拟，然后 T 了 44 个点。

发现在第三种情况中，我们会跳了太多次，所以考虑压一下跳的步数。

然后就没了。

CF R 729 Priority Queue [*2200]

  • https://codeforces.com/problemset/problem/1542/D

考虑对每个数计算它的贡献。

那么我们需要求出它不被删去的贡献，DP 即可。

设 fi,jf_{i,j} 表示在前 ii 个数中，选了多少个替罪羊，分几个情况讨论一下：

  1. ii 在当前枚举的数之前：
    • 若是一次删除：
      • fi,j=fi−1,j+fi−1,j+1f_{i,j}=f_{i-1,j}+f_{i-1,j+1}。
      • 注意特判 j=0j=0：fi,j=2×fi−1,j+fi−1,j+1f_{i,j}=2\times f_{i-1,j}+f_{i-1,j+1}。
    • 若是一次添加：
      • 若是替罪羊：
        • fi,j=fi−1,j−1+fi−1,jf_{i,j}=f_{i-1,j-1}+f_{i-1,j}。
        • 同样特判 j=0j=0：fi,j=fi−1,jf_{i,j}=f_{i-1,j}。
      • 若不是替罪羊，选与不选均可：
        • fi,j=2×fi−1,jf_{i,j}=2\times f_{i-1,j}。
  2. 若现在转移到 xx，显然 fx,j=fx,j−1f_{x,j}=f_{x,j-1}。
  3. ii 在之前枚举的数之后，类情况 11 不过要做一定的修改：
    • 当是删除且 j=0j=0 时，fi,j=fi−1,j+fi−1,j+1f_{i,j}=f_{i-1,j}+f_{i-1,j+1}。因为如果没有了替罪羊，我们要计算的就会被删去，只好不选。
    • 注意到本题有重复的数字，为了避免重复计算，在 i>xi>x 时，一个数能成为替罪羊，当且仅当 ai>axa_i>a_x，而不是之前的 ai≥axa_i\ge a_x。

记得取模。

https://codeforces.com/contest/1542/submission/122883000