T1 gift
Solution：
题目描述显然就是一个背包，然而就是不知道怎么拿背包做QAQ 爆搜+剪枝三十分 正解的确是01背包首先将
w
从小到大排序，题意可以转化为买其中若干物品后，剩余钱数小于所有剩余物品代价的最小值的方案数，那么我们按照排序后顺序做背包可以方便很多。
用
f[i][j]表示用编号为
i
~
n的物品组合成的，剩余容量为
j
的方案数，初始值
f[n 1][m]=1我们倒序枚举每一个物品时，用背包计算方案数假设枚举到i的时候，前
（i−1）
种物品全部选，第i个物品不选，
（i+1）
~
n
的物品已经做完了背包，由于我们已经排好序，所以i物品一定是不选的物品之中代价最小的一个，所以可行解的范围应该在
[sum[i−1],sum[i−2])之间那么满足题意的方案数应该是
∑min(sum[i],m)k=sum[i−1]dp[i+1][k]
，累加到答案里即可注意特判一下
∑ni=1w[i]<=m
的情况
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=
1010,mod=
1e9+
7;
int n,m;
int f[
1010][
1010],sum[
1010],w[
1010];
long long ans;
int main()
{
freopen(
"gift.in",
"r",stdin);
freopen(
"gift.out",
"w",stdout);
scanf(
"%d%d",&n,&m);
for(
int i=
1;i<=n;i++)
scanf(
"%d",&w[i]);
sort(w+
1,w+n+
1);
for(
int i=f[n+
1][m]=
1;i<=n;i++) sum[i]=sum[i-
1]+w[i];
for(
int i=n;i>=
1;i--)
{
for(
int j=sum[i-
1],k=min(m+
1,sum[i]);j<k;j++) ans+=f[i+
1][j];
for(
int j=m;j>=
0;j--)
{
f[i][j]=f[i+
1][j];
if(j+w[i]<=m) (f[i][j]+=f[i+
1][j+w[i]])%=mod;
}
}
printf(
"%lld",max(ans,
1ll)%mod);
return 0;
}
T2 fesq
模型转化一下，就是一个排列组合的经典问题(括号序列) 把每一个
+1
转化成一个
（1,0）
向量，
−1
转化为一个
（0,1）
向量，那么问题就转化为求不经过
y=x
以上的点到达
（n,m）
的路径数目，最后再除以一个路径总数
ans=Cmn+m−Cm−1n+mCmn+m=1−mn+1
然后
O(1)
回答就好
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int T;
scanf(
"%d",&T);
while(T--){
int n,m;
scanf(
"%d%d",&n,&m);
if(m>n)
puts(
"0.000000");
else printf(
"%.6f\n",(n-m+
1.0)/(n+
1));
}
return 0;
}
T3 lucky
数位DP或者暴力容斥，比较麻烦（雾） 待更TAT 考的比较惨烈啊
