Nanako

Problem L. Wizards Unite

Statement

给 $1$ 把金钥匙(可多次使用的钥匙),$k$ 把银钥匙(只能用一次)。给 $n$ 个箱子,每个箱子有一个打开所需时间 $t_i$(跟钥匙类型无关)。一把钥匙同时只能开一个箱子,问打开所有箱子所需的最小总时间。有 $z$ 组测试数据。

$0 \leq k < n \leq 10^5$

$0 \leq t_i \leq 10^9$

$\sum n \leq 10^6$

Solution

本场最简单的题。

不失一般性,我们认为所有箱子按 $t_i$ 排升序。显然方案只能是 $k$ 把银钥匙都用来开一个箱子,金钥匙开其他所有箱子,而答案就是以下两者中的较大值:用银钥匙的箱子中耗时最长的一个的耗时;金钥匙开其他所有箱子的耗时之和。

注意到答案无论如何也不可能小于 $t_n$,也就是说用银钥匙开 $t_n$ 箱子一定不会浪费时间。那么为了令金钥匙耗时之和尽可能小,实际上 $k$ 把银钥匙开的就是最右边的 $k$ 个箱子,于是答案就很显然了。时间复杂度 $O(n \log n)$。

阅读全文 »

Problem J. Space Gophers

Statement

有一个由边长为 $1$ 的小正方体组成的边长为 $10^6$ 的实心正方体。在其中挖 $n$ 条隧道,每条隧道用 $(-,y_i,z_i)$ 或 $(x_i,-,z_i)$ 或 $(x_i,y_i,-)$ 表示。挖隧道的含义是,指定其中两个维度的坐标,沿平行于另一个维度轴线的方向把 $10^6$ 个方块拿走。挖完 $n$ 条隧道之后,$q$ 次询问两个点 $(s_x,s_y,s_z)$ 和 $(t_x,t_y,t_z)$ 是否可以通过若干条隧道连通。保证 $s$ 和 $t$ 处于隧道中。有 $z$ 组测试数据。

$1 \leq z \leq 6$

$1 \leq n \leq 3 \times 10^5$, $1 \leq x_i,y_i,z_i \leq 10^6$

$1 \leq q \leq 5 \times 10^5$, $1 \leq s_x,s_y,s_z,t_x,t_y,t_z \leq 10^6$

Solution

clp 单切之前大致跟我讲了一下做法。实际上两条隧道连通 iff 某一个维度坐标相等或相差 1,于是我们要做的事情就是把所有这样的隧道对找出来,在并查集上 merge 起来。

这个东西说起来简单,实现起来就比较呕吐……具体还是看代码吧……似乎是这篇文章里最长的代码

Code (By clp012345)

阅读全文 »

Problem I. Sum of Palindromes

Statement

把给定的 $n$ 位数分解成不超过 $25$ 个回文数(不允许前导零)。有 $z$ 组测试数据。

$1 \leq z \leq 20000$

$1 \leq n \leq 10^5$

$\sum n \leq 3 \times 10^6$

Solution

跟国内比赛撞车了(2016 CCPC Changchun J),可能这些毛子出题人没怎么看国内比赛的题。

做法很简单,就是每次减掉小于当前数的最大的回文数。很显然每次可以减掉一半的长度,所以大概只需要 $\log n$ 次就够了。唯一的难点在于实现有点恶心,需要上高精度,不过我直接复制以前打 16 长春时候的代码了。(那个时候写得很丑不要骂我呜呜呜)

Code (By Nanako)

阅读全文 »

Problem H. Lighthouses

Statement

给一个有 $n$ 个顶点的凸多边形,其顶点用 $(x_i,y_i)$ 表示。以 $n$ 个顶点为结点,给定 $m$ 条边 $(u_i,v_i)$。希望求出图上最长的(指欧几里得距离)且不和自己相交的(几何意义上)路的长度。有 $z$ 组测试数据。

$3 \leq n \leq 300$, $0 \leq m \leq \frac{n(n-1)}{2}$, $1 \leq u_i \neq v_i \leq n$

$-10^9 \leq x_i, y_i \leq 10^9$

$\sum n \leq 3000$

Solution

这题赛中我读都没读就被 clp012345 切了,赛后才看。

经过观察我们发现其实合法的路只能是在环上往一个方向转,那么我们上一个区间 DP 就可以了。开三个维度,分别表示起点、终点、顺/逆时针,状态转移 $O(n)$ 枚举。时间复杂度 $O(n^3)$。

区间 DP 要上环的话,通常做法就是开两倍数组复制一遍吧,参考石子合并。

阅读全文 »

Problem G. Invited Speakers

Statement

给定 $2n$ 个不同的点 $(x_i,y_i)$,$A$ 类型和 $B$ 类型各 $n$ 个,保证不存在三点共线。希望你能给出一种方案把它们配对成 $n$ 对 $AB$,并且每对 $AB$ 之间用折线($[1, 100]$ 条首尾相连的线段)相连,折线之间两两不交。有 $z$ 组测试数据。

$1 \leq z \leq 200$

$1 \leq n \leq 6$

$0 \leq |x_i|,|y_i| \leq 100$

Solution

我读的题,第一反应是:就这?

还害我确认了好几遍题意和数据范围。

精通脚撕 FFT 的各种姿势的队友 Luowaterbi 曾经告诉我,没有三点共线的时候,两种一样多的点必然存在一种配对方案使得每对之间只用一条线段相连并且所有线段都不交。既然这题数据范围这么小,直接大力枚举配对方案,再大力枚举判断是否存在两线段交就行了。时间复杂度 $O(n!n^2)$。

阅读全文 »

Problem F. The Halfwitters

Statement

给定长度 $n$,给定 $a, b, c$,给 $d$ 次询问。每次询问是一个长度为 $n$ 的排列,你可以对这个票列做三种操作:

  1. 花费 $a$ 代价,交换相邻的两个数;

  2. 花费 $b$ 代价,翻转这个排列;

  3. 花费 $c$ 代价,shuffle 这个排列。

对于每次询问,你需要求出,在最优的操作策略下,把排列排成升序所需的最小期望代价。有 $z$ 组测试数据。

$2 \leq n \leq 16$, $1 \leq a, b, c \leq 1000$, $1 \leq d \leq 10000$

$\sum d \leq 10^5$

Solution

考虑只有第一种操作,我们不难发现,总代价只跟逆序对数 $inv$ 有关。

考虑加上第二种操作,我们不难发现,先翻转一下再只进行以上操作可能会更快!

阅读全文 »

Problem B. Binomial

Statement

给定序列 $a_1,a_2,\dots, a_n$,问有多少对 $(a_i,a_j)$ 满足 $\binom{a_i}{a_j} \bmod 2 = 1$ 。有 $z$ 组测试数据。

$1 \leq z \leq 10$

$1 \leq n \leq 10^6$, $1 \leq a_i \leq 10^6$

Solution

Lucas 定理有一个经典的推论:

因此,问题转化为求

记 $m = \lceil \log (\max a_i) \rceil$。显然,暴力枚举可以做到 $O(n^2)$ 的复杂度。优化一下,枚举子集可以做到 $O(3^m)$ 的复杂度。但是要通过这题还是不够。clp012345 说可以 Sum over Submask DP 做到 $O(m2^m)$,于是 triple_a 就现学现用写了一个。

这个算法本身就不讲了,可以看上面链接的文章。在国内,这个算法一般被称作快速莫比乌斯变换 (FMT) 或者子集和变换,英文不好的话也可以搜这两个词,但感觉其实大部分文章都写得对新手不是很友好。个人觉得可以看这篇,我觉得下面这张插图真的把 FMT 解释得非常清楚。

阅读全文 »

Problem A. Bags of Candies

Statement

把 $A = \{1,2,\dots,n\}$ 分成尽可能多对,使得每一对的两个数都不互质,问 $n$ 减去配对次数的值。有 $z$ 组测试数据。

$1 \leq z \leq 5$

$2 \leq n \leq 10^{11}$

Solution

半场的时候动这个题的队伍只有个位数。可能大家都觉得有别的题可做,不像我这么菜别的都不会就来瞎猜结论了啊。于是结论就是,将 $1$ 和大于 $\lfloor \frac n2 \rfloor$ 的质数从 $A$ 里删掉,剩下的集合 $A’$ 一定是可以匹配满的,所以配对次数就是 $\frac {|A’|}2$。

赛中是瞎猜的,这里给一个简单证明。

将 $A’$ 的所有元素按最大质因子 $d$ 分组,那么每组都可以表示成 $A_d = \{d,2d,\dots,\lfloor \frac nd \rfloor d\}$ 的形式(注意并不一定 $|A_d|=\lfloor \frac nd \rfloor$,比如 $77 \notin A_7$),显然组内的数都是不互质的。

如果 $|A_d|$ 是偶数,直接令组内的数任意两两配对;如果 $|A_d|$ 是奇数,则除了 $2d$ 以外任意两两配对。所有组都作完以上匹配之后,剩下的数都是 $2$ 的倍数,所以也都不互质,也可以任意两两配对。注意到对于任意 $d$ 有 $|A_d| \geq 2$ 即不存在 $|A_d| = 1$,所以最后剩下的数显然至多只有一个。

阅读全文 »