蓝桥杯刷题--python-29-hashmap

1402. 星空之夜 - AcWing题库

def dfs(a,b):
    p.append((a,b))
    q[a][b]="0"

    for x in range(a-1,a+2):
        for y in range(b-1,b+2):
            if x>=0 and x<h and y>=0 and y<w and q[x][y]=="1":
                dfs(x,y)

def get_dist(a,b):
    dx=a[0]-b[0]
    dy=a[1]-b[1]
    return ((dx*dx)+(dy*dy))**0.5
def get_hash(n,p):
    sum=0
    for i in range(n):
        for j in range(i):
            sum+=get_dist(p[i],p[j])
    return sum

def get_id(p):
    global k
    n=len(p)
    key=round(get_hash(n,p),6)
    if key not in d:
        d[key]=chr(k)
        k+=1
    c=d[key]
    return c

w=int(input())
h=int(input())
q=[]
for i in range(h):
    q.append(list(input()))
k=ord("a")
d={}

for i in range(h):
    for j in range(w):
        if q[i][j]=="1":
            p=[]
            dfs(i,j)
            id =get_id(p)
            for x,y in p:
                q[x][y]=id

for i in range(h):
    print(''.join(q[i]))

 1221. 四平方和 - AcWing题库

n=int(input())

i=0

h={}
while(i*i<=n):
    j=i
    while (j*j+i*i<=n):
        if (j*j+i*i) not  in h:
            h[j*j+i*i]=(i,j)

        j+=1
    i+=1
a=0
t=0
while(a*a<=n):
    b=a
    while (a*a+b*b<=n):
        s=n-(a*a+b*b)
        if s in h:
            print(a,b,h[s][0],h[s][1])

            t=1
            break

        b+=1
    if t:
        break
    a+=1
 

 

n=int(input())

class Node:
    def __init__(self,z,x,y):
        self.z=z
        self.x=x
        self.y=y
ans=[]
def erfen(x):
    l=0;r=len(ans)-1
    while(l<=r):
        mid=l+r>>1
        if ans[mid].z <x:
            l=mid+1
        elif ans[mid].z >x:
            r=mid-1
        else:
            return mid
    return False



i=0
while(i*i<=n):
    j=i
    while (j*j+i*i<=n):
        ans.append(Node(j*j+i*i,i,j))


        j+=1
    i+=1
ans.sort(key=lambda x: x.z)


a=0
t=0
while(a*a<=n):
    b=a
    while (a*a+b*b<=n):
        s=n-(a*a+b*b)
        tmp=erfen(s)
        if tmp:
            print(a,b,ans[tmp].x,ans[tmp].y)

            t=1
            break

        b+=1
    if t:
        break
    a+=1