Python备赛笔记2

1.区间求和

题目描述

给定a1……an一共N个整数，有M次查询，每次需要查询区间【L,R】的和。

输入描述:

第一行包含两个数：N,M

第二行输入N个整数

接下来的M行，每行有两个整数，L  R，中间用空格隔开，数据保证L<=R

1<=N,M<=1e5,-1e5<=ai<=1e5

输出描述:

输出共M行，即每次查询的区间和

示例

输入

5 3
1 2 3 4 5
1 3
3 3
4 5

输出

6
3
9

n,m=map(int,input().split())
N=[0]+list(map(int,input().split()))
for i in range(1,n+1):N[i]+=N[i-1]
for _ in range(m):L,R=map(int,input().split())print(N[R]-N[L-1])
#思路参考前缀和，将数组看为一个数列，先求出Si,再通过SR-Sl得出所求区间数组的和。

2.最大公约数

题目描述

给定两个正整数 A,B，求它们的最大公约数。

输入描述

第 11 行为一个整数 TT，表示测试数据数量。

接下来的 TT 行每行包含两个正整数 A,B。

1≤T≤105，1≤A,B≤109。

输出描述

输出共 T 行，每行包含一个整数，表示答案。

输入输出样例

示例 

输入

5
2 4
3 7
5 10
6 8
7 9

输出 

2
1
5
2
1

import os
import sys# 定义法def gcd1(x,y):while True:x,y=y,x%yif y==0:return x
#递归
def gcd2(x,y):if x==0:return yif y==0:return xreturn gcd2(x,y%x) if x<y else gcd2(y,x%y)
#位运算
def gcd3(x,y):while True:x=x%yy=y^xx=x^yy=y^xif y==0:return x
#这个我不知道是什么方法
def gcd4(x,y):while y!=0:x,y=y,x%yreturn x
T=int(input())
for _ in range(T):A,B=map(int,input().split())print(gcd4(A,B))

3.成绩统计

小蓝给学生们组织了一场考试，卷面总分为 100 分，每个学生的得分都是一个 0 到 100 的整数。

如果得分至少是 60 分，则称为及格。如果得分至少为 85 分，则称为优秀。

请计算及格率和优秀率，用百分数表示，百分号前的部分四舍五入保留整 数。

输入描述

输入的第一行包含一个整数 n (1≤n≤104)，表示考试人数。

接下来 n 行，每行包含一个 0 至 100 的整数，表示一个学生的得分。

输出描述

输出两行，每行一个百分数，分别表示及格率和优秀率。百分号前的部分 四舍五入保留整数。

输入输出样例

示例

输入 

7
80
92
56
74
88
100
0

输出 

71%
43%

n=int(input())
jg,yx=[]*n,[]*n
for _ in range(n):m=int(input())if m>=60:jg.append(m)if m>=85:yx.append(m)
j=(len(jg)/n)*100
y=(len(yx)/n)*100
print(f'%.0f%%'%j)
print(f'%.0f%%'%y)

4.数字三角形

题目描述

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。

输入描述

输入的第一行包含一个整数 N (1≤N≤100)，表示三角形的行数。

下面的 N 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。

输出描述

输出一个整数，表示答案。

输入输出样例

示例

输入

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输出 

27

import os
import sys# 请在此输入您的代码
n=int(input())
w=[list(map(int,input().split())) for _ in range(n)]
for i in range(1,n):for j in range(0,i+1):if j==0:w[i][j]+=w[i-1][j]elif j==i:w[i][j]+=w[i-1][j-1]else:w[i][j]+=max(w[i-1][j-1:j+1])
if n&1:print(w[-1][n//2])
else:print(max(w[-1][n//2-1],w[-1][n//2]))

5.单词分析

小蓝正在学习一门神奇的语言，这门语言中的单词都是由小写英文字母组 成，有些单词很长，远远超过正常英文单词的长度。小蓝学了很长时间也记不住一些单词，他准备不再完全记忆这些单词，而是根据单词中哪个字母出现得最多来分辨单词。

现在，请你帮助小蓝，给了一个单词后，帮助他找到出现最多的字母和这 个字母出现的次数。

输入描述

输入一行包含一个单词，单词只由小写英文字母组成。

对于所有的评测用例，输入的单词长度不超过 1000。

输出描述

输出两行，第一行包含一个英文字母，表示单词中出现得最多的字母是哪 个。如果有多个字母出现的次数相等，输出字典序最小的那个。

第二行包含一个整数，表示出现得最多的那个字母在单词中出现的次数。

输入输出样例

示例 1

lanqiao

a
2

示例 2

longlonglongistoolong

o
6

s=input()
res,cnt='a',0
for i in s:t=s.count(i)if t>=cnt:if t==cnt and i>res:continueres,cnt=i,t
print(res)
print(s.count(res))

 6.平面切分

平面上有 N 条直线，其中第 i 条直线是 y=Ai×x+Biy=Ai​×x+Bi​。

请计算这些直线将平面分成了几个部分。

输入描述

第一行包含一个整数 N。

以下 NN 行，每行包含两个整数 Ai,Bi。

其中，1≤N≤1000,−105≤Ai,Bi≤105。

输出描述

一个整数代表答案。

输入输出样例

示例

3
1 1
2 2
3 3

6

 

n=int(input())
k=[]
for i in range(n):a,b=map(int,input().split())k.append((a,b))
ke=set(k)
k=list(ke)
ans=2
for i in range(1,len(k)):count=0p = set()for j in range(i):if k[i][0]!=k[j][0]:x=(k[i][1]-k[j][1])/(k[i][0]-k[j][0])y=x*k[i][0]+k[i][1]p.add((x,y))else:continueans+=len(p)+1
print(ans)