发布时间：2025-04-12

前言

仅个人回忆，不保证正确性 貌似都是典题，针对python的长代码模拟题也没有，一小时速通了，希望不要翻车。

更新：B、G翻车了。。其他应该是对的

A

答案：103

B

应该是按长度排序，然后从按顺序遍历判断 但是刚刚想了一下，我当时是按字典序排的。。。白给5分

C

打印Q

import sys
from collections import defaultdict
from math import inf
input=lambda:sys.stdin.readline().strip()
read=lambda:map(int,input().split())


w,h,v=read()
for i in range(1,h+w+1):
    for j in range(1,v+w+1):
        if i<=h:
            if j<=w:print('Q',end='')
        else:print('Q',end='')
    print()

D

lqb的六种排列都是合法的，求最大分割数 很明显的dp，想了想贪心应该也行

import sys
from collections import defaultdict
from math import inf
input=lambda:sys.stdin.readline().strip()
read=lambda:map(int,input().split())

t='blq'
s=input()

n=len(s)
s=' '+s
def check(a,b,c):
    tmp=''.join(sorted([a,b,c]))
    return True if t==tmp else False
dp=[-inf]*(n+1)
dp[0]=0

for i in range(n):
    dp[i+1]=max(dp[i+1],dp[i])
    if i+3<=n and check(s[i+1],s[i+2],s[i+3]):dp[i+3]=max(dp[i+3],dp[i]+1)

print(dp[n])

E

给定$n$,求两个向量的点积$A \cdot B \leq n$，四个点的坐标都是正整数

• $1\leq n \leq 2^{20}$

• 实际求$x_1x_2+y_1y_2 \leq n$

• 定义$cnt_i$为两个数相乘小于等于$i$的个数，这很容易用枚举第一个数$i$，那么第二个数$j$的范围就是$\frac{n}{i}$，$\sum_{i=1}^n \frac{n}{i}=n \lg n$，令$cnt[ij]++$,然后再一遍前缀和累加即可

• 再用一次调和级数枚举$x_1=i,x_2=j$，那么累加答案$ans+=cnt[n-ij]$

• 复杂度$O(n \log n)$

import sys
from collections import defaultdict
from math import inf
input=lambda:sys.stdin.readline().strip()
read=lambda:map(int,input().split())

n=int(input())

cnt=[0]*(n+1)
for i in range(1,n+1):
    for j in range(1,n+1):
        if i*j>n:break
        cnt[i*j]+=1
for i in range(1,n+1):cnt[i]+=cnt[i-1]
ans=0
for i in range(1,n+1):
    for j in range(1,n+1):
        if i*j>n:break
        ans+=cnt[n-i*j]

print(ans)

F

• 等间隔的最长上升序列
• $n \leq 5000$
• 第一维枚举间隔$i$，第二维枚举$j$,那么$j\%i$相同的位置放到同一个数组，此时他们间隔相等，对每个对应的数组直接求

import sys
from collections import defaultdict
from math import inf
input=lambda:sys.stdin.readline().strip()
read=lambda:map(int,input().split())

n=int(input())
a=list(read())
ans=0
for i in range(1,n+1):
    b=[[] for _ in range(i)]
    for j in range(n):
        b[j%i].append(a[j])
    for j in range(i):
        cnt=0
        for k in range(len(b[j])):
            if k==0:
                cnt+=1
                ans=max(ans,cnt)
                continue
            if b[j][k]>b[j][k-1]:
                cnt+=1
                ans=max(ans,cnt)
                continue
            cnt=1
            ans=max(ans,cnt)
print(ans)

G

给一个排列，每次可以交换相邻的两个数，求使得他们升序的最小操作数

赛时思路：

• 经典结论：冒泡排序的操作次数=逆序对个数
• 树状数组求逆序对即可
• 复杂度：$O(n \log n)$

刚刚看了流出的pdf，好像读错题了，可以交换任意位置。。。我看成了交换相邻位置，错麻了。。最坏情况是0分。。

正解：

• 找出置换环的数量为$m$,答案为$n-m$

import sys
from collections import defaultdict
from math import inf
input=lambda:sys.stdin.readline().strip()
read=lambda:map(int,input().split())

n=int(input())
a=[0]+list(read())
vis=[0]*(n+1)
cnt=0
for i in range(1,n+1):
    if vis[i]:
        continue
    x=i
    cnt+=1
    while not vis[x]:
        vis[x]=1
        x=a[x]

print(n-cnt)

H

求$\sum_{i=1}^n \sum_{j=i+1}^n (a_i \oplus a_j)(j-i)$

• 很容易想到拆位，定义$cnt_{0/1,i}$为第$i$位$0/1$的个数，$Sum_{0/1,i}$为第$i$位的下标和
• 计算答案贡献，假设当前数下标为$i$，第$j$位为$c$,那么只有前面的数的第$j$位为$c \oplus 1$才有贡献
• 那么$ans+=(cnt_{c \oplus 1,j} \cdot i-Sum_{c \oplus 1,j})\cdot 2^j$
• 然后更新两个数组
• 复杂度$O(n \log n)$

import sys
from collections import defaultdict
from math import inf
input=lambda:sys.stdin.readline().strip()
read=lambda:map(int,input().split())

cnt=[[0]*25 for _ in range(2)]
Sum=[[0]*25 for _ in range(2)]
n=int(input())
a=[0]+list(read())
ans=0
for i in range(1,n+1):
    for j in range(22):
        c=a[i]>>j&1
        ans+=(cnt[c^1][j]*i-Sum[c^1][j])*(1<<j)
        cnt[c][j]+=1
        Sum[c][j]+=i

print(ans)

补题OJ：洛谷

书架还原和最长字符串翻车了，书架白给20分有点痛，75分不知道能不能省一。。