汗流浃背的一场,前一个小时出了2题,差点崩溃,还好稳定下来还是ak了

小红的葫芦

from collections import Counter
a=list(map(int,input().split()))
cnt=Counter(a)
if len(cnt)==2 and sorted(cnt.values())==[2,3]:
    print("YES")
else:
    print("NO")

按题意模拟

茉茉的密码

n=int(input())
cnt=[0]*26
for _ in range(n):
    s=sorted(set(list(input())))
    for i in s:
        cnt[ord(i)-ord("a")]+=1
for i in range(26):
    if cnt[i]==n:
        print(chr(ord("a")+i))
        exit()

脑筋急转弯,所有字符串的公共子串,那只需要一个字母就可以了

苗苗的气球

n=int(input())
s=list(map(int,input().split()))
mx=max(s)
tot=sum(s)
if n==2 and s[0]==s[1]:
    print(0)
elif mx>=tot-mx:
    print(1)
elif tot%2==1:
    print(n)
else:
    ans=0
    for i in s:
        if i>1:
            ans+=1
    print(ans)

众数

先把恰好有两种小球,且数量相同的情况特判掉,这个一定没有剩余

接着来检查众数,如果众数的个数比其他所有数字加起来都大,那么其他数一定没机会留下,有且只有众数能留下

然后是奇数的情况,奇数一定会留一个数,所以每种数字都有机会留下

最后是偶数的情况,偶数就不一定能留了,偶数想要有数留下,那留下的一定是若干个相同的数字,所以检查出现次数大于1的数

萌萌的好数

table=[13, 23, 43, 53, 73, 83, 103, 113, 133, 143]
def check(mid):
    cnt=mid-mid//3
    if mid>=13:
        k=(mid-13)//30
        cnt-=1+k*2
        if 13+k*30+10<=mid:
            cnt-=1
    return cnt
t=int(input())
for _ in range(t):
    n=int(input())
    l=0
    r=int(1e20)
    while l+1!=r:
        mid=(l+r)//2
        if check(mid)>=n:
            r=mid
        else:
            l=mid
    print(r)

看的出来出题人n=100就是专门卡数位dp的,我还是不死心t了两发才来找正解

第k个数这种描述肯定可以无脑套个二分,多个log就多吧,能过就行

二分了以后就变成判定前n个数里有多少个好数

先减掉3的倍数,即n//3

然后再减掉不是3的倍数里,末尾有3的数字,打个表可以看出来,从13开始,+10 +20 +10 +20 这个样子出现的

我们以30为周期,检查一下有几个数,最后在+10看看还有没有,都减掉即可

茜茜的计算器

mod=10**9+7
n=int(input())

if n%2==0:
    m=n//2
    x=pow(4,n,mod)
    y=pow(4,m,mod)
    xy=pow(2,m,mod)
    print((x+y-xy)%mod)
else:
    m=n//2
    x=pow(4,n,mod)
    y=pow(4,m,mod)*2
    xy=pow(2,m,mod)*2
    print((x+y-xy)%mod)

就是这道题搞了心态,我一直把1当作y轴对称来做的,而且还能过样例,卡了好久

其实就一句话   关于x轴对称的数字个数 + 关于y轴对称的数字个数 - 同时关于x轴和y轴对称

关于x轴,可以填 0 1 3 8

关于y轴,前一半可以填 0 1 2 5 8 后一半对称的是固定的,0 1 5 2 8

同时关于x轴和y轴,只能填0 8

n是奇数的时候,中间要少填个2 5 

花花的地图

from heapq import  heapify,heappop,heappush
inf=1<<60
m,n=map(int,input().split())
g=[input() for _ in range(m)]
cos=list(map(int,input().split()))
dis=[[[inf]*2 for _ in range(n)] for _ in range(m)]
dis[0][0][0]=0
dis[0][0][1]=cos[0]
h=[(0,0,0,0),(cos[0],0,0,1)]
while h:
    d,x,y,tmp=heappop(h)
    if d>dis[x][y][tmp]:
        continue
    for nx in [x-1,x+1]:
        if 0<=nx<m:
            if g[nx][y]=="#":
                ntmp=1
                nd=d+int(tmp==0)*cos[y]
            else:
                ntmp=tmp
                nd=d
            if nd<dis[nx][y][ntmp]:
                dis[nx][y][ntmp]=nd
                heappush(h,(nd,nx,y,ntmp))        
    for ny in [y-1,y+1]:
        if 0<=ny<n:
            if g[x][ny]=="#":
                ntmp=1
                nd=d+cos[ny]
            else:
                ntmp=0
                nd=d
            if nd<dis[x][ny][ntmp]:
                dis[x][ny][ntmp]=nd
                heappush(h,(nd,x,ny,ntmp)) 
print(min(dis[-1][-1]))

写了个分层图最短路

dis[x][y][0] 表示停在(x,y)点,第y列不删除的最小代价

dis[x][y][1] 表示停在(x,y)点,第y列删除的最小代价

dij应该没什么好讲的