本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-07-13 22:05:20

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

A. Tricky Sum:

考察：数学。
题目简述：
$t$ 组数据，每组数据给定 $n$，求： $$\sum_{i=1}^n(-1)^{[i\in\{x|x=2^k,k\in\mathbb N\}]}i$$ 数据范围：

• $1\le t\le 100$
• $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。
题目简述：
$t$ 组数据，每组数据有一个 $n\times m$ 的网格图水平摆放，你能操作若干次，每次操作水平或竖直中的仅一个方向沿网格边缘将一个网格图分成两半，所切割长度为 $p$，同时切完的网格图成为了两个独立的网格图，设每次操作的代价为 $p^2$，问能凑出 $k$ 个网格的最小代价。（这简述相当严谨了）
数据范围：

• $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 不会，我太菜了。