老张觉得比较简单,但我一道都不会做.
巧克力
如果颜色数目比较少,可以暴力枚举是哪 $k$ 种颜色作为连通块中必须包含的颜色.
二分一个美味度作为中位数,大于它的赋值为 $1001$ ,小于等于它的赋值为 $999$ .
这样就达到了一个二元组的效果,会优先个数最少,再尽量让选出的 $999$ 尽量多.
用斯坦纳树进行检验,判一下最优解中, $999$ 的个数是否 $\ge$ $1001$ 的个数.
用随机化乱搞加速,每次将每种颜色随机染成 $[0,k)$ 内的一种颜色,算一遍答案,这样算出来的答案肯定是合法的.
若染色时,将最优解中的 $k$ 种颜色染成了两两不同的颜色,就能求出这个最优解.
即,最劣情况下,只有一种颜色组合是最优解,此时做一次随机化求出正确答案的概率是 $\frac{k!}{k^k}$ .
当 $k=5$ 时,做 $300$ 次随机化,求不出最优解的概率就只有 $1-
(\frac{k}{k!})^{300}\approx 8\times 10^{-6}$ 了.
注意用斯坦纳树处理点权将集合 $S$ 拆成 $S1,S-S1$ 时,会将根节点的点权多算一次,需要减掉.
杜老师
把 $[L,R]$ 内的数可能含有的 $m$ 个质因数找出来,若选了 $x$ ,则 $x$ 含有的奇数次方的质因子出现次数会异或上 $1$ .
于是可以把每个数看成一个 $m$ 位的二进制数,现在要选出一些数,让它们异或起来为 $0$ .
方案数显然为 $2^k$ ,其中 $k$ 表示自由元的个数.
由于是异或方程,所以可以用线性基来代替高斯消元,最后的 $k$ 就是 $R-L+1$ 减去线性基的大小.
异或运算可以用 bitset 进行优化.
直接这样做,时间复杂度是 $O((R-L+1)\cdot \frac{R}{32})$ ,可以获得 $50$ 分.
优化一下,注意到每个数最多会有一个大于 $\sqrt R$ 的质因子,所以一个 $> \sqrt R$ 的质因子一旦出现,线性基里就肯定有它.
于是线性基只需要维护 $\le \sqrt R$ 的质因子.
对于最大质因子相同且 $>\sqrt R$ 的一堆数,只需要把第一个插到线性基里面,后面的异或上它再插进去.
时间复杂度优化到了 $O((R-L+1)\cdot \frac{\sqrt R}{32})$ ,可以获得 $70$ 分.
正解比较神仙,由于 $R\le 10^7$ ,所以当 $R-L>6000$ 时,就认为线性基的大小就是 $[L,R]$ 内所有质数的个数.
当 $R-L\le 6000$ 时,就用上面那个算法来做.
换桌
考虑先建出一个费用流的模型.
从源点 $S$ 向每个人所在的点连边,流量为 $1$ ,费用为 $0$ .
把同一张桌子的所有点连成一个环,每条边流量为 $\inf$ ,费用为 $0$ .
每个人所在的点向每张桌子对应的点连边,流量为 $1$ ,费用为换桌子需要的代价.
每个点向汇点 $T$ 连边,流量为 $1$ ,费用为 $0$ .
这个图的点数 $|V|$ 是 $O(nm)$ 的,但边数 $|E|$ 是 $O(n^2m)$ 的,可以获得 $70$ 分.
注意到每个人可以去的桌子是一段区间,可以用线段树来优化建边.
因为换桌子的花费有绝对值,所以可以拆成左右两边来做.
开 $2m$ 棵线段树,每个位置有 $2$ 棵线段树,一棵表示向左换桌子的,另一棵表示向右换桌子的.
向左换桌子的线段树,第 $i$ 个叶子的出边有个额外费用 $-2i$ ,向右的线段树额外费用为 $2i$ .
注意要限制对应的两个叶子总流量 $\le 1$ .
在第 $j$ 张桌子时,往左边连的边有额外费用 $2j$ ,往右边连的边有额外费用 $-2j$ .
仍然把同一张桌子上的叶子节点连成一个环,每条边流量为 $\inf$ ,费用为 $0$ ,这样就考虑了换位置的贡献.
边数被优化到了 $O(m\cdot n\log n)$ ,跑个 zkw 费用流就可以过了.
大魔法师
用线段树给每段区间维护一个列向量
$$
\begin{bmatrix}\sum A\\ \sum B \\ \sum C \\ len \end{bmatrix}
$$
其中 $len$ 表示这个区间的长度.
修改标记可以统一成一个 $4\times 4$ 的转移矩阵,然后就变成线段树的一些基本操作了.
时间复杂度 $O(n\log n\cdot k^3)$ ,其中 $k=4$ .
如果奇迹有颜色
考虑 $Burnside$ 引理,记 $f(i)$ 表示不考虑同构时长度为 $i$ 的合法环的方案数.
则答案为
$$
ans=\frac{\sum_{i=1}^n f(\gcd(i,n))}{n}=\frac{\sum_{d|n}\varphi(\frac n d)\cdot f(d)}{n}
$$
于是需要快速求出 $f(d)$ .
考虑暴力状压 $dp$ ,先枚举一个 $s$ 表示开头 $m-1$ 个点的颜色状态.
记 $g(i,t)$ 表示已经给 $i$ 个点染了色,最后 $m-1$ 个点的颜色状态用 $t$ 表示的方案数.
最后判断每个 $g(i,t)$ 的尾部是否能和首部的 $s$ 接在一起,若合法,就计入 $f(i)$ .
每次转移需要枚举当前的点染哪个颜色,每次转移的复杂度是 $O(m)$ .
于是得出状压 $dp$ 的总时间复杂度 $O(n\cdot m^{2m-1})$ .
直接 $dp$ 复杂度显然爆炸,可以在本地把每个 $m$ 对应的前 $1000$ 项 $f(i)$ 打出来,用 $BM$ 求线性递推式.
发现当 $m=7$ 时,线性递推式的长度为 $k=410$ .
于是需要写一个 $O(k^2\log n)$ 的线性递推.
将 $n$ 质因子分解后, $O(\frac {\sqrt n}{\ln n})$ 枚举所有 $d$ ,总时间复杂度 $O(k^2\sqrt n)$ .
最后一个点要特判一下,因为 $n$ 的因数比较多,常数大.
宇宙广播
不懂为啥要出成提答题,方便调精度?
设公切面为 $\sum_{i=0}^{K-1} a_i\cdot x_i=d$ ,并保证 $\sum_{i=0}^{K-1} a_i^2=1$ .
考虑 $K$ 维空间中一个点 $(x_0,x_1,\dots,x_{K-1})$ 到这个公切面的距离
$$
dis=\frac{|d-\sum_{i=0}^{K-1} a_i\cdot x_i|}{\sqrt{\sum_{i=0}^{K-1} a_i^2}}
$$
保证了分母为 $1$ ,所以这个点到公切面的距离就是 $|d-\sum_{i=0}^{K-1} a_i\cdot x_i|$ .
每个球的球心到公切面的距离都是这个球的半径.
所以对于第 $j$ 个球,可以得到方程 $|d-\sum_{i=0}^{K-1} a_i\cdot x_{j,i}|=r_j$ .
共有 $K$ 个这样的方程,暴力枚举每个方程绝对值取正号还是负号.
确定符号后高斯消元解出每个 $k_i,b_i$ ,表示 $a_i=k_i\cdot d+b_i$ 将所有的 $a_i$ 代入 $\sum_{i=0}^{K-1} a_i^2=1$ 就可以解出 $d$ 了.
解出 $d$ 后,这个公切面也就确定了,只需要再对每个球,求出公切面与这个球的切点.
用高斯消元解一个法向量 $\vec {n}$ 出来,把球心沿着/逆着这个法向量移动 $r$ 的距离,检验一下哪个在平面上,它就是切点了.
时间复杂度 $O(2^K\cdot K^3)$ .