字节8/21笔试最后一题骰子
最近经常水leetcode啥的，也来水下字节那个笔试最后一个吧，听群里说字节笔试挺难的，所以水了一下这场的第四个。
大体题意就是有两个人搞筛子，一个n个筛子一个m个筛子，每个筛子有个面数，问全仍完加起来的大的改了是多少。
乍一看以为是个概率dp哈，其实不是，由于数据范围很小，直接存下方案数就行，总方案数就是a仍各种数的方案数 * b仍各种方案数的个数
dp[i][j]表示 仍前i个筛子得到j的方案数，
总答案就是a的j大于b的j的总数 / 所有总数
所以其实就是个暴力统计算概率~ dp求一下方案数就可以
#include <bits/stdc++.h>
using namespace std;
double a[12345];
double b[12345];
double dpa[32][12345];
double dpb[32][12345];
// 1 3 8 2 3 4
int main() {
int n, m;
cin >> n >> m;
double sum1 = 0, sum2 = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum1 += a[i];
}
for (int i = 1; i <= m; i++) {
cin >> b[i];
sum2 += b[i];
}
dpa[0][0] = dpb[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = sum2; j >= 1; j--) {
// 倒着转移不然算多了
for (int k = 1; k <= a[i]; k++) {
if (j >= k) {
dpa[i][j] += dpa[i - 1][j - k];
}
}
}
}
for (int i = 1; i <= m; i++) {
for (int j = sum2; j >= 1; j--) {
for (int k = 1; k <= b[i]; k++) {
if (j >= k) {
dpb[i][j] += dpb[i - 1][j - k];
}
}
}
}
double ans1 = 0, ans2 = 0;
for (int i = 1; i <= sum1; i++)
ans1+= dpa[n][i];
for (int i = 1; i <= sum2; i++)
ans2+= dpb[m][i];
double ans = ans1 * ans2;
double res = 0;
for (int i = 1; i <= sum1; i++) {
for (int j = 1 - 1; j <= sum2; j++) {
if (j >= i) break;
// 就是a 比 b 大的总方案数
res += dpa[(int)n][i] * dpb[(int)m][j];
}
}
printf("%.3lf\n", res / ans);
return 0;
}
