Codeforces Round #382 (Div. 2) 继续python作死含树形DP

A - Ostap and Grasshopper

zz题能不能跳到每次只能跳K步不能跳到# 问能不能T-G 随便跳跳就可以了第一次居然跳越界0.0 *哦 WA1

n,k = map(int,input().split())

s = input()

i = 0

st = -1

def jump(st):

    while(st<n):

        st+=k

        if(st>=n or s[st]=='#'):

            return "NO"

        if(s[st]=='T' or s[st]=='G'):

            return "YES"

    return "NO"

while(i<n):

    if(s[i]=='T' or s[i]=='G'):

        if(st==-1):

            st=i

            break

    i+=1

print(jump(st))

B - Urbanization

均值之和最大贪心最大的放在小部分我们可以反证交换任意的人在两个city 会使情况变坏

n,x,y = map(int,input().split())

a = list(map(int,input().split()))

a.sort(reverse = True)

if(x>y):

    x,y = (y,x)

cx = 0

cy = 0

m,n = (x,y)

for i in a:

    if(x>0):

        x-=1

        cx+=i

    elif(y>0):

        y-=1

        cy+=i

    else:

        break

print(cx/m+cy/n)

C - Tennis Championship

相差一场的可以比赛那么最优的是相隔一次n,n+1 能产生n+2的所以就是斐波那契了这题ZZ

n = eval(input())

a = [0]*100

a[0] = 1

a[1] = 2

for i in range(2,100):

    a[i]=a[i-1]+a[i-2]

    if(a[i]>n):

        n = i-1

        break

print(n)

D - Taxes

问能分解为质数的最少个数答案就三种 1 2 3 我们先考虑本身为质数的 ans = 1
不是质数但是是偶数的哥德巴赫猜想 ans = 2

不是质数但是是奇数如果他能有两个质数组成那么其中一个一定是2 只需要判断n-2 是否为素数即可 ans = 2

否则的话就是ans = 3

然后就AC了...这套题的前四个有点水啊.... 但是还是累计wa3发

import math

n = eval(input())

def isP(n):

    lim = int(math.sqrt(n + 0.5))

    for i in range(2,lim+1):

        if(n%i==0):

            return False

    return True

ans = 0

if(isP(n)):

    ans = 1

elif(n%2==0):

    ans = 2

elif(isP(n-2)):

    ans = 2

else:

    ans = 3

print(ans)

AC代码

E - Ostap and Tree

mk一下树形DP

待补