汗流浃背的一场,前一个小时出了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应该没什么好讲的