校内OJ 2019.3.17 NOIP 模拟赛

前言

Rk 3,Rating 涨了,这次前两道题比较简单,最后一题比较毒瘤。

P1 身体训练

原题出自 LOJ #6162 「美团 CodeM 初赛 Round A」身体训练

题面

美团外卖的配送员用变速跑的方式进行身体训练。 他们训练的方式是: $n$ 个人排成一列跑步,前后两人之间相隔 $u$ 米,每个人正常速度均为 $v$ 米/秒。 当某个配送员排在最后的时候,他需要以当时自己的最高速度往前跑,直到超过排头的人$u$ 米,然后降回到原始速度 $v$ 米/秒。每个人最初的最高速度为 $c_i$ 米/秒,每轮衰减 $d_i$ 米/秒,也就是说,如果 $i$ 是第 $j$ 个跑的,那么他的速度就是 $c_i-(j-1)\times d_i$ 米/秒。 $n$ 个人初始以随机的顺序排列,每种顺序的概率完全相等,跑完一轮(每个人都追到排头一次,序列恢复原样)的期望需要的时间是多少?

思路

根据题意,每一个外卖员在每个位置上都会出现一次。每次他都会追上去,追过的都是整个队伍的长(因为他后面的外卖员全部追到前面后他才会追),不一样的只是速度。

所以对于每一个外卖员,只需要枚举他是第几个去追的,再根据小学生的追及问题,对于第 $i$ 个外卖员第 $j$ 个开始追,用的时间是 $\frac{n\times u}{c_i-(j-1)\times d_i-v}$。

总时间就是 $\sum_{i=1}^n\sum_{j=1}^n\frac{n\times u}{c_i-(j-1)\times d_i-v}$ ,期望为 $\frac{\mathrm{总时间}}n$ ,即 $\frac{\sum_{i=1}^n\sum_{j=1}^n\frac{n\times u}{c_i-(j-1)\times d_i-v}}n$ 。

时间复杂度为 $O(n^2)$,当然,优化一下也是可以到 $O(n)$ 的,不过 $O(n^2)$ 随便过本题最大 $1000$ 的数据,这里就不优化了。

代码

P2 能量项链

这题并不是区间 DP 的那道题,本题比那道题水。

正解是欧拉回路,不过玄学就可以过。

题面

给出 $n$ ,请你构造一个长度为 $2^n$ 的 $01$ 环,使得

每一个长度为 $n$ 的 $01$ 串 (共 $2^n$ 个)都作为这个环的一个子串恰好出现一次

比如当 $n=2$ 时 , 一个环 $0011$ 就是合法解之一,注意这个环是首尾相接的,也就是说 $10$ 也是这个环的一个子串。

本题有 $SPJ$ ,你的输出可以从环的任何地方断开。

思路

很容易就看出来,设长度为 $n-1$ 的 $01$ 排列为 $x$,在长度为 $n$ 的所有 $01$ 串中,以 $x$ 开头的 $01$ 串和以 $x$ 结尾的 $01$ 串数量是一样的,所以我们对于每个结尾,可以直接去找开头,而不用担心数量不够用。

以 $n=3$ 时的全排列为例:
在 $000,001,011,111,110,101,010,100$ 中:
以 $00$ 为开头的有 $2$ 个,为结尾的有 $2$ 个 ($000$ 既包括开头又包括结尾)
以 $01$ 为开头的有 $2$ 个,为结尾的有 $2$ 个
以 $10$ 为开头的有 $2$ 个,为结尾的有 $2$ 个
以 $11$ 为开头的有 $2$ 个,为结尾的有 $2$ 个 ($111$ 既包括开头又包括结尾)

所以答案的前 $n$ 个字符随便是什么,都可以构造成满足题意的字串了,不妨设它为 $000$ 。

然后不断的选出后 $n-1$ 位,将其后面加 $0$ 或加 $1$ ,如果这个子串没用过,那么直接把 $0$ 或 $1$ 中字串没用过的加到末尾就好了。(我在这里使用了哈希来判重)

如果两个都可用,优先选择 $1$ ,因为初始时 $0$ 已经使用了一个。

我们来模拟 $n=3$ 时的情况:
初始时字串为 $000$。
现在字串末 $n-1$ 位为 $00$ ,$000$ 已经使用过了, $001$ 还没有,于是将 $1$ 加入字串末尾(这样字串末尾就是 $001$ 了),字串变为 $0001$ 。
现在字串末 $n-1$ 位为 $01$ ,$000$ 和 $001$ 都没有使用,优先选择 $001$ ,将 $1$ 加入字串末尾,字串变为 $00011$ 。
现在字串末 $n-1$ 位为 $11$ ,$110$ 和 $111$ 都没有使用,优先选择 $111$ ,将 $1$ 加入字串末尾,字串变为 $000111$ 。
现在字串末 $n-1$ 位为 $11$ ,$111$ 已经使用过了, $110$ 还没有,将 $0$ 加入字串末尾,字串变为 $0001110$ 。
现在字串末 $n-1$ 位为 $10$ ,$100$ 和 $101$ 都没有使用,优先选择 $101$ ,将 $1$ 加入字串末尾,字串变为 $00011101$ 。
此时字串长已经为 $2^n$ ,答案字串即为 $00011101$ 。

我在比赛时每新加一位就要枚举后 $n-1$ 位来哈希,时间复杂度近似为 $O(2^n \times n)$,加一点小优化就可以变为 $O(2^n)$。

代码

P3 欧拉口算

考场暴力拿了 20。

题意

定义 $C(n)$ 表示把 $n$ 拆分成 $a \times b=n (a \leq b)$ ,且 $a$ , $b$ 的因子个数相同的方案数。

例如 $C(48)=1$ , $C(10!)=3$ 。

请求出 $C(n!)$ 。

思路

暂时没有思路,等待日后更新。

引用一段学长的题解:

首先要知道约数个数的公式。

然后这个题就是把 $n!$ 分解质因数 然后把每个质因数的指数分配给$A,B$,使得他们的指数+1的积相等。

这个正如LJN想的一样是可以折半的,但是他跑了20分钟,std却只要400ms,说明这个搜索是很细致的。

关键就在于折半的时候怎么分两半 。

比如现在有 $k$ 个质因子 $\prod^k p_i^{a_i}$

那么比较直观的是直接枚举在哪$m$分开,使得 $\text{max} \{\prod_1^m a_i+1,\prod_{m+1}^k a_i+1\}$ 最小。

但这还不是最优的,因为这些质因子最后一段必然都是只出现一次的,这些只会对乘积相等造成$\times 2$的影响,我们可以在折半之后枚举他。

假设有$r$个指数是$1$,那么我们要找的是 $\text{max} \{(\prod_1^m a_i+1)\times r,\prod_{m+1}^{k-r} a_i+1\}$ 最小。

暂无评论

发送评论


				
上一篇
下一篇