头像

tornadoH2O




离线:2小时前


最近来访(102)
用户头像
Lampropeltis
用户头像
yxc的小迷妹
用户头像
Mappel
用户头像
玖魂
用户头像
旁若无人
用户头像
Capoo-Capoo
用户头像
Eureka_24
用户头像
雨朔
用户头像
xiaozd
用户头像
NUC-CYJ
用户头像
zst_2001
用户头像
程点
用户头像
.Zero
用户头像
求求了不要WA
用户头像
喃喃自语
用户头像
Suimou
用户头像
你这个年纪怎么睡得着觉
用户头像
不过四级不改名_7
用户头像
ck1000
用户头像
xjtu_zfw


题目描述

Hello Kitty想摘点花生送给她喜欢的米老鼠。

她来到一片有网格状道路的矩形花生地(如下图),从西北角进去,东南角出来。

地里每个道路的交叉点上都有种着一株花生苗,上面有若干颗花生,经过一株花生苗就能摘走该它上面所有的花生。

Hello Kitty只能向东或向南走,不能向西或向北走。

问Hello Kitty最多能够摘到多少颗花生。

输入格式

第一行是一个整数T,代表一共有多少组数据。

接下来是T组数据。

每组数据的第一行是两个整数,分别代表花生苗的行数R和列数 C。

每组数据的接下来R行数据,从北向南依次描述每行花生苗的情况。每行数据有C个整数,按从西向东的顺序描述了该行每株花生苗上的花生数目M。

输出格式

对每组输入数据,输出一行,内容为Hello Kitty能摘到得最多的花生颗数。

输入样例

2
2 2
1 1
3 4
2 3
2 3 4
1 6 5

输出样例

8
16

题目分析

动态规划 $O(n^2)$

由于是二维的地图,因此用$f[i][j]$来表示,
状态表示$f[i][j]$:所有从$(1, 1)$到$(i,j)$的所有方案
属性:Max
状态转移:根据题意,只能向下或者向右边走,所以对于每一个点,只需考虑从两个地方转移过来的情况,并取最大值
$(i, j)$从$(i-1, j)$即上方过来
$(i, j)$从$(i, j-1)$即左方过来
但需要注意在最左边一列的位置是只能从上方转移,最上面一行的位置只能从左边转移过来

DP问题注意初始化:这里左上角的点的状态值应该初始化为这个点的花生数量
f[1][1] = w[1][1]
---------------------------------------------------------------------------------------------------------------------

tips:1 算法中的坐标系一般如下图所示,与数学意义上的坐标系存在区别
摘花生(数字三角形模型).jpg
2.二维数组这里暂时我只会分开来按行读入

Py 代码

import sys
input = lambda:sys.stdin.readline().rstrip()

N = 110
w = [[0] * N for i in range(N)]
f = [[0] * N for i in range(N)]


t = int(input())
for i in range(t):
    n, m = map(int, input().split())
    for i in range(1, n + 1):
        ls = list(map(int, input().split()))
        for j in range(1, m + 1):
            w[i][j] = ls[j - 1]

    f[1][1] = w[1][1]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if i == 1:
                f[i][j] = f[i][j - 1] + w[i][j]
            elif j == 1:
                f[i][j] = f[i -1][j] + w[i][j]
            else:
                f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j]

    print(f[n][m])




import sys
input = lambda:sys.stdin.readline().rstrip()

N = 3010
f = [[0] * N for i in range(N)]

n = int(input())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))

for i in range(1, n + 1):
    maxv = 1
    for j in range(1, n + 1):
        f[i][j] = f[i - 1][j]
        if a[i] == b[j]:
            f[i][j] = max(f[i][j], maxv)
        if b[j] < a[i]:
            maxv = max(maxv, f[i - 1][j] + 1)

print(max(f[n][:]))


活动打卡代码 AcWing 187. 导弹防御系统

import sys
input = lambda:sys.stdin.readline().rstrip()

N = 55
up = [0] * N
down = [0] * N


def dfs(u, su, sd):
    global ans
    if su + sd >= ans:
        return
    if u == n:
        ans = min(ans, su + sd)
        return

    l = 0; r = su
    while l < r:
        mid = l + r >> 1
        if up[mid] > h[u]:
            r = mid
        else:
            l = mid + 1

    if l == su:
        t1 = up[su]
        up[su] = h[u]
        dfs(u + 1, su + 1, sd)

        up[su] = t1
    else:
        t2 = up[l]
        up[l] = h[u]
        dfs(u + 1, su, sd)

        up[l] = t2



    l = 0; r = sd
    while l < r:
        mid = l + r >> 1
        if down[mid] < h[u]:
            r = mid
        else:
            l = mid + 1


    if l == sd:
        t3 = down[su]
        down[sd] = h[u]
        dfs(u + 1, su, sd + 1)

        down[sd] = t3
    else:
        t4 = down[l]
        down[l] = h[u]
        dfs(u + 1, su, sd)

        down[l] = t4



while True:
    n = int(input())
    if n == 0:
        break
    else:
        h = list(map(int, input().split()))

    ans = n

    dfs(0, 0, 0)

    print(ans)




活动打卡代码 AcWing 1010. 拦截导弹

import sys
input = lambda:sys.stdin.readline().rstrip()

N = 1010
f = [1] * N
q = [0] * N
h = list(map(int, input().split()))

len_h = len(h)


for i in range(len_h):
    for j in range(i):
        if h[i] <= h[j]: # 这里导弹是不下降的,所以要等号
            f[i] = max(f[i], f[j] + 1)
print(max(f))


cnt = 0 # cnt代表导弹系统数量
for i in range(len_h):
    k = 0 # k代表第i发应该被接在哪一个系统后面
    while k < cnt and q[k] < h[i]:
        k += 1
    if k == cnt:
        q[cnt] = h[i]
        cnt += 1
    else:
        q[k] = h[i]

print(cnt)



题目描述

现有 $m$ 所学校,每所学校预计分数线是 $a_i$。有 $n$ 位学生,估分分别为 $b_i$。

根据 $n$ 位学生的估分情况,分别给每位学生推荐一所学校,要求学校的预计分数线和学生的估分相差最小(可高可低,毕竟是估分嘛),这个最小值为不满意度。求所有学生不满意度和的最小值。

输入格式

第一行读入两个整数 $m,n$。$m$ 表示学校数,$n$ 表示学生数。

第二行共有 $m$ 个数,表示 $m$ 个学校的预计录取分数。第三行有 $n$ 个数,表示 $n$ 个学生的估分成绩。

输出格式

输出一行,为最小的不满度之和。

样例 #1

样例输入 #1

4 3
513 598 567 689
500 600 550

样例输出 #1

32

提示

数据范围:

对于 $30\%$ 的数据,$1\leq n,m\leq1000$,估分和录取线 $\leq10000$;

对于 $100\%$ 的数据,$1\leq n,m\leq100000$,估分和录取线 $\leq 1000000$ 且均为正整数。


题目分析:

根据题意可以知道,只要找到最接近分数的分数线就能求出答案。

二分:

左区间是小于等于该学生分数的分数线,右区间的是大于该学生分数的分数线,采用第一个模板,求左区间的右边界。

$check$函数的返回值为$True$的情况:a[i] <= target,此时处于左区间内,l = mid

时间复杂度:$O(n\log n)$

C++ 代码

import sys
input = lambda: sys.stdin.readline().rstrip()


n, m = map(int, input().split())

a = list(map(int, input().split()))
a.sort()
res = 0
b = list(map(int, input().split()))
for i in range(m):
    x = b[i]
    l = 0; r = n - 1
    while l < r:
        mid = l + r + 1>> 1
        if a[mid] <= x:
            l = mid
        else:
            r = mid - 1
    s1 = a[l]
    if s1 == x:
        continue
    elif l + 1 < n:
        s2 = a[l + 1]
        res += min(abs(s2 - x), abs(s1 - x))
    else:
        res += abs(s1 - x)

print(res)




题目描述

这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 $N$ 块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。

为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走 $M$ 块岩石(不能移走起点和终点的岩石)。

输入格式

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

接下来 $N$ 行,每行一个整数,第 $i$ 行的整数 $D_i( 0 < D_i < L)$, 表示第 $i$ 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同一个位置。

输出格式

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

样例 #1

样例输入 #1

25 5 2 
2
11
14
17 
21

样例输出 #1

4

提示

输入输出样例 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$。


题目分析:

最开始读了个假题,明明是至多移走$M$块石头,我却想成了一定要全部挪走。。。

题目中要求的是 最短跳跃距离的最大值,符合XX最短/最小的最大值或者XX最长/最大的最小值,满足二分答案的有界性和单调性。所以想到用二分做。

二分

因为需要移动石头,且移动数量有上限,所以把二分得到的“最短距离”和每块石头之间的距离进行比较,如果无法完成跳跃,那么就把石头挪走,如果挪走的石头没有超过已知的上限,那么$check$函数返回$True$,如果超过了上限,则返回$False$。

这里的$check$函数是记录需要移动的石头数量是否超过上限。

根据题意可以得出左右区间,左区间是小于等于最短跳跃距离的最大值,右区间是大于最短跳跃距离的最大值,所以用第一个模板,求左区间的右边界

如果$check$函数返回$True$的话(说明这个最短距离还可以再大,此时处于左区间内),应该是l = mid,反之r = mid - 1

时间复杂度 $O(n\log n)$

py 代码

import sys
input = lambda: sys.stdin.readline().rstrip()

N = 50010
a = [0] * N

def check(x):
    s = 0 # 需要挪走的石头总量
    now = 0 # 目前石头位置
    next_ = 0 #下一块石头的位置
    while next_ < n + 1:
        next_ += 1
        if a[next_] - a[now] < x:
            s += 1
        else:
            now = next_
    if s > m:
        return False
    else:
        return True

### 跳石头
d, n, m = map(int, input().split())

a[n + 1] = d
for i in range(1, n + 1):
    x = int(input())
    a[i] = x

l = 1; r = d
while l < r:
    mid = l + r + 1 >> 1
    if check(mid):
        l = mid
    else:
        r = mid - 1
print(l)





题目描述

木材厂有 $n$ 根原木,现在想把这些木头切割成 $k$ 段长度为 $l$ 的小段木头(木头有可能有剩余)。

当然,我们希望得到的小段木头越长越好,请求出 $l$ 的最大值。

木头长度的单位是 $\text{cm}$,原木的长度都是正整数,我们要求切割得到的小段木头的长度也是正整数。

例如有两根原木长度分别为 $11$ 和 $21$,要求切割成等长的 $6$ 段,很明显能切割出来的小段木头长度最长为 $5$。

输入格式

第一行是两个正整数 $n,k$,分别表示原木的数量,需要得到的小段的数量。

接下来 $n$ 行,每行一个正整数 $L_i$,表示一根原木的长度。

输出格式

仅一行,即 $l$ 的最大值。

如果连 $\text{1cm}$ 长的小段都切不出来,输出 0

样例 #1

样例输入 #1

3 7
232
124
456

样例输出 #1

114

提示

数据规模与约定

对于 $100\%$ 的数据,有 $1\le n\le 10^5$,$1\le k\le 10^8$,$1\le L_i\le 10^8(i\in[1,n])$。


分析过程

二分

时间复杂度: $O(n\log n)$

由于题目中出现了能够切割得到的小段的最大长度,一般如果有XX最短/最小的最大值就要想到二分答案。
因此可以通过二分求出切割得到的小段的最大长度。

小段的最小值是1,最大值是原木长度的最大值。

左区间是小于等于小段的最大长度,右区间是大于小段的最大长度,所以是求左区间的右边界,用第一个模板。
对于每一个小段长度,都能通过$check$函数求出对应的小段数量。

这里传入$check$函数的参数(小段长度)越大,对应的$check$函数值(小段数量)越小,反之亦然。

所以如果返回的小段数量大于等于目标值(说明此时小段长度比最大长度要小(在左区间中),此时是True的情况),那么l = mid,否则r = mid - 1

py 代码

import sys
input = lambda: sys.stdin.readline().rstrip()

def check(x):
    res = 0
    for i in range(n):
        res += a[i] // x
    return res


n, k = map(int, input().split())
a = []
for i in range(n):
    x = int(input())
    a.append(x)
a.sort()
res = 0

if k > sum(a):
    print(0)
else:
    l = 1; r = a[n - 1]
    while l < r:
        mid = l + r + 1 >> 1
        if check(mid) >= k:
            l = mid
        else:
            r = mid - 1
    print(l)






题目描述

给出一串正整数数列以及一个正整数 $C$,要求计算出所有满足 $A - B = C$ 的数对的个数(不同位置的数字一样的数对算不同的数对)。

输入格式

输入共两行。

第一行,两个正整数 $N,C$。

第二行,$N$ 个正整数,作为要求处理的那串数。

输出格式

一行,表示该串正整数中包含的满足 $A - B = C$ 的数对的个数。

样例 #1

样例输入 #1

4 1
1 1 2 3

样例输出 #1

3

提示

对于 $75\%$ 的数据,$1 \leq N \leq 2000$。

对于 $100\%$ 的数据,$1 \leq N \leq 2 \times 10^5$,$0 \leq a_i <2^{30}$,$1 \leq C < 2^{30}$。


思路:

时间复杂度:二分 $O(n\log n)$

显而易见这也是一道二分的题目,对于每一个数,先看这个数加上C是否在列表中,如果不在就continue,如果在列表中,那么利用二分求一下这个数在列表中的起始下标与末尾下标,二者相减并加一就是答案。


  1. 求起始下标:
    将列表分为左右两个区间,左区间是小于目标元素,右区间是大于等于目标元素。
    因此是求右区间的左边界,套用第二个模板
    $check$函数的$True$应该对应r = mid, $False$应该对应l = mid + 1
  2. 求末尾下标:
    将列表分为左右两个区间,左区间是小于等于目标元素,右区间是大于目标元素。
    因此是求左区间的右边界,套用第一个模板
    $check$函数的$True$应该对应l = mid,$False$应该对应r = mid - 1

注意元素个数右端点减去左端点后应该再加上1

py 代码

import sys
input = lambda: sys.stdin.readline().rstrip()


n, c = map(int, input().split())


def chek(q):
    l = 1; r = n; res = 0
    while l < r:
        mid = l + r >> 1
        if a[mid] >= q:
            r = mid
        else:
            l = mid + 1
    left = l
    if a[l] != q:
        return 0
    else:
        l = 1; r = n
        while l < r:
            mid = l + r + 1 >> 1
            if a[mid] <= q:
                l = mid
            else:
                r = mid - 1
        right = l
        if left == right:
            res += 1
        else:
            res += right - left + 1
    return res



a = [-10] + list(map(int, input().split()))
a.sort()
res = 0
max_ = a[n]
for i in range(1, n + 1):
    q = a[i] + c
    if q > max_:
        continue
    else:
        res += chek(q)

print(res)





题目描述

输入 $n$ 个不超过 $10^9$ 的单调不减的(就是后面的数字不小于前面的数字)非负整数 $a_1,a_2,\dots,a_{n}$,然后进行 $m$ 次询问。对于每次询问,给出一个整数 $q$,要求输出这个数字在序列中第一次出现的编号,如果没有找到的话输出 $-1$ 。

输入格式

第一行 $2$ 个整数 $n$ 和 $m$,表示数字个数和询问次数。

第二行 $n$ 个整数,表示这些待查询的数字。

第三行 $m$ 个整数,表示询问这些数字的编号,从 $1$ 开始编号。

输出格式

输出一行,$m$ 个整数,以空格隔开,表示答案。

样例输入 #1

11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6

样例输出 #1

1 2 -1

提示

数据保证,$1 \leq n \leq 10^6$,$0 \leq a_i,q \leq 10^9$,$1 \leq m \leq 10^5$

本题输入输出量较大,请使用较快的 IO 方式。


分析过程:

二分

时间复杂度: $O(n\log n)$

本题中的数据是非递减的非负整数,很容易想到二分。

题目求的是在序列中第一次出现的序号,根据二分的思想划分两个区间:左区间是小于目标值,右区间是大于等于目标值

注意二分求的是边界

第一次出现的序号是属于右区间的左边界

如果是左区间的右边界的话,那就并不是这个数(左区间的右边界仍然是在左区间,还是小于目标值的)
所以选择第二个模板

满足check函数的mid应该是在右区间里面,因此check函数应该是a[mid] >= target

py 代码

import sys
input = lambda: sys.stdin.readline().rstrip()


n, m = map(int, input().split())

a = [0] + list(map(int, input().split()))
b = list(map(int, input().split()))

for i in range(m):
    q = b[i]
    l = 1; r = n
    while l < r:
        mid = l + r >> 1
        if a[mid] >= q:
            r = mid
        else:
            l = mid + 1
    if a[l] != q:
        print(-1, end = " ")
    else:
        print(l, end = " ")




做了一些二分的题目,对这类题目还是有些害怕,希望整理过后可以做的好一点吧

二分的实质是找到一个边界,左半边满足这个性质,但右半边不满足这个性质(并不一定要满足单调的条件)
这样就可以通过二分来寻找边界,包括左边界与右边界
这里的左边界指的是右区间的左边界,右边界则是左区间的右边界。

注意:当题目出现XX最短/最小的最大值或者XX最长/最大的最小值,就要想到二分

  1. 情况一(求左区间的右边界)
    当check函数成立的时候,此时mid处于红色区间(左区间),mid满足check,所以直接l = mid
    当check函数不成立的时候,mid处于绿色区间(右区间),此时mid不满足check函数,所以需要减1向左侧靠拢r = mid - 1
    注意:这种情况的mid需要加一,mid = l + r + 1 >> 1
    代码:
mid = l + r + 1 >> 1
while l < r:
    if check():
       l = mid
    else:
       r = mid - 1 

  1. 情况二(求右区间的左边界)
    当check函数成立的时候,此时mid处于绿色区间(右区间),mid满足check,所以直接r = mid
    当check函数不成立的时候,mid处于红色区间(左区间),此时mid不满足check函数,所以需要加1向右侧靠拢l = mid + 1
    代码:
mid = l + r >> 1
while l < r:
    if check():
       r = mid
    else:
       l = mid + 1

做过的题目列表:
1. 洛谷 P2249. 【深基13.例1】查找
2. 洛谷 P1102. A-B 数对
3. 洛谷 P2440. 木材加工
4. 洛谷 P2678. 跳石头
5. 洛谷 P1678. 烦恼的高考志愿
6.

最近感觉做题的关键怎么在check函数上,只要想到check函数怎么写,就能做出来