[TJOI2007] 足彩投注

时间:2022-11-13 20:49:58

足彩投注

题目概述

题目背景

了解足球彩票的人可能知道,足球彩票中有一种游戏叫做“胜负彩”,意为猜比赛的胜负。下面是一些与胜负彩有关的术语

注 :每一组有效组合数据。

投 注:彩民以现金购买足球彩票的行为。

单式投注:彩民对于所有球队的比赛成绩均只选择一种预测结果的投注方式。投注的数量(注数)为1。

复式投注:彩民对于某些场次的比赛成绩选择两种以上的预测结果的投注方式。投注的数量为复式投注的组合数。例如,某彩民对一场比赛预测了两个结果(例如,胜平), 另一场比赛预测了三个结果(胜负平),其他比赛都只预测了一种结果,那么注数就是2×3 = 6。这样的一个复式投注,可以看成一个包含六种单式投注的集合。

胜负彩的玩法一般是这样的。彩票机构指定一轮比赛中的若干场,让彩民去猜每场比赛的结果(胜、负、平)。根据彩民猜中比赛的场次,来确定中奖的额度。

题目描述

我们现在考虑一个简化的模型。对于一轮比赛,彩民需要竞猜其中\(n\)场比赛的结果,每场比赛的胜负平都有一个概率\(p(i, r)\)。其中,\(i\)表示第i场比赛,\(r\) = 0, 1, 2,分别表示比赛结果的(主队)负、平、胜。\(p(i, r)\)则表示第\(i\)场比赛、结果为\(r\)的概率。此外,还有一个概率\(q(i, r)\),表示第i场比赛,投注购买结果为\(r\)的概率。

例如,如果q(1,0)=0.5,我们可以知道第一场比赛有50%的投注会买主队输球。我们假设这n场比赛互不相关,即p(i, r)的结果不会受p(j, r’)的影响,q(i, r)的结果也不会受q(j, r’)的影响(r ≠ r’)。

在这个模型里,我们规定,必须猜中全部\(n\)场比赛的结果才能获奖。总奖金为\(M\),由所有获奖的投注平分。因此,对于一个单式投注\(Ri = \{r_{i1}, r_{i2}, …, r{in}\}\),rij表示投注Ri对第j场比赛的预测结果,它的中奖概率为

\[P(R_i)=\prod_{i=1}^n\ p(j,r_{ij})
\]

设投注总数为N,那么中奖的投注总数为:

\[N*Q(R_i)=N*\prod_{i=1}^n\ p(j,r_{ij})
\]

于是,投注Ri所能得到的奖金的期望(平均意义下能够获得的奖金数)就是:

\[\frac {M} {N*Q(R_i)}*P(R_i)
\]

复式投注R中,只要有一个Ri猜对所有比赛结果,即可中奖。因此,复式投注R所能获得的奖金的期望就是:

\[\sum_{R_i\in R}\frac {M} {N*Q(R_i)}*P(R_i)
\]

我们的问题是,给定n场比赛的信息(胜负平的概率和彩民购买三种结果的概率),以及复式投注中可以购买的最大注数U,要求设计一种复式投注的方案,在不超过最大注数(复式投注的注数k ≤ U)的前提下,使得获得奖金的期望最大。

输入格式

第一行四个整数\(n, N, M, U(n, U ≤ 10^4, N, M ≤ 10^9)\)。

以下n行,每行六个实数。第i + 1行的六个实数为\(p(i, 0), p(i, 1), p(i, 2), q(i, 0), q(i, 1),q(i, 2)\),用来描述第i场比赛的相关信息。其中,\(p(i, 0) + p(i, 1) + p(i, 2) = 1, q(i, 0) + q(i, 1) + q(i, 2) = 1, q(i, j) ≠ 0\)。

输出格式

一个实数,表示最大的奖金期望的自然对数

\[ln(Max_{|R|≤U}(\sum_{R_i\in R}\frac {M} {N*Q(R_i)}*P(R_i)))
\]

输出保留3位小数(四舍五入)。

simple.in

1 10 10 1
0.3 0.2 0.5 0.7 0.2 0.1

simple.out

1.609

问题分析

样例分析

说实话,刚看到题时,我蒙了,这怎么多数学公式怎么搞。所以推明白了样例,就大概明白了

拿出我的Casio,\(e^{1.609}=4.9978\),那么没有求对数时就是5,在乘上N除以M就知道\(\frac {P(R_i)} {Q(R_i)}\)是5通过细致细致入微的关差,刚好0.5/0.1=5。

注意p是结果的概率,q是投注的概率

我们看到U=1,则最大注数是1,也就是说都是单注,那事实上在这个样例,我们就要求一个\(Max_{0<=i<=2}\{\frac{p(1,i)}{q(1,i)} \}\),那么这个样例分析,\(U=1\)时看不出来什么有什么的,我们把\(U=2\),再来看这个样例,我们可以把复式投注看成是两个单注,投注赢的奖金是0.3/0.7=0.428,而投注平的奖金为0.2/0.2=1,投注输的奖金为0.5/0.1=5(这怕不是国足)

这时我们的两个注要压平和输。

在\(U=3\)时我们三个注都压。那么对于,一场比赛我们的押注方式共有7种,可事实上,我们只用考虑其中的三种情况,因为由于贪心的思想在注数一定时,我们选择概率奖金数最大(即\(\sum_{e=1}^k\frac{p(i,j)}{q(i,j)}\))的。

于是我们真的懂了这个又臭又长的答案式子,先不考虑ln

\[ans=\prod_{i=1}^n(a(i,k_i))*\frac{M}{N}
\]

其中\(a(i,k_i)\),表示我第i场比赛投\(k_i\)个注的期望的最大奖金概率就是好几个\(\frac{p(i,j)}{q(i,j)}\)

引理

ln(ab)=ln(a)+ln(b,证明吗,幂运算,送的。

考虑到小数乘法的精度损失——其实挺重要的

我们不妨对式子先取ln,成为加法,又快有准

于是式子两边同时取ln有

\[ln(ans)=\sum_{i=1}^nln(a(i,k_i))+ln\frac{M}{N}
\]

我们就有了以下代码来生成a

for(int i=1;i<=n;i++){
scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f);
tmp[0]=a/d;
tmp[1]=b/e;
tmp[2]=c/f;
cha[i][1]=log(max(tmp[1],max(tmp[0],tmp[2])));
cha[i][2]=log(max(tmp[1]+tmp[0],max(tmp[1]+tmp[2],tmp[0]+tmp[2])));
cha[i][3]=log(tmp[1]+tmp[0]+tmp[2]);
}

算法分析

题目是问我们一个最大的期望答案,又不输出方案,那我就是dp

考虑他的状态\(f(i,j)\),,表示在已经押注了i场比赛,还剩j个注是期望奖金概率的最大值取ln,这里我们用了\(log_e(i)\)函数的单增性,这是一个不完全重复背包

我们的所求即为\(f(n,U)\),再来考虑我们的转移方程

\[f(i,j)=\begin{cases}0&i=0 \\Max_{1<=k<=3}\{ f(i-1,j/k)+a[i][k]\}&i≠0\end{cases}
\]

注意这里的j一定不能为0因为注数为零时后面投不下去了

我们要注意的是这个t题的数据有些大,如果开二维的话要10G左右\(qwq\),在计算\(f(i,j)\),是我们只用到了f(i-1,j/k)的数据那么我们可以加上一维数组优化,注意递推是要倒序求(完全的要顺序)。

for(int i=1;i<=n;i++)
for(int j=U;j>=1;j--)
for(int k=1;k<=3;k++)
if(j/k>=1)
data[j]=max(data[j],data[j/k]+cha[i][k]);

于是我就很愉快的卡过了这道题

接下来是完整代码

#include <bits/stdc++.h>
using namespace std;
const int Maxn=10001,MaxU=10001;
double a,b,c,d,e,f,data[MaxU],cha[Maxn][4],tmp[3];;
int n,M,N,U;
int main(){
scanf("%d%d%d%d",&n,&N,&M,&U);
for(int i=1;i<=n;i++){
scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f);
tmp[0]=a/d;
tmp[1]=b/e;
tmp[2]=c/f;
cha[i][1]=log(max(tmp[1],max(tmp[0],tmp[2])));
cha[i][2]=log(max(tmp[1]+tmp[0],max(tmp[1]+tmp[2],tmp[0]+tmp[2])));
cha[i][3]=log(tmp[1]+tmp[0]+tmp[2]);
}
for(int i=1;i<=n;i++)
for(int j=U;j>=1;j--)
for(int k=1;k<=3;k++)
if(j/k>=1)
data[j]=max(data[j],data[j/k]+cha[i][k]);
printf("%.3lf",log(M)-log(N)+data[U]);
return 0;
}

很短,只有24行,这又一次说明了推样例的重要性

回头望月

当我再看我的dp是有些伤感,我是怎么堆出dp转移方程的?每一场比赛,你必须投注,那么,在dp过程中万一一次dp的之不改变即cha<0,怎么办,我是错了吗。

事实上,在思考之后这个问题等价于\(a+b+c=1,d+e+f=1\)

问在\(\frac{a}{d},\frac{b}{e},\frac{c}{f}\)中有最大的一个,两个,三个求和,和是否大于1。

其实是显然的,考虑和谐的情况三个都是1,显然的吗,哈哈

[TJOI2007] 足彩投注的更多相关文章

  1. 世界杯足彩怎么买划算?机器学习AI告诉你答案&lpar;含预测&rpar;

    本文首发于InfoQ公众号头条. 四年一度的世界杯又来了,作为没什么时间看球的码农,跟大家一样,靠买买足彩给自己点看球动力和乐趣, 然而总是买错球队,面对各种赔率也不知道怎么买才划算,足彩是不是碰大运 ...

  2. zw版足彩大数据&报价

    zw版足彩大数据&报价 ::zw增强版足彩大数据,文件名后缀是'.dat' ::文件格式是标准文本格式,逗号分隔 ::zw增强版,在标准版赔率基础上,增加了倒数.比率两组归一化数据 ::zw版 ...

  3. 零起点PYTHON足彩大数据与机器学习实盘分析

    零起点PYTHON足彩大数据与机器学习实盘分析 第1章 足彩与数据分析 1 1.1 “阿尔法狗”与足彩 1 1.2 案例1-1:可怕的英国足球 3 1.3 关于足彩的几个误区 7 1.4 足彩·大事件 ...

  4. c&num; 模拟网易足彩算法

    using System; using System.Collections; using System.Collections.Generic; using System.Linq; using S ...

  5. zw黑天鹅足彩实盘测试5月数据包

    [文件说明] $mx1,是单日数据:$mx9,是日数据和 入选率:2%, 准确度:40% 盈利率:120%左右 目前在测试稳定性 5月1日-6月14日,实盘数据 $mx9,15061409x15061 ...

  6. bzoj AC倒序

    Search GO 说明:输入题号直接进入相应题目,如需搜索含数字的题目,请在关键词前加单引号 Problem ID Title Source AC Submit Y 1000 A+B Problem ...

  7. VB程序破解之API断点&lbrack;bp &lowbar;&lowbar;vbaVarTstEq&rsqb;

    软件名称:风云足彩1.7软件大小:2.1M下载地址:http://free.ys168.com/?zhinengxuanhao软件保护:注册码编写软件:Microsoft Visual Basic 5 ...

  8. 酷睿彩票合买代购网站管理系统 v2016 - 源码下载 有合买功能 有免费版 标准版 高级版

    源码介绍 免费版下载地址 电信 浙江腾佑 网鼎科技 正易网络下载 联通 网鼎联通   标准版联系QQ:1395239152 彩票合买代购网站管理系统公司独立开发,完全拥有软件自主知识产权.具有电脑We ...

  9. 【目录】C&num;搭建足球赛事资料库与预测平台与彩票数据分析目录

    本博客所有文章分类的总目录链接:本博客博文总目录-实时更新 1.彩票数据分析与预测 6.智彩足球技术研究团队成员介绍 5.关于组建“智彩足球技术研究团队”的说明 4.为什么选择玩足球彩票以及玩彩票的心 ...

随机推荐

  1. TJpgDec—轻量级JPEG解码器

    TJpgDec-轻量级JPEG解码器 本文由乌合之众lym瞎编,欢迎转载blog.cnblogs.net/oloroso 下文中解码一词皆由decompression/decompress翻译而来. ...

  2. WPF学习05:2D绘图 使用Transform进行控件变形

    在WPF学习04:2D绘图 使用Shape绘基本图形中,我们了解了如何绘制基本的图形. 这一次,我们进一步,研究如何将图形变形. 例子 一个三角形,经Transform形成组合图形: XAML代码: ...

  3. uva 12304

    题意:要求解答6个关于圆的问题. 1.给出三角形坐标求外接圆 2.给出三角形坐标求内切圆 3.给出一个圆心和半径已知的圆,求过点(x,y)的所有和这个圆相切的直线 4.求所有和已知直线相切的过定点(x ...

  4. PCIE&lowbar;DMA实例三:Xilinx 7系列&lpar;KC705&sol;VC709&rpar;FPGA的EDK仿真

    一:前言 好久没写博客了,前段时间有个朋友加微信请教关于PCIe的一些学习方法.本人也不是专家,只是略知一些皮毛.对于大家反馈的问题未必能一一解答,但一定知无不言.以后我会常来博客园看看,大家可以把问 ...

  5. 第九周博客作业 &lt&semi;西北师范大学&vert; 周安伟&gt&semi;

    第九周助教作业 助教博客链接https://home.cnblogs.com/u/zaw-315/ 作业要求博客链接https://www.cnblogs.com/nwnu-daizh/p/10726 ...

  6. Python内置模块之序列化模块

    序列化模块 json dumps loads dump load pickle dumps loads dump load shelve json 1: dumps/loads import json ...

  7. dedecms 5&period;7sp2 20170405运行PHP7&period;1的大坑(dedecms PHP7&period;1)

    今天一个小站用了dedecms最新版,也就是5.7SP220170405版,(见下图) 点进去到下载页面下载,用了UTF8版本的.(见下图) 下载完成后,自己新开发了一套模板,听说PHP7.1性能提升 ...

  8. SGU---103 最短路变形

    题目链接: https://cn.vjudge.net/problem/SGU-103#author=ECUST_FZL 题目大意: Dingiville 城市的交通规则非常奇怪,城市公路通过路口相连 ...

  9. Windows App开发之集成设置、帮助、搜索和共享

    应用设置和应用帮助 "设置"合约 上一节中我们学习了怎样将应用设置保存到本地.这样的方式是通过在App内加入设置选项,这里另一种方式. 微软将其称为"设置"合约 ...

  10. HTML 学习笔记 JQuery(DOM 操作3)

    设置和获取HTML 文本 和 值 1.html()方法 类似于JavaScript中的innerHTML属性,可以用来读取或者设置某个元素中的HTML内容 例子 <html> <he ...