暑假第十九测

题解：第一题：为了不重复，我们只能算某一个物品被剩下时不能选的方案；

我们枚举第几小的物品不能选，则他前面都能选，所以我们需要的体积是sum[[i - 1] -- sum[i - 1] + v[i] - 1, 达到这个体积的方案数怎么求，我们可以先倒着做一遍dp; 那么我们就可以知道装满dp[m - sum[i - 1]] -- dp[m - sum[i] - v[i] + 1] 的方案数了；

对于第 i 小不选的方案数为 sum (dp[i + 1][m - sum[i - 1] ---- m - sum[i] - v[i] + 1] );

这个dp方程还是要好好想想的，可以从后面做一次来优化转移的复杂度

#include<bits/stdc++.h>
using namespace std;
const int M = 1005, mod = 1000000007;
int dp[M][M], ans, sum[M], n, m, v[M];
inline int moc(int a){return a >= mod ? a - mod : a;};

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", &v[i]);
    sort(v + 1, v + 1 + n);
    for(int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + v[i];
    dp[n + 1][0] = 1;
    for(int i = n; i >= 1; i--){
        for(int j = 0; j < v[i]; j++)dp[i][j] = dp[i + 1][j];
        for(int j = m; j >= v[i]; j--)
            dp[i][j] = moc(dp[i + 1][j] + dp[i + 1][j - v[i]]);
    }
    for(int i = 1; i <= n; i++){
        int res = m - sum[i - 1];
        for(int j = res; j >= max(0, res - v[i]); j--)
            ans = moc(ans + dp[i + 1][j]);
    }
    printf("%d
", ans);
}

View Code

第二题：

算法：组合数学题
可以将原问题转化一下，看成是在一个二维平面上行走，+1看成移动(1,0)
-1看成移动(0,1)，那么到达(N,M)点且路线又不走到y=x这条直线上方的路线总数就是
答案，这个组合问题很经典，方案数为C(M,M+N)-C(M-1,M+N)，所以
可以知道答案就是1-M/(N+1)

我忘特判n < m了

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int main(){
    freopen("fseq.in","r",stdin);
    freopen("fseq.out","w",stdout);
    int T;
    scanf("%d", &T);
    while(T--){
        double n, m;
        scanf("%lf%lf", &n, &m);
        if(n < m)printf("0.000000
");
        else printf("%.6lf
", 1 - m/(n+1));
    }
}

View Code

第三题：数位dp; 但是我们发现前面的数会对后面产生影响，当总位数为 7， 8时，第一位上的限制是不一样的，所以dp要限制一个总位数，开一个vis[总位数][dep]记录dep位不能填什么，为什么这样就没有影响呢？

因为总位数一样时，最高位填3或4，最低位都有9个数可以选择，而中间的情况是一样的；

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[20][20][2], vis[20][20];
int digit[20];
ll dfs(int tot, int dep, int f, int zero){
    if(!dep)return 1;
    if(dp[tot][dep][f] != -1)return dp[tot][dep][f];
    int i = f ? digit[dep] : 9;
    ll tmp = 0;

    for( ; i >= 0; i--){
        if(i != vis[tot][dep]){
            tot -= (zero & (i == 0));
            if(dep > (tot + 1)/2) vis[tot][tot - dep + 1] = i;
            tmp += dfs(tot, dep - 1, f & (i == digit[dep]), zero & (i == 0));    
        }
    }
    return dp[tot][dep][f] = tmp;
}



ll get(ll x){
    memset(dp ,-1, sizeof(dp));
    memset(vis, -1, sizeof(vis));
    int cnt = 0;
    while(x){
        digit[++cnt] = x%10;
        x /= 10;
    }
    return dfs(cnt, cnt, 1, 1);
}
int main(){
    freopen("lucky.in","r",stdin);
    freopen("lucky.out","w",stdout);
    
    ll L, R;
    cin>>L>>R;
    ll ans1 = get(R);
    ll ans2 = get(L-1);
    //cout<<ans2<<" "<<ans1<<endl;
    cout<<ans1-ans2<<endl;
}

View Code

今天爆零了！！！！！