POJ2785 4 Values whose Sum is 0

MayFlyyh | 二分答案 | 2018-07-16
> 题意:四列,每列找一个数,得到和为0的序列,有几种不同的方案 一开始想的是dfs。。。后来想的是前两列两两组合将和放入多重集multiset里然后后两列每次查询一下就可以,但还是T了。 原来是把前两列两两组合,后两列两两组合然后每次查询就可以。 看来是set常数太大了。 ``` #include #include #include #include #include #inc... [阅读全文]

POJ 2976 Dropping tests

MayFlyyh | 二分答案 | 2018-07-16
> 给定n个二元组(a,b),扔掉k个二元组,使得剩下的a元素之和与b元素之和的比率最大。题目求的是 max(∑a[i] * x[i] / (b[i] * x[i])) 其中a,b都是一一对应的。 x[i]取0,1 并且 ∑x[i] = n - k。 --- 看到除法,应该是分数规划吧。每次二分以后计算出一串数字对答案的贡献大小,从小到大排序选前n-k个。如果都大于0就说明还可以选择一个更好的分数... [阅读全文]

题解 Luogu P1314 聪明的质监员

MayFlyyh | 二分答案 | 2018-02-24
题解 Luogu P1314 聪明的质监员
题解 Luogu P1314 聪明的质监员 小T 是一名质量监督员,最近负责检验一批矿产的质量。这批矿产共有 n 个矿石,从 1到n 逐一编号,每个矿石都有自己的重量 wi 以及价值vi 。检验矿产的流程是: 1 、给定m 个区间[Li,Ri]; 2 、选出一个参数 W; 3 、对于一个区间[Li,Ri],计算矿石在这个区间上的检验值Yi: 这批矿产... [阅读全文]
Ɣ回顶部