第十四届蓝桥杯大赛软件组省赛 Python大学A组 个人暴力题解

04-13 1028阅读

4.23 update: 省一咯

Powered by:NEFU AB-IN

文章目录

  • Python大学A组 个人暴力题解
    • 试题 A: 特殊日期
      • 题意
      • 思路
      • 代码
      • 试题 B: 分糖果
        • 题意
        • 思路
        • 代码
        • 试题 C: 三国游戏
          • 题意
          • 思路
          • 代码
          • 试题 D: 平均
            • 题意
            • 思路
            • 代码
            • 试题 E: 翻转
              • 题意
              • 思路
              • 代码
              • 试题 F: 子矩阵
                • 题意
                • 思路
                • 代码
                • 试题 G: 阶乘的和
                  • 题意
                  • 思路
                  • 代码
                  • 试题 H: 奇怪的数
                    • 题意
                    • 思路
                    • 代码
                    • 试题 I: 子树的大小
                      • 题意
                      • 思路
                      • 代码
                      • 试题 J: 反异或 01 串
                        • 题意
                        • 思路
                        • 代码

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

                          Python大学A组 个人暴力题解

                          • 试题 A: 特殊日期

                            • 题意

                              第十四届蓝桥杯大赛软件组省赛 Python大学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: 分糖果

                              • 题意

                                第十四届蓝桥杯大赛软件组省赛 Python大学A组 个人暴力题解

                              • 思路

                                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 = 2 and i + j  A + B:
        ans = max(ans, cnt)
print(ans if ans != 0 else -1)

                              • 试题 D: 平均

                                • 题意

                                  第十四届蓝桥杯大赛软件组省赛 Python大学A组 个人暴力题解

                                • 思路

                                  唯一一个觉得暴力是正解的题

                                  就是每个数最多就是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  k:
       ans += (lst[i][l - k])
print(ans)

                                • 试题 E: 翻转

                                  • 题意

                                    第十四届蓝桥杯大赛软件组省赛 Python大学A组 个人暴力题解

                                  • 思路

                                    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大学A组 个人暴力题解

                                    • 思路

                                      这版是直接暴力做的

                                      考试最后写了一点线段树优化，只不过只维护了行和列的最小值和最大值，但感觉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: 阶乘的和

                                      • 题意

                                        第十四届蓝桥杯大赛软件组省赛 Python大学A组 个人暴力题解

                                      • 思路

                                        还是暴力，思路就是可以把共因子都提出来，剩下的加和，从提出来的共同的因子的最大值开始，让加和除以它，直到不能除了，就是答案

                                        其中，用哈希表记录用过的阶乘值，预处理一些阶乘值

                                      • 代码

                                        # 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]

                                      • 试题 H: 奇怪的数

                                        • 题意

                                          第十四届蓝桥杯大赛软件组省赛 Python大学A组 个人暴力题解

                                        • 思路

                                          还是暴力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
VPS购买请点击我

文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。

相关阅读

目录[+]