「JSOI2015」非诚勿扰
2024-08-30 15:31:32
「JSOI2015」非诚勿扰
我们首先考虑一名女性选中她列表里第 \(x\) 名男性的概率(假设她列表里共有 \(s\) 名男性):
\[P = p \times (1 - p) ^ {x - 1} + p \times (1 - p) ^ {s + x - 1} + p \times (1 - p) ^ {2s + x - 1} + \cdots + p \times (1 - p) ^ {ns + x - 1}
\]
\]
根据等比数列求和公式以及极限的相关计算,不难求出:
\[P = \frac{p \times (1 - p) ^ {x - 1}}{1 - (1 - p) ^ s}
\]
\]
然后我们发现题目要求的是类似于逆序对的东西,但是我们要清楚这个期望怎么算。
由于期望具有可加性,所以我们就可以对每 \(1\) 的贡献都算一遍期望,这个是很好算的,然后我们发现还可以用树状数组维护,其实就是相当于把可以造成贡献的部分提了个公因式然后对于后面那一大堆用前缀和来搞。
还有就是这题好像要开 long double
才行。
参考代码:
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <cmath>
#define rg register
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
using namespace std;
template < class T > inline void read(T& s) {
s = 0; int f = 0; char c = getchar();
while ('0' > c || c > '9') f |= c == '-', c = getchar();
while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();
s = f ? -s : s;
}
const int _ = 5e5 + 5;
int n, m; long double p;
vector < int > vec[_];
struct BIT {
long double tr[_];
inline void update(int x, long double v) { for (rg int i = x; i <= m; i += i & -i) tr[i] += v; }
inline long double query(int x) { long double res = 0.0; for (rg int i = x; i >= 1; i -= i & -i) res += tr[i]; return res; }
} tr;
int main() {
#ifndef ONLINE_JUDGE
file("cpp");
#endif
read(n), read(m), scanf("%Lf", &p);
for (rg int u, v, i = 1; i <= m; ++i) read(u), read(v), vec[u].push_back(v);
for (rg int i = 1; i <= n; ++i) sort(vec[i].begin(), vec[i].end());
long double ans = 0.0, P;
for (rg int i = 1; i <= n; ++i) {
P = p / (1.0 - pow(1.0 - p, (long double) vec[i].size()));
for (rg int j = 0; j < vec[i].size(); ++j, P *= (long double) 1.0 - p)
ans += P * (tr.query(m) - tr.query(vec[i][j])), tr.update(vec[i][j], P);
}
printf("%.2Lf\n", ans);
return 0;
}
最新文章
- mysql 安装
- 如何从投票的网站的管理后台导出已投票的邀请码数据至Excel,并且稍修改,再导入到现场抽奖软件中?
- Spring学习笔记之三----基于Annotation的Spring IOC配置
- UE4 使用UGM制作血条
- vs2008编译boost
- 《MFC游戏开发》笔记七 游戏特效的实现(一):背景滚动
- Cocos开发中性能优化工具介绍之Visual Studio内存泄漏检测工具——Visual Leak Detector
- VS的一部分快捷键
- CSDN挑战编程——《数学问题》
- 【Ecstore2.0】导出问题解决(未导出或导出文件为0字节)
- MySQL数据库mysqlcheck的使用方法
- Smarty属性
- MVC常见的控制器,接口,数据层之间的操作
- 编写一条sql命令,sql删除没有中文的表
- ajax提交的javascript代码
- SSH框架的多表查询(方法二)增删查改
- 【Java系列】Eclipse与Tomcat
- Bootstrap使用-1
- Android 简单登陆 涉及 Button CheckBox TextView EditText简单应用
- EntityFramework4.5使用Expression类创建动态查询及动态查询导航属性
热门文章
- Web服务器项目详解 - 00 项目概述
- AntDesign(React)学习-13 Warning XX should not be prefixed with namespace XXX
- git&;github 的使用
- 用户注册(php)login(非美化)
- 2019牛客多校第五场C generator 2 hash,bsgs模板
- java-日期取特定值
- dp--B - Hard problem
- 第一个Mybatis项目
- c# DPI SCale
- 题解【洛谷P2513/CJOJ1345】[HAOI2009]逆序对数列