一、第一题:孤独的照片
解题思路:贡献法+乘法原理
预处理出眉头牛其左右两边不同的牛的数量,然后考虑怎么算就可以
【Python程序代码】
n = int(input())
s = input()
l,r = [0]*(n+5),[0]*(n+5)
g,h = 0,0
for i in range(n):if s[i]=='G':l[i],h,g=h,0,g+1else:l[i],g,h=g,0,h+1
g,h = 0,0
for i in range(n-1,-1,-1):if s[i]=='G':r[i],h,g=h,0,g+1else:r[i],g,h=g,0,h+1
res = 0
for i in range(n):res += l[i]*r[i] + max(r[i]-1,0) + max(l[i]-1,0)
print(res)
二、第二题:牛的基因学
解题思路:贡献法+组合计数
仔细读题思考,可以发现结论:答案为出现数量最多的种类数的n次方取模
【Python程序代码】
n = int(input())
s = input()
ct = [0]*4
for i in range(n):if s[i]=='A':ct[0]+=1if s[i]=='C':ct[1]+=1if s[i]=='G':ct[2]+=1if s[i]=='T':ct[3]+=1
ct.sort(reverse=True)
k = 0
while k<3 and ct[k]==ct[k+1]:k+=1
print(pow(k+1,n,1000000007))
三、第三题:子串分值
解题思路: 贡献法
首先考虑每个字母给答案带来的贡献,预处理出每种字母出现的位置,注意最左边为-1,最右边为n就好。然后考虑怎么算,组合计数方法。
【Python程序代码】
s = input()
pos = [[] for i in range(30)]
for i in range(len(s)):idx = ord(s[i])-ord('a')if len(pos[idx])==0:pos[idx].append(-1)pos[idx].append(i)
for i in range(26):if len(pos[i]):pos[i].append(len(s))
res = 0
for i in range(26):if len(pos[i]):for j in range(1,len(pos[i])-1):res += (pos[i][j]-pos[i][j-1]-1)+(pos[i][j+1]-pos[i][j]-1)+(pos[i][j]-pos[i][j-1]-1)*(pos[i][j+1]-pos[i][j]-1)
res += len(s)
print(res)