T1 gift

Solution：

  • 题目描述显然就是一个背包，然而就是不知道怎么拿背包做QAQ 爆搜+剪枝三十分 正解的确是01背包
  • 首先将 <nobr> w </nobr>从小到大排序，题意可以转化为买其中若干物品后，剩余钱数小于所有剩余物品代价的最小值的方案数，那么我们按照排序后顺序做背包可以方便很多。
  • 用 <nobr> f[i][j] </nobr>表示用编号为 <nobr> i </nobr>~ <nobr> n </nobr>的物品组合成的，剩余容量为 <nobr> j </nobr>的方案数，初始值 <nobr> f[n+1][m]=1 </nobr>
  • 我们倒序枚举每一个物品时，用背包计算方案数
  • 假设枚举到i的时候，前 <nobr> （i−1） </nobr>种物品全部选，第i个物品不选， <nobr> （i+1） </nobr>~ <nobr> n </nobr>的物品已经做完了背包，由于我们已经排好序，所以i物品一定是不选的物品之中代价最小的一个，所以可行解的范围应该在 <nobr> [sum[i−1],sum[i−2]) </nobr>之间
  • 那么满足题意的方案数应该是 <nobr> ∑min(sum[i],m)k=sum[i−1]dp[i+1][k] </nobr>，累加到答案里即可
  • 注意特判一下 <nobr> ∑ni=1w[i]<=m </nobr>的情况
#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];//做 i~n 物品的背包，剩余空间为 j 的方案数 
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

  • 模型转化一下，就是一个排列组合的经典问题(括号序列)
  • 把每一个 <nobr> +1 </nobr>转化成一个 <nobr> （1,0） </nobr>向量， <nobr> −1 </nobr>转化为一个 <nobr> （0,1） </nobr>向量，那么问题就转化为求不经过 <nobr> y=x </nobr>以上的点到达 <nobr> （n,m） </nobr>的路径数目，最后再除以一个路径总数
    <nobr> ans=Cmn+m−Cm−1n+mCmn+m=1−mn+1 </nobr>

    然后 <nobr> O(1) </nobr>回答就好
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
// freopen("fseq.in","r",stdin);
// freopen("fseq.out","w",stdout);
    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
考的比较惨烈啊