ACM

zoj 3329 One Person Game(带环概率dp,转化)

zoj 3329 One Person Game(带环概率dp,转化)
题目意思是你现在有三个骰子,die1,die2,die3,如果抛出die1=a,die2=b,die3=c,那么你你的积分清零,否则你的积分加上这个三个骰子之和。求你的积分大于n的期望?这个题比较有意思,就算你想到了递推式也很难想到转化,哈哈。首先我们假定当前积分是i,那么有递推式:E[i] = ∑(E[i+k]*p[k]) + E[0]*p[0] + 1     &... 继续阅读 »
ACM

POJ 3744 Scout YYF I(概率dp,递推,矩阵快速幂)

POJ 3744 Scout YYF I(概率dp,递推,矩阵快速幂)
题意:YYF要深入敌后,现在要经过一条地雷路,这些路上有很多的地雷(这些地雷都是长在地图上的,看得到,不用怕)。然后YYF有p的概率走一步,有1-p的概率跳两步。现在问你他安全走过雷区的概率是多少?自己先在草稿纸上画画就能推出递推式,比如我是这样画的:x ox _ ox _ _ o。。。。。。(注意,题目给的数据必定无序,所以先排序)x代表安全起点,o代表地雷,然后手动模拟概率就可以得出递推式:d... 继续阅读 »
ACM

POJ 2096 Collecting Bugs(概率dp)

POJ 2096 	Collecting Bugs(概率dp)
题目意思是有个人喜欢收集bug,然后现在的收集规则是这样的:一个软件的bug分为n类,软件还有s种子组件,找到一个bug有可能是n种分类中的一种并且还属于s种子组件里面的其中一个组件。问题是求:找出的bug有n种分类并且还存在于s种子组件里面。我们可以定义下一次找到bug的情况的四种概率(i为分类的变量,j为子组件的变量):下一个bug属于已经找到的i种分类,j种子组件 :p1= i*j/n*s;... 继续阅读 »
ACM

HYSBZ 1452 颜色计数(二维树状数组)

HYSBZ 1452 颜色计数(二维树状数组)
对每个颜色分别建立树状数组即可。其他的都是模板思想了。然后,树状数组嘛,很神奇,自己搜索一下资料看看,仔细想想就理解了代码:StatusAcceptedTime4768msMemory42960kBLength1365LangC++#include <iostream> #include <cstdio> #include <algo... 继续阅读 »
ACM

HDU 1085 Holding Bin-Laden Captive!(数学,母函数)

HDU 1085	Holding Bin-Laden Captive!(数学,母函数)
给出你定值硬币的数量,问你这些硬币不能组成的最小价值是多少。这个题嘛,乱搞,dp,找规律都行,但是学长说这个用母函数做。。。乱搞代码:StatusAcceptedMemory1560kBLength486LangG++#include <iostream> #include <cstdio> using namespace std... 继续阅读 »
ACM

HDU - 5776 sum(前缀和、抽屉原理)

HDU - 5776 sum(前缀和、抽屉原理)
题目的意思是,给你一段序列,问你他的一段子序列能否被一个数整除。我们可以来看一个序列:a0,a1,a2......am......an......aq我们假设从a0到am的和模x为1,如果a0到an的和模x也为1,那么从am+1到an的和就能被x整除了。代码:StatusAcceptedTime62msMemory2348kBLength533LangG++#include <io... 继续阅读 »
ACM

UVALive - 5009 Error Curves(三分)

UVALive - 5009 Error Curves(三分)
题目的意思很难看懂啊,不过画下图就知道了,x轴上每个点都有对应的抛物线的值,任取一个点,把这个点上所有的抛物线的值计算出来取最大值,然后在这些最大值里面取他们的最小值,这样应该能理解了吧。由于抛物线的单调特性可以利用三分来做。代码:StatusAcceptedTime246msLength869LangC++11 5.3.0#include <iostream> #incl... 继续阅读 »
ACM

BZOJ 1293 生日礼物(尺取)

BZOJ 1293 生日礼物(尺取)
录入信息,按照位置排个序,然后尺取法进行标记统计处理即可。代码:tatusAcceptedTime1804msMemory13012kBLength913LangC++#include <iostream> #include <cstdio> #include <algorithm> #include <mem... 继续阅读 »
ACM

BZOJ 1202 狡猾的商人(乱搞||带权并查集)

BZOJ 1202 狡猾的商人(乱搞||带权并查集)
这个题嘛,说是用带权并查集,额,可是还没想通,所以先把乱搞的方法写下。乱搞的方法就是,知道x-y,y-z,x-z的值,我们只要先排序,然后把x-z的值减去x-y的值,就可以得到y-z的值,然后验证与原来的值是否相等即可。代码:StatusAcceptedTime524msMemory1388kBLength1878LangC++#include <iostream> #in... 继续阅读 »
ACM

POJ 1845 Sumdiv(唯一分解+递归二分+快速幂+大数模)

POJ 1845 	Sumdiv(唯一分解+递归二分+快速幂+大数模)
题目意思是,给出一个底数和他的幂,请计算这个数的所有因素之和。下面对四个知识点进行梳理:1、唯一分解定理:定义:任何一个大于1的自然数N,如果N不为质数,那么N可以唯一分解成有限个质数的乘积A=p1^a1 * p2^a2 * p3^a3 *...* pn^an,这里p1<p2<p3......<pn均为质数,其中指数ai是正整数。这样的分解称为N的标准分解式。由于 A... 继续阅读 »