THUSC 题九则

不知为何起了一个如此贴近小学课文标题的名字233

THUSC 2016

补退选

Trie上标记一下就行了,这题好像去年写的,最大的收获是让我知道了指针不是默认NULL的(

https://loj.ac/submission/206604

成绩单

题目的意思其实就相当于每次取出一个子序列,而且子序列之间的部分都取过。

设$f_{l, r, i, j}$表示在区间$[l, r]$内,现在选的子序列中,最小值是$i$,最大值是$j$,已经取过的部分的代价之和,$g_{l, r}$表示将$[l, r]$取空的最小代价,则可以得到转移方程

$$f_{l, r, \min{w_{r}, i}, \max{w_r, j}} = \min\limits_{l\leq k< r}{f_{l, k, i, j} + g_{k + 1, r – 1}}\\
g_{l, r} = \min\limits_{l\leq k\leq r}{f_{l, k, i, j} + g_{k+1, r} + a + b(j – i)^2}$$

https://loj.ac/submission/459327

星露谷物语

THUSC 2017

巧克力

看一眼部分分,很容易发现$1\leq c_{i, j}\leq 14$的部分大概可以斯坦纳树。就是先二分一下中位数$p$,把所有$a_{i, j} > p$的位置$(i, j)$的权值设为$1001$,其他位置权值设为$1000$,那么斯坦那树求来的就是在选的巧克力最少的情况下尽量多选比$p$小的值,如果选的比$p$小的值太少就说明答案比$p$大,否则答案比$p$小

而只要把颜色随机分成$K$组,在相同的组的视为同一种颜色,然后多跑几遍,问题也就解决了。

每次的话最优解正好分配到不同的颜色的概率是$\frac{k!}{k^k}$,其实期望几十次就能跑出来,可以我比较菜所以至少要跑200次QAQ

https://loj.ac/submission/459912

杜老师

显然,对于每个质数可以列一个关于奇偶性的异或方程组,以$L = 1, R = 10$为例,列出的方程组为

$$\begin{cases}
\begin{split}
x_{2}\oplus x_{6}\oplus x_{8}\oplus x_{10} &= 0\\
x_{3}\oplus x_{6} &= 0\\
x_{5}\oplus x_{10} &= 0\\
x_{7} &= 0\\
\end{split}
\end{cases}$$

其实这就是个和线性基差不多的玩意,设矩阵的秩为$r$,则自由元数量就是$R – L + 1 -r$,答案就是$2^{R – L + 1 -r}$。

这样的话列出的方程组太多了,我们可以发现,所有$> \sqrt{R}$的质因子,最多次数只会是$1$,所以对于一个质因子$p > \sqrt{R}$,可以钦定随便一个包含$p$的数是自由元,那么其他的包含$p$的数的质因子的奇偶性就可以异或上它的。然后普通的高斯消元就可以了。

另外有一个结论,当$R – L \geq 6000$时,矩阵的秩就等于区间内包含的质数个数,所以这样就过了

https://loj.ac/submission/460684

换桌

显然可以想出一个最小费用最大流的模型,然后我们发现连边是在区间上的,线段树优化即可

讲道理这题最大的难点是代码好长啊QAQ

https://loj.ac/submission/461294

大魔法师

这题好像是NOIP之后有人讲课然后我当时随口秒掉的……感觉智商日渐衰退……

用矩阵维护一下lazy tag就行了

本质就是个傻逼题,用于衬托D2另外两道题的毒瘤

https://loj.ac/submission/460447

如果奇迹有颜色

宇宙广播

对于一个超平面,有
$$\sum \limits_{i=1}^Ka_ix_i + d = 0$$
根据点到直线的距离公式,我们可以口胡一个点到超平面的距离公式$$\text{dis} = \frac{\left|\sum \limits_{i = 1}^Ka_ix_i + d\right|}{\sqrt{\sum \limits_{i = 1}^{K}{a_i}^2}}$$
强行令$\sum \limits_{i = 1}^K {a_i}^2 = 1$,那么距离就是
$$\text{dis} = \left|\sum \limits_{i = 1}^Ka_ix_i + d\right|$$
对于每个球,就有
$$\left|\sum \limits_{i = 1}^Ka_ix_{i, j} + d\right| = r_i$$
通过$O(2^K)$将绝对值符号去掉,然后高斯消元,将每个$a_i$表示为$bd+c$的形式,带回$\sum \limits_{i=1}^K{a_i}^2 = 1$解二元一次方程即可求出$d$。
据说超平面的法向量就是$(a_1, a_2, \dots , a_k)$,那么就能直接求出切点了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注