Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem DescriptionHearthstone
is an online collectible card game from Blizzard Entertainment.
Strategies and luck are the most important factors in this game. When
you suffer a desperate situation and your only hope depends on the top
of the card deck, and you draw the only card to solve this dilemma. We
call this “Shen Chou Gou” in Chinese.
Now
you are asked to calculate the probability to become a “Shen Chou Gou”
to kill your enemy in this turn. To simplify this problem, we assume
that there are only two kinds of cards, and you don’t need to consider
the cost of the cards.
- A-Card: If the card deck contains less than
two cards, draw all the cards from the card deck; otherwise, draw two
cards from the top of the card deck. - B-Card: Deal X damage to your enemy.
Note that different B-Cards may have different X values.
At
the beginning, you have no cards in your hands. Your enemy has P Hit
Points (HP). The card deck has N A-Cards and M B-Cards. The card deck
has been shuffled randomly. At the beginning of your turn, you draw a
card from the top of the card deck. You can use all the cards in your
hands until you run out of it. Your task is to calculate the probability
that you can win in this turn, i.e., can deal at least P damage to your
enemy.
InputThe first line is the number of test cases T (T<=10).
Then
come three positive integers P (P<=1000), N and M (N+M<=20),
representing the enemy’s HP, the number of A-Cards and the number of
B-Cards in the card deck, respectively. Next line come M integers
representing X (0<X<=1000) values for the B-Cards. OutputFor
each test case, output the probability as a reduced fraction (i.e., the
greatest common divisor of the numerator and denominator is 1). If the
answer is zero (one), you should output 0/1 (1/1) instead. Sample Input23 1 21 23 5 101 1 1 1 1 1 1 1 1 1 Sample Output1/346/273 AuthorSYSU Source 2016 Multi-University Training Contest 7
Solution:状压DP.我第一次设计的DP状态是:$\text{dp}[s][i]:$ 当前已经抽得的卡的集合是 $s$, 还剩下 $i$ 次抽卡机会的方案数.但是超内存了……算了一下, 发现这个 $\text{dp}$ 数组确实开不下, 后来想到 $i$ 只和 $s$ 有关, 也就意味着根本不需要 $\text{dp}$ 的第二维.设 $s$ 中有 $x$ 张A-Card, $y$ 张B-Card, 那么剩余的抽卡次数就是 $2x+1-(x+y) = x-y+1$ ，但是这样改过之后就陷入了无尽的超时，这个做法的复杂度是 $O((m+n)2^{m+n})$ ，竟然卡常数……
我第一发 TLE 的 NAIVE 写法:
#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N{};
int T, n, m, p;
int a[N];LL dp[<<];int calc(int s){
int res=;
for(int i=; i<m; i++)
if(s&<<i) res+=a[i];
return res;
}int ones(int s){
int res=;
for(int i=; i<n+m; i++)
res+=bool(s&<<i);
return res;
}int r(int s){
int x=, y=;
for(int i=; i<(n+m); i++)
if(s&<<i){
x++;
if(i>=m) y++;
}
return *y+-x;
}//int main(){ LL f[N]{};
for(int i=; i<N; i++)
f[i]=f[i-]*i; for(cin>>T; T--; ){
cin>>p>>n>>m;
for(int i=; i<m; i++)
cin>>a[i]; int tot=m+n; memset(dp, , sizeof(dp));
dp[]=; for(int s=; s<<<tot; s++)
if(dp[s] &&r(s)>)
for(int j=; j<tot; j++)
if(!(s&<<j))
dp[s|<<j]+=dp[s]; LL res=;
int full=(<<tot)-; for(int s=; s<<<tot; s++)
if(calc(s)>=p && (r(s)== || s==full))
res+=dp[s]*f[tot-ones(s)]; // cout<<res<<endl; LL gcd=__gcd(res, f[tot]);
printf("%lld/%lld\n", res/gcd, f[tot]/gcd);
}
}
最后一发TLE的写法:
#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N{<<};
int T, n, m, p;int a[N], ones[<<];LL dp[<<], f[N]{};inline int calc(int s){
int res=;
for(int i=; i<m; i++)
if(s&<<i) res+=a[i];
return res;
}inline int r(int s){
int res=;
for(int i=; i<m; i++)
res+=bool(s&<<i);
// return 2*(ones[s]-res)+1-ones[s];
return ones[s]-(res<<)+;
}//int main(){ for(int i=; i<<<; i++)
for(int j=; j<; j++)
if(i&<<j) ones[i]++; for(int i=; i<N; i++)
f[i]=f[i-]*i; for(scanf("%d", &T); T--; ){
scanf("%d%d%d", &p, &n, &m);
for(int i=; i<m; i++)
scanf("%d", a+i); // LL res=0; int tot=m+n;
LL res=, full=(<<tot)-; if(calc(full)>=p){ memset(dp, , sizeof(dp));
dp[]=;
for(int s=; s<<<tot; s++)
if(dp[s])
if(r(s)== || s==full){
if(calc(s)>=p) res+=dp[s]*f[tot-ones[s]];
}
else{
for(int j=; j<tot; j++)
if(!(s&<<j))
dp[s|<<j]+=dp[s];
}
} LL gcd=__gcd(res, f[tot]);
printf("%lld/%lld\n", res/gcd, f[tot]/gcd);
}
}
这个写法赛后在题库中AC了, 跑了907ms…
AC的姿势:
#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N{<<};
int T, n, m, p;int a[N], ones[<<];LL dp[<<], f[N]{};inline int calc(int s){
int res=;
for(int i=; i<m; i++)
if(s&<<i) res+=a[i];
return res;
}inline int r(int s){
int res=;
for(int i=; i<m; i++)
res+=bool(s&<<i);
// return 2*(ones[s]-res)+1-ones[s];
return ones[s]-(res<<)+;
}//int main(){ for(int i=; i<<<; i++)
for(int j=; j<; j++)
if(i&<<j) ones[i]++; for(int i=; i<N; i++)
f[i]=f[i-]*i; for(scanf("%d", &T); T--; ){
scanf("%d%d%d", &p, &n, &m); for(int i=; i<m; i++)
scanf("%d", a+i); // LL res=0; int tot=m+n;
LL res=, full=(<<tot)-; if(calc(full)>=p){
memset(dp, , sizeof(dp));
dp[]=;
for(int s=; s<<<tot; s++)
if(dp[s])
if(calc(s)>=p) res+=dp[s]*f[tot-ones[s]];
else if(r(s)>)
for(int j=; j<tot; j++)
if(!(s&<<j))
dp[s|<<j]+=dp[s];
} LL gcd=__gcd(res, f[tot]);
printf("%lld/%lld\n", res/gcd, f[tot]/gcd);
}
}
这个跑了358ms.
Conclusion:
1. 剪枝
2. 预处理 $\text{ones}$ 表, $\mathrm{ones}[i]$ 表示 $i$ 的二进制表达式中$1$的个数.
这题应该还有复杂度更优的做法, 之后再补充.
