14天百题计划第一期

我会记录这 \(14\) 天（\(\texttt{2024-8-23 至 2024-9-5}\)）做的题目。预计难度范围再 \(\texttt{[2000,2500]}\) 之间，既可以和博客园的小伙伴们一起学习，也可以让博客园的小伙伴们监督我。

\(\texttt{2024-8-23}\)

• CF1034B Little C Loves 3 II \(\texttt{*2000}\)

分类讨论 \(1\) 行、\(2\) 行的情况。代码

• CF1984F Reconstruction \(\texttt{*2500}\)

在前面加 P 后面加 S。那么完整（填完）的串中一定有 PS 这样就可以求出 \(\sum\) 了。接下来对于每一个 \(\operatorname{sum}\) 进行 \(\texttt{dp}\)。代码

• CF612E Square Root of Permutation \(\texttt{*2300}\)

思考：建 \(i\to q_i\)的边。那么会有环：

1. 奇数环 \(a_1,a_2,\cdots,a_n\)，那么 \(p\) 的环是 \(a_1,a_3,a_5,\cdots,a_n,a_2,a_4,\cdots,a_{n-1}\)。
2. 偶数环 \(a_1,a_2,\cdots,a_n\)，那么分为两个环 \(p\) 的环是 \(a_1,a_3,\cdots,a_{n-1}\) 和 \(a_2,a_4,\cdots,a_{n}\)。

所以 \(p\) 的图有环需要满足对于 \(\forall i=2k\)，长度为 \(i\) 的环个数为偶数个。 代码

• CF1184C2 Heidi and the Turing Test (Medium)
  转换为切比雪夫距离，双指针 + 线段树即可。
  代码； 草稿

• P1306 斐波那契公约数
  \(\gcd(f(x),f(y))=f(\gcd(x,y))\)。矩阵加速。

\(\texttt{2024-8-24}\)

• CF1364D Ehab's Last Corollary \(\texttt{*2100}\)
  分讨：

1. \(n=k\) 树 ：方案 \(1\)；否则方案 \(2\)
2. \(n > k\) 任意取 k 个节点转换为 \(n=k\)。

代码

• CF992D Nastya and a Game \(\texttt{*2100}\)
  因为 \(2^{63}\le \max_n\max_k\max_a\) 所以子序列中非 \(1\) 的个数小于 \(64\)。

代码

• CF1433F Zero Remainder Sum
  直接 \(4\) 维 \(dp\)。
  代码

\(\texttt{2024-8-25}\)

• CF1181C Flag
  预处理下面与他相同的点，枚举每一个点，判断这一列 + 扩展到右边，时间复杂度 \(O(n^2)\)。
• CF1379C Choosing flowers
  枚举选多个的花，在二分选出只选 \(a\) 的花。
• CF475D CGCDSSQ
  枚举 \(l\),二分找到 \(\gcd\) 为 \(\gcd [l,r_{(也就是 n)}]\) 的个数，并更新 \(r\)，以此类推
• CF628D Magic Numbers
  数位 \(dp\)。
• CF768D - Jon and Orbs
  概率 \(dp\)

\(\texttt{2024-8-26}\)

• CF1036F - Relatively Prime Powers
  只要是形如 \(x^y\) 的形式的数。容斥原理。莫比乌斯反演。
• CF960E - Alternating Tree
  考虑每一个点的贡献，树形 dp 即可。
• CF1037E - Trips
  好题。因为不强制在线。所以倒着来，每次删边。做类似于拓扑排序的操作。
• CF1438D - Powerful Ksenia
  分类讨论 \(n\) 的奇偶性。偶数再讨论异或和。

\(\texttt{2024-8-27}\)

• P4018 Roy&October之取石子
  判断是否是 \(6\) 的倍数即可。
• P2197 【模板】Nim 游戏
  见 博弈论基础
• P4279 [SHOI2008] 小约翰的游戏
  见 博弈论基础
• P6487 [COCI2010-2011#4] HRPA
  见 博弈论基础

\(\texttt{2024-8-28}\)

• P2148 [SDOI2009] E&D
  见 博弈论基础
• AGC002E [AGC002E] Candy Piles
  见 博弈论基础
• CF87C Interesting Game
  见 博弈论基础
• CF388C Fox and Card Game
  见 博弈论基础
• ABC297G Constrained Nim 2
  见 博弈论基础

目前进度

◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼◼
◼◼◼◼◼◼◻◻◻◻◻◻◻◻◻◻◻◻◻◻
◻◻◻◻◻◻◻◻◻◻◻◻◻◻◻◻◻◻◻◻
◻◻◻◻◻◻◻◻◻◻◻◻◻◻◻◻◻◻◻◻
◻◻◻◻◻◻◻◻◻◻◻◻◻◻◻◻◻◻◻◻