[Python知识库]【kickstart 2021 round D】前三题python题解

第一题：
题目：给定一个3*3数组，中心位置数字缺失，问可以任意整数填充该位置的情况下最多可有多少个等差数列（行、列、对角线）
此处需注意下只能用整数填充

from collections import defaultdict
def diff(x):
    interval=[]
    n=len(x)
    for i in range(1,n):
        interval.append(x[i]-x[i-1])
    return interval
T=int(input())
for tt in range(T):
    grids=[]
    row1=[int(s) for s in input().split()]
    row2=[int(s) for s in input().split()]
    row3=[int(s) for s in input().split()]
    grids.append(row1)
    grids.append([row2[0],0,row2[1]])
    grids.append(row3)
    # top left bottom right 
    top=row1
    bottom=row3
    left=[grids[0][0],grids[1][0],grids[2][0]]
    right=[grids[0][2],grids[1][2],grids[2][2]]
    ans=0
    top_diff=diff(top)
    bottom_diff=diff(bottom)
    left_diff=diff(left)
    right_diff=diff(right)
    if top_diff[0]==top_diff[1]:
        ans+=1
    if bottom_diff[0]==bottom_diff[1]:
        ans+=1
    if left_diff[0]==left_diff[1]:
        ans+=1
    if right_diff[0]==right_diff[1]:
        ans+=1
    ## horizontal vertical diagonal*@
    hori=(grids[1][2]-grids[1][0])/2+grids[1][0]
    vert=(grids[2][1]-grids[0][1])/2+grids[0][1]
    diag1=(grids[2][2]-grids[0][0])/2+grids[0][0]
    diag2=(grids[2][0]-grids[0][2])/2+grids[0][2]
    dict1=defaultdict(int)
    ll=[]
    for i in [hori,vert,diag1,diag2]:
        if int(i)==i:
            ll.append(i)
    for i in ll:
        dict1[i]+=1
    if dict1:
        ans+=max(dict1.values())
    
    print('Case #%d: %d' %(tt+1,ans))

第二题：
题目：现有N个间隔，最多可切分C次（只能在整数处切分），问切分后最多可有多少个间隔。
唉，好难，看了两个人的做法还是没搞懂一些步骤

第三题：
题目：有不同难度的考试题（用interval表示每个set里难度的最小最大值），要分配给与之水平最接近的学生，考试题难度各不相同，且不可重复使用，求不同学生对应的考试题。
解释：将考试题难度用dict存储，将key排序后用二分找对应的试卷难度区间，而后需要更新dict，或是删除原有key，或是改变key对应的value以及增加新的key。
以下代码只能过test 1，大数据会TLE，感觉思路没错，回头试试C++（虽然估计不知道多久才能写出来，唉，这半年真是把过年学的C++忘没了）

from bisect import bisect_left 
from collections import defaultdict
T=int(input())
for tt in range(T):
    N,M=[int(s) for s in input().split()]
    mmap1=defaultdict(int)
    for i in range(N):
        a,b=[int(s) for s in input().split()]
        mmap1[a]=b
    student=[int(s) for s in input().split()]
    ans=[]
    for mm in range(M):
        x=student[mm]
        arr=list(mmap1.keys())
        arr.sort()
        index=bisect_left(arr, x, lo = 0, hi = len(arr))
        # x<arr[0]
        if index==0:
            c=arr[index]
            ans.append(c)
            if mmap1[c]-c>=1:
                end=mmap1[c]
                del mmap1[c]
                mmap1[c+1]=end
            else:
                del mmap1[c]
        elif index==len(arr):
            a=arr[index-1]  # 41
            if x>=mmap1[a]: # 60>50
                ans.append(mmap1[a])
                if mmap1[a]-a>=1:
                    mmap1[a]=mmap1[a]-1
                else:
                    del mmap1[a]
            else:
                ans.append(x)
                end=mmap1[a]
                if x-1>=a:
                    mmap1[a]=x-1
                else:
                    del mmap1[a]
                if end>=x+1:
                    mmap1[x+1]=end
        else:
            a=arr[index-1] #9 11
            b=arr[index] #41 50
            if x>mmap1[a]:
                if abs(x-mmap1[a])<=abs(x-b):
                    ans.append(mmap1[a])
                    if mmap1[a]-a>=1:
                        mmap1[a]=mmap1[a]-1
                    else:
                        del mmap1[a]
                else:
                    ans.append(b)
                    end=mmap1[b]
                    if end-b>=1:
                        mmap1[b+1]=end
                        del mmap1[b]
                    else:
                        del mmap1[b]
            else:
                ans.append(x)
                end=mmap1[a]
                if a<=x-1:
                    mmap1[a]=x-1
                else:
                    del mmap1[a]
                if end>=x+1:
                    mmap1[x+1]=end
            
        #print(mmap1)
    print('Case #%d: ' %(tt+1), end='')
    print(*ans,sep=' ')

真的是运气好才会做第一题，后面的真的。。少玩多学，赶紧补救。