4.23 update: 省一咯

Powered by:NEFU AB-IN

博主个人的暴力题解，基本很少是正解，求轻喷

Python大学A组 个人暴力题解

• 试题 A: 特殊日期

  • 题意

    

  • 思路

    模拟即可，本身想用Python自带的datetime库，结果发现年不能开那么大，就直接手写了

  • 代码

    '''
    Author: NEFU AB-IN
    Date: 2023-04-08 14:15:52
    FilePath: \Vscode\ACM\LanQiao\2023PythonA\a.py
    LastEditTime: 2023-04-08 14:19:47
    '''
    # AB-IN AK Lanqiao !!
    # http://222.27.161.91/home.page
    # aR7H4tDF
    import sys, math
    from collections import Counter, deque, defaultdict
    from bisect import bisect_left, bisect_right
    from heapq import heappop, heappush, heapify
    from typing import *
    from datetime import datetime, timedelta
    
    N = int(1e6 + 10)
    INF = int(2e9)
    
    sys.setrecursionlimit(INF)
    read = lambda: map(int, input().split())
    
    
    class sa:
        def __init__(self, y, m, d):
            self.y = y
            self.m = m
            self.d = d
    
        def __lt__(self, x):
            pass
    
    
    # ---------------divrsion line ----------------
    
    # t1 = datetime(2000, 1, 1)
    # t2 = datetime(2000, 1, 2)
    
    # ans = 0
    # while True:
    #     if t1.year % t1.month == 0 and t1.year % t1.day == 0:
    #         ans += 1
    #     t1 = t1 + timedelta(days=1)
    #     if t1 == t2:
    #         break
    # print(ans)
    
    mouths = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    
    
    def func(t1):
        y, m, d = t1.y, t1.m, t1.d
        if (y % 4 == 0 and y % 100) or (y % 400 == 0):
            mouths[2] = 29
        else:
        	mouths[2] = 28
        d += 1
        if d > mouths[m]:
            d = 1
            m += 1
        if m > 12:
            m = 1
            y += 1
        return sa(y, m, d)
    
    
    t1 = sa(2000, 1, 1)
    t2 = sa(2000000, 1, 2)
    
    ans = 0
    while True:
        if t1.y % t1.m == 0 and t1.y % t1.d == 0:
            ans += 1
        t1 = func(t1)
        if t1.y == t2.y and t1.m == t2.m and t1.d == t2.d:
            break
    print(ans)
    
    # 35813063
    

• 试题 B: 分糖果

  • 题意

    

  • 思路

    DFS爆搜即可

  • 代码

    # AB-IN AK Lanqiao !!
    import sys, math
    from collections import Counter, deque, defaultdict
    from bisect import bisect_left, bisect_right
    from heapq import heappop, heappush, heapify
    from typing import *
    from datetime import datetime, timedelta
    
    N = int(1e6 + 10)
    INF = int(2e9)
    
    sys.setrecursionlimit(INF)
    read = lambda : map(int, input().split())
    
    class sa:
        def __init__(self, x, y):
            self.x = x
            self.y = y
        def __lt__(self, x):
            pass
    
    # ---------------divrsion line ----------------
    # 两种糖果分别有 9 个和 16 个，要全部分给 7 个小朋友，每个小朋友得到
    # 的糖果总数最少为 2 个最多为 5 个，问有多少种不同的分法。
    
    ans = 0
    def dfs(sum1, sum2, cnt):
        global ans
        if sum1 < 0 or sum2 < 0:
            return
        if cnt == 8:
            if sum1 == 0 and sum2 == 0:
                ans += 1
            return
        for i in range(2, 6):
            dfs(sum1 - i, sum2, cnt + 1)
        for i in range(2, 6):
            dfs(sum1, sum2 - i, cnt + 1)
        for i in range(2, 6):
            for j in range(2, 6):
                if i + j >= 2 and i + j <= 5:
                    dfs(sum1 - i, sum2 - j, cnt + 1)
    
    dfs(9, 16, 1)
    print(ans)
    
    # 148540
    

• 试题 C: 三国游戏

  • 题意

    

  • 思路

    直接没思路，一看到数据范围瞬间怂了，脑子里想的只有暴力，这个题是留到最后写的，就写了个最差的二进制枚举

  • 代码

    # AB-IN AK Lanqiao !!
    import sys, math
    from collections import Counter, deque, defaultdict
    from bisect import bisect_left, bisect_right
    from heapq import heappop, heappush, heapify
    from typing import *
    from datetime import datetime, timedelta
    
    N = int(1e6 + 10)
    INF = int(2e9)
    
    sys.setrecursionlimit(INF)
    read = lambda : map(int, input().split())
    
    class sa:
        def __init__(self, x, y):
            self.x = x
            self.y = y
        def __lt__(self, x):
            pass
    
    # ---------------divrsion line ----------------
    # 最差方法 二进制枚举
    
    n, = read()
    a = list(read())
    b = list(read())
    c = list(read())
    ans = 0
    
    for i in range(1 << n):
        A, B, C, cnt = 0, 0, 0, 0
        for j in range(n):
            if i & 1 << j:
                A += a[j]
                B += b[j]
                C += c[j]
                cnt += 1
        if A > B + C or B > A + C or C > A + B:
            ans = max(ans, cnt)
    
    print(ans if ans != 0 else -1)
    

• 试题 D: 平均

  • 题意

    

  • 思路

    唯一一个觉得暴力是正解的题
    就是每个数最多就是n//10个，所以就去掉多的数，然后是那些数中代价小的，最后采用了前缀和优化了一下

  • 代码

    # AB-IN AK Lanqiao !!
    import sys, math
    from collections import Counter, deque, defaultdict
    from bisect import bisect_left, bisect_right
    from heapq import heappop, heappush, heapify
    from typing import *
    from datetime import datetime, timedelta
    
    N = int(1e6 + 10)
    INF = int(2e9)
    
    sys.setrecursionlimit(INF)
    read = lambda : map(int, input().split())
    
    class sa:
       def __init__(self, a, b):
           self.a = a
           self.b = b
       def __lt__(self, t):
           if self.a != t.a:
               return self.a < t.a
           return self.b < t.b
    
    # ---------------divrsion line ----------------
    
    n, = read()
    lst = [[] for _ in range(10)]
    
    for i in range(n):
       a, b = read()
       lst[a].append(b)
    
    for i in range(10):
       lst[i].sort()
       lst[i] = [0, *lst[i]]
       # 前缀和
       for j in range(1, len(lst[i])):
           lst[i][j] += lst[i][j - 1]
    
    # 保留的个数
    k = n // 10
    
    ans = 0
    for i in range(10):
       l = len(lst[i]) - 1
       if l > k:
           ans += (lst[i][l - k])
    
    print(ans)
    

• 试题 E: 翻转

  • 题意

    

  • 思路

    BFS暴力，不会剪枝，剪枝想了一种，但是没有证明正确性，所以就没有采用

  • 代码

    # AB-IN AK Lanqiao !!
    import sys, math
    from collections import Counter, deque, defaultdict
    from bisect import bisect_left, bisect_right
    from heapq import heappop, heappush, heapify
    from typing import *
    from datetime import datetime, timedelta
    
    N = int(1e6 + 10)
    INF = int(2e9)
    
    sys.setrecursionlimit(INF)
    read = lambda : map(int, input().split())
    
    class sa:
        def __init__(self, s, step):
            self.s = s
            self.step = step
        def __lt__(self, x):
            pass
    
    # ---------------divrsion line ----------------
    # BFS暴力 不会剪枝 没证明剪枝一定正确
    
    def solve():
        t = input()
        s = input()
    
        t = " " + t
        s = " " + s
    
        if t[1] != s[1] or t[-1] != s[-1]:
            return -1
    
        q = deque()
        q.appendleft(sa(s, 0))
        while len(q):
            tp = q.pop()
            s, step = tp.s, tp.step
            if s == t:
                return step
            for i in range(2, len(s) - 1):
                if s[i] == '0' and s[i - 1] == '1' and s[i + 1] == '1':
                    g = s[:i - 1] + "111" + s[i + 2:]
                    if g == t:
                        return step + 1
                    q.appendleft(sa(g, step + 1))
                if s[i] == '1' and s[i - 1] == '0' and s[i + 1] == '0':
                    g = s[:i - 1] + "000" + s[i + 2:]
                    if g == t:
                        return step + 1
                    q.appendleft(sa(g, step + 1))
        return -1
    
    
    T, = read()
    for _ in range(T):
        print(solve())
    

• 试题 F: 子矩阵

  • 题意

    

  • 思路

    这版是直接暴力做的
    考试最后写了一点线段树优化，只不过只维护了行和列的最小值和最大值，但感觉Python写的线段树也优化不了多少

  • 代码

    # AB-IN AK Lanqiao !!
    import sys, math
    from collections import Counter, deque, defaultdict
    from bisect import bisect_left, bisect_right
    from heapq import heappop, heappush, heapify
    from typing import *
    from datetime import datetime, timedelta
    
    N = int(1e3 + 10)
    MOD = 998244353
    INF = int(2e9)
    
    sys.setrecursionlimit(INF)
    read = lambda : map(int, input().split())
    
    class sa:
        def __init__(self, x, y):
            self.x = x
            self.y = y
        def __lt__(self, x):
            pass
    
    # ---------------divrsion line ----------------
    # RMQ 问题 可写ST表 但我忘了...
    # 暴力！
    g = [[0] * N for _ in range(N)]
    n, m, a, b = read()
    
    def func(t1, t2):
        mn, mx = INF, 0
        for i in range(t1.x, t2.x + 1):
            for j in range(t1.y, t2.y + 1):
                mn = min(mn, g[i][j])
                mx = max(mx, g[i][j])
        return mx * mn % MOD
    
    for i in range(1, n + 1):
        g[i][1:] = read()
    
    ans = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            t1 = sa(i, j)
            t2 = sa(i + a - 1, j + b - 1)
            if i + a - 1 > n or j + b - 1 > m:
                continue
            ans = (ans + func(t1, t2)) % MOD 
    
    print(ans)
    

• 试题 G: 阶乘的和

  • 题意

    

  • 思路

    还是暴力，思路就是可以把共因子都提出来，剩下的加和，从提出来的共同的因子的最大值开始，让加和除以它，直到不能除了，就是答案
    其中，用哈希表记录用过的阶乘值，预处理一些阶乘值

  • 代码

    # AB-IN AK Lanqiao !!
    import sys, math
    from collections import Counter, deque, defaultdict
    from bisect import bisect_left, bisect_right
    from heapq import heappop, heappush, heapify
    from typing import *
    from datetime import datetime, timedelta
    
    N = int(1e5 + 10)
    INF = int(2e9)
    
    sys.setrecursionlimit(INF)
    read = lambda : map(int, input().split())
    
    class sa:
       def __init__(self, x, y):
           self.x = x
           self.y = y
       def __lt__(self, x):
           pass
    
    # ---------------divrsion line ----------------
    # 暴力！
    # 预处理1 ~ 5000阶乘
    dd = Counter()
    cnt = 1
    for i in range(1, 5000):
       cnt *= i
       dd[i] = cnt
    # ---------------------------------------------
    a = [0] * N
    
    n, = read()
    a[1:] = list(read())
    d = Counter()
    
    base = min(a[1:])
    ans = 0
    for i in range(1, n + 1):
       tmp = 1
       if a[i] < 5000:
           d[a[i]] = dd[a[i]] // dd[base]
       elif d[a[i]] == 0:
           for j in range(a[i], base, -1):
               tmp *= j
           d[a[i]] = tmp
       ans += d[a[i]]
    
    while True:
       if ans == 1 or ans % (base + 1) != 0:
           break
       base += 1
       ans //= base
    
    print(base)
    

• 试题 H: 奇怪的数

  • 题意

    

  • 思路

    还是暴力DFS
    相当于搜满足条件的n位数，直接搜每一位即可，因为奇数位为奇数，偶数位为偶数
    优化就是每次搜每一位的时候，和前面的四位数加和，判断是否小于等于m，如果不满足就直接不搜了

  • 代码

    # AB-IN AK Lanqiao !!
    import sys, math
    from collections import Counter, deque, defaultdict
    from bisect import bisect_left, bisect_right
    from heapq import heappop, heappush, heapify
    from typing import *
    from datetime import datetime, timedelta
    
    N = int(1e6 + 10)
    INF = int(2e9)
    MOD = 998244353
    
    sys.setrecursionlimit(INF)
    read = lambda : map(int, input().split())
    
    class sa:
        def __init__(self, x, y):
            self.x = x
            self.y = y
        def __lt__(self, x):
            pass
    
    # ---------------divrsion line ----------------
    # 感觉像数位dp，先打DFS暴力
    # 想不出递推式 就优化暴力吧
    
    n, m = read()
    
    ji = ["1", "3", "5", "7", "9"]
    ou = ["0", "2", "4", "6", "8"]
    stji, stou = [0] * 5, [0] * 5
    ans = 0
    
    def dfs(s, d):
        global ans
        if d == n + 1:
            ans = (ans + 1) % MOD
            return
    
        for i in range(5):
            if d % 2 == 1:
                cnt = int(ji[i])
                for j in range(max(1, d - 4), d):
                    cnt += int(s[j])
                if cnt <= m:
                    dfs(s + ji[i], d + 1)
            if d % 2 == 0:
                cnt = int(ou[i])
                for j in range(max(1, d - 4), d):
                    cnt += int(s[j])
                if cnt <= m:
                    dfs(s + ou[i], d + 1)
        return  
    
    
    dfs(" ", 1)
    print(ans % MOD)
    

• 试题 I: 子树的大小

  • 题意

    

  • 思路

    没时间想了，感觉暴力都很麻烦

  • 代码

• 试题 J: 反异或 01 串

  • 题意

    

  • 思路

    没时间想了，就特判了几种情况

  • 代码

    # AB-IN AK Lanqiao !!
    import sys, math
    from collections import Counter, deque, defaultdict
    from bisect import bisect_left, bisect_right
    from heapq import heappop, heappush, heapify
    from typing import *
    from datetime import datetime, timedelta
    
    N = int(1e6 + 10)
    INF = int(2e9)
    
    sys.setrecursionlimit(INF)
    read = lambda : map(int, input().split())
    
    class sa:
        def __init__(self, x, y):
            self.x = x
            self.y = y
        def __lt__(self, x):
            pass
    
    # ---------------divrsion line ----------------
    # 骗分
    
    def solve(s):
        d = Counter(s)
        if len(s) == d['0']:
            return 0
        if len(s) == d['1']:
            return len(s) // 2
        if s == "00111011":
            return 3
        return d['1']
        
    s = input()
    
    print(solve(s))