mipha™

分类

题解(11)

/ 注册

全部文章（共10篇）

题解 | #tb的排列问题#

哈哈，就做出一题，最后一题F，还是最后一分钟做出来的思路 - 滑动窗口假设a,b = A[i],B[i] 若b不存在于A，那a只能换取窗口中的-1 有多少个-1，就乘以多少种情况若没有-1，那就返回0 若b存在于A，那a只能换窗口中的A[j]，且A[j] == b 若存在A[j]，那...

Python3 滑动窗口

2024-09-20

4 112

题解 | #不是烤串故事#

思路二分 + 字符串哈希对于每次翻转，二分lcp即可，check函数通过字符串哈希进行哈希值快速获取，然后判断即可。代码 # 字符串哈希 base, mod = 1331, 10**9 + 7 base_inv = pow(base,mod-2,mod) def getPreHash(s): ...

Python3 字符串哈希函数滚动哈希二分查找

2024-08-18

1 193

题解 | #牛客周赛 Round 46#

A 乐奈吃冰。。。 a,b = map(int,input().strip().split()) print(a + min(a // 2,b)) B 素世喝茶。。。 n,x = map(int,input().strip().split()) a = list(map(int,input()...

pypy3

2024-06-09

3 273

题解 | #牛客周赛 Round 42#

D 树形dp + 贪心总节点数为奇数时返回-1 贪心：凑够偶数个节点就断开。 import sys sys.setrecursionlimit(200000) n = int(input()) from collections import defaultdict road = defaultd...

Python3 贪心记忆化搜索动态规划数学树形dp

2024-05-12

8 318

题解 | #本初字符串# F

F 本初字符串枚举首先确定S的本初字符串T的长度有多少种情况，显然len(T) <= len(S)，枚举所有长度的话肯定超时，自己造几个样例，其实很容易发现规律，只需要枚举len(S)的所有因数。作为T长度就可以了，不想证明（其实是不会。。。）由于要使T长度尽量小，所以肯定使从小到大枚举...

Python3 贪心字符串枚举

2024-05-11

0 332

题解 | #小A的线段（hard version）# #牛客小白月赛90# F题

排序根据输入的线段，按l排序 n,m = map(int,input().strip().split()) arr = [] for _ in range(m): l,r = map(int,input().strip().split()) arr.append((l,r)) ...

Python3 动态规划

2024-04-05

0 283

题解 | #小红的区间删除# G题

树状数组求逆序对总数total，用树状数组即可求解滑动窗口滑动窗口 [l,r]，代表移除的区间。建立两个树状数组left和right。在滑动过程中，维护树状数组left和right，并维护逆序对总数total。滑动过程中保证维护后的total >= k，即可统计可删除区间总数。代...

Python3 树状数组滑动窗口

2024-03-25

0 358

题解 | #牛客周赛 Round 37# D,E,F

D 首先最后肯定只会剩下一个字母，因为小紫希望这个字符串的字典序尽可能小，比如：a < aa，小紫肯定会把aa删剩下a。假如字符串为b?????g，小红先行动，所以答案至少为g(g > b)，如果?中存在一个字母比g大，小红想保留这个?字母，轮到小紫行动，肯定能把这个?字母给删除掉，使...

Python3 脑筋急转弯哈希表最短路

2024-03-17

0 231

题解 | #牛客周赛 Round 36# E,F

E题蛇皮走位即可 n 为奇数时：在最后一行第2个位提前拐弯 zyxwvu zyxwvt ryxwvt ryxwvs rpxwvs n 为偶数时：在倒数第二行最后一位直接拐到终点 zyxwvu zyxwvt qyxwvt qyxwvs pyxwvs pyxwvr 拐弯处选字母优先选出现...

Python3 设计树状数组

2024-03-12

0 319

题解 | F题模拟

模拟只需模拟两个起点 (0,0) (0,1) 方向都是UR，模拟过程中统计消除的块，回到起点或者碰到角落就结束模拟。 n,***p(int,input().strip().split()) D *= 2 # 角落 corner = set() corner.add((0,0)) corner...

Python3 模拟

2024-03-09

1 262