# 二分 #
  • AcWing 340. 通信线路

    在郊区有 N 座通信基站,P 条 双向 电缆,第 i 条电缆连接基站 \(A_i\) 和 \(B_i\)。 特别地,1 号基站是通信公司的总站,N 号基站位于一座农场中。 现在,农场主希望对通信线路进行升级,其中升级第 i 条电...

    刷题记录
  • 数的范围

    题目 给定一个按照升序排列的长度为n的整数数组,以及 q 个查询。 对于每个查询,返回一个元素k的起始位置和终止位置(位置从0开始计数)。 如果数组中不存在该元素,则返回“-1 -1”。 输入格式 第一行包含整数n和q...

    刷题记录
  • Garland(UVA1555)

    题意 有 n 个灯笼,第一个的高度是 A,最后一个是 B,灯笼的关系给出,并要求每个灯笼的高度是非负数的,求最低的 B 。 分析 二分,首先我们将公式变换一下得到 H[i]=2*H[i-1]+2-H[i-2],然后我们知道...

    刷题记录
  • Telephone Lines(POJ3662)

    题意 一共有N个电线杆,有P对电线杆是可以连接的,用几条线连接在一起的电线杆之间都可相互通信,现在想要使得电线杆1和电线杆N能相互通信,并且电线公司提出K条电线是可以免费使用的,当使用电线的数量超过K条,超出的电线要收费,收的总费用为...

    刷题记录
  • Showstopper(POJ3484)

    题意 给出了多个等差数列的首项X_i,末项Y_i和公差Z_i,我们现在可以想象成把这些等差数列里的所有不同的数组成一个集合S,需要寻找集合S里的一个元素,这个元素在所有这些等差数列中总共出现过奇数次。 分析 将集合 S 中...

    刷题记录
  • Matrix(POJ3685)

    题意 题目中给出了一个 N*N 阶的矩阵,矩阵中第 i 行第 j 列的元素Aij的值等于i * i + j * j + 100000 * i - 100000 * j + i * j,要找到这个矩阵元素中第 k 小的元素。 分析...

    刷题记录
  • Median(POJ3579)

    题意 给你 n 个数,任意两个数之间的差共有 m=(n-1)*n/2 种然后让你输出这些数中间的那一个,规则为:若 m为 奇数,中间的那一个为第(m+1)/2 小的数, 若 m 为为偶数,中间那个数指的是第 m/2 小的数。 分...

    刷题记录
  • K Best(POJ3111)

    题意 给出 N , K,代表有 N 颗宝石,要求从中选择 K 颗,使等式   的 S 值达到最大,输出应该选择哪几颗宝石。 分析 最大化平均值 AC代码 #include <cstdio> #in...

    刷题记录
  • Dropping tests(POJ2976)

    题意 在一场测试中有 n 项,每一项都有 bi 个题目,答对 ai 个。总的答对率就是(a1+a2+....+an-1)/(b1+b2+....+bn-1),现在可以让你从这 n 项测验中抽出 k 门不计入总的答题中,问最高答对率会是...

    刷题记录
  • Cow Acrobats(POJ3045)

    题目 n 头牛叠起来,每头牛的重量 w 和力量 s,每头牛都面临的风险值为自己上面的牛的总重减去自己的力量,问这 n 头牛叠起来面临的最小危险值的最大值是多少? 分析 对于第 i 头牛,不妨设它自己与其上部牛的体重总和为...

    刷题记录