首页 > 代码库 > 高橋君とカード / Tak and Cards

高橋君とカード / Tak and Cards

2024-08-11 04:05:09   218人阅读

 高橋君とカード / Tak and Cards

Time limit : 2sec / Stack limit : 256MB / Memory limit : 256MB

Score : 300 points

Problem Statement

Tak has N cards. On the i-th (1≤i≤N) card is written an integer xi. He is selecting one or more cards from these N cards, so that the average of the integers written on the selected cards is exactly A. In how many ways can he make his selection?

Constraints

  • 1≤N≤50
  • 1≤A≤50
  • 1≤xi≤50
  • N, A, xi are integers.

Partial Score

  • 200 points will be awarded for passing the test set satisfying 1≤N≤16.

Input

The input is given from Standard Input in the following format:

N Ax1 x2 … xN

Output

Print the number of ways to select cards such that the average of the written integers is exactly A.

Sample Input 1

4 87 9 8 9

Sample Output 1

5
  • The following are the 5 ways to select cards such that the average is 8:
    • Select the 3-rd card.
    • Select the 1-st and 2-nd cards.
    • Select the 1-st and 4-th cards.
    • Select the 1-st, 2-nd and 3-rd cards.
    • Select the 1-st, 3-rd and 4-th cards. 

分析：二维背包；

代码：

#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <climits>#include <cstring>#include <string>#include <set>#include <map>#include <queue>#include <stack>#include <vector>#include <list>#define rep(i,m,n) for(i=m;i<=n;i++)#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)#define mod 1000000000#define inf 0x3f3f3f3f#define vi vector<int>#define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair<int,int>#define Lson L, mid, rt<<1#define Rson mid+1, R, rt<<1|1const int maxn=1e5+10;using namespace std;ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}int n,m,k,t;ll dp[51][2501];int a,now;ll ans;int main(){    int i,j;    dp[0][0]=1;    scanf("%d%d",&n,&a);    rep(i,1,n)    {        scanf("%d",&k);        now+=k;        for(j=i;j>=1;j--)            for(t=now;t>=k;t--)                dp[j][t]+=dp[j-1][t-k];    }    rep(i,1,n)ans+=dp[i][a*i];    printf("%lld\n",ans);    //system("Pause");    return 0;}

高橋君とカード / Tak and Cards


联系
我们