百度站长平台论坛_西安企业建站系统模板_经典软文广告_最新实时新闻

前言

仅个人回忆，不保证正确性
貌似都是典题，针对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]=0for 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\le n$，四个点的坐标都是正整数

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

• 实际求$x_1{x}_2+y_1{y}_2\le n$

• 定义$cn{t}_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:breakcnt[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:breakans+=cnt[n-i*j]print(ans)

F

• 等间隔的最长上升序列
• $n\le 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=0for k in range(len(b[j])):if k==0:cnt+=1ans=max(ans,cnt)continueif b[j][k]>b[j][k-1]:cnt+=1ans=max(ans,cnt)continuecnt=1ans=max(ans,cnt)
print(ans)

G

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

• 经典结论：冒泡排序的操作次数=逆序对个数
• 树状数组求逆序对即可
• 复杂度：$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())class Fenwick:def __init__(self,n):self.c=[0]*(n+1)self.n=ndef add(self,x,y):while x<=self.n:self.c[x]+=yx+=x&-xdef query(self,x):ans=0while x>0:ans+=self.c[x]x-=x&-xreturn ansn=int(input())
a=list(read())
t=Fenwick(n+10)
ans=0
for i in range(n-1,-1,-1):ans+=t.query(a[i]-1)t.add(a[i],1)print(ans)

刚刚看了流出的pdf，好像读错题了，可以交换任意位置。。。
那就是置换环的数量为$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]:continuex=icnt+=1while not vis[x]:vis[x]=1x=a[x]print(n-cnt)

H

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

• 很容易想到拆位，定义$cn{t}_{0/1,i}$为第$i$位$0/1$的个数，$Su{m}_{0/1,i}$为第$i$位的下标和
• 计算答案贡献，假设当前数下标为$i$，第$j$位为$c$,那么只有前面的数的第$j$位为$c\oplus 1$才有贡献
• 那么$ans+=(cn{t}_{c\oplus 1,j}\cdot i-Su{m}_{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&1ans+=(cnt[c^1][j]*i-Sum[c^1][j])*(1<<j)cnt[c][j]+=1Sum[c][j]+=iprint(ans)