专栏文章

题解：P1737 [NOI2016] 旷野大计算

SSegTree
P1737题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mio0b736
此快照首次捕获于
2025/12/02 11:16
3 个月前
此快照最后确认于
2025/12/02 11:16
3 个月前
查看原文

Task 1

给定 a,ba,b，输出 −2a−2b-2a-2b。66 行。
提取公因式变成 −2(a+b)-2(a+b)，可以用加法代替乘 22。

Task 2

给定 aa，求 11+e17a\dfrac{1}{1+e^{17a}}。66 行。
乘 1717 拆成右移 44 加自己，然后取反调用 SS 即可。

Task 3

给定 aa，求 sign(a)\text{sign}(a)。66 行。
注意到题目的精度限制远小于计算节点的精度限制，这启示我们可以使用极限的思想。
下文中我们使用 inf\text{inf} 替代一个足够大的值。具体取什么需要代入每个 task 算一下使得不会爆范围。
注意到 lim⁡x→∞S(x)=0,S(0)=12,lim⁡x→∞S(x)=1\lim_{x\to \infty}S(x)=0,S(0)=\dfrac{1}{2},\lim_{x\to \infty}S(x)=1，可以得到 g(x)=S(x⋅inf)={0x<012x=01x>0g(x)=S(x\cdot \text{inf})=\begin{cases}0 & x<0\\ \dfrac{1}{2} & x=0\\ 1 & x>0\end{cases}。此时 sign(x)=2g(x)−1\text{sign}(x)=2g(x)-1 就做完了。

Task 4

给定 aa，求 ∣a∣|a|。1414 行。
因为输入不超过 99 位，我们可以制造 eps=10−10eps=10^{-10} 的偏差使得没有 a=0a=0 的情况。
通过 Task 3 的启发，我们完全可以构造一个函数 x+g(x)⋅infx+g(x)\cdot \text{inf} 使得 x<0x<0 仍然是 xx，否则是 inf\text{inf}。
这有什么好处？代入 SS 就会发现 x<0x<0 是 S(x)S(x) 否则是 11。
但是如果这么做我们就需要一个从 S(x)S(x) 还原回 xx 的方法，在减掉 g(x)⋅infg(x)\cdot \text{inf} 后我们就得到了 min⁡(x,0)={xx<00x=0\min(x,0)=\begin{cases}x & x<0\\ 0 & x=0\end{cases}。
对 SS 求导，有 S′(x)=e−x(1+e−x)2S'(x)=\dfrac{e^{-x}}{(1+e^{-x})^2}，代入 x=0x=0 得到 S′(0)=14S'(0)=\dfrac{1}{4}，我们可以认为 S(xinf)=14×xinf+12S(\dfrac{x}{\text{inf}})=\dfrac{1}{4}\times \dfrac{x}{\text{inf}}+\dfrac{1}{2}。
这样就可以从 S(x)S(x) 还原回 xx 了。
最后 ∣x∣=−2min⁡(x,0)+x|x|=-2\min(x,0)+x 就做完了。
适当优化一下。

Task 5

输入 3232 个二进制位上的值，转成数。9595 行。
没啥好说的，优化一下 i=0i=0 的右移就行了。

Task 6

输入数，转成 3232 个二进制位上的值。190190 行。
从高到低做，事实上我们只需要返回 [x≥2i][x\ge 2^i]。
前面的 Task 3&4 已经教会大家 S 函数的打开方法了，直接求 S((x−2i+10−10)⋅inf)S((x-2^i+10^{-10})\cdot \text{inf})。
精细实现一下，一开始就加上 eps\text{eps} 并乘上 inf\text{inf}。

Task 7

输入 a,ba,b，求 aa 异或 bb。605605 行。
利用 Task 5&6，只需要做 a,b∈{0,1}a,b\in \{0,1\} 的情况。
转成 a+b−[a+b≥2]2a+b-[a+b\ge 2]2，这个类似 Task 6 直接用 SS 就可以了。

Task 8

输入 aa，求 a10\dfrac{a}{10}。77 行。
求出一个点 pp 满足 S′(p)=110S'(p)=\dfrac{1}{10}，则答案是 S(p+xinf)−S(p)inf\dfrac{S(p+\dfrac{x}{\text{inf}})-S(p)}{\text{inf}}。
解出来 p=ln⁡(4+15)p=\ln(4+\sqrt{15})。

Task 9

输入长度为 1616 的序列，排序。30003000 行。
考虑朴素的排序方法：
CPP
for(int i=0;i<16;++i)for(int j=i+1;j<16;++j)if(a[i]>a[j])swap(a[i],a[j]);
只需要求 min⁡(a,b)=a+min⁡(0,b−a)\min(a,b)=a+\min(0,b-a)，这个在 Task 4 已经会做了。

Task 10

给定 a,b,ma,b,m，求 ab mod mab\bmod m。20002000 行。
一个自然的想法是使用快速幂的思想，这样我们需要实现在 a∈{0,1}a\in\{0,1\} 时的 abab。这里假定 b≥0b\ge 0。
注意到 ab=min⁡(a⋅inf,b)ab=\min(a\cdot \text{inf},b)，套用前面的做法。
这个做法可能需要轻微卡一下常数。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...