Throwing Dice LightOJ - 1064 || (勉强能用的)分数类
2024-09-06 12:41:58
方法:
设ans[i][j]表示i个骰子点数恰好为j的概率。那么ans[1][1]到ans[1][6]都为1/6。
显然,$ans[i][j]=sum\{ans[i-1][j-k]\}(1<=k<=6,j>k)$
n和x上限很小,直接处理出所有点数恰好为某个值的结果,然后再做一遍类似前缀和的东西处理出所有点数大于等于某个值的结果。这里答案需要分数,于是乱写了一个分数结构体。
分数运算(没有优化的):
初始化空的分数:分子为0,分母为1
加法:先通分,然后加分子,然后约分
乘法:先互相约分,然后分子分母分别相乘
错误次数:1次
错误原因:由于把前缀和的范围限制与原数据的范围限制搞混,66行>=0写成>=i,导致WA
#include<cstdio>
typedef long long LL;
LL gcd(LL a,LL b)
{
LL t;
while(b!=)
{
t=a;
a=b;
b=t%b;
}
return a;
}
struct X
{
LL a,b;
X()
{
a=;b=;
}
X(int x,int y)
{
a=x;b=y;
}
X operator+(const X& c)
{
X ans;
LL tmp=gcd(b,c.b);
ans.b=b/tmp*c.b;
ans.a=ans.b/b*a+ans.b/c.b*c.a;
tmp=gcd(ans.a,ans.b);
ans.a/=tmp;
ans.b/=tmp;
return ans;
}
X operator*(const X& c)
{
LL tmp1=gcd(a,c.b),tmp2=gcd(b,c.a);
X ans;
ans.a=a/tmp1*c.a/tmp2;
ans.b=b/tmp2*c.b/tmp1;
return ans;
}
void print()
{
if(b==)
printf("%lld",a);
else
printf("%lld/%lld",a,b);
}
}ans[][],ans2[][];
LL T,TT,n,x;
int main()
{
int i,j,k;
for(i=;i<=;i++)
ans[][i]=(X){,};
for(i=;i<=;i++)
for(j=i;j<=*i;j++)
for(k=;k<=;k++)
if(j-k>)
ans[i][j]=ans[i][j]+ans[i-][j-k]*ans[][];//ans[1][1]就是1/6
for(i=;i<=;i++)
{
ans2[i][*i]=ans[i][*i];
for(j=*i-;j>=;j--)
ans2[i][j]=ans2[i][j+]+ans[i][j];
}
scanf("%lld",&T);
for(TT=;TT<=T;TT++)
{
scanf("%lld%lld",&n,&x);
printf("Case %lld: ",TT);
ans2[n][x].print();
puts("");
}
return ;
}
最新文章
- C#基础:值类型、引用类型与ref关键字
- Nancy 学习-视图引擎 继续跨平台
- discuz内置常用CSS代码分析
- buildroot linux filesystem 初探
- Android Touch事件原理加实例分析
- Android中Touch事件分析--解决HorizontalScrollView滑动和按钮事件触发问题
- Kohana框架ORM类的基本使用
- Domj4读取xml文件
- 优酷播放器demo
- [置顶] Objective-C ,ios,iphone开发基础:ios数据库(The SQLite Database),使用终端进行简单的数据库操作
- poj 1456 Supermarket(并查集维护区间)
- 快速上手UIBezierPath
- Hive函数:GROUPING SETS,GROUPING__ID,CUBE,ROLLUP
- lombok @EqualsAndHashCode 注解讲解
- 记一次eureka客户端注册失败的问题
- JavaScript碎片—函数闭包(模拟面向对象)
- Learning Spread-out Local Feature Descriptors
- 归并排序(Java实现)
- yii动态配置International(Yii::t())
- Spring Cloud(2)A Eureka server端 服务注册建立
热门文章
- linux 输入子系统(3) button platform driver
- appium第一个安卓自动化工程
- php浏览次数累加代码
- 浅谈JavaScript的事件(事件委托)
- 每天一个JavaScript实例-apply和call的使用方法
- 自定义UISearchDisplayController的“No Results“标签和”Cancel“按钮
- iOS 各种编译错误汇总
- java zip压缩优化版 解决压缩后文件一直被占用无法删除
- Spring中的AOP(学习笔记)
- Understanding When to use RabbitMQ or Apache Kafka Kafka RabbitMQ 性能对比