Fork me on GitHub

牛客网练习赛20

发表于 | 分类于

A 礼物

题目描述：

我从买奥利奥的事情中想出了一个算法题：假设某个店铺有N种不同类型的1元奥利奥和M种不同类型的2元奥利奥,而且余量无限,我的钱有k元,我想把k元都用来买奥利奥,且可以买同类型的奥利奥,你能帮我算出有多少种购买方式吗？设答案为Z,这个数字也许会很大,所以我们只需要输出Z mod P的值。

输入描述：

输入的第一行包含一个整数T，表示测试组数。
每个测试用例前面都有一个空白行。
每个测试用例由包含整数N,M,K和素数P的单行组成。

输出描述：

对于每个测试用例输出一个整数：表示不同的购买奥利奥的方式的数量Z mod P的值。

示例：

输入：
3

0 10 2 47

2 2 4 47

5 5 10 47

输出：
10
14
6

说明：

在第一个测试样例中，我们必须购买一包2元的奥利奥，并且有10种类型。
在第二个测试样例中，我们有以下选择：
购买两包2元的奥利奥：3种方式
购买一包2元的奥利奥和两包1元的奥利奥： 2 × 3 = 6 种方式
购买四包1元的奥利奥：5种方法
因此答案是（3 + 6 + 5）mod 47 = 14 mod 47 = 14 。

备注：

T=100
3 ≤ P ≤ 1000000
0 ≤ N,M ≤ 1000和1 ≤ ķ ≤ 1000

思路：

有两种思路：一是背包，二是组合数。
背包就是(i,j)在j状态i的类型选与不选 f[i][j]=f[i][j]+f[i][j-1];
f[i][j]=f[i][j]+f[i][j-2];
组合数
这个题可以转换成相同的小球放到不同的盒子可以有空盒(k是相同的小球n,m是不同的盒子)（经典的隔板法）;本题方案数公式C(n-1+k)(n-1)*c(m-1+k-(n-1))(m-1);

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>

using namespace std;
const int maxn=1005;
int main(){
    int f[maxn];
    int t;
    cin>>t;
    while(t--){
        int n,m,k,p;
        cin>>n>>m>>k>>p;
        memset(f,0,sizeof(f));
        f[0]=1;
         for(int i=1;i<=n;i++)
            for(int j=1;j<=k;j++)
             f[j]=(f[j]+f[j-1])%p;
         for(int i=1;i<=m;i++)
            for(int j=2;j<=k;j++)
              f[j]=(f[j]+f[j-2])%p;
         cout<<f[k]<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2010;
ll c[maxn][maxn];
int n,m,k,p;
void init(){
   c[0][0]=1;
    c[1][0]=1;
    c[1][1]=1;
    for(int i=2; i<2009; i++)
        for(int j=0; j<=i; j++)
        {
            if(j==0||j==i)
                c[i][j]=1;
            else c[i][j]=(c[i-1][j-1]+c[i-1][j])%p;////////这里组合数太大，已经炸了
   
        }
}
int main(){
    int T;
    cin>>T;
    for(int i=1;i<=T;i++){
        cin>>n>>m>>k>>p;
           init();
        ll ans=0;
        if(n==0&&m==0)
            ans=0;
        else if(n==0&&m!=0){
                if(k%2!=0)
                    ans=0;
                else ans+=c[m+k/2-1][m-1];
                //cout<<c[m+k/2-1][m-1]<<endl;
            }else if(n!=0&&m==0){
                    ans+=c[n+k-1][n-1];
            }else{
             for(int j=0;j<=k;j+=2){
                    if(j/2+m-1>=0&&n+k-j-1>=0){
                       ans=(ans+c[j/2+m-1][m-1]*c[k-j+n-1][n-1])%p;
                    }//枚举有多少给2元类型的钱
                }
            }
            cout<<ans%p<<endl;
    }
  
}

总结：一般dp的代码比较简洁，但我很难推出状态转移方程，组合数的话要建立好组合模型就好做本次最大的收获是杨辉三角求组合数，还是太菜a。

F 填数字

题目描述：

托米发现了一种新的游戏–填数字!
每填写一次数字(1≤ i≤9)需要花费ai枚金币,托米总共有n枚金币.
托米想知道他能得到的最大数字是多少.
如果填不了请输出-1。
不需要用完所有金币

输入描述：

第一行一个数字n,表示金币总数.
第二行9个正整数,第i个数字表示填写一次数字i所需要的金币数.

输出描述：

输出满足条件的最大数字.

示例1

输入：
5
5 4 3 2 1 2 3 4 5

输出：
55555

示例2

输入：
2
9 11 1 12 5 8 9 10 6
输出：
33

示例3：

输入：
0
1 1 1 1 1 1 1 1 1
输出：
-1

备注：

0≤ n≤ 106
1≤ ai≤ 105

思路：

先从a[i]数列中找出最小值 min len=n/min 保证位数最多
然后再把剩余的钱币用来生成比最小值所对应数字大的数字 从9
开始遍历保证最高位数字最大。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
 
using namespace std;
const int maxn=1e6+20;
int b[maxn];
int main(){
    int n,a[10],Min=1e6,x;
    cin>>n;
    for(int i=1;i<=9;i++){
        cin>>a[i];
        if(Min>=a[i]){
            Min=a[i];
            x=i;
        }
    }
    int len=n/Min;
    int l=n%Min;
    int sum=0;
    if(len==0){
        cout<<-1<<endl;
        return 0;
    }
    int j=1;
    for(int i=9;i>=x&&len>=1;i--){
        if(i==x){
            while(len){
                b[j++]=x;
                len--;
            }
        }
        else {
            while(l>=a[i]-a[x]&&len>=1){
                b[j++]=i;
                l=l-(a[i]-a[x]);
                len--;
            }
        }
    }
    for(int k=1;k<j;k++){
        cout<<b[k];
    }
    cout<<endl;
    return 0;
}

总结：这题比赛时没做出来感觉可做打比赛时还是要多想，贪心挺好玩的