米哈游笔试 0914

1.寻找k个"mihoyo"的最短子串

n, k = list(map(int, input().split()))
s = input()
target = 'mihoyo'


def func(s):
    if n < k * 6:
        print(-1)
        return
    elif target * k in s:
        idx = s.find(target * k, 0, n)
        print(idx, idx+6 * k-1)
        return
    else:
        l = 0
        r = 6
        count = k
        length = -1
        idx = -1
        while r <= n:
            while r <= n and count != 0:
                # 窗口滑动
                if s[r - 6:r] == target:
                    count -= 1
                    r += 6
                else:
                    r += 1
            if count == 0:
                if length == -1:
                    length = r - l-6
                    idx = l
                else:
                    if r - l-6 < length:
                        length = r - l-6
                        idx = l
                l=r-12
                count=k-1
        if length==-1:
            print(-1)
        else:
            # print(idx,length)
            print(idx, idx+length-1)
        return
func(s)

2.猜数：可能的值的数量

n=int(input())
nums=list(map(int,input().split()))
x,y=list(map(int,input().split()))
nums.sort()
if y==n&nbs***bsp;x==n:
    print("infinity")
else:
    maxv=nums[y]
    minv=nums[y-1]+1
    if maxv>=minv:
        pos=maxv-minv+1
        print(pos)
    else:
        print(0)

3.树：连通块的数量（暂时按二叉树做的，忘记题目有没有限定树的类别了。若为多叉树，不适用）

if __name__=='__main__':
    sum=0
    def dfs(edges,start,end):
        global sum
        lis=[]
        for (x,y) in edges:
            if x==start and y!=end:
                lis.append(y)
            elif y==start and x!=end:
                lis.append(x)
        if len(lis)==1:
            tmp=dfs(edges,lis[0],start)
            if lis[0]%2!=start%2:
                tmp+=1
            sum+=tmp
            return tmp
        elif len(lis)==2:
            h=dfs(edges,lis[0],start)+dfs(edges,lis[1],start)
            if lis[0]%2==start%2 and lis[1]%2==start%2:
                h-=1
            elif lis[0]%2!=start%2 and lis[1]%2!=start%2:
                h+=1
            sum+=h
            return h
        elif len(lis)==0:
            sum+=1
            return 1

    n,x=list(map(int,input().split()))
    edges=[]
    for i in range(n-1):
        edge=list(map(int,input().split()))
        edges.append(edge)
    dfs(edges,x,0)
    print(sum)

#米哈游##米哈游笔试#