赛后——2.9 寒假模拟5
\(\text{T1}\) 猜单词
题意
小 \(S\) 手上有一个长度为 \(n\) 的单词。
现在,小 \(S\) 发现这个单词有 \(m\) 处被污染了（用#代替），已经看不出原来是什么了。
现在知道每个被污染的地方都有 \(k\) 个备选的可能字母。
现在，小 \(S\) 想要知道，在所有可能的单词里面。字典序第 \(x\) 小的是哪个？
对于 \(100\%\) 的数据，\(1\le n\le 500,1\le m\le n,1\le k\le 26,1\le x\le 10^9\)
思路
实质就是将一个十进制数 \(x\) 转成 \(k\) 进制数并映射到所取的字符集上。
显然不带#的不用管。
代码
int main(){
n=read(),m=read(),k=read(),x=read();
scanf("%s",_in+1);
for(int i=1;i<=m;i++){
scanf("%s",s[i]+1);
sort(s[i]+1,s[i]+1+k);
}
for(int i=m;i>=1;i--){
int pos=x%k;
if(!pos) pos=k;
_out[i]=s[i][pos];
x=(x-1)/k+1;
}
int tot=0;
for(int i=1;i<=n;i++){
if(_in[i]=='#'){
cout<<_out[++tot];
}
else{
cout<<_in[i];
}
}
}
\(\text{T2}\) 树的权
题意
给你一棵树，书上的每个节点有一个权值 \(v_i\)。
定义一条路径的权值是这条路径上所有节点的权值乘积除以这条路径上的节点个数。比如，一条路径包含一个权值为 \(3\) 的节点和一个权值为 \(5\) 的节点，那么它的权值就是 \(\frac{3\times 5}{2}=7.5\)。
现在，你想要知道这棵树上权值最小的路径权值是多少？请以既约分式形式输出，即 \(P/Q\) 的形式输出（且 \(\gcd(P,Q)=1\)）。
对于 \(20\%\) 的数据，\(n\le 1000\)
对于另外 \(30\%\) 的数据，每个节点最多与两个节点相邻。
对于 \(100\%\) 的数据，\(n\le 10^6,1\le v_i\le 10^9\)
思路
结论1：若所有点的权值均 \(>1\)，那么答案为最小的点权
先考虑两个点的路径，设 \(a_1\ge a_2\ge 2\)，那么此时的权值为 \(\frac{a_1\times a_2}{2}=a_1\times \frac{a_2}{2}\ge a_1\times 1\ge a_1\ge a_2\)，因此选单个最小显然是更优的。
结论2：答案所在路径只可能是最长的 \(1\) 串也可能是中间夹有 \(1\) 个 \(2\) 的 \(1\) 串
前半句显然是对的，而例如 \(S_1=\{1,1,1,1\},S_2=\{1,1,1,1,2,1,1,1,1\}\)，\(S_2\) 比 \(S_1\) 更优的，但中间夹的数不能多于 \(1\) 个也不能大于 \(2\) 原因是，把它补成一个等价于 \(1\) 串的路径，显然另一半是更有的。
例如在答案为 \(1/l\) 的 \(1\) 串后加上一个 \(3\) 再补齐后，其答案仍为 \(3/3l=1/l\)，就要补 \(2l-1\) 个 \(1\)，那 \(1/(2l-1)\) 更优，只取这一段即可。
于是我们维护出以 \(u\) 为根的子树的最长和次长 \(1\) 链 \(f_{u,0/1}\)，以及 \(u\) 子树以外的且以 \(u\) 的父亲 \(fa\) 为一端的最长 \(1\) 链 \(g_u\)，最后枚举每个节点，关心权值为 \(1\) 或 \(2\) 的情况，根据结论更新答案即可。
代码
#include
#include
#include
#include
#include
#include
#include \(\text{T3}\) 丢手绢
题意
小 \(S\) 在玩一个叫丢手绢的游戏。
一共 \(n\) 个小朋友围成一圈，其中第 \(i\) 个小朋友的能力值是 \(p_i\)。
小 \(S\) 一共会丢 \(n\) 个手绢，其中第 \(i\) 个手绢的能力值是 \(v_i\)，他会先站在第 \(a_i\) 个小朋友身后，如果当前这个小朋友手上没有手绢，他就会把当前这个手绢交给这个小朋友。否则。他就会走向下一个人。
现在，小 \(S\) 想要让尽量多的人得到的手绢能力值比他本身的能力值大，手绢可以按任意顺序发放。求这个最大值。
对于 \(40\%\) 的数据，\(a_i=1\)
对于 \(100\%\) 的数据，\(n\le 5\times 10^5,1\le a_i\le n,1\le p_i,v_i\le 10^9\)
思路
首先看部分分，显然不会出现从第 \(n\) 个小朋友去到第 \(1\) 个小朋友的情况，于是得到一条链，贪心尽可能地找\(\operatorname{upper\_bound}\) 即可。
考虑对全部数据，是否存在一个断环成链的位置呢？答案是肯定的，从三方面证明。
-
若 \(a_i\) 两两不同，就相当于在每个位置都放置一个手绢，也就是说，每个位置都可以断环成链。
-
若在 \(a_i\) 累计放置的手绢数都恰好为 \(a_{i+1}-a_i\)，即到下一个放手绢位置的小朋友数，那么两个放置位置间不会有手绢流动，这些位置可以断环成链。
-
若存在 \(a_i\) 累计放置的手绢小于到下一个放手绢位置的小朋友数，那么在这一段会出现空，也就是说后面的手绢数会经过如此补上来，且不会到 \(a_{i+1}\)，而这就是断环成链之处。
于是可以发现，断环成链的点满足这一段是没有手绢流动的，我们设一个区间手绢数与小朋友数之差为 \(b\)。
对于整个环而言，\(b=0\)，而因为断边 \((i,i+1)\) 不会有流量，于是所有以 \(i\) 为终点的段，其 \(b\le 0\)，从而相反一部分，即所有以 \(i+1\) 为起点的段，其 \(b\ge 0\)。
而对于任意的一个 \(j\)，以为 \((1,i)\) 与 \((j,i)\) 的 \(b\) 都是 \(\le 0\) 的，而 \(b_{1,j}+b_{j,i}=b_{1,i}\) 所以 \(b_{1,j}\ge b_{1,i}\)，也就是说，找到最小的那个 \(b_{1,i}\) 就是要找到断点。
代码
vector v[maxn];
set s;
int main(){
n=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
for(int i=1;i<=n;i++){
p[i]=read();
}
for(int i=1;i<=n;i++){
int x=read();
v[a[i]].push_back(x);
}
for(int i=1;i<=n;i++){
cnt[i]=cnt[i-1]+v[i].size()-1;
}
for(int i=1;i<=n;i++){
if(cnt[i]::iterator it=s.upper_bound(p[tmp]);
if(it==s.end()) s.erase(s.begin());
else{
s.erase(it);
ans++;
}
}
printf("%d\n",ans);
return 0;
}
\(\text{T4}\) Trie
题意
给你 \(n\) 个字符串 \(s_i\)，你可以任意打乱他们。现在要最小化他们建成Trie树的节点总数，求这个最小值
对于 \(100\%\) 的数据，\(n\le 16,\sum |s_i|\le 10^6\)
思路
Trie树的本质，是把公共前缀放在一起，显然前缀是对每个字符的个数取 \(\min\) 的，但是，每一小组字符串也可能存在大于总前缀的公共前缀。形似区间dp。
\(n\) 很小，于是要枚举每种状态的子集，考虑状压记录这种区间，然后大力转移即可。
代码
int main(){
n=read();
for(int i=1;i<=n;i++){
scanf("%s",s+1);
for(int j=1;j<=strlen(s+1);j++){
cnt[i][s[j]-'a']++;
}
}
for(int i=0;i<(1<