前言
喵喵于 \(2024.3.18\) 建立 \(vjudge\) 团队 \(NOIP2024\) ，成员为全体 \(HZOI2024\) 初三现役人员，旗下三个板块的专题训练，分别为动态规划、图论、字符串，其中题目非紫即黑，存在少量蓝。
并于 \(2024.3.19\) 成功关闭 \(luogu\) 。
接下来做的题我会按照开题顺序（大抵等同于从易到难）将 \(A\) 掉的题记录下来，同时可能有类似题的扩展。
动态规划专题
B - Birds
混合背包 \(DP\) 。
定义 \(f_{i,j}\) 表示取到鸟巢 \(i\) ，获得 \(j\) 只小鸟时所剩的魔力值。
显然有 \(f_{0,0}=1\) 。
转移为：
\[f_{i+1,j+k}=\max(f_{i+1,j+k},\min(f_{i,j}-k\times cost_i+x,w+(j+k)\times b)) \]其中 \(k\) 表示对于鸟巢 \(i\) 取了几个鸟，其余变量意义与上述表达或题面相同。
特别的，有任意 \(f_{i+1,j+k}\leq w+(j+k)\times b\) ，又题意可得。
注意：
-
将所有 \(f_{i,j}\) 初始化为 \(-1\) （表示没有更新过，而 \(0\) 可能是恰好为 \(0\) 并非未更新，会产生歧义），若 \(f_{i,j}\) 没有更新过，即他此时所剩魔力值 \(<0\) ，则无法更新 \(f_{i+1,j+k}\) 。
-
若 \(f_{i,j}-k\times cost_i<0\) 说明无法取这么多鸟，那么显然更大的 \(k\) 也无法取到，所以 \(break\) 。
-
对于 \(j\) 应循环到 \(sum_i\) ，\(sum_i\) 表示 \(c_i\) 的前缀和，即最多取这么多鸟。
同理的，\(k\) 循环到 \(c_i\) 。
当然，\(j,k\) 均从 \(0\) 开始循环。
最后处理答案，显然我们取完鸟巢 \(n\) 后的答案将体现在 \(f_{n+1,j}\) 中，答案为所有 \(\geq 0\) 的 \(f_{n+1,j}\) 中 \(j\) 的最大值。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e3+10,M=1e4+10;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
int n,w,b,x,ans,c[N],v[N],sum[N],f[N][M];
signed main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
read(n),read(w),read(b),read(x);
for(int i=1;i<=n;i++)
read(c[i]),
sum[i]=sum[i-1]+c[i];
for(int i=1;i<=n;i++) read(v[i]);
memset(f,-1,sizeof(f));
f[0][0]=w;
for(int i=0;i<=n;i++)
for(int j=0;j<=sum[i];j++)
for(int k=0;k<=c[i];k++)
{
int s=f[i][j];
if(s<0) break;
s-=k*v[i];
if(s<0) break;
s=min(s+x,w+(j+k)*b);
f[i+1][j+k]=max(f[i+1][j+k],s);
}
for(int i=0;i<=sum[n];i++)
if(f[n+1][i]>=0)
ans=max(ans,i);
cout<<ans;
}
I - Game on Sum (Easy Version)
此题为简单版，可以直接跑 \(DP\) 。
定义 \(f_{i,j}\) 表示进行了 \(i\) 轮，其中 \(Bob\) 选择加的有 \(j\) 轮时的分数。
设 \(x_i\) 表示 \(Alice\) 本轮选择的数。
-
若选择加，则有本轮分数为 \(f_{i-1,j-1}+x_i\) 。
-
若选择减，则有本轮分数为 \(f_{i-1,j}-x_i\) 。
显然 \(Bob\) 会选择 \(\min(f_{i-1,j-1}+x_i,f_{i-1,j}-x_i)\) 。
已知两者相加为定值，那么显然当两者相等时，\(\min(f_{i-1,j-1}+x_i,f_{i-1,j}-x_i)\) 最大。
所以 \(Alice\) 会选择两者相等时的情况，则有：
\[f_{i,j}=\min(f_{i-1,j-1}+x_i,f_{i-1,j}-x_i)=\dfrac{f_{i-1,j-1}+f_{i-1,j}}{2} \]同时，显然有 \(f_{i,0}=0\) ，\(f_{i,i}=i\times k\) 。
最后答案为 \(f_{n,m}\) 。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=2010,P=1e9+7;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
int t,n,m,k,f[N][N],inv2;
int qpow(int a,int b)
{
int ans=1;
for(;b;b>>=1)
{
if(b&1) (ans*=a)%=P;
(a*=a)%=P;
}
return ans;
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
read(t);
inv2=qpow(2,P-2);
while(t--)
{
read(n),read(m),read(k);
for(int i=1;i<=n;i++)
for(int j=0;j<=min(i,m);j++)
if(i==j) f[i][j]=(k*i)%P;
else if(j==0) f[i][j]=0;
else f[i][j]=(((f[i-1][j]+f[i-1][j-1])%P)*inv2)%P;
cout<<f[n][m]<<endl;
}
}
Game on Sum (Hard Version)
此题为困难版，将 \(n,m,t\) 的范围都大大增加，无法跑正常的 \(DP\) 。
所以去思考上面所述 \(DP\) 中关于答案的贡献。
不难发现，上述 \(DP\) 可以组成一个类似于杨辉三角的东西。
去考虑 \(f_{i,i}\) 对于答案的贡献，因为只有 \(f_{i,i}\) 在跑 \(DP\) 之前是确定的。
我们发现对于 \(f_{i,j}\) ，他将对 \(f_{i+1,j}\) 与 \(f_{i+1.j+1}\) 产生 \(1\) 的贡献（ \(1\) 指 $1\times $ 自身）。
那么以此类推，\(f_{i,i}\) 将对 \(f_{n,m}\) 产生 \(n-i\) 的贡献，其中选择 \(m-i\) 去加。
但同时如果从 \(f_{i,i}\) 去考虑的话，他还会给 \(f_{i+1,i+1}\) 产生 \(1\) 的贡献，但这里已经填好了，显然这一次是不可能给 \(m\) 加的，所以在 \(n-i-1\) 的贡献中选择 \(m-i\) 次去给 \(m\) 加。
也就是 \(f_{i,i}\) 对 \(f_{n,m}\) 的贡献为 \(\dfrac{i\times k\times \text{C}_{n-i-1}^{m-i}}{2^{n-i}}\) 。
这个 \(2^{n-i}\) 显然，每次都是要 \(÷2\) 的，而 \(i\times k\) 表示 \(f_{i,i}\) 自身。
由此最后的答案就为：
\[\sum\limits_{i=1}^{m}\dfrac{i\times k\times \text{C}_{n-i-1}^{m-i}}{2^{n-i}} \]至于只循环到 \(m\) ，因为 \(Bob\) 只会选择 \(m\) 轮去加。
关于代码：首先需要预处理阶乘与每个 \(2^i\)，乘法逆元可用费马小定理 \(+\) 快速幂，因为预处理需要到 \(1e9\) 显然会炸。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+10,P=1e9+7;
template<typename Tp> inline void read(Tp&x)
{
x=0;register bool z=true;
register char c=getchar();
for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
x=(z?x:~x+1);
}
int t,n,m,k,jc[N],inv2[N];
int qpow(int a,int b)
{
int ans=1;
for(;b;b>>=1)
{
if(b&1) (ans*=a)%=P;
(a*=a)%=P;
}
return ans;
}
void pre()
{
jc[0]=jc[1]=1;
for(int i=2;i<=N-1;i++) jc[i]=(jc[i-1]*i)%P;
inv2[0]=1,inv2[1]=2;
for(int i=2;i<=N-1;i++) inv2[i]=(inv2[i-1]*2)%P;
}
int C(int m,int n)
{
if(m==0||n==m) return 1;
return (((jc[n]*qpow(jc[m],P-2))%P)*qpow(jc[n-m],P-2))%P;
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
pre();
read(t);
while(t--)
{
read(n),read(m),read(k);
if(n==m)
{
cout<<(n*k)%P<<endl;
continue;
}
int ans=0;
for(int i=1;i<=m;i++)
(ans+=(((((i*k)%P)*C(m-i,n-i-1))%P)*qpow(inv2[n-i],P-2))%P)%=P;
cout<<ans<<endl;
}
}