愿备考的小伙伴们都取得一个自己满意的成绩。 持续更新中~~~~

印章 【DP】

问题描述
　　共有n种图案的印章，每种图案的出现概率相同。小A买了m张印章，求小A集齐n种印章的概率。
将印章当做彩票，印章是太拗口了。
dp[i][j] 表示 购买i张彩票，有j种彩票的概率。
当i<j时，买i张是肯定没有j种彩票。
当j == 1时，买i张相同的彩票时，每张彩票都是相同的概率，也就是1/n
其他条件，买第i张彩票的情况有两种，一是和前面i-1张有重复，二是和前面i-1张没有重复。
    有重复就是已经凑齐了j种，dp[i-1][j], 再从凑齐的j种里面选一种的概率为j/n， 于是概率为dp[i-1][j]*j/n
    没有重复就是只凑齐了j-1种，dp[i-1][j-1]，再从没有凑齐的n-j+1种里面选一种的概率为(n - j + 1)，于是概率为dp[i-1][j-1] * (n - j + 1) / n


n, m = map(int, input().split())
dp = [[0] * (n + 1) for _ in range(m + 1)]

p = 1 / n

for i in range(1, m + 1):
    for j in range(1, n + 1):
        if i < j:
            continue
        if j == 1:
            dp[i][j] = p ** (i - 1)
        else:
            dp[i][j] = dp[i - 1][j] * j / n + dp[i - 1][j - 1] * (n - j + 1) / n

print("{:.4f}".format(dp[m][n]))

拿金币 【DP】

问题描述
　　有一个N x N的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到最多的金币。
    经典dp问题。

n = int(input())
mp = []
for _ in range(n):
    row = list(map(int, input().split()))
    mp.append(row)

dp = [[0] * n for _ in range(n)]
dp[0][0] = mp[0][0]
for i in range(1, n):
    dp[i][0] = dp[i - 1][0] + mp[i][0]
    dp[0][i] = dp[0][i - 1] + mp[0][i]
for i in range(1, n):
    for j in range(1, n):
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + mp[i][j]

print(dp[n - 1][n - 1])

数字游戏【杨辉三角 + DFS】

无聊的逗 【DFS】

问题描述
　　逗志芃在干了很多事情后终于闲下来了，然后就陷入了深深的无聊中。不过他想到了一个游戏来使他更无聊。他拿出n个木棍，然后选出其中一些粘成一根长的，
    然后再选一些粘成另一个长的，他想知道在两根一样长的情况下长度最长是多少。
    
    将木棒分为两堆，初始化第一堆为全部的木棍。之后枚举每根木棍有三种情况。
    1.木棍不分给第二堆
    2.木棍分给第二堆
    3.不要这个木棍
    递归这三种状态，遇到l==r时更新沾成木棍最长的长度。

n = int(input())
a = list(map(int, input().split()))
s = sum(a)
a.sort(reverse=True)
ans = 0


def dfs(ind, l, r):
    global ans
    if l == r and ans < l:
        ans = l
        return
    if l < r or ind >= n:
        return
    dfs(ind + 1, l, r)
    dfs(ind + 1, l - a[ind], r + a[ind])
    dfs(ind + 1, l - a[ind], r)


dfs(0, s, 0)
print(ans)

礼物 【二分】

    JiaoShou在爱琳大陆的旅行完毕，即将回家，为了纪念这次旅行，他决定带回一些礼物给好朋友。
　　在走出了怪物森林以后，JiaoShou看到了排成一排的N个石子。
　　这些石子很漂亮，JiaoShou决定以此为礼物。
　　但是这N个石子被施加了一种特殊的魔法。
　　如果要取走石子，必须按照以下的规则去取。
　　每次必须取连续的2*K个石子，并且满足前K个石子的重量和小于等于S，后K个石子的重量和小于等于S。
　　由于时间紧迫，Jiaoshou只能取一次。
　　现在JiaoShou找到了聪明的你，问他最多可以带走多少个石子。

    思路：
    先求石子重量的前缀和。可以通过s[i + k] - s[i] 来判断连续k个石子的重量。
    本题为金典的二分题。枚举连续的2*k个石子看是否满足条件。

from itertools import accumulate

n, k = map(int, input().split())
w = list(map(int, input().split()))
s = [0] * (n + 1)
for i in range(1, n + 1):
    s[i] = s[i - 1] + w[i - 1]
#s = list(accumulate(a, initial=0))


def check(mid):
    # 为什么是循环，因为找的是所有2 * k的石子数，例如n为10， [1, 10],mid = 2, 就有[1,2]和[3,4]，[2,3]和[4,5]等等。
    for i in range(mid, n - mid + 1):
        if s[i] - s[i - mid] <= k and s[i + mid] - s[i] <= k:
            return True
    return False


l, r = 0, n + 1  # 一定是开区间(0, n+1)
while l + 1 < r:
    mid = (l + r) >> 1
    if check(mid):
        l = mid
    else:
        r = mid

print(2 * l)

跳马 【BFS】

问题描述
　　一个8×8的棋盘上有一个马初始位置为(a,b)，他想跳到(c,d)，问是否可以？如果可以，最少要跳几步？
    
    用bfs求最小的层数。


x, y, dx, dy = map(int, input().split())
q = [(x, y)]
vis = [[0] * 15 for _ in range(15)]
l = 0
vis[x][y] = 1
while True:
    flag = 0
    next_q = []
    while len(q):
        cx, cy = q.pop(0)
        if cx == dx and cy == dy:
            flag = 1
            break
        for i, j in [[1, 2], [2, 1], [-1, 2], [-2, 1], [1, -2], [2, -1], [-1, -2], [-2, -1]]:
            xx, yy = cx + i, cy + j
            if xx < 0 or yy < 0 or xx > 12 or yy > 12 or vis[xx][yy]:
                continue
            vis[xx][yy] = 1
            next_q.insert(0, (xx, yy))
    if flag:
        break
    l += 1
    q = next_q

print(l)

kAc给糖果你吃【贪心】

问题描述
　　kAc有n堆糖果，每堆有A[i]个。
　　kAc说你只能拿m次糖果，聪明的你当然想要拿最多的糖果来吃啦啦啦~
　　//第二天，kAc问你还想吃糖果么？（嘿嘿嘿）说着眼角路出奇怪的微笑...
    贪心

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
print(sum(a[i] for i in range(m)))

数字潜能

问题描述
　　将一个数N分为多个正整数之和，即N=a1+a2+a3+…+ak，定义M=a1*a2*a3*…*ak为N的潜能。
　　给定N，求它的潜能M。
　　由于M可能过大，只需求M对5218取模的余数。

    将n分解成多个3相乘，如果身下的是1，则用1和3换成2和2
    然后再用快速幂计算3的幂次方

MOD = 5218

def fast_power(a, b):
    res = 1
    while b:
        if b % 2 == 1:
            res = res * a % MOD
        a = a * a % MOD
        b >>= 1
    return res % MOD

n = int(input())
a, b = divmod(n, 3)
if b == 1 and a > 0:
    a -= 1
    b = 4

ans = fast_power(3, a)
if b:
    ans = ans * b % MOD
print(ans)

娜神平衡【DFS】

问题描述
　　娜娜是一个特别可爱的女孩子，作为学神的她最近在情感方面出现了一点点小问题。
　　她暗恋的琦琦是一名学霸，他只喜欢长得漂亮和学习很好的女生。
　　娜娜学习确实很神，但是她在琦琦面前却总是表现不出平时的神力。
　　琦琦感受到了娜娜对他的爱，但是他还是觉得娜娜的学习并不是特别好，于是他出了一道题给娜娜。
　　“娜娜，我们之间的关系需要在不断深入的同时保持一定的平衡，不可以你总是强势或者我总是弱势。”
　　琦琦给了娜娜一些两两不等的数，希望娜娜能把这些数分成两组A和B，满足以下条件：
　　1：每一次只能操作一个数，即只取出一个数分入A中或B中；
　　2：每一次操作完成后，A中数之和与B中数之和的差不能超过r。
　　新时代的丘比特们啊，帮帮娜娜吧！


n, r = map(int, input().split())
a = list(map(int, input().split()))
first = a[0]
a.sort()
flag = 0
def print_a(arr):
    arr.sort()
    print(" ".join(str(ch) for ch in arr))
def dfs(L=[], R=[]): # 默认d = sum(L) - sum(R)
    global flag
    if abs(sum(L) - sum(R)) > r:
        return
    if len(a) == 0:
        flag = 1
        if first not in L:  # 如果a[0]不在L中，先打印R
            L, R = R, L
        print_a(L)
        print_a(R)
        return
    for i in range(len(a)):
        L.append(a[i])  # 先放入L数组中
        a.pop(i)
        dfs(L, R)
        if flag:
            return
        a.insert(i, L.pop()) # 回溯
    for i in range(len(a)):
        R.append(a[i])  # 再放入R数组中
        a.pop(i)
        dfs(L, R)
        if flag:
            return
        a.insert(i, R.pop())

dfs()

粘木棍 【贪心】

问题描述
　　有N根木棍，需要将其粘贴成M个长木棍，使得最长的和最短的的差距最小。
    先将最大的m个数放到b列表中，将这m个数从a中删除
    每次将a中的最大元素加到b数组中的最小元素中，然后删除a中的元素。

n, m = map(int, input().split())
a = list(map(int, input().split()))
if n == m:
    print(max(a) - min(a))
else:
    b = []
    for i in range(m):
        b.append(max(a))
        a.remove(max(a))
    for i in range(n - m):
        t = min(b)
        b.remove(t)
        t += max(a)
        a.remove(max(a))
        b.append(t)
    print(max(b) - min(b))

车的放置

问题描述
　　在一个n*n的棋盘中，每个格子中至多放置一个车，且要保证任何两个车都不能相互攻击，有多少中放法(车与车之间是没有差别的)

    类似于n皇后问题，n皇后问题是判断到放置n个皇后的时候再统计数量，而本题是遍历0-n一共有多少满足条件的放法。


n = int(input())
row = [0] * n
col = [0] * n
ans = 0


def dfs(m, num, step):
    global ans, row, col
    if num == m:
        ans += 1
        return

    for i in range(step, n):
        if row[i]:
            continue
        row[i] = 1
        for j in range(n):
            if col[j]:
                continue
            col[j] = 1
            dfs(m, num + 1, i + 1)
            col[j] = 0  # 回溯第j列
        row[i] = 0  # 回溯第i行


for i in range(n + 1):
    dfs(i, 0, 0)
print(ans)

24点 【DFS】

问题描述
　　24点游戏是一个非常有意思的游戏，很流行，玩法很简单：给你4张牌，每张牌上有数字（其中A代表1，J代表11，Q代表12，K代表13），你可以利用数学中的加、减、乘、除以及括号想办法得到24，例如：
　　((A*K)-J)*Q等价于((1*13)-11)*12=24
　　加减乘不用多说了，但除法必须满足能整除才能除！这样有一些是得不到24点的，所以这里只要求求出不超过24的最大值。

    解题思路：
    通过DFS来枚举当前两个元素的每一种可能(加减和乘除，同时注意减法和除法满足交换律)


def dfs(num, n):
    global ans
    if n == 1:
        ans = num[n - 1] if ans < num[n - 1] <= 24 else ans
        return

    for i in range(n-1):
        for j in range(i + 1, n):
            x, y = num[i], num[j]
            # 乘法和加法满足交换律
            num[j] = x + y
            num[i] = num[n - 1]
            dfs(num, n - 1)
            num[j] = x * y
            num[i] = num[n - 1]
            dfs(num, n - 1)
            # 除法和减法不满足交换律
            k = 2
            while k:
                if k == 1:
                    x, y = y, x
                k -= 1
                num[j] = x - y
                num[i] = num[n - 1]
                dfs(num, n - 1)

                if x != 0 and y % x == 0:
                    num[j] = y // x
                    num[i] = num[n - 1]
                    dfs(num, n - 1)

            num[i], num[j] = y, x  # 回溯，同时注意x和y交换过。


for i in range(int(input())):
    num = []
    for _ in range(4):
        num.append(int(input()))
    ans = 0
    dfs(num, 4)
    print(ans)

最大分解 【DFS】

问题描述
　　给出一个正整数n，求一个和最大的序列a0，a1，a2，……，ap，满足n=a0>a1>a2>……>ap且ai+1是ai的约数，输出a1+a2+……+ap的最大值



def dfs(num):
    global cur_s, max_s
    if num in [2, 3]:  # 如果是两个最小的素数，分解就是本身和1
        cur_s += 1
        max_s = max(cur_s, max_s)
        cur_s -= 1  # 回溯，不影响下一次递归
        return
    t = 0
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            t = num // i
            if t == i:  # 如果num是平方数，例如25,49， 但不能是36，因为会被2,3提前分解
                cur_s += i
                max_s = max(max_s, cur_s)
                cur_s -= i
                return
            # 如果不是平方数,那么先递归大的数

            cur_s += t
            dfs(t)
            cur_s -= t

            cur_s += i
            dfs(i)
            cur_s -= i
    if t == 0:
        cur_s += 1
        max_s = max(max_s, cur_s)
        cur_s -= 1
        return


n = int(input())
cur_s = max_s = 0
dfs(n)
print(max_s)

士兵杀敌（二）【模拟or线段树】

问题描述
　　南将军手下有N个士兵，分别编号1到N，这些士兵的杀敌数都是已知的。
　　小工是南将军手下的军师，南将军经常想知道第m号到第n号士兵的总杀敌数，请你帮助小工来回答南将军吧。
　　南将军的某次询问之后士兵i可能又杀敌q人，之后南将军再询问的时候，需要考虑到新增的杀敌数。

import sys


def push_up(rt):
    tree[rt] = tree[rt << 1] + tree[rt << 1 | 1]


def push_down(rt, ln, rn):
    add[rt << 1] = add[rt]
    add[rt << 1 | 1] = add[rt]
    tree[rt << 1] = ln * add[rt]
    tree[rt << 1 | 1] = rn * add[rt]
    add[rt] = 0


def build(rt, l, r):
    if l == r:
        tree[rt] = arr[l]
        return
    mid = (l + r) >> 1
    build(rt << 1, l, mid)
    build(rt << 1 | 1, mid + 1, r)
    push_up(rt)


def update(rt, l, r, L, R, num):
    if L <= l and r <= R:
        tree[rt] += num * (r - l + 1)
        add[rt] += num
        return
    mid = (l + r) >> 1
    if add[rt] != 0:
        push_down(rt, mid - l + 1, r - mid)
    if L <= mid:
        update(rt << 1, l, mid, L, R, num)
    if mid < R:
        update(rt << 1 | 1, mid + 1, r, L, R, num)
    push_up(rt)


def query_sum(rt, l, r, L, R):
    if L <= l and r <= R:
        return tree[rt]
    mid = (l + r) >> 1
    if add[rt] != 0:
        push_down(rt, mid - l + 1, r - mid)
    res = 0
    if L <= mid:
        res += query_sum(rt << 1, l, mid, L, R)
    if mid < R:
        res += query_sum(rt << 1 | 1, mid + 1, r, L, R)
    return res


while True:
    line = sys.stdin.readline()
    if not line:
        break
    n, m = (int(x) for x in line.split())
    tree = [0] * 4 * n
    add = [0] * 4 * n  # 区间更新的数组
    arr = list(map(int, input().split()))
    arr.insert(0, 0)
    build(1, 1, n)
    for _ in range(m):
        row = input().split()
        a, b = int(row[1]), int(row[2])
        if row[0][0] == "Q":
            print(query_sum(1, 1, n, a, b))
        else:
            update(1, 1, n, a, a, b)
        
        最简单的单点更新加区间查询
        if row[0][0] == "Q":
            print(sum(arr[a - 1:b]))
        else:
            arr[a - 1] += b
        但假如本题考区间查询和区间更新，本题就要用线段树。就在这里复习一下