2026.3.11 月考记录

从上学期就开始说的打比赛不要急是什么意思！
就是T2被卡了，以及T6交的前两发输出格式都不对。

泰波拿契數

n=int(input())
a=[0,1,1]
for i in range(3,n+1):
    a.append(a[i-1]+a[i-2]+a[i-3])
print(a[n])

稳定的符文序列

滑动窗口。每次只有右指针新添加的会影响，右移一位左移若干位。

s=input()
n=len(s)
a=[0]*26
t=set()
left=0
ans=0
cur=0
for i in range(n):
    a[ord(s[i])-ord('a')]+=1
    cur+=1
    while(a[ord(s[i])-ord('a')]>1):
        a[ord(s[left])-ord('a')]-=1
        cur-=1
        left+=1
    ans=max(ans,cur)
print(ans)

十进制整数的反码

n=int(input())
t=bin(n)[2:]
ans=""
for i in range(len(t)):
    if(t[i]=='0'):
        ans+='1'
    else:
        ans+='0'
print(int(ans,2))

亦可创建全1掩码然后按位异或。

Ultra-QuickSort

求逆序对。

ans=0
def merge(l,r):
    global ans
    if(l==r):
        return
    mid=(l+r)>>1
    merge(l,mid)
    merge(mid+1,r)
    i=l
    j=mid+1
    cur=l
    while(i<=mid and j<=r):
        if(a[i]>a[j]):
            ans+=(mid-i+1)
            a_new[cur]=a[j]
            cur+=1
            j+=1
        else:
            a_new[cur]=a[i]
            cur+=1
            i+=1
    while(i<=mid):
        a_new[cur]=a[i]
        cur+=1
        i+=1
    while(j<=r):
        a_new[cur]=a[j]
        cur+=1
        j+=1
    a[l:r+1]=a_new[l:r+1]
while(True):
    n=int(input())
    if(n==0):
        break
    a=[]
    ans=0
    a_new=[0]*n
    for i in range(n):
        t=int(input())
        a.append(t)
    merge(0,n-1)
    print(ans)

逃离紫罗兰监狱

from collections import deque
r,c,k=map(int,input().split())
a=[]
for i in range(r):
    t=input()
    a.append(t)
for i in range(r):
    for j in range(c):
        if(a[i][j]=='S'):
            x0=i
            y0=j
        elif(a[i][j]=='E'):
            x1=i
            y1=j
q=deque()
vis=[[[0 for _ in range(k+1)]for _ in range(c)]for _ in range(r)]
q.append([x0,y0,0,0])
vis[x0][y0][0]=1
dx=[0,1,0,-1]
dy=[1,0,-1,0]
flag=0
while(q):
    x,y,cur,l=q.popleft()
    if(flag==1):
        break
    for i in range(4):
        xx=x+dx[i]
        yy=y+dy[i]
        if(xx>=0 and xx<r and yy>=0 and yy<r):
            if(a[xx][yy]=='.'):
                if(vis[xx][yy][cur]==0):
                    vis[xx][yy][cur]=1
                    q.append([xx,yy,cur,l+1])
            elif(a[xx][yy]=='#'):
                if(cur<k and vis[xx][yy][cur+1]==0):
                    vis[xx][yy][cur+1]=1
                    q.append([xx,yy,cur+1,l+1])
            elif(a[xx][yy]=='E'):
                flag=1
                print(l+1)
                break
if(flag==0):
    print(-1)

狭路相逢

注意审题，幸存者包括人和怪。因此使用栈，幸存的怪一定在栈底。

from collections import deque
n=int(input())
a=list(map(int,input().split()))
s=deque()
for i in range(n):
    if(a[i]>0):
        s.append(a[i])
    else:
        tmp=-a[i]
        while(s):
            t=s[-1]
            if(t<0):
                break
            s.pop()
            if(t>tmp):
                t-=tmp
                s.append(t)
                tmp=0
                break
            else:
                tmp-=t
        if(tmp>0):
            s.append(-tmp)
print(len(s))
print(" ".join(map(str,s)))