做题记录 #1：CCPC2024 重庆站

FFTotoro · 2025-08-11 23:29:26 · 个人记录

:::align{center}

\color{Black}\textsf{CCPC 2024 Chongqing Site}

:::

:::align{center}

\color{Green}\textsf{\textbf{[A] 乘积，欧拉函数，求和}}

:::

• 标签：紫，数论，DP。
• 解法：欧拉函数有性质：\varphi(n)=n\prod\limits_{p\in\text{primes}}[p|n]\frac{p-1}{p}，也就是说只用关心选出的数的乘积以及乘积中包含了哪些质因数。由此有一个 O(n2^{\pi(V)}) 的状压 DP 做法，其中 V=3000 表示 a_i 的值域，但是它太慢了。注意到 \pi(\sqrt{V})=16 不大，而 >\sqrt{V} 的质因数在 a_i 中最多出现 1 次，可以据此对 a_i 进行分类，对于每一类 DP。时间复杂度 O(n2^{\pi(\sqrt{V})})，可以通过。

:::align{center}

\color{Green}\textsf{\textbf{[B] osu!mania}}

:::

• 标签：黄，模拟。
• 解法：简单的模拟题，只需要注意浮点数运算的一些小问题，例如使用 round 函数需要加上 \epsilon。

:::align{center}

\color{Green}\textsf{\textbf{[C] 连方}}

:::

• 标签：绿，构造。
• 解法：特判给定的两行至少一行全满的情况。对于第 2 行 / 第 6 行，考虑在第 1 行 / 第 5 行为 . 的位置填上 #（全部连通），在第 3 行 / 第 5 行仅仅使用一个 # 使其和第 2 行 / 第 6 行连通，在第 4 行分类讨论把第 3 行和第 5 行连起来。

:::align{center}

\color{Green}\textsf{\textbf{[D] 有限小数}}

:::

• 标签：蓝，数学，扩展欧几里得。
• 解法：假设 b=2^x5^yr（x,y\in\N 且均是极大的），那么 d=2^{x'}5^{y'}r（直接暴力枚举），进而发现只需要求一个乘法逆元，使用扩展欧几里得算法即可。逆元可以提到循环外面算，时间复杂度 O(\log^2V)。更多细节请参照本人题解。

:::align{center}

\color{Green}\textsf{\textbf{[E] 合成大西瓜}}

:::

• 标签：黄，图论。
• 解法：考虑先二分转 0/1，分析后可以得到简洁的结论：答案为以下两者的较大值：
  • 所有度数不为 1 的结点权值的最大值；
  • 所有度数为 1 的结点权值的次大值。

:::align{center}

\color{Green}\textsf{\textbf{[F] Pico Park}}

:::

• 标签：黑，组合数学，DP。
• 解法：注意到一个结论：如果一个人将另一个人缩小，那么前者向后者连边后，会形成若干条链，链的数量即为答案——并且每条链都对应初始位置的一个区间。于是据此进行 DP，转移系数可以使用组合数计算。时间复杂度 O(n^3)。更多细节请参照本人题解。

:::align{center}

\color{Gray}\textsf{\textbf{[G] 魔弹}}

:::

待更新。

:::align{center}

\color{Green}\textsf{\textbf{[H] str(list(s))}}

:::

• 标签：紫，DP。
• 解法：设 f_{i,j} 为迭代 i 次后位置 \bmod p=j 的“信息”：该“信息”包含这些位置上所有字符的 ASCII 之和、非单引号字符个数、单引号个数。转移直接模拟，时间复杂度 O(|s|+kp)。实现时“信息”可以打包成一个结构体：

  struct S{
  int s,c,q;
  S(int s=0,int c=0,int q=0):s(s),c(c),q(q){}
  S operator +(S x){
    return S(add(s,x.s),add(c,x.c),add(q,x.q));
  }
  S operator +=(S x){
    return *this=*this+x;
  }
  S t0(bool f=false){
    return S(add(1ll*' '*(c+q)%P,f?'['-' ':0),add(c,q),0);
  }
  S t1(){
    return S(add(1ll*'\''*c%P,1ll*'"'*q%P),q,c);
  }
  S t4(bool f=false){
    return S(add(1ll*','*(c+q)%P,f?']'-',':0),add(c,q),0);
  }
  };

:::align{center}

\color{Green}\textsf{\textbf{[I] 算术}}

:::

• 标签：黄，数学，分类讨论，模拟。
• 解法：考虑每组的构成可能是怎样的，分析后发现只可能是 x,x+1,1+1+1 三种形式，并且 1+1+1 比 1+1 更优（3^2>2^3）。于是按照如下方式模拟即可得到最优方案：
  • 如果存在 1,2 不断将其变为 3；
  • 如果存在 1,1,1 不断将其变为 3；
  • 如果存在 1,1 将其变为 2；
  • 如果仍然存在 1，将其和剩余数中最小的合并。

:::align{center}

\color{Green}\textsf{\textbf{[J] 骰子}}

:::

• 标签：橙，数学。
• 解法：注意到每个格子最终都可以转到 6，故答案为 6nm。

:::align{center}

\color{Green}\textsf{\textbf{[K] 小 C 的神秘图形}}

:::

• 标签：橙，数学，模拟。
• 解法：分析可得结论：当且仅当两个三进制数在每一位上都至少有一个是 1 时答案为 1，否则为 0。直接模拟。

:::align{center}

\color{Gray}\textsf{\textbf{[L] 沙堆}}

:::

待更新。

:::align{center}

\color{Gray}\textsf{\textbf{[M] Median Replacement}}

:::

待更新。