Codeforces Round #597 (Div. 2)

A.Good ol' Numbers Coloring

题目大意：如果涂成黑色块的块数无限，输出infinite，如果有限，输出finite。

分析：只用判断一下gcd是不是等于1，如果等于1，输出finite，如果不等于1，输出infinite。

代码：

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


t = input()
t = int(t)
for i in range(t):
    a, b = input().split()
    a = int(a)
    b = int(b)
    if gcd(a, b) == 1:
        print("Finite")
    else:
        print("Infinite")

B.Restricted RPS

题目大意：石头剪刀布的游戏，一个人的出石头剪刀布的情况是已知的，另一个人是未知的，但是你知道另外一个人的出的次数的情况。让你找一种可以让那个人赢的情况，如果不能的话，输出NO，否则输出YES，并输出一种可行的方法。

分析：贪心即可，先尽量让第一个人赢，看看能赢不，再把剩下的往上添就好了。

代码：

t = input()
t = int(t)
for i in range(t):
    n = input()
    n = int(n)
    a, b, c = input().split()
    a = int(a)
    b = int(b)
    c = int(c)
    s = input()
    lose = 0
    way = []
    for ch in s:
        if ch == 'R' and b > 0:
            b -= 1
            way.append('P')
        elif ch == 'P' and c > 0:
            c -= 1
            way.append('S')
        elif ch == 'S' and a > 0:
            a -= 1
            way.append('R')
        else:
            lose += 1
            way.append('T')
    if lose > n//2:
        print("NO")
        continue
    print("YES")
    for ch in way:
        if ch == 'T':
            if a > 0:
                a -= 1
                print('R', end = "")
            elif b > 0:
                b -= 1
                print('P', end = "")
            else:
                c -= 1
                print('S', end = "")
        else:
            print(ch, end = "")
    print()

C.Constanze's Machine

题目大意：当键入w的时候会键入uu，当键入m的时候会键入nn。给定一个字符串，问你这个字符串本来应该是什么，输出可能的种类数mod1e9+7。

分析：这是一个简单的线性dp。推出状态转移方程就好了。

代码：

mod = int(1e9 + 7)
s = input()
dp = []
n = len(s)
for i in range(n+1):
    dp.append(0)
dp[0] = 1
flag = False
if s[0] == 'w' or s[0] == 'm':
    flag = True
for i in range(n):
    if i == 0:
        continue
    dp[i] = dp[i-1]
    if s[i] == 'w' or s[i] == 'm':
        flag = True
    if s[i] == 'u' and s[i-1] == 'u':
        if i == 1:
            dp[i] = (dp[i] + 1) % mod
        else:
            dp[i] = (dp[i] + dp[i-2]) % mod
    if s[i] == 'n' and s[i-1] == 'n':
        if i == 1:
            dp[i] = (dp[i] + 1) % mod
        else:
            dp[i] = (dp[i] + dp[i-2]) % mod
if flag == True:
    print(0)
else:
    print(dp[n-1])

Codeforces Round #597 (Div. 2)

推荐阅读