Q1.

有三只球队，每只球队编号分别为球队1，球队2，球队3，这三只球队一共需要进行 n 场比赛。现在已经踢完了k场比赛，每场比赛不能打平，踢赢一场比赛得一分，输了不得分不减分。已知球队1和球队2的比分相差d1分，球队2和球队3的比分相差d2分，每场比赛可以任意选择两只队伍进行。求如果打完最后的 (n-k) 场比赛，有没有可能三只球队的分数打平。

  • 输入描述:
  1. 第一行包含一个数字 t (1 <= t <= 10)
  2. 接下来的t行每行包括四个数字 n, k, d1, d2(1 <= n <= 10^12; 0 <= k <= n, 0 <= d1, d2 <= k)
  • 输出描述:
  1. 每行的比分数据，最终三只球队若能够打平，则输出“yes”，否则输出“no”
  • 输入例子1:
2
3 3 0 0
3 3 3 3
  • 输出例子1:
yes
no
  • 例子说明1:
  1. case1: 球队1和球队2 差0分，球队2 和球队3也差0分，所以可能的赛得分是三只球队各得1分
  2. case2: 球队1和球队2差3分，球队2和球队3差3分，所以可能的得分是 球队1得0分，球队2得3分, 球队3 得0分，比赛已经全部结束因此最终不能打平。

  • Analysis

  • Python Code

# input parameters ==========================================
# input number of play cases t
#t = int(input("please input t, (1<=t<=10), (example: 2):"))
t = int(input())
#t = 5
# play cases
cases = []
#cases = [[3, 0, 0, 0], [3, 3, 0, 0], [6, 4, 1, 0], [6, 3, 3, 0], [3, 3, 3, 2]]
#cases = [[150, 31, 15 ,16], [150, 31, 15 ,17], [150 ,31, 15 ,20], [150, 31 ,15 ,23]]

for i in range(t):
    #case = input("please input a case, (n, k, d1, d2) (example: 3 3 0 0):")
    case = input()
    cases.append([int(x) for x in case.split(' ')])
#print("t is: ", t)
#print("cases are: ", cases)

# caculate scores ============================================
"""
(+-) d1 = score_1 - score_2
(+-) d2 = score_2 - score_3
score_1 + score_2 + score_3 = k
score_1 >= 0
score_2 >= 0
score_3 >= 0

=> 3 * score_1 +- 2 * d1 +- d2 = k
=> score_1 = (k +- 2 * d1 +- d2) / 3

we know, 3 teams played n game totally, suppose team_1 joined all the games
for team_1, their socre is between [0, n]
"""
flags = ["no" for i in range(t)]
#print(flags)
for i in range(t):
    scores = []
    if (cases[i][1] + 2*cases[i][2] + cases[i][3])%3 == 0: #1
        pass
        score_1 = (cases[i][1] + 2*cases[i][2] + cases[i][3])//3
        score_2 = score_1 - cases[i][2]
        score_3 = score_2 - cases[i][3]
        if (score_1 >= 0) & (score_2 >= 0) & (score_3 >= 0):
            #print("1: ", score_1, "--   2: ", score_2, "--  3: ", score_3, "==========#1")
            if ([score_1, score_2, score_3] not in scores):
                 scores.append([score_1, score_2, score_3])
    if (cases[i][1] + 2*cases[i][2] - cases[i][3])%3 == 0: #2
        pass
        score_1 = (cases[i][1] + 2*cases[i][2] - cases[i][3])//3
        score_2 = score_1 - cases[i][2]
        score_3 = score_2 + cases[i][3]
        if (score_1 >= 0) & (score_2 >= 0) & (score_3 >= 0):
            #print("1: ", score_1, "--   2: ", score_2, "--  3: ", score_3, "==========#2")
            if ([score_1, score_2, score_3] not in scores):
                scores.append([score_1, score_2, score_3])
    if (cases[i][1] - 2*cases[i][2] + cases[i][3])%3 == 0: #3
        pass 
        score_1 = (cases[i][1] - 2*cases[i][2] + cases[i][3])//3
        score_2 = score_1 + cases[i][2]
        score_3 = score_2 - cases[i][3]
        if (score_1 >= 0) & (score_2 >= 0) & (score_3 >= 0):
            #print("1: ", score_1, "--   2: ", score_2, "--  3: ", score_3, "==========#3")
            if ([score_1, score_2, score_3] not in scores):
                scores.append([score_1, score_2, score_3])
    if (cases[i][1] - 2*cases[i][2] - cases[i][3])%3 == 0: #4
        pass
        score_1 = (cases[i][1] - 2*cases[i][2] - cases[i][3])//3
        score_2 = score_1 + cases[i][2]
        score_3 = score_2 + cases[i][3]
        if (score_1 >= 0) & (score_2 >= 0) & (score_3 >= 0):
            #print("1: ", score_1, "--   2: ", score_2, "--  3: ", score_3, "==========#4")
            if ([score_1, score_2, score_3] not in scores):
                scores.append([score_1, score_2, score_3])
    
    #print(scores)
    #print(len(scores))
    if len(scores) == 0:
        continue

    left_game = cases[i][0] - cases[i][1] # n-k
    
    for score in scores:
        if left_game == 0: 
            if (score[0] == score[1]) & (score[1] == score[2]):
                flags[i] = "yes"
                break
        else:
            max_score = max(score)
            if (cases[i][0] % 3 == 0) & ((cases[i][0] // 3) >= max_score):
                flags[i] = "yes"
                break
            pass
        pass
for flag in flags:
    print(flag)

Q2.

有一个仅包含’a’和’b’两种字符的字符串s，长度为n，每次操作可以把一个字符做一次转换（把一个’a’设置为’b’，或者把一个’b’置成’a’)；但是操作的次数有上限m，问在有限的操作数范围内，能够得到最大连续的相同字符的子串的长度是多少。

  • 输入描述:
  1. 第一行两个整数 n , m (1<=m<=n<=50000)，第二行为长度为n且只包含’a’和’b’的字符串s。
  • 输出描述:
  1. 输出在操作次数不超过 m 的情况下，能够得到的 最大连续 全’a’子串或全’b’子串的长度。
  • 输入例子1:
8 1
aabaabaa
  • 输出例子1:
5
  • 例子说明1:
  1. 把第一个 ‘b’ 或者第二个 ‘b’ 置成 ‘a’，可得到长度为 5 的全 ‘a’ 子串。
  • Python Code
# input parameters ==========================================
# input n, m in row_1
"""
row_1 = input()
row_1 = [int(x) for x in row_1.split(' ')]
row_2 = input()

n = row_1[0]
m = row_1[1]
s = row_2
"""
n = 8
m = 3
s = "aabaabaa"

# calculate ==================================================
a_tokens = s.split('b')
b_tokens = s.split('a')

len_a_tokens = [len(token) for token in a_tokens]
len_b_tokens = [len(token) for token in b_tokens]

max_len = 0
if (m >= len(len_a_tokens) -1) | (m >= len(len_b_tokens) -1):
    max_len = n
    print(max_len)
else:

    for len_tokens in [len_a_tokens, len_b_tokens]:
        pointer = 0
        while pointer < len(len_a_tokens) -m:
            len_token = len_tokens[pointer]
            for indice in range(1, m+1):
                len_token += 1 + len_a_tokens[pointer + indice] 
            
            pointer += 1
            if len_token > max_len:
                max_len = len_token

    print(max_len)