2023.4.24测试
区间第2大
题目大意
\(a[1\dots n]\) 是 \(1\dots n\) 的某个排列，对于所有 \(1\leq l<r\leq n\)，将出 \(a[l\dots r]\) 中第二大数累加到 \(ans\)，求 \(ans\)
\(n\leq 10^5\)
解题思路
-
对于 \(a[i]\)，考虑它被计算了多少次，容易看出只需找出它左边第一个比它大的数，左边第二个比它大的数，右边第一个，右边第二个即可
-
\(\mathrm{ST}\) 表 + 二分即可
竹子
题目大意
有 \(n\) 棵竹子从左往右排成一行，编号 \(1\) 至 \(n\)，第 \(i\) 棵竹子的高度是\(h_i\)。
每天你需要砍掉 \(1\) 棵竹子，被砍的竹子的高度会变成 \(0\)，假设你当天砍掉的是第 \(i\) 棵竹子，那么此次的代价是 \(h_{i-1}+h_i+h_{i+1}\)。
我们认为 \(h_0=h_{n+1}=0\)。
显然，总共有 \(n!\) 种不同的砍竹子的方案，有多少种不同的方案，使得砍完所有竹子的总代价最小？
输出能使得总代价最小的不同方案数。答案模 \(1000000007\)。
解题思路
-
蒟蒻我考场只会 \(O(n!)\) 的暴力
-
第一次接触 插入\(\mathrm{dp}\) ，只考虑前 \(i\) 课竹子，后面的竹子等到插入时再考虑。设 \(f[i][j]\) 表示第 \(i\) 课竹子在前 \(i\) 棵竹子中是第 \(j\) 棵砍的，此时总代价的最小值，那么就有
\[f[i][j]=\min\begin{cases}f[i-1][k]+h_i+h_i&1\leq k<j\\f[i-1][k]+h_i+h_{i-1}&j\leq k\leq i-1\end{cases} \] -
用一个前后缀预处理即可转移
-
设 \(g[i][j]\) 表示第 \(i\) 课竹子在前 \(i\) 棵竹子中是第 \(j\) 棵砍的，此时让总代价最小的方案数，随着 \(f\) 的转移进行转移即可
代码
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=4010;
const LL MOD=1000000007;
int n;
LL h[N],f[N][N],g[N][N];
LL ff[N][2],gg[N][2];
int main()
{
memset(f,0x3f,sizeof(f));
memset(ff,0x3f,sizeof(ff));
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%lld",&h[i]);
f[1][1]=h[1];
g[1][1]=1;
ff[1][0]=ff[1][1]=f[1][1];
gg[1][0]=gg[1][1]=1;
for(int i=2; i<=n; i++)
{
for(int j=1; j<=i; j++)
{
LL a=ff[j-1][0]+h[i]+h[i],b=ff[j][1]+h[i]+h[i-1];
if(a==b)
g[i][j]=(gg[j-1][0]+gg[j][1])%MOD;
else if(a<b)
g[i][j]=gg[j-1][0];
else
g[i][j]=gg[j][1];
f[i][j]=min(a,b);
}
memset(ff,0x3f,sizeof(ff));
memset(gg,0,sizeof(gg));
for(int j=1; j<=i; j++)
ff[j][0]=min(ff[j-1][0],f[i][j]);
for(int j=i; j>=1; j--)
ff[j][1]=min(ff[j+1][1],f[i][j]);
for(int j=1; j<=i; j++)
{
if(f[i][j]==ff[j-1][0])
gg[j][0]=(gg[j-1][0]+g[i][j])%MOD;
else if(f[i][j]<ff[j-1][0])
gg[j][0]=g[i][j];
else
gg[j][0]=gg[j-1][0];
}
for(int j=i; j>=1; j--)
{
if(f[i][j]==ff[j+1][1])
gg[j][1]=(gg[j+1][1]+g[i][j])%MOD;
else if(f[i][j]<ff[j+1][1])
gg[j][1]=g[i][j];
else
gg[j][1]=gg[j+1][1];
}
}
LL mn=1e14,ans=0;
for(int i=1; i<=n; i++)
mn=min(mn,f[n][i]);
for(int i=1; i<=n; i++)
if(f[n][i]==mn)
ans=(ans+g[n][i])%MOD;
printf("%lld",ans);
return 0;
}
奶牛安家
题目大意
有 \(n\) 头奶牛，在一条数轴上选择自己的家。数轴上有 \(m\) 个整点，分别是 \(0\) 至 \(m-1\)。每头奶牛都选择一个不同的整点作为的自己的家。第 \(i\) 头奶牛有一个安全距离 \(R[i]\)，表示的意义是第 \(i\) 头奶牛与它的邻居的距离不能小于 \(R[i]\)。也就是说，如果奶牛 \(i\) 和奶牛 \(j\) 是邻居，那么这两头奶牛之间的距离不能小于 \(\max(R[i],R[j])\)。输出有多少种不同的合法安家方案，答案模 \(1000000007\)。
解题思路
-
显然最终的答案和奶牛的排列有关。如果我们知道最后奶牛之间的距离限制总和 \(s\)，那么我们就可以使用插板法求出答案，为 \(C_{m-s+n-1}^{n}\)
-
现在考虑如何计算限制长度和为 \(s\) 的方案数。我们先将奶牛按 \(R\) 从小到大排序，将限制抽象成一条链，那这条链可以是由多条链连接在一起的。因为我们排了序，那么后面的奶牛参与到链的拼接时就无需考虑大小关系。
-
考虑 \(\mathrm{dp}\)，设 \(f[i][j][k]\) 表示到第 \(i\) 头奶牛，目前的链数为 \(j\)，链的总长度为 \(k\)。那么考虑我为人人，\(f[i][j][k]\) 可以对哪些状态作出贡献
-
\(f[i][j][k]\rightarrow f[i+1][j+1][k]\)
表示第 \(i+1\) 头奶牛单独成链
-
\(f[i][j][k]*j*(j-1)\rightarrow f[i+1][j-1][k+R[i+1]*2]\)
表示用第 \(i+1\) 头奶牛连接任意两条链
-
\(f[i][j][k]*2*j\rightarrow f[i+1][j][k+R[i+1]]\)
表示将第 \(i+1\) 头奶牛任意接到一条链的头或尾
-
-
做完 \(\mathrm{dp}\) 后组合数求解即可。注意因为组合数涉及阶乘和除法的运算，所以需要做预处理，还要求逆元。因为模数 \(1000000007\) 是质数，所以可以用费马小定理来求。
代码
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=50,M=100010;
const LL MOD=1000000007;
int G,n,m,r[N];
LL pw[M+N],f[N][N][N*N];
LL ans;
LL ksm(int a,LL b)
{
if(b==0)
return 1;
if(b==1)
return a;
LL tmp=ksm(a,b/2);
if(b%2==0)
return tmp*tmp%MOD;
return tmp*tmp%MOD*a%MOD;
}
LL C(int a,int b)
{
if(a<b)
return 0;
return pw[a]*ksm(pw[a-b],MOD-2)%MOD*ksm(pw[b],MOD-2)%MOD;
}
int main()
{
pw[0]=1;
for(int i=1; i<=M+N-20; i++)
pw[i]=(pw[i-1]*i)%MOD;
scanf("%d",&G);
while(G--)
{
memset(f,0,sizeof(f));
scanf("%d%d",&m,&n);
for(int i=1; i<=n; i++)
scanf("%d",&r[i]);
sort(r+1,r+1+n);
f[0][0][0]=1;
for(int i=0; i<n; i++)
{
for(int j=0; j<=i; j++)
{
for(int k=0; k<=40*n; k++)
{
f[i+1][j+1][k]=(f[i+1][j+1][k]+f[i][j][k])%MOD;
if(j>=2)
f[i+1][j-1][k+r[i+1]*2]=(f[i+1][j-1][k+r[i+1]*2]+f[i][j][k]*1LL*j%MOD*(j-1)%MOD)%MOD;
if(j>=1)
f[i+1][j][k+r[i+1]]=(f[i+1][j][k+r[i+1]]+f[i][j][k]*1LL*2*j%MOD)%MOD;
}
}
}
ans=0;
for(int i=0; i<=40*n; i++)
ans=(ans+f[n][1][i]*C(m-i+n-1,n)%MOD)%MOD;
printf("%lld\n",ans);
}
return 0;
}
加强版 [COCI2021-2022#2] Magneti
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=60,M=10010;
const LL MOD=1000000007;
int G,n,m,r[N];
LL pw[M+N],f[N][N][M];
LL ans;
LL ksm(LL a,LL b)
{
if(b==0)
return 1;
if(b==1)
return a;
LL tmp=ksm(a,b/2);
if(b%2==0)
return tmp*tmp%MOD;
return tmp*tmp%MOD*a%MOD;
}
LL C(int a,int b)
{
if(a<b)
return 0;
return pw[a]*ksm(pw[a-b],MOD-2)%MOD*ksm(pw[b],MOD-2)%MOD;
}
int main()
{
pw[0]=1;
for(int i=1; i<=M-10; i++)
pw[i]=(pw[i-1]*i)%MOD;
memset(f,0,sizeof(f));
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
scanf("%d",&r[i]);
sort(r+1,r+1+n);
f[0][0][0]=1;
for(int i=0; i<n; i++)
{
for(int j=0; j<=i; j++)
{
for(int k=0; k<=m; k++)
{
f[i+1][j+1][k]=(f[i+1][j+1][k]+f[i][j][k])%MOD;
if(j>=2 && k+r[i+1]*2<=m)
f[i+1][j-1][k+r[i+1]*2]=(f[i+1][j-1][k+r[i+1]*2]+f[i][j][k]*1LL*j%MOD*(j-1)%MOD)%MOD;
if(j>=1 && k+r[i+1]<=m)
f[i+1][j][k+r[i+1]]=(f[i+1][j][k+r[i+1]]+f[i][j][k]*1LL*2*j%MOD)%MOD;
}
}
}
ans=0;
for(int i=0; i<=m; i++)
ans=(ans+f[n][1][i]*C(m-i+n-1,n)%MOD)%MOD;
printf("%lld\n",ans);
return 0;
}