发布时间：2025-03-08

题目链接

A

我方最大次大和对方次小最小比

import sys
from math import sqrt,inf
from functools import lru_cache
input=lambda:sys.stdin.readline().strip()
sys.setrecursionlimit(1000000)



v=list(map(int,input().split()))
a=list(map(int,input().split()))
v.sort()
a.sort()
if a[2]>v[1] and a[1]>v[0]:
    print("Yes")
else:
    print("No")

B

贪心，两个n合成一个y

import sys
from math import sqrt,inf
from functools import lru_cache
input=lambda:sys.stdin.readline().strip()
sys.setrecursionlimit(1000000)



n=int(input())
s=input()
ans=0
i=0
while i<n:
    if s[i]=='y':
        ans+=1
        i+=1
        continue
    j=i
    while j+1<n and s[j+1]==s[j]:j+=1
    ans+=(j-i+1)//2
    i=j
    i+=1
print(ans)

C

预处理前缀后缀，拼接即可

import sys
from math import sqrt,inf
from functools import lru_cache
input=lambda:sys.stdin.readline().strip()
sys.setrecursionlimit(1000000)



n=int(input())
s=['']*n
for i in range(n):
    s[i]=input()

suf=[0]*(n+1)
pre=[0]*(n+1)
ans=0
for i in range(n-1,-1,-1):
    if i==n-1 or s[i+1]==s[i]:
        suf[i]=suf[i+1]+1
    else:
        suf[i]=1

for i in range(n):
    if i==0:
        pre[i]=1
    elif s[i]==s[i-1]:
        pre[i]=pre[i-1]+1
    else:
        pre[i]=1
    if i+2<n and s[i]==s[i+2]:
        ans=max(ans,pre[i]+suf[i+2])

print(ans)

D

因为无后效性，直接dp即可，判断当前时刻有墙仅当$x+y-2\geq v$

import sys
from math import sqrt,inf
from functools import lru_cache
input=lambda:sys.stdin.readline().strip()
sys.setrecursionlimit(1000000)



n,m=map(int,input().split())

a=[[]]
for _ in range(n):
    a.append([0]+list(map(int,input().split())))

dp=[[-inf]*(m+1) for _ in range(n+1)]
t=[[inf]*(m+1) for _ in range(n+1)]
q=int(input())
while q:
    q-=1
    x,y,v=map(int,input().split())
    t[x][y]=v
ans=0
for i in range(1,n+1):
    for j in range(1,m+1):
        if i==1 and j==1:
            dp[i][j]=a[i][j]
            ans=a[i][j]
            continue
        if t[i][j]!=inf:
            if i+j-2>=t[i][j]:continue
        dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j]
        ans=max(ans,dp[i][j])
        # print(i,j,a[i][j])
print(ans)

E

• $st[x]=True$当且仅当$x$处有线段
• 假设长是竖着的，如下图所示，当前位置为$i$，枚举高度$j$从$k+1$到$m$，那么对于后面的$pos，i \lt pos$，满足$j-(pos-i)=k,pos=i+j-k$,会产生一个矩形，并且可以上下移动，因为高度为$j$，因此上下移动的贡献为$m-j+1$，因此对于当前$i$而言贡献为$\sum_{j=k+1}^m st[i+j-k]\cdot(m-j+1)$
• 如果是横着的，那么竖着枚举宽度，容易得贡献为$\sum_{j=1}^mst[i+j+k]\cdot(m-j+1)$
• 总贡献为$\sum_{st[i]=True}(\sum_{j=k+1}^m st[i+j-k]\cdot(m-j+1)+\sum_{j=1}^mst[i+j+k]\cdot(m-j+1))$
• 对于前面一部分$pos$的范围为$[i+1,i+m-k]$，区间为定长，因此可以考虑滑动窗口从后往前维护答案，对于每一个合法位置的贡献，容易发现，每向前移动一单位，每个合法产生的贡献恰好减1，当移出区间时这个位置贡献恰好为0，第一次进入区间时的贡献为$m-k$，因此只需要维护区间内合法的位置数量即可转移
• 后面一部分同理
• 赛后发现，上面式子是一个卷积的形式，也可以直接套板子fft

import sys
from math import sqrt,inf
from functools import lru_cache
input=lambda:sys.stdin.readline().strip()
sys.setrecursionlimit(1000000)

N=10**5+10
a=[False]*N
n,m,k=map(int,input().split())

tmp=list(map(int,input().split()))
for x in tmp:a[x]=True

ans=0
mxr,cnt,val=N-1,0,0
for i in range(N-1,0,-1):
    if mxr>i+m-k:
        if a[mxr]:
            cnt-=1
        mxr-=1
    if a[i]:ans+=val
    # if(i<=10):print(i,val)
    val-=cnt
    if a[i]:
        cnt+=1
        val+=m-k
# print(ans)
mxr,cnt,val=N-1,0,0
for i in range(N-1,0,-1):
    if mxr>i+k+m:
        if a[mxr]:
            cnt-=1
        mxr-=1
    if a[i]:ans+=val
    val-=cnt
    if i+k<N and a[i+k]:
        cnt+=1
        val+=m
print(ans)

F (数论,EXGCD)

• 首先如果$n=k$数组元素不相等可以直接输出$-1$
• 假设最终数组元素均为$x$，那么可以得到$\sum_{i=1}^n(a_i-x) \mod k=0$
• 因此$\sum_{i=1}^na_i-nx=ky$，令$\sum_{i=1}^na_i=s$，则$nx+ky=s$这是一个线性同余方程，直接用exgcd解,$a=n,b=k$
• 令$g=\gcd(a,b),a_1=\frac{a}{g},b_1=\frac{b}{g}$通解为$x+tb_1,y-ta_1$,前面的是最终元素的值，后面的是最小操作次数
• 首先最终元素要小于等于$\min a_i$,即$x+tb_1 \leq \min a_i$,$t \leq \frac{\min a_i-x}{b_1}$
• 操作次数要大于等于$0$,即$y-ta_1 \geq 0$，$t \leq \frac{y}{a_1}$
• 最后最大值减去$x$必须小于等于操作次数才是合法的，即$\max a_i-(x+tb_1) \leq y-ta_1$,$t \leq \frac{y+x- \max a_i}{a_1-b_1}$
• 上面三个值取min就是t能达到的最大上界，此时操作数最小

import sys
from math import sqrt,inf
from functools import lru_cache
input=lambda:sys.stdin.readline().strip()
read=lambda:map(int,input().split())
sys.setrecursionlimit(1000000)

def exgcd(a,b):
    if b==0:
        return a,1,0
    d,x,y=exgcd(b,a%b)
    return d,y,x-a//b*y

n,k=read()
v=list(read())

v.sort()
if v[0]==v[-1]:
    print(0)
    exit(0)
if n==k:
    print(-1)
    exit(0)

s=sum(v)
# s-n*x=k*y
# n*x+k*y=s
a,b,x,y=n,k,0,0
g,x,y=exgcd(a,b)
if s%g!=0:
    print(-1)
    exit(0)

x*=s//g
y*=s//g
a1,b1=a//g,b//g
# x+t*b1<=a[0],y-t*a1>=0
# t<=(a[0]-x)/b1,t<=y/a1
t=min((v[0]-x)//b1,y//a1)

# a[-1]-(x+t*b1)<=y-t*a1
# t*(a1-b1)<=y+x-a[-1]
# t<=y+x-a[-1]/(a1-b1)
t=min(t,(y+x-v[-1])//(a1-b1))

print(y-t*a1)

```