CF598(EDU1) 题解

zrl123456 · 2025-07-13 22:05:20 · 题解

显然这篇题解是给自己看的，代码不贴。

A. Tricky Sum:

考察：数学。
题目简述：

• 1\le n\le 10^9

  上边那个式子长的太不像人样了，所以我们给它简化一下：

  \begin{aligned}\sum_{i=1}^n(-1)^{[i\in\{x|x=2^k,k\in\mathbb N\}]}i&=\sum_{i=1}^ni-2[i\in\{x|x=2^k,k\in\mathbb N\}]i\\&=(\sum_{i=1}^ni)-2(\sum_{i=1}^{\lfloor\log_2n\rfloor}2^i)\\&=\frac{n(n+1)}{2}-2^{\lfloor\log_2n+2\rfloor}+2\end{aligned}

  照着式子直接算，时间复杂度为 \Theta(t\log n)。

  B. Queries on a String:

  考察：字符串。
  题目简述：
  给你一个由小写字母构成的字符串 s，后面有 m 次修改，第 i 次修改给定 l_i,r_i,k_i，表示执行一下操作 k_i 次：

• \forall j\in[l_i,r_i],s_{(j-l_i)\bmod(r_i-l_i)+l_i+1}\leftarrow s_j

最后输出字符串 s。
数据范围：

• 1\le|s|\le 10^4
• 1\le m\le 300
• \forall i\in[1,m],1\le l_i\le r_i\le |s|
• \forall i\in[1,m],1\le k_i\le 10^6

  首先容易想到在区间 [l,r] 执行该操作 k 次结果会如下：

• \forall j\in[l,r],s_{(j+k-1-l)\bmod(r-l)+l+1}\leftarrow s_j

然后好像就没有了，注意一些实现上的小细节就行了，时间复杂度为 \Theta(|s|m)。

C. Nearest vectors:

考察：线性代数，精度优化。
题目简述：
有 n 条射线在同一平面直角坐标系内，第 i 条射线过原点和点 (x_i,y_i) 并以原点为端点，求射线两两之间非优夹角（自己定义的：度数小于 180° 的夹角）最小的一组，若有多组任意输出满足条件的一组。
数据范围：

• 1\le n\le 10^5
• \forall i\in[1,n],(x_i,y_i)\in\complement_{\{(x,y)|-10^4<=x<=10^4,-10^4<=y<=10^4,x\in \mathbb Z,y\in \mathbb Z\}}\{(0,0)\}

  如图，这里有 7 条射线：
  
  我们注意到，若要求非优夹角要小，则两条射线一定要相邻，则我们在一开始要排序。
  那么我们以什么为标准排序呢？
  注意到我们可以根据原点外的那一点求出这条射线与射线 \{(x,y)|x\ge 0,y=0\} 之间形成的上夹角（有超过一半在 x 轴上方或度数等于 0° 的夹角），通过 atan2 函数即可实现。

  注意这里不能用 atan，精度会炸。

排完序后，我们对射线间非优夹角进行计算即可，时间复杂度为 \Theta(n\log n)。

D. Igor In the Museum:

考察：DFS。
题目简述：
给你一个 n\times m 的网格图，由 . 和 * 组成，有 k 次询问，第 i 次询问给定 x_i,y_i，求网格 x_i,y_i 所在的 . 四联通块的与 * 相邻的部位数。
这里的部位不同当且仅当这个 * 位置不同或这个与 * 相邻的 . 的位置不同。
数据范围：

• 3\le n\le1000,3\le m\le 1000
• 1\le k\le\min(nm,10^5)
• \forall i\in[1,k],1\le x_i\le n,1\le y_i\le m

  由于 k 较大，故考虑预处理，我们需要对于每个 . 均摊 \Theta(1) 地求出每个 . 所在连通块与 * 相邻的部位数。
  套路题，对于每个连通块，先求出它与 * 相邻的部位数，再依次将这个值赋给连通块中的每个网格。
  求值和赋值都可以用 DFS 实现，最后对于每个询问 \Theta(1) 回答即可，时间复杂度为 \Theta(nm+q)。

  E. Chocolate Bar:

  考察：dp。
  题目简述：

  数据范围：
• 1\le t\le 40910
• 1\le n\le 30,1\le m\le 30
• 1\le k\le\min(nm,50)

  同 D，观察到 t 的值域较大，而 n,m,k 的值域都较小，考虑预处理。
  设 f_{a,b,c} 为在 a\times b 的网格图中通过操作凑出 c 个网格的最小代价，暴力按题意推式子：

  f_{a,b,c}=\begin{cases}0&c\in\{0,ab\}\\+\infty&c>ab\\\min(\min_{x=1}^{\lfloor\frac{a}{2}\rfloor}(\min_{y=0}^c(f_{x,b,y}+f_{a-x,b,c-y}+b^2)),\min_{x=1}^{\lfloor\frac{b}{2}\rfloor})(\min_{y=0}^c(f_{a,x,y}+f_{a,b-x,c-y}+a^2))&\text{otherwise}\end{cases}

  容易发现最后时间复杂度为 \Theta(nmk^2(n+m)+t)，可以通过。

F 不会，我太菜了。