目录
- A - Jiro
- 题目描述
- 算法思路
- 代码实现
- B - Taro
- 题目描述
- 算法思路
- 代码实现
- D - 1D Country
- 题目描述
- 算法思路
- 代码实现
- E - I Hate Sigma Problem
- 题目描述
- 算法思路
- 代码实现
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 n+1-i n+1−i
这时候作为起点的1,给他所有子序列都贡献了一个唯一的数,于是答案加上6。
接着观察到第四个元素的时候,再次出现了元素1,如下图所示
蓝色表示的是以这个1为起点的子集,通过 n + 1 − i n+1-i n+1−i可以算出有3个子序列,1为这三个子序列各贡献了一个唯一的元素。但是通过观察发现,他又为以2和3为起点的子序列(绿色和紫色)贡献了一个唯一的元素,而且绿色和紫色的子序列的个数分别与蓝色子序列的个数相同。于是我们可以得出下面的结论:
对于每一个数,先给以所有它为起点的子序列贡献1,然后找到当前位置和这个数上一次出现的位置之间的数,给这些数为起点且包含当前数的子序列贡献1。
于是推出下面的公式(设当前数上一次出现的位置为last,默认0)
每一个数的贡献为
( n − i + 1 ) ∗ ( i − l a s t ) (n-i+1)*(i-last) (n−i+1)∗(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)