前言

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$ 的数据，这里就不优化了。

代码

#include<bits/stdc++.h>
using namespace std;
int n;
double v,u;
double c[2000],d[2000],s[2000],ans=0;
int main(){
	cin>>n>>v>>u;
	for (int i=1;i<=n;i++){
		cin>>c[i];
	}
	for (int i=1;i<=n;i++){
		cin>>d[i];
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			s[i]+=n*u/((c[i]-(j-1)*d[i])-v);
		}
		s[i]/=n;
		ans+=s[i];
	}
	printf("%.3lf",ans);
}

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)$。

代码

#include<bits/stdc++.h>
using namespace std;
short ans[2000000];
int n,f[5000000],top=0;
int main(){
	cin>>n;
	for (int i=1;i<=n;i++){
		ans[++top]=0;
		putchar(ans[top]+'0');
	}
	f[0]=1;
	int t=pow(2,n);
	for (int i=1;i<=t-n;i++){
		int q=0;
		for (int j=i+1;j<=i+n-1;j++){
			q=q*2+ans[j];
		}
		int q0=q*2,q1=q*2+1;
		if (!f[q1]){
			f[q1]=1;
			ans[++top]=1;
		}else if (!f[q0]){
			f[q0]=1;
			ans[++top]=0;
		}
		putchar(ans[top]+'0');
	}
}

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\}$ 最小。