Codeforces 229E Gifts 概率dp (看题解)
2024-10-18 20:22:54
感觉题解写的就是坨不知道什么东西。。
看得这个题解。
#include<bits/stdc++.h>
#define LL long long
#define LD long double
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long using namespace std; const int N = + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-;
const double PI = acos(-); template<class T, class S> inline void add(T& a, S b) {a += b; if(a >= mod) a -= mod;}
template<class T, class S> inline void sub(T& a, S b) {a -= b; if(a < ) a += mod;}
template<class T, class S> inline bool chkmax(T& a, S b) {return a < b ? a = b, true : false;}
template<class T, class S> inline bool chkmin(T& a, S b) {return a > b ? a = b, true : false;} int n, m, num1, num2;
int cnt[N];
int need[N];
bool have[N];
vector<PII> vc; double dp[N][N]; double sum[N]; double calc(int n, int m) {
return exp(sum[m] + sum[n - m] - sum[n]);
} int main() {
for(int i = ; i < N; i++) sum[i] = sum[i - ] + log(i);
scanf("%d%d", &n, &m);
for(int i = ; i <= m; i++) {
scanf("%d", &cnt[i]);
for(int j = ; j <= cnt[i]; j++) {
int x; scanf("%d", &x);
vc.push_back(mk(x, i));
}
}
sort(vc.rbegin(), vc.rend());
int val = vc[n - ].fi;
num1 = n; num2 = ;
if(SZ(vc) == n || vc[n].fi != val) val = -;
if(~val) {
for(auto& t : vc) {
if(t.fi > val) need[t.se]++, num1--;
else if(t.fi == val) have[t.se] = true, num2++;
else break;
}
} else {
for(int i = ; i < n; i++) need[vc[i].se]++;
num1 = , num2 = ;
}
dp[][] = 1.0;
for(int i = ; i <= m; i++) {
for(int j = ; j <= i && j <= num1; j++) {
if(!have[i]) {
dp[i][j] = dp[i - ][j] * calc(cnt[i], need[i]);
}
else {
if(j) dp[i][j] = dp[i - ][j] * calc(cnt[i], need[i]) + dp[i - ][j - ] * calc(cnt[i], need[i] + );
else dp[i][j] = dp[i - ][j] * calc(cnt[i], need[i]);
}
}
}
printf("%.15f\n", dp[m][num1] * calc(num2, num1));
return ;
} /*
*/
最新文章
- linux格式批量转换为dos格式
- UVA 11766 Racing Car Computer --DP
- hot code replace
- 定义页面的Dispose方法:[before]unload事件启示录
- PHP_CURL请求教程, 内含简单粗暴curl
- 共享参数ContentProvider 类与数据库绑定,如何通过共享参数测试类,测试数据库的增删改查功能
- 转 : ANT 调用sqlplus 客户端
- Invalid character found in the request target. The valid characters are defined in RFC 7230 and RFC
- php list()函数
- 了解unix操作系统发展阶段
- python爬取网页的通用代码框架
- 弱引用(WeakReference)
- shell(3)-mysql主从监控shell
- cf983E NN Country (倍增+dfs序+树状数组)
- __Linux__文件和目录
- 2017年蓝桥杯省赛A组c++第5题(递归算法填空)
- hadoop-1(单机模式配置)
- idea项目左边栏只能看到文件看不到项目结构
- Hibernate5笔记5--关联关系映射
- 【Nginx】ngx_event_core_module模块