题目1:题目 3040: An Easy Problem
给定一个正整数N，求最小的、比N大的正整数M，使得M与N的二进制表示中有相同数目的1。
举个例子，假如给定的N为78，其二进制表示为1001110，包含4个1，那么最小的比N大的并且二进制表示中只包含4个1的数是83，其二进制是1010011，因此83就是答案。
输入格式
输入若干行，每行一个数n(1≤n≤1000000)，输入"0"结束。
输出格式
输出若干行对应的值。
样例输入
1
2
3
4
78
0
样例输出
2
4
5
8
83
python代码
def searching(n):
o=int(n)#n为字符串类型，取整
one=str(bin(o)).count('1')#计算o的二进制中的含有‘1’的数量
while True:
o+=1
if str(bin(o)).count('1')==one:
print(o)
break#找到第一个符合条件的以后必须退出，否则将会一直输出，而且题目要求找到最小的
while True:
n=input()
if n=='0':
break
else:
searching(n)
知识点
- bin(x):十进制x转化为二进制
- oct(x):十进制x转化为八进制
- hex(x):十进制x转化为十六进制
str.count(i):i必须是str类型
题目2：P1223 排队接水
有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。
输入格式
共两行，第一行为n(1≤n≤1000)；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。
输出格式
输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。
样例输入
10
56 12 1 99 1000 234 33 55 99 812
样例输出
3 2 7 8 1 4 9 6 10 5
291.90
python代码
n=int(input())
t_list=[int(i) for i in (input().split())]
s=0#总计等待时间
t=t_list.copy()
t.sort()#时间排序，让最短的放在前面
sorted_id=sorted(range(n),key=lambda k:t_list[k])
id=[i+1 for i in sorted_id]
for i in range(n):
s+=t[i]*(n-i-1)
for i in range(n):
print(id[i],end=' ')
print()
#print(t_list)
print('%.2f'%(s/n))
知识点
- 不知道有没有利用贪心的思想，让接水时间最短的 放在最前面，之后计算其余人等待的时间，除以人数
- 记录列表a递增或递减排序后的索引值：
sorted_id=sorted(range(n),key=lambda k:a[k],reverse=False/True)
题目3：5399. 矩形总面积
平面上有两个矩形 R1 和 R2，它们各边都与坐标轴平行。
设 (x1,y1)和 (x2,y2)依次是 R1 的左下角和右上角坐标，(x3,y3) 和 (x4,y4)
依次是 R2的左下角和右上角坐标，请你计算 R1
和 R2的总面积是多少?
注意：如果 R1 和 R2有重叠区域，重叠区域的面积只计算一次。
输入格式
输入只有一行，包含 8 个整数，依次是: x1,y1,x2,y2,x3,y3,x4,y4
输出格式
一个整数，代表答案
样例输入
2 1 7 4 5 3 8 6
样例输出
22
python代码
x1,y1,x2,y2,x3,y3,x4,y4=map(int,input().split())
o1x=(x1+x2)/2#矩形1中点x坐标
o1y=(y1+y2)/2#矩形1中点y坐标
o2x=(x3+x4)/2#矩形2中点x坐标
o2y=(y3+y4)/2#矩形2中点y坐标
w1=abs(x2-x1)#矩形1宽度
h1=abs(y2-y1)#矩形1高度
w2=abs(x3-x4)#矩形2宽度
h2=abs(y3-y4)#矩形2高度
x_1=max(x1,x3)
y_1=max(y1,y3)
x_2=min(x2,x4)
y_2=min(y2,y4)
if abs(o1x-o2x)<(w1+w2)/2 and abs(o1y-o2y)<(h1+h2)/2: #相交
square=h1*w1+h2*w2-abs(x_2-x_1)*abs(y_2-y_1)
elif abs(o1x-o2x)>=(w1+w2)/2 or abs(o1y-o2y)>=(h1+h2)/2:#相离
square=h1*w1+h2*w2
else:#内含
square=max(h1*w1,h2*w2)
print(square)
知识点
- 利用矩形中心点1 与 矩形中心点2的在x轴上的分量与在y轴上的分量 与 两矩形的宽度和或高度的一半 进行比较，当两个中心点x距离小于宽度的一半，同时两个中心点y距离小于高度的一半，即相交
- 当两个中心点x距离大于宽度的一半，同时两个中心点y距离大于高度的一半，相等的情况是外切，计算面积与相离等同
- 相交的时候，相交矩形的顶点坐标，可以通过上述方法实现
题目4：题目 2149: 信息学奥赛一本通T1321-删数问题
输入一个高精度的正整数n，去掉其中任意s个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的n和s，寻找一种方案使得剩下的数字组成的新数最小。
输出新的正整数。（n不超过240位）
输入数据均不需判错。
输入格式
n 和 s
输出格式
一个正整数，即最少需要的组数。
样例输入
175438
4
样例输出
13
python代码
n=list(input())
t=len(n)
s=int(input())
d=0#已删除个数
while d<s:
for i in range(len(n)-1):
flag=0#标记是否进行了删除操作
if n[i]>n[i+1]:
n.pop(i)
d+=1
flag=1
break
if flag==0:
break
for i in range(s-d):
n.pop()
if int(n[0])!=0:
print(''.join(n))
else:
for i in range(t-s):
new=int(n[i])*pow(10,t-s-1-i)
print(new)
知识点
- 一些细节问题需要考虑到位，比如使用
''.join(s)拼接成一个数，那么若s[0]==0?显然不符合正常规则，或者分母为0等情况,需要进行分类讨论
题目5：题目 1197: 发工资咯
作为程序猿，最盼望的日子就是每月的9号了，因为这一天是发工资的日子，养家糊口就靠它了，呵呵
但是对于公司财务处的工作人员来说，这一天则是很忙碌的一天，财务处的小李最近就在考虑一个问题：如果每个员工的工资额都知道，最少需要准备多少张人民币，才能在给每位员工发工资的时候都不用员工找零呢？
这里假设程序猿的工资都是正整数，单位元，人民币一共有100元、50元、10元、5元、2元和1元六种。
输入格式
输入数据包含多个测试实例，每个测试实例的第一行是一个整数n（n<100），表示员工的人数，然后是n个员工的工资。
n=0表示输入的结束，不做处理。
输出格式
对于每个测试实例输出一个整数x,表示至少需要准备的人民币张数。每个输出占一行。
样例输入
3 1 2 3
0
样例输出
4
python代码
def culi(gz,n):
cny=0#需要的纸币数量
money=[100,50,10,5,2,1]
for i in range(n-1,-1,-1):
for j in range(6):
cny+=gz[i]//money[j]
gz[i]%=money[j]
print(cny)
return(cny)
while True:
gz=list(map(int,input().split()))
n=gz[0]
if n!=0:
gz.pop(0)
culi(gz,n)
else:
break
知识点
- 输入部分没有什么说的，找好思路很重要。每一份工资，整除以每一份面额，若工资小于面额，那么整除结果是0，若工资大于面额，那么整除后得到该面额的数量，之后该工资变为 之前的求余结果
题目6:题目 1357: 母舰
在小A的星际大战游戏中，一艘强力的母舰往往决定了一场战争的胜负。一艘母舰的攻击力是普通的MA(Mobile Armor)无法比较的。 对于一艘母舰而言，它是由若干个攻击系统和若干个防御系统组成的。两艘母舰对决时，一艘母舰会选择用不同的攻击系统去攻击对面母舰的防御系统。当这个攻击系统的攻击力大于防御系统的防御力时，那个防御系统会被破坏掉。当一艘母舰的防御系统全部被破坏掉之后，所有的攻击都会攻击到敌方母舰本身上去造成伤害。 这样说，一艘母舰对对面的伤害在一定程度上是取决于选择的攻击对象的。 在瞬息万变的战场中，选择一个最优的攻击对象是非常重要的。所以需要写出一个战斗系统出来，判断出你的母舰最多能对对手造成多少伤害并加以实现。
输入格式
输入第一行两个整数M和N，表示对方母舰的防御系统数量和你的母舰的攻击系统数量。 接着M行每行一个整数每一个表示对方防御系统的防御力是多少。 接着N行每行一个整数每一个表示己方攻击系统的攻击力是多少
输出格式
输出仅有一行，表示可以造成的最大伤害。
样例输入
3 5
1000
2000
1200
2100
2000
1200
1000
1000
样例输出
2000
python代码
m,n=map(int,input().split())
enemy=[]#对方母舰的防御系统
self=[]#己方母舰攻击系统
for i in range(m):
enemy.append(int(input()))
for j in range(n):
self.append(int(input()))
victor=0#已经攻破数量
enemy.sort(reverse=True)
self.sort()
while victor<m:
for z in range(len(self)):
if self[z]>enemy[0]:#攻击系统从最小开始，防御从最大开始
victor+=1
enemy.pop(0)
self.pop(z)
break
print(sum(self))
知识点
- 越来越感觉对题目的理解至关重要
- 错误思考：己方攻击系统 与 敌方防御系统 排序，然后用攻击力最大的攻击敌方最大的，直到全部攻破为止，但这样明显不是最优方案，留下的都是小炮弹，攻击力不是最大的
- 正确思考：防御系统从最大开始，攻击系统从最小进行遍历，找到满足条件（攻击力>防御力）且最小的攻击炮弹，列表相应删除，最后对剩余的进行加和。
题目7：题目 1361: 矩形分割
出于某些方面的需求，我们要把一块N×M的木板切成一个个1×1的小方块。 对于一块木板，我们只能从某条横线或者某条竖线（要在方格线上），而且这木板是不均匀的，从不同的线切割下去要花不同的代价。而且，对于一块木板，切割一次以后就被分割成两块，而且不能把这两块木板拼在一起然后一刀切成四块，只能两块分别再进行一次切割。 现在，给出从不同的线切割所要花的代价，求把整块木板分割成1×1块小方块所需要耗费的最小代价。
输入格式
输入文件第一行包括N和M，表示长N宽M的矩阵。 第二行包括N-1个非负整数，分别表示沿着N-1条横线切割的代价。 第三行包括M-1个非负整数，分别表示沿着M-1条竖线切割的代价。
输出格式
输出一个整数，表示最小代价。
样例输入
2 2
3
3
样例输出
9
python代码
n,m=map(int,input().split())
s=input().split()#竖切代价（n-1个数）
h=input().split()#横切代价（m-1个数）
s=[int(l)for l in s]
h=[int(p)for p in h]
s.sort(reverse=True)
h.sort(reverse=True)
count=0#代价
i=0
j=0
x=y=1#两个方向砍出来的木板数量
while i<n-1 and j<m-1:
if s[i]>=h[j]:#先切代价大的
count+=s[i]*y#乘以对面方向的数量
i+=1
x+=1
else:
count+=h[j]*x
j+=1
y+=1
if i==n-1:
for j in range(j,m-1):
count+=h[j]*x
y+=1
else:
for i in range(i,n-1):
count+=s[i]*y
x+=1
print(count)
知识点
- 样例非常水，可以说没提供思考价值，需要充分理解题目
- 第二行、第三行不是说 只有1个数
- 横着切一刀，竖着会切两刀，因此代价大的先切