【kickstart 2021 round C】前三题python题解

第一题：
题目：给定长度为N的字符串S，它是由字母表上的前K个字母构成，问字典序小于S且长度为N的回文字符串（由字母表上的前K个字母构成）有多少个？
解释：参考官方题解，计算多少个长度为N/2的字符串的字典序小于S[::math.ceil(N/2)]，这里计算的方法可采用将字符串转化为K进制数–>十进制数。【代码暂时只能过test set 1，正在查找错误】注：小于该字符串的字符串个数就是这个K进制数。

import math
T=int(input())
for tt in range(T):
    N,K=[int(s) for s in input().split()]
    ss=input()
    if N==1:
        ans=ord(ss)-97
    else:
        hh=math.ceil(N/2)
        s1=ss[:hh]
        mm=[]
        for ii in range(hh):
            mm.append(ord(s1[ii])-97)
        num=0
        for ii in range(hh-1,-1,-1):
            num+=mm[ii]*math.pow(K,hh-ii-1)
        if N%2==0:
            news=s1+s1[::-1]
        else:
            news=s1[:-1]+s1[::-1]
        map_s=[]
        map_news=[]
        for ii in range(N):
            map_s.append(ord(ss[ii])-97)
            map_news.append(ord(news[ii])-97)
        num_s=0
        num_news=0
        for ii in range(N-1,-1,-1):
            num_s+=map_s[ii]*math.pow(K,N-ii-1)
            num_news+=map_news[ii]*math.pow(K,N-ii-1)
        if num_s<=num_news:
            ans=num
        else:
            ans=num+1
        ans=ans%(1e9+7)
    print('Case #%d: %d' %(tt+1,ans))

第二题：
题目：求连续的自然数序列，首项为X，共N项，则末项为X+N-1，该序列的和为（2*X+N-1）N=2G，给定G，求有多少个这样的连续自然数序列。

T=int(input())
for tt in range(T):
    G=int(input())
    N=1
    ans=0
    while N*N<2*G:
        if 2*G%N==0:
            if (2*G/N+1-N)%2==0:
                ans+=1
        N+=1
    print('Case #%d: %d' %(tt+1,ans))

第三题：
题目：你和朋友玩石头剪刀布游戏，朋友的策略是统计你之前出石头剪刀布各项的频率，进而决定自己的当前行为（按概率）。赢和平各得到W分和E分，X为希望达到的T天后的得分平均期望，每天的W和E可能与之前不同，求每天的行为策略（不唯一）。
一开始题意理解错误，我以为朋友只有在有两项或三项概率相同的情况下才会按概率出（其余情况的行为是确定的），这样考虑只能过test 1，先分享这种解法，等我再好好理解下官方题解里如何记录行为矩阵再来更新。

T=int(input())
X=int(input())
for tt in range(T):
    W,E=[int(s) for s in input().split()]
    # everyday there should be output of 60 letters 
    num=W/3+(E/3)
    ans='R'
    map_={'R':1,'P':0,'S':0}
    dict1={'R':'S','P':'R','S':'P'}
    while num<X or len(ans)<60:
        if map_['R']==map_['P']==map_['S']:
            num+=W/3+E/3
            ans+='R'
            map_['R']+=1
        else:
            # max -> 1
            max_v=max(map_.values())
            max_num=0
            can=[]
            for i in ['R','P','S']:
                if map_[i]==max_v:
                    max_num+=1
                    can.append(i)
            if max_num==1:
                num+=W
                ans+=dict1[can[0]]
                map_[dict1[can[0]]]+=1
            else:
                num+=W/3+E/3
                ans+=dict1[can[0]]
                map_[dict1[can[0]]]+=1
            # max -> 2
    if len(ans)>60:
    	ans=ans[:60]
    print('Case #%d: ' %(tt+1), end='')
    print(ans)