T1 线段

题意

$n$ 个区间，从其中选出 $m$ 个，使得全部 $m$ 个线段交非空。求这 m 个线段长度极差的最小值。

思路

线段按长度排序，随后双指针。开线段树表示每个位置被覆盖次数，最大值大于 $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，第一个要动脑筋的地方。

这个 $P$ 函数之后也非常有用，在这里直接 $2P(x)-1$ 即可。

Task 4

14 个节点满分。

6 分

这个 task 满分比较难，在此先使用上问结果乘以 a 得到 6 分。

10 分

至于为啥把 $x<0$ 弄成 -2x，这是因为后面直接把这个玩意 $+x$，这样正负部分的斜率都对了。然后再使用 $P$ 函数把正半轴的截距搞到 0 即可。实现时注意不要重复计算，精细实现即可满分。

1
2
3
4
5
6

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 左移。 需要精细实现：

1
2
3
4
5
6
7
8
9

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$ 函数值）：

1
2
3
4

string magic = "2.06343706889556054672728117262013187145659144988339249983603269276590284284740991";
data x = (read() >> 100) + magic;
x = S(x) + "-0.887298334620741688517926539978239961083292170529159082658757376611348309193697903351";
prt(x << 100);

就过了，但在考场上大概是看不出这个问题的。。

Task 9

发现如果我们把 $x$ 当成 $-x$ 带入到这个函数里，再把正半轴上多的东西减掉，用类似刚才 abs 的手法，就能的到 $\max(x,0)$ 的函数，相当于一个阉割版的 abs。 然后就好弄了：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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$ 取模即可。 （我至今还没调出来）