---

title: Panasonic Programming Contest 2020题解 date: 2020-03-16 15:17:06 categories: 算法 tags: [python, 比赛]

Tasks

---

Task NameTime LimitMemory LimitAKth Term2 sec1024 MBSubmitBBishop2 sec1024 MBSubmitCSqrt Inequality2 sec1024 MBSubmitDString Equivalence2 sec1024 MBSubmitEThree Substrings2 sec1024 MBSubmitFFractal Shortest Path2 sec1024 MBSubmit

ABC

AB很水，就不多做解释了，就是B题题意有点绕。

C题注意一下精度问题，题意要求判断是否 $$sqrt(a)+sqrt(b)<sqrt(c)$$ 注意一下精度即可。

ort sys,math sys.setrecursionlimit(10**9) from collections import defaultdict IA = lambda: map(int,input().split()) IAS= lambda: map(str,input().split()) a,b,c=IA() temp=c-a-b if temp<0: print("No") else: if temp*temp>4*a*b: print("Yes") else: print("No")

D - String Equivalence

题意

同构：

两个字符串s和t

输入字符串长度n，要求你找到所有的长度为n且字典序最小的字符串。

样例解释：

n=1

a,b,c,......,z字典序最小的是a Input: 1 Output: a

n=2

aa,bb,cc,......,zz字典序最小的是aa ab,ac,ad,......,zy字典序最小的是ab Input: 2 Output: aa ab

n=3

aaa,bbb,ccc,......,zzz字典序最小的是aaa aab,aac,aad,......,zzy字典序最小的是aab aba,aca,ada,......,zyz字典序最小的是aba abb,acc,add,......,zyy字典序最小的是abb abc,abd,ade,......,zyx字典序最小的是abc Input: 3 Output: aaa aab aba abb abc

分析

多模拟几次可以发现规律：

字符串s = s1s2 … sN的条件为规范形式：

s1 = ask ≤ max {s1，…，sk−1} + 1（∀2≤k≤N）

即求一个序列，如果这个位置是 s[i]，那么 1~i-1 内一定出现过所有 ‘a’~s[i]-1 的所有字母

代码

import sys,math sys.setrecursionlimit(10**9) import itertools from collections import defaultdict IA = lambda: map(int,input().split()) IAS= lambda: map(str,input().split()) n=int(input()) def dfs(s,lim): if len(s)==n: print(s) else: for i in range(ord('a'),ord(lim)+1): if i==ord(lim): dfs(s+chr(i),chr(ord(lim)+1)) else: dfs(s+chr(i),lim) dfs('','a')

E题待补