1316: 選房子
[命題人 : 外部導(dǎo)入]
時間限制 : 1.000 sec 內(nèi)存限制 : 128 MB
題目描述
棟棟和李劍已經(jīng)大四了，想要出去找房子住。他們一共看中了n套房子。其中第i套房子已經(jīng)住了ai個人了，它最多能住bi個人。棟棟和李劍想要住在一起，那么請問他們有幾套可以選擇的房子？
輸入
輸入的第一行為一個正整數(shù)T (T<=1000)，代表一共有T組測試數(shù)據(jù)。
每組測試數(shù)據(jù)的第一行有一個正整數(shù)n (1<=n<=100)，代表一共有n套房子。接下來n行，每行有兩個正整數(shù)ai，bi (1<=ai<=bi<=100)，分別代表現(xiàn)在已經(jīng)住了ai個人和最多能住bi個人。
輸出
對于每組測試數(shù)據(jù)，輸出一行包含一個整數(shù)，代表他們可以選擇房子的數(shù)量。
樣例輸入 Copy
2
2
1 2
1 3
3
1 10
2 10
3 10
樣例輸出 Copy
1
3
來源/分類
首屆全國中醫(yī)藥院校大學(xué)生程序設(shè)計(jì)競賽
分析：由題意得只要b-a>=2即可
代碼：
重慶分公司
重慶分公司
n=int(input())
for i in range(n):
m=int(input())
count=0
for j in range(m):
a,b=map(int,input().split( ))
if b-a>=2:
count=count+1
print(count)2158: 倍數(shù)問題
[命題人 : 202001080138]
時間限制 : 1.000 sec 內(nèi)存限制 : 128 MB
題目描述
眾所周知，小蔥同學(xué)擅長計(jì)算，尤其擅長計(jì)算一個數(shù)是否是另外一個數(shù)的倍數(shù)。
但小蔥只擅長兩個數(shù)的情況，當(dāng)有很多個數(shù)之后就會比較苦惱。
現(xiàn)在小蔥給了你 n 個數(shù)，希望你從這 n 個數(shù)中找到三個數(shù)
使得這三個數(shù)的和是 K 的倍數(shù)，且這個和大。數(shù)據(jù)保證一定有解。
輸入
第一行包括 2 個正整數(shù) n,?K。
第二行 n 個正整數(shù)，代表給定的 n 個數(shù)。
1<= n?<= 10^5,?1<= K?<= 10^3，給定的 n 個數(shù)均不超過 10^8。
輸出
輸出一行一個整數(shù)代表所求的和。
樣例輸入 Copy
4 3
1 2 3 4
樣例輸出 Copy
9
來源/分類
分析：利用插入排序最多保留同一個余數(shù)的前三大數(shù)，然后再利用cnt=(k-(i+j)%k)%k或者cnt=( 2*k-i-j) % k,兩重循環(huán)得出滿足條件的cnt,i,j三個數(shù)。細(xì)節(jié)如下：
代碼：
n, k = map(int, input().split())
s = list(map(int, input().split()))
m = [[0 for i in range(3)] for i in range(k)] #只取同一個余數(shù)大的前三個
for i, t in enumerate(s):# 插入交換
if t in m[t % k]:
continue
if t >m[t%k][0]:
m[t%k][0],m[t%k][1],m[t%k][2]=t,m[t%k][0],m[t%k][1]
elif t>m[t%k][1]:
m[t % k][0], m[t % k][1], m[t % k][2] = m[t % k][0],t, m[t % k][1]
elif t >m[t % k][2]:
m[t % k][0], m[t % k][1], m[t % k][2] = m[t % k][0], m[t % k][1], t
sum1 = 0
for i in range(k):
if m[i][0] ==0:
continue
for j in range(k):
if m[j][0] == 0:#如果第一個數(shù)為0則代表這個列表里面沒有元素
continue
z = ( 2*k-i-j) % k#z=(k-(i+j)%k)%k也可
sum2=0 #分為5種情況：
if i == j and j != z and m[z][0] >0 and m[i][0] >= 0:# i和j在一個余數(shù)列表里面,z不在，然后判斷各自余數(shù)列表里面有沒有這么多元素，沒有就直接跳過，節(jié)約時間.
sum2 =m[i][0] + m[i][1] + m[z][0]
elif i == j and j == z and m[i][2] >0:#原理同上
sum2 = m[i][0] + m[i][1] + m[j][2]
elif i == z and j != z and m[i][1] >0 and m[j][0] >0:
sum2 = m[i][0] + m[i][1] + m[j][0]
elif i != j and j != z and z != i and m[i][0] >0 and m[z][0] >0 and m[j][0] >0:
sum2 = m[i][0] + m[j][0] + m[z][0]
elif j == z and i != z and m[j][1]>0 and m[i][0] >0:
sum2 = m[i][0] + m[j][0] + m[j][1]
if sum2>sum1: #注意為了防止超時，最好不要用python自帶函數(shù)max.
sum1=sum2
print(sum1)藍(lán)橋云課AC截圖
2196: X星游戲
[命題人 : admin]
時間限制 : 1.000 sec 內(nèi)存限制 : 128 MB
題目描述
X星人這幾天很無聊，他發(fā)明了一個自娛自樂的小游戲。
現(xiàn)在有若干張寫有0、1、2、3、…、9這10個數(shù)字之一的紙牌，每一次可以拿出一張牌。
將抽取到的牌中的數(shù)字連成一個數(shù)列，如果當(dāng)前抽的牌中的數(shù)字在前面出現(xiàn)過，則收取這兩張牌及其它們之間所有的牌。
請你編寫一個程序，計(jì)算最多的一次可以收取到多少張牌？
【注：可能最后還留有一些牌沒有被收取】
輸入
單組輸入。
第1行輸入一個數(shù)字N，表示X星人總共抽取的牌數(shù)，N<=1000。
第2行輸入N個數(shù)字，分別對應(yīng)X星人每一次抽取到的紙牌上的數(shù)字，兩兩之間用空格隔開。
輸出
輸出最多一次可以收取到的牌的數(shù)量。
樣例輸入 Copy
10
0 1 2 3 1 1 0 4 2 1
樣例輸出 Copy
4
提示
對于樣例數(shù)據(jù)而言，最多收取4張牌，對應(yīng)的數(shù)字序列是：1 2 3 1，即第2張牌到第5張牌。
來源/分類
分析：由題意模擬即可，用棧模擬也可。
代碼：
def find(n,k):#從前面找到和n相同的數(shù)字的序號
for i in range(len(k)-1,-1,-1):
if k[i]==n:
return i
def pick(a,b,k):#將a到b的值設(shè)為“p”
for i in range(a,b):
if k[i]!='p':
k[i]="p"
def maxs(a,b,k):#計(jì)算a，b兩張牌之間一共還有幾張牌
sum1=1
for i in range(a,b):
if k[i]!='p':
sum1+=1
return sum1
while True:
n=int(input())
s=list(map(int,input().split()))
k=[]
max1=0
for t in s:#如果t不在列表，就加入
if t not in k:
k.append(t)
else:
index=find(t,k)#找到前面和t相同數(shù)字的序號
max1=max(max1,maxs(index,len(k),k))#更新相同兩張牌之間的大數(shù)目
pick(index,len(k),k)#將前面和數(shù)字t相同的數(shù)字到數(shù)字t給去掉，為了防止頻繁的插入和刪除超時，就直接將其值改為“p”
print(max1)1034: 近似回文詞
[命題人 : 外部導(dǎo)入]
時間限制 : 1.000 sec 內(nèi)存限制 : 128 MB
題目描述
輸入一行文本，輸出最長近似回文詞連續(xù)子串。所謂近似回文詞是指滿足以下條件的字符串：
輸入
輸入包含不超過25組數(shù)據(jù)，每組數(shù)據(jù)包含兩行。第一行是整數(shù)k（0<=k<=200），第二行為字符串S，包含不超過1000個字符（換行符不算）。S只包含字符、空格和其他可打印字符（比如逗號，句號），并且不會以空白字符開頭。
輸出
對于每組測試數(shù)據(jù)，輸出最長近似回文子串的長度和起始位置（S的第一個字符是位置1）。如果有多個最長近似回文子串解，起始位置應(yīng)盡量小。
樣例輸入 Copy
1
Wow, it is a Race cat!
0
abcdefg
0
Kitty: Madam, I’m adam.
樣例輸出 Copy
Case 1: 8 3
Case 2: 1 1
Case 3: 15 8
來源/分類
湖南省第九屆大學(xué)生計(jì)算機(jī)程序設(shè)計(jì)競賽
分析：我用暴力模擬直接超時，oj只過了50%,然后在看到大佬的博客之后醍醐灌頂，以后遇到這類問題再也不怕超時了。思路：先記錄字母和其序號，然后再以i為回文串的中心，以j為回文串的半徑循環(huán)枚舉，如果有k個不同就直接退出，進(jìn)入下輪循環(huán)。注意要區(qū)分字符串長度的奇偶，細(xì)節(jié)如下：
代碼：
cnt = 0
while True:
try:
cnt += 1
k = int(input())
p = input()
maxlen, index = 0, 0
s=[]
sign=[]
for i, t in enumerate(p):#記錄字母和其序號，并將字母全部變?yōu)樾? if t.isalpha():
sign.append(i)
s.append(t.lower())
for i in range(len(s)):#以i為中心
j, count = 0, 0
while i + j< len(s) and i - j >= 0:#以j為半徑的回文字符串，偶數(shù)情況下
if s[i + j] != s[i - j]:#如果兩邊不等就記錄+1
count += 1
if count >k:#
break
j += 1
j-=1# 因?yàn)閖退出時多加了1
if sign[i + j] - sign[i - j]+1 >maxlen:#sign[i + j] - sign[i - j]+1，+1是因?yàn)榱斜硎菑南聵?biāo)為0開始的
maxlen = sign[i + j] - sign[i - j] + 1
index = sign[i - j]#記錄開始的點(diǎn)
j, count = 0, 0
while i + j + 1< len(s) and i - j >= 0:#奇數(shù)情況，其他同上
if s[i + j+1] != s[i - j]:
count += 1
if count >k:
break
j += 1
j-=1
if j<0:continue
if sign[i + j+1] - sign[i - j]+1 >maxlen:
maxlen = sign[i + j+1] - sign[i - j] + 1
index = sign[i - j]
print('Case %d: %d %d'%(cnt, maxlen, index+1))
except:
breakAC截圖：
1749: 最少硬幣
[命題人 : admin]
時間限制 : 1.000 sec 內(nèi)存限制 : 128 MB
題目描述
假設(shè)有4種硬幣，它們的面值分別為1分、5分、10分和25分。
現(xiàn)在要找給顧客n分錢。
請問怎樣找零錢才能使給顧客的硬幣個數(shù)最少？
輸出所需最少硬幣的枚數(shù)。
輸入
輸入需要找給顧客的零錢n（單位：分）。
輸出
輸出所需最少硬幣的枚數(shù)。
樣例輸入 Copy
8
10
63
樣例輸出 Copy
4
1
6
來源/分類
算法分析與設(shè)計(jì) 貪心
分析：可以直接貪心從大的硬幣名額遍歷求得最少硬幣的枚數(shù)，也可以采用dp算法時效性最好。
dp算法：
while True:
n=int(input())
s=[1,5,10,25]
m=[0 for i in range(n+1)]
def solve():
for i in range(n+1):
m[i]=float("inf")
m[0]=0
for j in range(4):
for i in range(s[j],n+1):
m[i]=min(m[i],m[i-s[j]]+1)#滾動數(shù)組
solve()
print(m[n])
貪心算法：
k=[25,10,5,1]
while True:
count=0
n=int(input())
for i in range(4):
z=0
if n>=k[i]:
z=n//k[i]
n=n-z*k[i]
count=count+z
else:
continue
print(count)
2079: X星大學(xué)
[命題人 : admin]
時間限制 : 1.000 sec 內(nèi)存限制 : 128 MB
題目描述
X星大學(xué)新校區(qū)終于建成啦！
新校區(qū)一共有N棟教學(xué)樓和辦公樓?，F(xiàn)在需要用光纖把這N棟連接起來，保證任意兩棟樓之間都有一條有線網(wǎng)絡(luò)通訊鏈路。
已知任意兩棟樓之間的直線距離（單位：千米）。為了降低成本，要求兩棟樓之間都用直線光纖連接。
光纖的單位成本C已知（單位：X星幣/千米），請問最少需要多少X星幣才能保證任意兩棟樓之間都有光纖直接或者間接相連？
注意：如果1號樓和2號樓相連，2號樓和3號樓相連，則1號樓和3號樓間接相連。
輸入
單組輸入。
第1行輸入兩個正整數(shù)N和C，分別表示樓棟的數(shù)量和光纖的單位成本（單位：X星幣/千米），N<=100，C<=100。兩者之間用英文空格隔開。
接下來N*(N-1)/2行，每行包含三個正整數(shù)，第1個正整數(shù)和第2個正整數(shù)表示樓棟的編號（從1開始一直到N），編號小的在前，編號大的在后，第3個正整數(shù)為兩棟樓之間的直線距離（單位：千米）。
輸出
輸出最少需要多少X星幣才能保證任意兩棟樓之間都有光纖直接或者間接相連。
樣例輸入 Copy
3 10
1 2 5
1 3 6
2 3 7
樣例輸出 Copy
110
來源/分類
分析：可以采用prime算法最小生成樹,這里采用并查集，利用路徑壓縮優(yōu)化查詢。
代碼：
def init(n, k):#初始化并查集，每個人得祖先是自己
for i in range(1, n + 1):
k[i] = i
return k
def find(x, k):#遞歸尋找祖先
if x != k[x]:
k[x] = find(k[x],k)
return k[x]
def union(x, y, k):#合并，指向同一個祖先
x = find(x,k)
y = find(y,k)
if x != y:
k[x] = k[y]
while True:
n, c1 = map(int, input().split())
k = [[] for i in range(n + 1)]
init(n, k)
sum1 = 0
w = [[] for i in range((n * (n - 1) // 2))]
for i in range(n * (n - 1) // 2):#列舉路徑數(shù)
a, b, c = map(int, input().split())
w[i].append(a)
w[i].append(b)
w[i].append(c)
w.sort(key=lambda x: x[2], reverse=False)#將路徑小的排前面
for t in w:
x, y, z = t[0], t[1], t[2]
x1 = find(x, k)#尋找兩個的祖先
y1 = find(y, k)
if x1 != y1:#不同則合并指向同一個祖先
union(x, y, k)
sum1 += z
print(sum1*c1)2086: 獎牌榜
[命題人 : admin]
時間限制 : 1.000 sec 內(nèi)存限制 : 128 MB
題目描述
X星學(xué)校的運(yùn)動會正在激烈進(jìn)行中。
現(xiàn)在需要請你編寫一個程序來顯示所有班級的獎牌榜，顯示規(guī)則如下：
(1) 優(yōu)先按照金牌數(shù)量降序排列后顯示。
(2) 如果金牌數(shù)相等則比較銀牌數(shù)，銀牌數(shù)多者顯示在前。
(3) 如果金牌和銀牌數(shù)都相等，則比較銅牌數(shù)，銅牌數(shù)多者顯示在前。
(4) 如果金、銀、銅數(shù)量均相等，則按照班級編號從小到大排列后顯示。
(5) 需要按照班級編號、金牌數(shù)、銀牌數(shù)、銅牌數(shù)、獎牌總數(shù)的順序顯示每個班級的獎牌情況。
已知X星學(xué)校的班級編號為一個四位正整數(shù)，且班級編號具有唯一性。
輸入
單組輸入。
第1行輸入一個正整數(shù)N，表示班級的總數(shù)量，N<=9000。
接下來N行，每1行包含四個正整數(shù)，分別表示班級編號、金牌數(shù)、銀牌數(shù)和銅牌數(shù)。金牌數(shù)、銀牌數(shù)和銅牌數(shù)均小于100。兩兩之間用英文空格隔開。
輸出
顯示按照規(guī)則排序之后的獎牌榜，每一行都包含班級編號、金牌數(shù)、銀牌數(shù)、銅牌數(shù)和獎牌總數(shù)，兩兩之間用英文空格隔開。
樣例輸入 Copy
4
1000 4 10 5
1001 5 11 6
1002 4 11 4
1003 4 10 5
樣例輸出 Copy
1001 5 11 6 22
1002 4 11 4 19
1000 4 10 5 19
1003 4 10 5 19
來源/分類
分析：多維數(shù)組排序，細(xì)節(jié)見：python如何自定義排序
代碼：
while True:
n=int(input())
s=[]
for i in range(n):
s.append(list(map(int,input().split())))
s.sort(key=lambda x:(x[1],x[2],x[3],-x[0]),reverse=True)
for i in range(n):
s[i].append(sum(s[i][1:]))
for j in range(5):
if j!=0:
print(" ",end="")
print(s[i][j],end="")
print()代碼寫的比較爛，各位大佬多多指教
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
