这周没什么人写题解，那就我来写一下吧，不会排版xjb写的，大家xjb看一下就行了
a题
n=int(input()) res=0 while n%10!=0: n+=1 res+=1 print(res)末尾有0，那么就是整除10，一直自增直到整除10即可
b题 模运算
s=input() res=t=0 for i in s: t=(t*10+int(i))%9 if t==0: res+=1 print(res)删掉一个后缀，也就是检查所有的前缀形成的数字是否能整除9
讲不太来，可以去lc2575下面看一下
c题 构造
n,k=map(int,input().split())
res=[]
ch=0
while k:
if k==1:
res+=[ch]*2
k-=1
else:
l=0;r=n
while l+1!=r:
mid=(l+r)//2
if mid*(mid-1)//2>k:
r=mid
else:
l=mid
res+=[ch]*l
k-=l*(l-1)//2
ch=(ch+1)%26
while len(res)<n:
res+=[ch]
ch=(ch+1)%26
print("".join([chr(ord("a")+i) for i in res]))
恰好有k个长度大于1的回文子串，这题我感觉我和大多数人的脑回路都不一样
填还是一样的，按abcd...循环着填就可以了，主要是要构造恰好k个
一个长度为x的字母完全相同子字符串，会有x(x-1)/2个大于1的回文串
直接贪心的每次都填最多的就可以了，每次二分找到这个最大值
d题 贪心
n,k=map(int,input().split()) arr=list(map(int,input().split())) d=[] for i in range(1,n): d.append(abs(arr[i]-arr[i-1])) d.sort() if d[-1]<k: print(1) elif d[-1]==k: print(0) else: res=0 for i in d: if i>k: res+=(i+k-1)//k-1 print(res)先把每相邻两项的差的绝对值拿出来放一起
如果最大值小于k，那么需要一次
如果最大值等于k，那么需要0次
如果最大值大于k，那么把所有大于k的项x取出来
如果恰好是k的倍数，那么中间需要分成x//k份，否则需要分成x//k+1份
合起来写就是(x+k-1)//k份
一个东西分成(x+k-1)//k份，那么就需要切(x+k-1)//k-1刀
e题 调和级数+dp
n=int(input())
a=list(map(int,input().split()))
cnt=[0]*(2*10**5+1)
for i in a:
cnt[i]+=1
dp={}
res=max(cnt)
for i in range(1,2*10**5+1):
if cnt[i]:
for j in range(2*i,2*10**5+1,i):
if cnt[j]:
k=j//i
if (i,k) not in dp:
t=1
else:
t=dp[(i,k)]
res=max(res,t+1)
dp[(j,k)]=t+1
print(res)
首先需要知道一个知识点，从1到n，每次枚举他们的倍数，每个数一直枚举到大于n停下
总的复杂度是nlogn的，具体可以搜一下调和级数
也就是说如果n是1e5，那么枚举出他们的所有倍数大概需要枚举1e6次，n是1e6，那么就要枚举1e7次
要构成等比数列，一种公比是1，那么我们开头的时候计个数，然后把频率最大值当作初始答案
另一种公比是多少我们不知道，但是肯定大于1的，所以我们从1到2e5，每次枚举他们的倍数，就可以算出这个公比，然后用哈希表+元组dp即可
复杂度是严格的nlogn的
复杂度是严格的nlogn的
f题 离线回答+树状数组
from collections import deque,defaultdict
class BIT:
"""单点修改,区间和查询"""
__slots__ = "size", "bit", "tree"
def __init__(self, n: int):
self.size = n
self.bit = n.bit_length()
self.tree = [0]*(n+1)
def add(self, index: int, delta: int) -> None:
# index 必须大于0
while index <= self.size:
self.tree[index]+=delta
index += index & -index
def _query(self, index: int) -> int:
res = 0
while index > 0:
res += self.tree[index]
index -= index & -index
return res
def query(self, left: int, right: int) -> int:
return self._query(right) - self._query(left - 1)
n,q=map(int,input().split())
arr=[0]+list(map(int,input().split()))
d=defaultdict(deque)
for i in range(1,n+1):
d[arr[i]].append(i)
query=[[] for _ in range(n+1)]
res=[0]*q
bit=BIT(n+5)
for i in range(q):
l,r=map(int,input().split())
query[r].append((i,l))
for r in range(1,n+1):
while r-d[arr[r]][0]>1:
x=d[arr[r]].popleft()
bit.add(x,1)
while query[r]:
i,l=query[r].pop()
res[i]=bit.query(l,r)
for i in res:
if i:
print("YES")
else:
print("NO")
给定一个数组，多次询问一个区间[l,r]，问该区间是否有长度严格大于2的回文子序列
其实我们只需要求是否有长度为3的回文子序列即可，那么只要有一个数字，出现了两次，且这两次的间隔大于1即可
先预处理出每个数字的出现位置，分别放在一个队列里
然后离线回答，把回答按右端点排序
从小到大遍历下标，对于该下标的数，左侧如果有与他距离大于1且还没出队列的，那么就出队，树状数组单点+1
然后批量回答该右端点的问题，如果区间的和大于0，则就有这样的回文子序列
g题 双指针+树状数组
class BIT: """单点修改,区间和查询""" __slots__ = "size", "bit", "tree" def __init__(self, n: int): self.size = n self.bit = n.bit_length() self.tree = [0]*(n+1) def add(self, index: int, delta: int) -> None: # index 必须大于0 while index <= self.size: self.tree[index]+=delta index += index & -index def _query(self, index: int) -> int: res = 0 while index > 0: res += self.tree[index] index -= index & -index return res def query(self, left: int, right: int) -> int: return self._query(right) - self._query(left - 1) sz=10**6+1 n,k=map(int,input().split()) a=list(map(int,input().split())) bit=BIT(sz+5) tot=0 for i in range(n): tot+=bit.query(a[i]+1,sz+2) bit.add(a[i],1) if tot<k: print(0) exit() bit2=BIT(sz+5) res=0 l=r=0 while r<n: tot-=bit._query(a[r]-1)+bit2.query(a[r]+1,sz+2) bit.add(a[r],-1) while tot<k: tot+=bit._query(a[l]-1)+bit2.query(a[l]+1,sz+2) bit2.add(a[l],1) l+=1 res+=r-l+1 r+=1 print(res+1)
求有多少个区间，删除以后剩下的部分逆序数大于等于k
首先求出原区间的逆序数，如果小于k，则无解
然后使用双指针，对左指针左侧部分，和右指针右侧部分各维护一个值域树状数组，设为b1和b2
右指针r右移时 逆序数 = 逆序数 - b1中小于a[r]的个数 - b2中大于a[r]的个数
左指针l右移时 逆序数 = 逆序数 + b1中小于a[l]的个数 + b2中大于a[l]的个数
最后还要加上删除空区间的答案
京公网安备 11010502036488号