CodeForces 54C-First Digit Law(数位,概率dp)

时间:2022-09-05 16:20:47

题意:

给你n个区间,在每个区间里各取一个数(随机取),求这n个数中超过K%的数是首位为1数的概率

分析:

dp[i][j]取前i个数,有j个是首位为1的数的概率

易知,dp[i][j]=dp[i-1][j]*(1-p[i])+dp[i-1][j-1]*p[i];

现在关键是求p[i],第i个区间首位为1的数出现的概率,用数位统计一下即可

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <complex>
#include <cassert>
#include <utility>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
#define lson l,m,rt<<1
#define pi acos(-1.0)
#define rson m+1,r,rt<<11
#define All 1,N,1
#define read freopen("in.txt", "r", stdin)
const ll INFll = 0x3f3f3f3f3f3f3f3fLL;
const int INF= 0x7ffffff;
const int mod = ;
ll sum[],a[];
double dp[][],p[];
int bit[],n,k;
void init(){
sum[]=;
for(int i=;i<=;++i)
sum[i]=sum[i-]*;
}
ll countsum(int l){
ll total=;
for(int i=;i<=l;++i)
total+=sum[i];
return total;
}
//统计首位为1数的数量
ll countone(ll x){
if(x==)return ;
init();
int len=;
while(x){
bit[++len]=x%;
x/=;
}
if(bit[len]>){
return countsum(len-);
}
else{
ll tmp=countsum(len-);
a[]=;
for(int i=;i<=len-;++i)
a[i]=a[i-]+bit[i]*sum[i-];
tmp+=a[len-]+;
return tmp;
}
}
int main()
{
ll l,r;
while(~scanf("%d",&n)){
for(int i=;i<=n;++i){
scanf("%I64d%I64d",&l,&r);
ll tmp=countone(r)-countone(l-);
//cout<<tmp<<endl;
p[i]=1.0*tmp/(r-l+);
//cout<<p[i]<<endl;
}
dp[][]=p[];
dp[][]=1.0-p[];
for(int i=;i<=n;++i)
for(int j=;j<=i;++j){
dp[i][j]+=dp[i-][j]*(1.0-p[i]);
if(j>)
dp[i][j]+=dp[i-][j-]*p[i];
}
scanf("%d",&k);
double ans=0.0;
for(int j=;j<=n;++j)
if(j>=(1.0*n*k/))
ans+=dp[n][j];
printf("%.15lf\n",ans);
}
return ;
}

CodeForces 54C-First Digit Law(数位,概率dp)的更多相关文章

  1. Codeforces 678E&period; Another Sith Tournament(概率DP,状压)

    Codeforces 678E. Another Sith Tournament 题意: n(n<=18)个人打擂台赛,给定任意两人对决的胜负概率,比赛规则:可指定一人作为最开始的擂主,每次可指 ...

  2. Codeforces B&period; Bad Luck Island(概率dp)

    题目描述: Bad Luck Island time limit per test 2 seconds memory limit per test 256 megabytes input standa ...

  3. Codeforces 148D Bag of mice:概率dp 记忆化搜索

    题目链接:http://codeforces.com/problemset/problem/148/D 题意: 一个袋子中有w只白老鼠,b只黑老鼠. 公主和龙轮流从袋子里随机抓一只老鼠出来,不放回,公 ...

  4. Codeforces 167B Wizards and Huge Prize&lpar;概率dp&rpar;

    题意: n个人,开始有一个容量为k得背包,击败一个人背包可以获得一定容量或得到一个财富(放入背包内),给出击败每个人的概率,求至少击败l个人,且背包容量大于获得的总财富值的概率 分析: 状态好确定,d ...

  5. Codeforces 601C Kleof&&num;225&semi;š and the n-thlon 概率dp

    Kleofáš and the n-thlon 我们可以用dp算出比当前这个人得分少的概率, 然后人数乘概率就好啦. dp[ i ][ j ]表示进行了 i 轮 得分为 j 的概率, 因为每个人都是独 ...

  6. Codeforces 280C Game on tree【概率DP】

    Codeforces 280C Game on tree LINK 题目大意:给你一棵树,1号节点是根,每次等概率选择没有被染黑的一个节点染黑其所有子树中的节点,问染黑所有节点的期望次数 #inclu ...

  7. codeforces&num;1139D&period; Steps to One (概率dp&plus;莫比乌斯反演)

    题目链接: http://codeforces.com/contest/1139/problem/D 题意: 在$1$到$m$中选择一个数,加入到一个初始为空的序列中,当序列的$gcd$和为$1$时, ...

  8. 2018&period;12&period;12 codeforces 931E&period; Game with String(概率dp)

    传送门 感觉这题难点在读懂题. 题目简述:给你一个字符串s,设将其向左平移k个单位之后的字符串为t,现在告诉你t的第一个字符,然后你可以另外得知t的任意一个字符,求用最优策略猜对k的概率. 解析: 预 ...

  9. CodeForces 55D &quot&semi;Beautiful numbers&quot&semi;(数位DP&plus;离散化处理)

    传送门 参考资料: [1]:CodeForces 55D Beautiful numbers(数位dp&&离散化) 我的理解: 起初,我先定义一个三维数组 dp[ i ][ j ][ ...

  10. Codeforces &num;548 &lpar;Div2&rpar; - D&period;Steps to One(概率dp&plus;数论)

    Problem   Codeforces #548 (Div2) - D.Steps to One Time Limit: 2000 mSec Problem Description Input Th ...

随机推荐

  1. ModelDataExchange - Import

    ModelDataExchange - Import eryar@163.com Abstract. The ModelDataExchange import utility enables the ...

  2. LoopBar – Tap酒吧与无限滚动

    相约 LoopBar – 标签栏与无限滚动为Android由Cleveroad 在Cleveroad我们最近认识到通过使用任何一个应用程序类别的导航,导航面板是很无聊和琐碎.这就是为什么我们的设计师的 ...

  3. 锋利的JQuery-Jquery中DOM操作

    <html> <head> <meta http-equiv="Content-Type" content="text/html; char ...

  4. tomcat 192&period;168&period;1&period;110?不烦吗?

    最近做一个在线播放器,因为要用到网络服务器做在线播放,又不想直接在本地用tomcat做实验,因为没有真实感. so,手边两台电脑,同时连在局域网. 客户端,笔记本,ip1:192.168.1.101 ...

  5. java多态加深

    当超类对象引用变量引用子类对象时,被引用对象的类型而不是引用变量的类型决定了调用谁的成员方法,但是这个被调用的方法必须是在超类中定义过的,也就是说被子类覆盖的方法. public class Dtai ...

  6. JavaScript面向对象&lpar;一&rpar;——JS OOP基础与JS 中This指向详解

      前  言 JRedu 学过程序语言的都知道,我们的程序语言进化是从"面向机器".到"面向过程".再到"面向对象"一步步的发展而来.类似于 ...

  7. Python爬虫之使用celery加速爬虫

      celery是一个基于分布式消息传输的异步任务队列,它专注于实时处理,同时也支持任务调度.关于celery的更多介绍及例子,笔者可以参考文章Python之celery的简介与使用.   本文将介绍 ...

  8. 《团队作业第一周》五小福团队作业——UNO

    <团队作业第一周>团队作业--UNO 一.团队展示 队员学号 队名:五小福 (真是个红红火火恍恍惚惚的队名)> 拟作的团队项目描述 基于安卓开发的有趣味性的UNO纸牌小游戏 队员风采 ...

  9. vb&period;net 變量及数据类型

    Dim过程级变量 Private模块级变量 Public全局变量 Integer(整型) Long(长整型) Single(單精度浮點型) Double(双精度浮点型) Decimal(十进制型) S ...

  10. RHEL6&period;x查看网卡槽位对应设备文件及路径

    先查看网卡mac地址,由于我的服务器做了mac地址绑定,所以会有相同的hwaddr地址,请忽略. [root@node-0a0a05d3- net]# ifconfig eth0 | grep HWa ...