T1 线段
题意
$n$ 个区间，从其中选出 $m$ 个，使得全部 $m$ 个线段交非空。求这 m 个线段长度极差的最小值。
\[m\le n \le 5\times 10^5\]思路
线段按长度排序，随后双指针。开线段树表示每个位置被覆盖次数，最大值大于 $m$ 时合法。
T2 国王饮水记
(见之前题解)
T3 旷野大计算
题意：略
一些关于 $S(x)$ 的性质（注意 S 函数非常有用）：
- $S^\prime(x)=\frac{e^{-x}}{(1+e^{-x})^2}$
- $\lim_{x\to 0}S(x)=\frac 12$
- $\lim_{x\to \infin}S(x)=1$
- $\lim_{x\to -\infin}S(x)=0$
后文中，我们定义 $\infin$ 为一个超级大的数，具体实现时一般用 2 的多少次幂，方便用左移右移搞出来。
Task 1,2：略
Task 3
要求节点数量不超过 6，第一个要动脑筋的地方。
注意到输出不是线性的，因此不用 s 是不可能做到的。然后，我们定义
\[P(x)=S(x\times \infin)=\left\{ \begin{aligned} 1 &\qquad &x>0 \\ 0.5 &&x=0\\ 0 &&x<0 \end{aligned} \right.\]这个 $P$ 函数之后也非常有用，在这里直接 $2P(x)-1$ 即可。
Task 4
14 个节点满分。
6 分
这个 task 满分比较难，在此先使用上问结果乘以 a 得到 6 分。
10 分
（没想出来，只能揣测下出题人思路）
首先，绝对值也不是线性函数，必定会用到 S 函数。然后考虑我们用 S 搞出个什么函数之后我们可以通过平移和线性变换变成绝对值函数。
发现这个函数必然然是一个两段的折线，就是说，存在某个 $x_0$，使得这一函数在 $x<x_0$ 的斜率不等于 $x>x_0$ 时的斜率。
这样，我们可以先把 $x_0$ 平移到 0，然后整体加上某个一次函数，使其变成一个偶函数。最后再整体乘上一个常数，使得其斜率变成 $\pm 1$。
当然，这里也有很多巧合的因素，因为在整体加一次函数和整体乘常数的时候，这个一次函数的斜率和常数都必须非常整，才可以在有限次数中用左移右移凑出来。
考虑如下函数（该函数 0 点的函数值比较麻烦，实现的时候先把输入加上一个 EPS 再做）：
\[f(x)=S(P(x)\times \infin+\frac x {\infin})= \left\{ \begin{aligned} 1&&x>0\cr 0.5+\frac x {4\infin}&&x<0 \end{aligned} \right.\]
这函数是这样的
然而这个函数在并不是一个折线，两个一次函数在 $x=0$ 除没有连起来。然而不要紧，我们可以在最后通过 $P$ 函数把正半轴的函数值全都加上某个数，因此作如下变换：
\[g(x)=(0.5-f(x))\times 8\infin= \left\{ \begin{aligned} -0.5\times 8\infin&&x>0\cr -2x &&x<0 \end{aligned} \right.\]至于为啥把 $x<0$ 弄成 -2x，这是因为后面直接把这个玩意 $+x$，这样正负部分的斜率都对了。然后再使用 $P$ 函数把正半轴的截距搞到 0 即可。实现时注意不要重复计算，精细实现即可满分。
data x = read();
data p = s((x + 1e-20) << 100) << 102; //非零
data r1 = s((x >> 100) + p); // x>=0等于1，x<0等于x>>102+0.5
data r2 = (-r1 + 0.5) << 103; // x>=0等于-0.5*2^103,x<0等于-2x
data r3 = x + r2 + p; //大于0的时候加上2^102
prt(r3);
Task 5
要求95次操作。
模拟即可，需要精细实现，不该加的时候不要乱加。
Task 6
要求190次操作。
从高向低枚举每一位，输出 $P(x-2^i+0.5)$，然后再 $x\gets x- P(x-2^i+0.5)\times 2^i$。
注意到计算 P 的过程中，多次把 x 左移。所以还不如一开始就把 x 左移。
需要精细实现：
data x = read();
x = x << 30;
for (ll i = 31; ~i; i--) {
//减去对应位，判断正负
data res = i ? s(x + (1e6 - powl(2, i + 30))) : x >> 30;
prt(res);
//删除当前位置
if (i) x = x + (-(res << (i + 30)));
}
Task 7
要求600多次操作。
在前两问基础上实现一个异或函数即可。
注意到 $x\oplus y=x+y-2[x+y>1]=x+y-2P(x+y-1.5)$。
Task 8
要求 7 次操作。
一个思路是用二进制把 $\frac 1{10}$ 凑出来，然而七次操作精度太差，只能精确到三位小数。
一个大胆的想法：$S$ 函数的斜率均匀变化，可否找到某处斜率为 $\frac 1{10}$，然后把这段放大放大再放大，用来拟合 $y=\frac x{10}$？
答案是肯定的，一开始你的想法是二分出这个位置，然而：
精度不够。。
求个导：$S^\prime(x)=\frac{e^{-x}}{(1+e^{-x})^2}$，然后算出来这个位置的精确值：$\ln(\sqrt{15}+4)$ 用 C++ 算了一下，输出出来，依然是一个 wa。。
我十分不解，于是翻了翻题解，根据题解的说法，在场上的时候需要用计算器算出小数点后几十位，然后拿程序输出出来才行，于是（第一个数是位置，第二个数是那个位置的 $S$ 函数值）：
string magic = "2.06343706889556054672728117262013187145659144988339249983603269276590284284740991";
data x = (read() >> 100) + magic;
x = S(x) + "-0.887298334620741688517926539978239961083292170529159082658757376611348309193697903351";
prt(x << 100);
就过了，但在考场上大概是看不出这个问题的。。
Task 9
要求 3000 次操作。
自然的想法是插入或冒泡排序。因此，我们需要设计一个模块，输入两个数，这个模块把这两个数按大小顺序排好输出出来。
只要知道了 $\max(x,y)$，也就是第二个数，那么第一个数一减就出来了。
因为 $\max(x,y)=x+\max(y-x,0)$，我们需要设计一个模块，把某个数和 0 取 max。
发现 $y=\max(x,0)$ 的函数竟跟刚刚算绝对值构造的函数有几分相似，这里再回顾一下：
\[f(x)=S(P(x)\times \infin+\frac x {\infin})= \left\{ \begin{aligned} 1&&x>0\cr 0.5+\frac x {4\infin}&&x<0 \end{aligned} \right.\]
发现如果我们把 $x$ 当成 $-x$ 带入到这个函数里，再把正半轴上多的东西减掉，用类似刚才 abs 的手法，就能的到 $\max(x,0)$ 的函数，相当于一个阉割版的 abs。
然后就好弄了：
auto mx0 = [](data x) {
x = -x;
data p = s((x + 1e-20) << 100) << 101; //非零
data r1 = s((x >> 100) + p); // x>=0等于1，x<0等于x>>102+0.5
data r2 = (-r1 + 0.5) << 102; // x>=0等于-0.5*2^102,x<0等于-x
data r3 = r2 + p; // x>=0=0,x<0=-x
return r3;
};
auto swp = [&](data &x, data &y) {
data delt = (-x) + y;
data tmp = mx0(delt);
data sum = x + y;
y = x + tmp;
x = sum + (-y);
};
data arr[20];
for (ll i = 1; i <= 16; i++) {
arr[i] = read();
for (ll j = i; j > 1; j--) swp(arr[j - 1], arr[j]);
}
for (ll i = 1; i <= 16; i++) prt(arr[i]);
Task 10
要求 2000 个节点。
两个大数相乘显然不现实，两个大数相取模也不太现实，因此考虑用龟速乘的搞法。我们需要实现一个模块：输入 $x,y(x\in{0,1})$ 输出 $xy$。
猜想这个模块可以写成 $S(ax+by+c)$。
当 x 取 0 时，无论 y 如何变化，结果都不变，但是当 x 取 1 时，y 变化，结果就变化。
- 说明当 x 取 0 时，$S(by+c)$ 的变化率极小，也就是说 $by+c$ 离 0 很远。
- 说明当 x 取 1 时，$S(a+by+c)$ 的变化率比较大，也就是说 $a+by+c$ 离 0 很进。
不难想到，$a+c=0$，且 b 远小于 1 的时候是满足这个条件的。
同样得，用 $P$ 函数把这个玩意得截距搞一下就好了。
接下来还要实现一个取模的模块，参考取模优化的搞法，如果 $x\gets x- [x\ge mod]\times mod$，直接利用上面的乘法模块即可。
最后还需要把被乘数 $y$ 自身取模一遍，依次用取模模块把 y 对 $2^{31}mod,2^{30}mod \cdots$ 取模即可。
（我至今还没调出来）
作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接
阅读量: