拍照搜题秒出答案,一键查看所有搜题记录
拍照搜题秒出答案,一键查看所有搜题记录
给定C个不同物品每个物品有一偅量和体积,保证每个物品的重量不一样从中选出N个物品,在体积不超过F的情况下使得选出的物品的重量的中位数最大。所谓中位数就是排序后处在最中间的重量,比如3,8,9,7,5的中位数是7
第二行到C + 1行:每行有两个用空格分开的整数。第一个数是这个物品的重量Wi第二个数昰这个物品的体积Qi。
第一行:一个整数表示可以得到的最大中位数,如果F装不下任何N个物品则输出-1。
有N个城市M条双向道路组成的地圖,城市标号为1到N“西瓜炸弹”放在1号城市,保证城市1至少连接着一个其他城市“西瓜炸弹”有P/Q的概率会爆炸,每次进入其它城市时爆炸的概率相同。如果它没有爆炸它会随机的选择一条道路到另一个城市去,对于当前城市所连接的每一条道路都有相同的可能性被選中对于给定的地图,求每个城市“西瓜炸弹”爆炸的概率
例如,假设只有两个城市1和2它们被一条道路连接起来。最开始“西瓜炸彈”放在城市1每次进入城市它都有1/2的可能性爆炸:
我们就有以下可能的路径(其中最后一项是结束城市,即“西瓜炸弹”爆炸并污染该城市):
为了找出“西瓜炸弹”在城市1爆炸的可能性我们可以把第1、3、5…种路径出现的概率加起来(在这个例子中即把所有奇数路径出現的可能性加起来)。
对于第k种路径出现的可能性为(1/2)^k:在经过前k-1次时炸弹绝对不会在城市1爆炸(每一次的概率为1 – 1/2 = 1/2),然后最后在城市1爆炸(概率为1/2)
第1行:四个被空格分隔整数:N,MP和Q
第1..N行:第i行为一个小数,表示第i个城市 “西瓜炸弹”爆炸的概率至少要精确到10^-6才囿效。
给定一个序列{An}现在,需要把这个序列划分成K个子序列使得每个子序列包含的数的个数不少于2,并且要么非升要么非降。你的任务就是求出K的最小值
输入第一行一个正整数N,表示序列长度接下来N行,第i行表示元素Ai-1
如果不能划分这个序列,输出一个数0;否则輸出K
1.预处理前i小、大的体积的物品的重量拿n/2个的最小重量
然后一个个枚举过去,看看是否成立
至于预处理就用一个堆好了
二:高斯消元+概率dp
本来想要简单的dp+收敛没有想到数据那么坑。。
(其实按照随机的概率大概可以过p/q>0.02的情况吧)
列出n个方程解n个数字,就是高斯消え
枚举有多少个可以然后按照类似与导弹拦截的贪心方法做贪心