【Python刷题】Atcoder Beginner Contest 371

A - Jiro

题目描述

有三个人，知道他们之中每两个人的年龄关系，输出年龄第二大的那个人是谁

算法思路

直接把所有情况列举即可

代码实现

s=list(input().split())
a=0
b=0
c=0
if s[0]=='<':if s[1]=='<' and s[2]=='<':print('B')elif s[1]=='<' and s[2]=='>':print('C')elif s[1]=='>':print('A')
elif s[0]=='>':if s[1]=='>' and s[2]=='>':print('B')elif s[1]=='>' and s[2]=='<':print('C')elif s[1]=='<':print('A')

B - Taro

题目描述

输入多组数据，每一组数据第一个值表示来自的家庭，第二个值表示出生孩子的性别，输入的数据已经按照出生时间来排序，对于每个家庭第一个出生的男孩输出Yes，其余输出No。

算法思路

用一个数组data来记录下每个家庭的第一个男孩是否出现即可。

代码实现

n,m=map(int, input().split())
data=[0]*(n+1)
for i in range(m):s=list(input().split())f=int(s[0])if s[1]=='M' and data[f]==0:print('Yes')data[f]=1else:print('No')

D - 1D Country

题目描述

有两个数组，每个数组对应的位置上分别记录村庄的位置以及村庄的人数。之后每次输入两个坐标然后输出这两个坐标之间的村庄的总人数

算法思路

前缀和预处理村庄人数，然后用bisect来找到左右两端点在村庄数组中的索引，最后计算出结果。

代码实现

from bisect import bisect_left, bisect_right
n = int(input())
x = list(map(int, input().split()))
p = list(map(int, input().split()))
qzh = [0] * (n + 1)
for i in range(n):qzh[i + 1] = qzh[i] + p[i]
q = int(input())
for _ in range(q):l, r = map(int, input().split())left_idx = bisect_left(x, l)right_idx = bisect_right(x, r)ans = qzh[right_idx] - qzh[left_idx]print(ans)

E - I Hate Sigma Problem

题目描述

输入n个数，计算出所有子序列中不重复元素的个数之和。

算法思路

这题如果用双重循环加set()来计算还是会超时。
于是用下面的算法：
把题目转换为求每一个元素给他所在的子序列贡献的值的和
假设是这样一组数

设输入的序列为data，我们用变量i作为data的下标从前往后遍历子集的起点，第一个数1为起点时他有下面这些子集。

设data的总长度为n不难发现以当前元素为起点时，子集的个数是$n+1-i$
这时候作为起点的1，给他所有子序列都贡献了一个唯一的数，于是答案加上6。
接着观察到第四个元素的时候，再次出现了元素1，如下图所示

蓝色表示的是以这个1为起点的子集，通过$n+1-i$可以算出有3个子序列，1为这三个子序列各贡献了一个唯一的元素。但是通过观察发现，他又为以2和3为起点的子序列（绿色和紫色）贡献了一个唯一的元素，而且绿色和紫色的子序列的个数分别与蓝色子序列的个数相同。于是我们可以得出下面的结论：
对于每一个数，先给以所有它为起点的子序列贡献1，然后找到当前位置和这个数上一次出现的位置之间的数，给这些数为起点且包含当前数的子序列贡献1。
于是推出下面的公式(设当前数上一次出现的位置为last,默认0)
每一个数的贡献为
$(n-i+1)\ast (i-last)$

代码实现

n = int(input())
a = [0] * (n + 1)
b = [0] * (n + 1)
ans = 0
data=list(map(int, input().split()))
for i in range(1, n + 1):a[i] = int(data[i-1])ans += (n - i + 1) * (i - b[a[i]])b[a[i]] = i
print(ans)