赛后——2.8 寒假模拟4
\(\text{T1}\) 阿
题意
给定一个 \(0 \sim n-1\) 的排列 \(p\)。
一个 \(0\sim n-2\) 的排列 \(q\) 被认为是完美的，当且仅当满足下列条件：
对排列 \(s=\{0,1,2\cdots n-1\}\) 进行 \(n-1\) 次交换（下标从 \(0\) 开始），第 \(i\) 次交换时，交换 \(s[q_{i-1}],s[q_{i-1}+1]\)，最后能使排列 \(s=p\)。
问有多少个优美的排列，答案对 \({10}^9+7\) 取模。
思路
由 \(s\) 得到 \(p\) 与由 \(p\) 得到 \(s\) 是等价的，于是考虑把 \(p\) 弄成一个有序的排列 \(s\)。
发现在一次交换 \(p_k,p_k+1\) 后，后一部分的任意一个数都应大于前一部分的任意一个数（因为不会在对这两个区间跨区间交换），于是考虑区间 \(dp\)。
只要找到一个能保证满足上述左右性质的下标，交换后转移即可。
对于区间 \([L,R]\) 中交换 \(k\)，区间内可以交换的数对为 \(R-L\) 个，除去当前一个，并在其中选择 \(k-L\) 个（我们假设是按序交换的，乘上排列数后就释放了这一限制），得到排列数 \(\mathrm{C}_ {R-L+1}^{k-L}\)。
代码
int n;
int p[55];
ll dp[55][55],C[55][55];
inline ll dfs(int l,int r){
if(dp[l][r]!=-1) return dp[l][r];
if(l==r) return dp[l][r]=1;
dp[l][r]=0;
int maxx=0;
for(int i=l;i\(\text{T2}\) 姨
题意
小 \(S\) 在一个 \(n\times n\) 的棋盘上玩游戏。
他首先在方格上随机地填入 \(1\) 到 \(m\) 之间的正整数（每个方格填的数互不相同），然后随机地选出 \(k\) 个数字（可能不在棋盘上），把它们出现在棋盘上的方格涂黑。
设有 \(R\) 行被整行涂黑，有 \(C\) 列被整列涂黑，便可以得到 \(2^{R+C}\) 分。
求它的期望得分。
若结果大于 \(10^{99}\) 输出 \(10^{99}\)。
思路
每个 \(R\) 行 \(C\) 列都有一个 \(2^{R+C}\) 的贡献，发现恰好这个 \(R\) 行 \(C\) 列的方格有 \(2^{R+C}\) 个子集（行和列在本质上是一样的），于是每个子集对答案的贡献为 \(1\)。
接着枚举 \(i\in[0,n],j\in[1,n]\) 表示一个 \(i\) 行 \(j\) 列的子集，保证他已经被填满，显然这个子集的情况数是 \(\mathrm{C}_ {n}^i\times \mathrm{C}_ {n}^j\)。填满需要的数字为 \(x=(i+j)\times n-i\times j\)，于是剩余的填入正整数个数为 \(m-x\)，可染色的个数为 \(k-x\)，于是\(i\) 行 \(j\) 列以外情况数为 \(\mathrm{C}_ {m-x}^{k-x}\)，总情况数是 \(\mathrm{C}_ {m}^{k}\)。
于是答案：
\[\operatorname{ans}=\sum_{i=0}^n\sum_{j=0}^n \frac{\mathrm{C}_ {n}^i\times \mathrm{C}_ {n}^j\times \mathrm{C}_ {m-x}^{k-x}}{\mathrm{C}_ {m}^{k}} \]考虑怎样快速求这个式子，显然任何一个 \(\mathrm{C}_ n^i\) 都能递推出来，递推式为：
\[\mathrm{C}_ n^i=\frac{n!}{i!(n-i)!}=\frac{n!}{(i-1)!(n-i+1)!}\times \frac{n-i+1}{i}=\mathrm{C}_ n^{i-1}\times \frac{n-i+1}{i} \]而同样的，剩余的分式，也可以递推得出：
\[\frac{\mathrm{C}_ {m-i}^{k-i}}{\mathrm{C}_ m^k}=\frac{\mathrm{C}_ {m-i+1}^{k-i+1}}{\mathrm{C}_ m^k}\times \frac{k-i+1}{m-i+1} \]代码
int n,m,k;
db c[305],f[maxn];
db ans;
int main(){
n=read(),m=read(),k=read();
c[0]=1.0,f[0]=1.0;
for(int i=1;i<=n;i++){
c[i]=c[i-1]*(n-i+1)/i;
}
for(int i=1;i<=k;i++){
f[i]=f[i-1]*(k-i+1)/(m-i+1);
}
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
int siz=(i+j)*n-i*j;
if(siz<=k){
ans+=c[i]*c[j]*f[siz];
}
}
}
if(ans>1e99) printf("1e99\n");
else printf("%.7lf\n",ans);
return 0;
}
\(\text{T3}\) 洗
题意
小 \(S\) 有一个 \(n\) 个节点的二叉树。每个节点上有一个权值。节点从 \(1\) 开始编号。
现在，小 \(S\) 打算把这个二叉树改造成一个二叉排序树，二叉排序树的定义是，它的权值要比左子树的权值要大，但是比右子树要小。
他要修改某些节点的权值，使得它成为一个二叉排序树，求最小的修改次数。
思路
把树上问题转移到线性，发现要求的是这棵树的中序遍历修改成单调递增序列的最小次数。
如果直接求最长上升子序列的长再用 \(n\) 去减显然是错的，因为有可能一个区间的定义域大于值域，直接把这个区间修改时显然错的。
于是设一个 \(f_i\) 表示前 \(i\) 个数无需修改的个数，最后答案是 \(n-f_n\)，发现这个的转移是 \(\max_{j}^{i-1}\{f_j+1\}\ (val_i-val_j\ge i-j)\)，换句话说，转移次数就是最终的结果，那么为了让 \(n-f_n\) 最小，要让转移次数最多，也就是尽量长的一个 \(val_i-val_j\ge i-j\)，移项得到 \(val_i-i\ge val_j-j\)，于是设 \(a_i=val_i-i\)，显然是要求 \(a\) 的最长不下降子序列长度，也就是 \(f_n\) 了。
这里不能用朴素的 \(\operatorname{LIS}\) 算法，需要二分优化。
代码
int n,len;
int val[maxn],a[maxn],tot;
int tr[maxn][2];
inline void dfs(int u){
if(tr[u][0]) dfs(tr[u][0]);
a[++tot]=val[u];
if(tr[u][1]) dfs(tr[u][1]);
}
int f[maxn],g[maxn];
inline int get(int x){
int l=1,r=len;
int res=0;
while(l<=r){
int mid=(l+r)>>1;
if(g[mid]<=x){
res=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
return res;
}
int main(){
n=read();
for(int i=1;i<=n;i++){
val[i]=read();
}
for(int i=2;i<=n;i++){
int fa=read(),ch=read();
tr[fa][ch]=i;
}
dfs(1);
for(int i=1;i<=n;i++){
a[i]-=i;
}
for(int i=1;i<=n;i++){
f[i]=get(a[i])+1;
g[f[i]]=a[i];
len=max(len,f[i]);
}
printf("%d\n",n-len);
return 0;
}
\(\text{T4}\) 铁路
题意
小 \(S\) 有一个长度为 \(n\) 的序列。
一个区间 \([L,R]\) 是好的，当且仅当存在 \(k\in [L,R]\)，使得 \(\forall\ i\in [L,R],\ a_k\mid a_i\)。
现在，小 \(S\) 想要知道，最长的好的区间是多少，并且这些区间是什么。
思路
首先这个 \(a_k\) 显然只能是 \([L,R]\) 的最小值，赛时用线段树去维护这东西（不要问我为什么不带修用线段树），预处理出一堆前缀后缀和之类的，复杂度是 \(O(n^2\log n)\) 的。
然而正解是 \(O(n\log n)\) 的，用 \(\operatorname{ST}\) 表去维护静态的区间最小值和区间 \(\gcd\)，二分答案 \(len\) 去判断每一个这样的区间最小值与 \(\gcd\) 是否相等，然后大力判断输出答案即可。
代码
int n;
int a[maxn];
int stmin[maxn][21],stgcd[maxn][21];
inline int gcd(int a,int b){
if(!b) return a;
return gcd(b,a%b);
}
inline bool check(int len){
if(!len) return true;
for(int i=1;i+len<=n;i++){
for(int k=20;k>=0;k--){
if((1<=0;k--){
if((1<>1;
if(check(mid)){
len=mid;
l=mid+1;
}
else{
r=mid-1;
}
}
print(len);
return 0;
}