今日概览

今天记录了 3 道题。

题号	题目	状态	语言	标签
P1001	A+B Problem	AC	Python	-
P1024	[NOIP 2001 提高组] 一元三次方程求解	AC	Python	二分
P2678	[NOIP 2015 提高组] 跳石头	AC	Python	二分、贪心

刷题记录

P1001 A+B Problem

• 题目：A+B Problem
• 状态：AC
• 语言：Python

题目原文

题目描述

输入两个整数 $a,b$，输出它们的和。 注意： 1. Pascal 使用 integer 会爆掉哦！ 2. 有负数哦！ 3. C/C++ 的 main 函数必须是 int 类型。程序正常结束时的返回值必须是 0。这不仅对洛谷其他题目有效，而且也是 NOIP/CSP/NOI 比赛的要求！ 好吧，同志们，我们就从这一题开始，向着大牛的路进发。 > 任何一个伟大的思想，都有一个微不足道的开始。

输入格式

输入两个以空格分隔的整数 $a,b$。

输出格式

输出一个整数，表示 $a+b$。

说明/提示

数据范围 对于所有测试数据，$-{10}^9 \le a,b \le {10}^9$。

代码

a,b = map(int,input().split())
print(a+b)

P1024 [NOIP 2001 提高组] 一元三次方程求解

• 题目：[NOIP 2001 提高组] 一元三次方程求解
• 状态：AC
• 语言：Python
• 标签：二分

题目原文

题目描述

有形如：$a x^3 + b x^2 + c x + d = 0$ 这样的一个一元三次方程。给出该方程中各项的系数（$a,b,c,d$ 均为实数），并约定该方程存在三个不同实根（根的范围在 $-100$ 至 $100$ 之间），且根与根之差的绝对值 $\ge 1$。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后 $2$ 位。 提示：记方程 $f(x) = 0$，若存在 $2$ 个数 $x_1$ 和 $x_2$，且 $x_1

输入格式

一行，$4$ 个实数 $a, b, c, d$。

输出格式

一行，$3$ 个实根，从小到大输出，并精确到小数点后 $2$ 位。

说明/提示

【题目来源】 NOIP 2001 提高组第一题

代码

a,b,c,d = map(float,input().split())
def func(n):
    return a*(n*n*n)+b*(n*n)+c*n+d
inf = -100
sup = 100
mis = 0.01
count = 0
res = []
def find(inf,sup):
    global count,res
    if sup-inf < mis:
        if func(sup)*func(inf)<0:
            res.append(float((sup+inf)/2))
        return
    mid = (inf+sup)/2
    find(inf,mid)
    find(mid,sup)
find(inf,sup)
result = [f"{x:.2f}" for x in res]
print(*result)

P2678 [NOIP 2015 提高组] 跳石头

• 题目：[NOIP 2015 提高组] 跳石头
• 状态：AC
• 语言：Python
• 标签：二分、贪心

题目原文

题目描述

一年一度的“跳石头”比赛又要开始了！ 这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 $N$ 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。 为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 $M$ 块岩石（不能移走起点和终点的岩石）。

输入格式

第一行包含三个整数 $L,N,M$，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 $L \geq 1$ 且 $N \geq M \geq 0$。 接下来 $N$ 行，每行一个整数，第 $i$ 行的整数 $D_i,( 0

输出格式

一个整数，即最短跳跃距离的最大值。

说明/提示

输入输出样例 1 说明 将与起点距离为 $2$ 和 $14$ 的两个岩石移走后，最短的跳跃距离为 $4$（从与起点距离 $17$ 的岩石跳到距离 $21$ 的岩石，或者从距离 $21$ 的岩石跳到终点）。

数据规模与约定 对于 $20\%$的数据，$0 \le M \le N \le 10$。 对于 $50\%$ 的数据，$0 \le M \le N \le 100$。 对于 $100\%$ 的数据，$0 \le M \le N \le 50000,1 \le L \le 10^9$。

思路

最短距离的最大值，是典型的二分答案问题。我们假设该值为(L+1)//2，然后从左到右扫描，如果两个石头之间的距离小于该值，则移除石头i，最终得到一个remove，若小于M，则说明该假设值可行，尝试更大的left=mid+1，若大于M，则缩小范围，right = mid-1

代码

L, N, M = map(int, input().split())
rocks = [0] * (N + 2)
rocks[0] = 0
rocks[N + 1] = L
for i in range(1, N + 1):
    rocks[i] = int(input())

left, right = 1, L
ans = 0

while left <= right:
    mid = (left + right) // 2
    removed = 0
    prev = 0
    for i in range(1, N + 2):
        if rocks[i] - rocks[prev] < mid:
            removed += 1
        else:
            prev = i
    if removed <= M:
        ans = mid
        left = mid + 1
    else:
        right = mid - 1

print(ans)