题型:
1.思维题/杂题:数学公式,分析题意,找规律
2.BFS/DFS:广搜(递归实现),深搜(deque实现)
3.简单数论:模,素数(只需要判断到 int(sqrt(n))+1),gcd,lcm,快速幂(位运算移位操作),大数分解(分解为质数的乘积)
4.简单图论:最短路(一对多(Dijstra,临接表,矩阵实现),多对多(Floyd,矩阵实现)),最小生成树(并查集实现)
5.简单字符串处理:最好转为列表操作
6.DP:线性DP,最长公共子序列,0/1背包问题,最长连续字符串,最大递增子串
7.基本算法:二分,贪心,组合,排列,前缀和,差分
8.基本数据结构:队列,集合,字典,字符串,列表,栈,树
9.常用模块:math,datetime,sys中的设置最大递归深度(sys.setrecursionlimit(3000000)),collections.deque(队列),itertools.combinations(list,n)(组合),itertools.permutations(list,n)(排列) heapq(小顶堆)
目录
题型:
刷题:
1.《排列字母》真题练习(内置函数)
2.《寻找整数》真题练习(埃氏筛法,或者枚举遍历)
3.纸张尺寸(循环,判断)
4.数位排序(自定义排序规则,字符串操作)
5.《蜂巢》真题练习(思维题,坐标转换)
6.《消除游戏》真题练习(暴力循环,列表,字符串操作)
7.《全排列的价值》真题练习(数学性质,排列组合)编辑
8.《技能升级》真题练习(二分)
9.《最长不下降子序列》真题练习(dp,线段树)
10.《最优清零方案》真题练习(暴力枚举,线段树维护)
刷题:
1.《排列字母》真题练习(内置函数)
初步思想:调用内置函数排序就行了
标程:
s = "WHERETHEREISAWILLTHEREISAWAY"
s = list(s)
s.sort()
print("".join(s))
2.《寻找整数》真题练习(埃氏筛法,或者枚举遍历)
初步思想:遍历,肯定有规律,然后递增找最小值就行。或者就是埃式筛法。
大致思想代码:
import os
import sys
mp = {2:1, 3:2, 4:1, 5:4, 6:5,7:4,8:1,9:2,10:9,11:0,12:5,13:10,
14:11,15:14,16:9,17:0,18:11,19:18,20:9,21:11,22:11,23:15,24:17,25:9,
26:23,27:20,28:25,29:16,30:29,31:27,32:25,33:11,34:17,35:4,36:29,37:22,
38:37,39:23,40:9,41:1,42:11,43:11,44:33,45:29,46:15,47:5,48:41,49:46}
# # 先从100-9999里面看看能不能找出一部分
# ls = [i for i in range(100,10**4)]
# result = []
# # 先在[100,9999]中找出除以2-10的余数符合的数字们
# for i in range(2,10):
# # 使用filter lambda表达式的形式
# ls = list(filter(lambda x:x%i==mp[i], ls))
# '''print(ls)
# 此处的结果是[1649, 4169, 6689, 9209],这个结果是有规律的,
# 4169-1649=2520
# 6689-4169=2520
# 9209-6689=2520
# 故而,1649+2520*n的一众结果满足2-10,我们依次接着往下做
# range(起始、末尾、步长)
# '''
#
# #第二次,直接把目光放到(1000,10**9)里面找
# #找10-20之间的
# ls = [i for i in range(1649, 10**9, 2520)]
# for i in range(10,20):
# ls = list(filter(lambda x: x%i==mp[i], ls))
'''
print(ls)
结果是[88209209, 321001769, 553794329, 786586889]
[1]-[0]=232792560
[2]-[1]=232792560
故而,88209209+232792560*n
'''
#第三次,直接把目光放在[88209209,10**16]
#找20-30之间的
# ls = [i for i in range(88209209, 10**16, 232792560)]
# for i in range(20,30):
# ls = list(filter(lambda x:x%i==mp[i], ls))
'''
print(ls)
[391179710009, 2720269272809, 5049358835609,
'''
# a = 2720269272809-391179710009
# ls = [i for i in range(391179710009,10**18,a)]
# for i in range(30,40):
# ls = list(filter(lambda x:x%i==mp[i],ls))
# print(ls[0])
# 结果是[2022040920220409, 7364972377283609, 12707903834346809,.......
# 只取第一个
print('2022040920220409')
标程:
from math import gcd
#求数字a,b的最小公倍数
def lcm(a, b):
return a * b // gcd(a, b)
a=[0, 0,
1,2,1,4,5,4,1,2,9,0,5,10,
11,14,9,0,11,18,9,11,11,15,17,9,
23,20,25,16,29,27,25,11,17,4,29,22,
37,23,9,1,11,11,33,29,15,5,41,46]
x = 0
step = 1
for i in range(2, 50):
#暴力求解满足x % i = a[i]
while x % i != a[i]:
x += step
step = lcm(step, i)
print(x)
3.纸张尺寸(循环,判断)
初步想法: 读懂题意,照着逻辑敲出来就行了,没得难度,送分,长除以2的时候可能需要维护长边,因为可能长会比宽大
标程:
x = int(input()[1])
a, b = 1189, 841
for i in range(x):
a //= 2
if a < b:
a, b = b, a
print(a)
print(b)
4.数位排序(自定义排序规则,字符串操作)
初步思路:将数字以字符形式存储,然后转列表,自定义排序规则,首先比较和,如果和相同再按字典序排序,自定义排序规则(functools)
标程:
n = int(input())
m = int(input())
a = [i for i in range(1, n + 1)]
b = [0] * (n + 1)
for i in range(1, n + 1):
#求i的数位之和
num = i
while num != 0:
b[i] += num % 10
num //= 10
a.sort(key=lambda x: (b[x], x))
print(a[m - 1])
5.《蜂巢》真题练习(思维题,坐标转换)
初步思路:转换为直角坐标来做!
正解:也是转为二元组坐标,但是是以3为x的正方向,2为y的正方向
标程:
# 方向增量
dir = [[-1, 0], [-1, 1], [0, 1], [1, 0], [1, -1], [0, -1]]
# 将<d,p,q>转换成新坐标系下的<x,y>
def change(d, p, q):
x, y = 0, 0
x += dir[d][0] * p
y += dir[d][1] * p
d = (d + 2) % 6
x += dir[d][0] * q
y += dir[d][1] * q
return x, y
d1, p1, q1, d2, p2, q2 = map(int, input().split())
Ax, Ay = change(d1, p1, q1)# 转换坐标
Bx, By = change(d2, p2, q2)
first, second = Ax - Bx, Ay - By# 计算差值向量
if first * second >= 0:# 分类讨论
print(abs(first) + abs(second))
else:
print(max(abs(first), abs(second)))
6.《消除游戏》真题练习(暴力循环,列表,字符串操作)
初步思路:遍历一次找到所有的边缘字符,记录下标,然后删除。最后如果数组长度不变或者长度为零,就退出。
正解:思路类似,有个优化,就是标记数组长度为当前字符长度,可以节约时间。
s = list(input())
last_length = 0
while True:
length = len(s)
#如果长度等于0,终止
if length == 0:
print("EMPTY")
break
#如果长度未发生变化,终止
if length == last_length:
print("".join(s))
break
vis = [0] * length
#根据题意找出边缘字符
for i in range(length): # 加条件判断边界
if (i - 1) >= 0 and (i + 1) < length and s[i] == s[i - 1] and s[i] != s[i + 1]:
vis[i] = vis[i + 1] = 1
if (i - 1) >= 0 and (i + 1) < length and s[i] != s[i - 1] and s[i] == s[i + 1]:
vis[i] = vis[i - 1] = 1
#将边缘字符去除
tmp_s = []
for i in range(length):
if vis[i] == 0:
tmp_s.append(s[i])
s = tmp_s
last_length = length
7.《全排列的价值》真题练习(数学性质,排列组合)
初步思想:找规律,看是否有规律,没得的话就暴力,能过多少过多少。(无规律)
正解:数学性质可以得到,顺序对个数加上逆序对个数 的和是一定的,等于n*(n-1)//2。
同时所有排列的顺序对之和等于所有排列的逆序对之和
mod = 998244353
n = int(input())
ans = n * (n - 1) // 2 % mod
for i in range(3, n + 1):
ans = ans * i % mod
print(ans)
8.《技能升级》真题练习(二分)
初步思想:贪心,优先升级升级后增加点数最多的,每次升级后更新升级点数和技能有用值。(过40%数据)
import sys #设置递归深度
import collections #队列
import itertools # 排列组合
import heapq #小顶堆
import math
sys.setrecursionlimit(300000)
import functools # 自定义比较函数 -1不变,1交换
save=[]
n,m=map(int,input().split())
for i in range(n):
a,b=map(int,input().split())
save.append([a,b,math.ceil(a/b)])
save.sort(key=lambda x:x[0],reverse=True) # 按当前升级增点树排序
#print(save)
ans=0
for i in range(m): # 升级m次技能
for i in save:
if i[2]>0: # 升级还有效
ans+=i[0]
i[2]-=1
i[0]=i[0]-i[1]
break
save.sort(key=lambda x:x[0],reverse=True) # 按当前升级增点树排序
#print(save)
print(ans)
正解:将问题转变成在 N 个递减的等差数列中前 M 大和是多少,第 i 个等差数列的首项为 Ai,公差为 Bi。由于是等差数列,存在单调性,可以使用二分答案求出第 M 大的数值。
标程:
n, m = map(int, input().split())
a = [0] * (n + 1)
b = [0] * (n + 1)
for i in range(1, n + 1):
a[i], b[i] = map(int, input().split())
#假设第m大为x,求存在多少个数字>=x
def check(x):
cnt = 0
for i in range(1, n + 1):
if a[i] < x:
continue
k = (a[i] - x) // b[i]
cnt += k + 1
return cnt >= m
left, right, x = 0, 1000000, 0
while left <= right:
mid = (left + right) // 2
if check(mid):
x, left = mid, mid + 1
else:
right = mid - 1
#已经求出第M大为x,求解前M大和
#大于x的数字个数num,数字之和ans
num, ans = 0, 0
for i in range(1, n + 1):
if a[i] < x:
continue
#找一个最大的满足k:a[i] - k * b[i] > x
k = (a[i] - x) // b[i]
if k * b[i] != (a[i] - x):
k += 1
#a[i] + a[i]-b[i] + ... +a[i]-(k-1)*b[i]
ans += (a[i] + a[i] - (k - 1) * b[i]) * k // 2
num += k
ans += (m - num) * x
print(ans)
9.《最长不下降子序列》真题练习(dp,线段树)
初步思想:首先通过dp算出最长递增子序列,然后从最长结尾倒推回去看是否有区间满足<=k,有的话+k就行了。(不要这道题分,不会)
正解:dp最长不下降子序列,线段树
标程:
import sys
input = lambda: sys.stdin.buffer.readline().rstrip()
maxn = 100010
b = [0] * maxn
dp = [0] * maxn
tree = [0] * (maxn * 4)
#权值线段树,维护dp数组,不需要初始化
#更新下标为x,与val取max
def update(o, l, r, x, val):
if l == r:
tree[o] = max(tree[o], val)
return
mid = (l + r) >> 1
if x <= mid:
update(o << 1, l, mid, x, val)
else:
update(o << 1 | 1, mid + 1, r, x, val)
tree[o] = max(tree[o << 1], tree[o << 1 | 1])
#查询区间[L,R]最大值
def query(o, l, r, L, R):
if L <= l and r <= R:
return tree[o]
mid = (l + r) >> 1
ans = 0
if L <= mid:
ans = max(ans, query(o << 1, l, mid, L, R))
if R > mid:
ans = max(ans, query(o << 1 | 1, mid + 1, r, L, R))
return ans
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
if n == k:
print(n)
else:
#离散化
S = set(a) #去重
b = list(S) #排序
tot = len(b)
b.sort()
for i in range(len(a)):
left, right, ans = 0, tot - 1, -1
while left <= right:
mid = (left + right) >> 1
if b[mid] >= a[i]:
ans = mid
right = mid - 1
else:
left = mid + 1
a[i] = ans + 1
a = [0, *a]
ans = 0
#从前往后遍历a,放入权值线段树中
for i in range(1, n + 1):
dp[i] = query(1, 1, tot, 1, a[i]) + 1
update(1, 1, tot, a[i], dp[i])
#重新清空权值线段树
tree = [0] * (maxn * 4)
for i in range(n, k, -1):
#a[i-k+1] ... a[i]相等 均等于a[i-k]
#最后一段要注意:查询的是[a[i-k],tot]中的最大值
ans = max(ans, dp[i - k] + k - 1 + query(1, 1, tot, a[i - k], tot) + 1)
tmp = query(1, 1, tot, a[i], tot) + 1
ans = max(ans, tmp + k)
update(1, 1, tot, a[i], tmp)
print(ans)
10.《最优清零方案》真题练习(暴力枚举,线段树维护)
初步思路:循环遍历就行,优先操作2,其次操作1。
正解:思路类似,从左到右枚举遍历,但是用线段树维护
标程:
maxn = 1000000 + 10
tree_mi = [0] * (maxn * 4)
tree_add = [0] * (maxn * 4)
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
a = [0, *a]
#线段树模板
#利用左右儿子信息更新节点o
def push_up(o):
tree_mi[o] = min(tree_mi[o << 1], tree_mi[o << 1 | 1])
#利用节点o的lazy标记add更新左右儿子
def push_down(o):
if tree_add[o] != 0:
tree_add[o << 1] += tree_add[o]
tree_mi[o << 1] += tree_add[o]
tree_add[o << 1 | 1] += tree_add[o]
tree_mi[o << 1 | 1] += tree_add[o]
tree_add[o] = 0
#建树
def build(o, l, r):
tree_add[o] = 0
if l == r:
tree_mi[o] = a[l]
return
mid = (l + r) >> 1
build(o << 1, l, mid)
build(o << 1 | 1, mid + 1, r)
push_up(o)
#查询区间[L,R]的最小值
def query(o, l, r, L, R):
if L <= l and r <= R:
return tree_mi[o]
push_down(o);
mid = (l + r) >> 1
ans = 1000000000;
if L <= mid:
ans = min(ans, query(o << 1, l, mid, L, R))
if R > mid:
ans = min(ans, query(o << 1 | 1, mid + 1, r, L, R))
return ans
#区间更新[L,R]统一加上val
def update(o, l, r, L, R, val):
if L <= l and r <= R:
tree_mi[o] += val
tree_add[o] += val
return
push_down(o);
mid = (l + r) >> 1
if L <= mid:
update(o << 1, l, mid, L, R, val)
if R > mid:
update(o << 1 | 1, mid + 1, r, L, R, val)
push_up(o);
build(1, 1, n)
ans = 0
for i in range(1, n - k + 2):
#查询区间[i, i+k-1]的最小值
mi = query(1, 1, n, i, i + k - 1)
if mi == 0: #无法进行区间消除
#res表示当前的a[i]
res = query(1, 1, n, i, i)
#把当前的a[i]置为0
update(1, 1, n, i, i, -res)
ans += res
else:
ans += mi
#区间消除
update(1, 1, n, i, i + k - 1, -mi)
#res表示当前的a[i]
res = query(1, 1, n, i, i)
#把当前的a[i]置为0
update(1, 1, n, i, i, -res)
ans += res
for i in range(n - k + 2, n + 1):
ans += query(1, 1, n, i, i)
print(ans)