Q1：MT 是美團(tuán)的縮寫，因此小美很喜歡這兩個(gè)字母?，F(xiàn)在小美拿到了一個(gè)僅由大寫字母組成字符串，她可以最多操作k次，每次可以修改任意一個(gè)字符。小美想知道，操作結(jié)束后最多共有多少個(gè)'M' 和'T' 字符? 輸入 輸入兩個(gè)正整數(shù)n和k，代表字符串長度和操作次數(shù)第二行輸入一個(gè)長度為n的、僅由大寫字母組成的字符串。

約束條件

1≤k≤n≤10^5

輸出描述

輸出操作結(jié)束后最多共有多少個(gè)'M' 和'T'字符

A1: 送分

import sys

n,k = map(int,sys.stdin.readline().split())
s = str(sys.stdin.readline())

count = 0
for c in s:
    if c=='M' or c=='T':
        count += 1

print(min(count+k,n))

Q2: 小美拿到了一個(gè)由正整數(shù)組成的數(shù)組，但其中有一些元素是未知的(用0來表示)。現(xiàn)在小美想知道，如果那些未知的元素在區(qū)間[l,r]范圍內(nèi)隨機(jī)取值的話，數(shù)組所有元素之和的最小值和最大值分別是多少?共有q次詢問。

輸入描述 第一行輸入兩個(gè)正整數(shù)n和 q，代表數(shù)組大小和詢問次數(shù)。 第二行輸入 n個(gè)整數(shù) ai，其中如果輸入的ai為0，那么說明ai是未知的。 接下來的 q行，每行輸入兩個(gè)正整數(shù) l 和r，代表一次詢問。

約束條件 1≤n,q≤10^5 0≤a_i≤10^9 1≤l≤r≤10^9

輸出描述 輸出 q行，每行輸出兩個(gè)正整數(shù)，代表所有元素之和的最小值和最大值。

A2:送分

import sys

n,q = map(int,sys.stdin.readline().split())
array = list(map(int,sys.stdin.readline().split()))
count = 0
for a in array:
    if not a:
        count += 1
s = sum(array)
for i in range(q):
    l,r = map(int,sys.stdin.readline().split())
    print(s+count*l,s+count*r)

Q3:小美拿到了一個(gè) nxn 的矩陣，其中每個(gè)元素是0或者1。小美認(rèn)為一個(gè)矩形區(qū)域是完美的，當(dāng)且僅當(dāng)該區(qū)域內(nèi)0的數(shù)量恰好等于1的數(shù)量?，F(xiàn)在，小美希望你回答有多少個(gè)ixi的完美矩形區(qū)域。你需要回答1≤i≤n的所有答案。 輸入描述 第一行輸入一個(gè)正整數(shù) n，代表矩陣大小。 接下來的 n行，每行輸入一個(gè)長度為n的 01串，用來表示矩陣 約束條件 1≤n≤200 輸出描述 輸出n行，第i行輸出 ixi的完美矩形區(qū)域的數(shù)量。

A3:完美矩陣：二維前綴和

import sys

n = int(sys.stdin.readline())

dp = [[0]*(n+1) for _ in range(n+1)]

for i in range(1,n+1):
    s = list(map(int,list(sys.stdin.readline().strip())))
    su = 0
    for j in range(1,n+1):
        su += s[j-1]
        dp[i][j] = dp[i-1][j]+su

for i in range(1,n+1):
    res = 0
    if i%2:
        print(0)
    else:
        for j in range(1,n+1):
            for k in range(1,n+1):
                num = dp[j][k]-dp[j][k-i]-dp[j-i][k]+dp[j-i][k-i]
                if num == i*i//2:
                    res += 1
        print(res)

Q4: 小美拿到了一個(gè)大小為n的數(shù)組，她希望刪除一個(gè)區(qū)間后，使得剩余所有元素的乘積未尾至少有k個(gè)0。小美想知道，一共有多少種不同的刪除方案?

輸入描述 第一行輸入兩個(gè)正整數(shù)n和 k。 第二行輸入n個(gè)正整數(shù) ai，代表小美拿到的數(shù)組。

約束條件 1≤n,k≤10^5 1≤ai≤10^9

輸出描述 一個(gè)整數(shù)，代表刪除的方案數(shù)。

A4:去除子區(qū)間的個(gè)數(shù)：前綴和+滑動(dòng)窗口

import sys

n,k = map(int,sys.stdin.readline().split())
array = list(map(int,sys.stdin.readline().split()))

num_2,num_5 = [0]*(n+1),[0]*(n+1)
for i,a in enumerate(array):
    num_2[i+1],num_5[i+1]=num_2[i],num_5[i]
    while a%2==0:
        num_2[i+1]+=1
        a//=2
    while a%5==0:
        num_5[i+1]+=1
        a//=5

left,res = 0,0
for right in range(n):
    while left<right and (num_2[n]-(num_2[right]-num_2[left])<k or num_5[n]-(num_5[right]-num_5[left])<k):
        left+=1
    res+=right-left
print(res)

Q5: 小美認(rèn)為，在人際交往中，隨著時(shí)間的流逝，朋友的關(guān)系也會(huì)慢慢變淡，最終朋友關(guān)系就會(huì)淡忘?，F(xiàn)在初始有一些朋友關(guān)系，存在一些事件會(huì)導(dǎo)致兩個(gè)人淡忘了他們的朋友關(guān)系。小美想知道某一時(shí)刻中，某兩人是否可以通過朋友介紹互相認(rèn)識(shí)。 事件共有 2 種: 1.1uv:代表編號(hào)u的人和編號(hào)v的人淡忘了他們的朋友關(guān)系 2.2uv:代表小美查詢編號(hào)u的人和編號(hào)v的人是否能通過朋友介紹互相認(rèn)識(shí)。 注:介紹可以有多層，比如2號(hào)把1號(hào)介紹給3號(hào)，然后3號(hào)再把1號(hào)介紹給4號(hào)，這樣1號(hào)和4號(hào)就認(rèn)識(shí)了。

輸入描述 第一行輸入三個(gè)正整數(shù) n,m,q，代表總?cè)藬?shù)，初始的朋友關(guān)系數(shù)量，發(fā)生的事件數(shù)量。 接下來的 m 行，每行輸入兩個(gè)正整數(shù) u,v，代表初始編號(hào)u的人和編號(hào)v的人是朋友關(guān)系。 接下來的 q行，每行輸入三個(gè)正整數(shù) op,u,v，含義如題目描述所述。

約束條件 1≤n≤10^9 1≤m,q≤10^5 1≤u,v≤n 1≤op≤2 保證至少存在一次查詢操作。

輸出描述 對(duì)于每次2號(hào)操作，輸出一行字符串代表查詢的答案。如果編號(hào)u的人和編號(hào)心的人器涵過朋友介紹互治認(rèn)識(shí),則輸出"Yes"。否則輸出"No"。

A5: 判斷關(guān)系并且刪除關(guān)系（不是online的）：逆序并查

import sys

n,m,q = map(int,sys.stdin.readline().split())

s = set()
for i in range(m):
    u,v = map(int,sys.stdin.readline().split())
    s.add((u,v))

s_construct = s.copy()
query = []
for i in range(q):
    op,u,v = map(int,sys.stdin.readline().split())
    query.append((op,u,v))
    if op == 1:
        if (u,v) in s_construct:
            s_construct.remove((u,v))
        if (v,u) in s_construct:
            s_construct.remove((v,u))
            
fa = [-1]*(n+1)
csize = [1]*(n+1)

def find(x):
    if fa[x] == -1:
        return x
    fa[x] = find(fa[x])
    return fa[x]

def union(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if csize[x] < csize[y]:
        x,y = y,x
    fa[y] = x
    csize[x] += csize[y]
    
for u,v in s_construct:
    union(u,v)

res = []
for op,u,v in query[::-1]:
    if op == 1:
        if (u,v) in s or (v,u) in s:
            union(u,v)
    else:
        res.append('YES' if find(u) == find(v) else 'NO')
print('\n'.join(res[::-1]))