post
#n=5
#lines=[[160,180],[150,200],[280,300],[300,330],[190,210]]
n=int(input())
lines=[list(map(int,input().split())) for i in range(n)]
def merge(lineA,lineB):#return OVERLAP
    overlap=False
    #b頭a尾有重疊
    if lineB[0]<=lineA[1]:
        if lineB[1]>lineA[1]:
            lineA[1]=lineB[1]#已經改變lineA的值,不用再回傳
        return True #overlap=True
    else:
        return False
lines.sort()
#print("sort start=",lines)
current=[0,0]
total=0
for line in lines:
    if merge(current,line):
        pass
    else:
        total+=(current[1]-current[0])#listA不和listB重疊,計算listA的總長
        current=line
    #print("total=",total,"current=",current)
total+=(current[1]-current[0])#最後那段還沒被加進去!
print(total)
c296: APCS-2016-1029-3定時K彈

Code

小測資

n,m,k=5,2,4#共n人,炸掉開始後的第m人,爆k次
#輸入list1,移除炸掉的
list1=list(range(1,n+1))
#print(list1)
def kkbomb(list1,m,k):
    for i in range(k):
        for j in range(m-1):
            list1.append(list1.pop(0)) #把炸掉的元素「前面的」元素推回list1。pop(0)才會移除最前面的,pop()是移除頂層元素
        list1.pop(0)
        #print("now=",list1)
    return list1
list1=kkbomb(list1,m,k)
print(list1[0])

大測資

#n,m,k=8,3,6#共n人,炸掉開始後的第m人,爆k次
def findlucky(luckyidx,list1,m):
    print("before=",list1)
    popidx=(luckyidx+m-1)%len(list1)
    list1.pop(popidx)
    luckyidx=(popidx+len(list1))%len(list1)
    print("nowlist1=",list1)
    return luckyidx
n,m,k=map(int,input().split())
list1=list(range(1,n+1))
luckyidx=0
for _ in range(k):
    luckyidx=findlucky(luckyidx,list1,m)
    print("luckyidx=",luckyidx,"luckyitem=",list1[luckyidx])
print(list1[luckyidx])#不能print(list1),不一定有炸到剩一個
f698:後序運算式

Code

Correct Code

#data="6 3 / 1 4 - * 3 + 8 -"
def postfix(instr):
    list1=list(map(str,instr.split()))
    stack=[]
    #print("len=",len(list1))
    for i in range(len(list1)):
        if list1[i] not in "+-*/":
            stack.append(list1[i])
        else:
            a=stack.pop()
            b=stack.pop()
            ope=b+list1[i]+a
            #print("a=",a,"b=",b)
            #print("ope=",ope)
            stack.append(str(int(eval(ope))))
    #print(stack)
    return stack[0]
data=str(input())
ans=postfix(data)
print(ans)

不能用string直接算

如果用string直接算的話,長度和元素會算入空白!所以必須轉換成list,切出可用元素。
例如下面的code,data長度是5,而a會是空白

data="2 1 -"
print("data=",data)
#print("outer len",len(data))
def postfix (instr):
    stack=[]
    print("len=",len(instr))
    for i in range(len(instr)):
        if instr[i] not in "+-*/":
            stack.append(instr[i])
        else:
            a=stack.pop()
            b=stack.pop()
            ope=b+instr[i]+a
            print("a=",a,"b=",b)
            print("ope=",ope)
            stack.append(str(eval(ope)))
    print(stack)
    return stack[0]
ans=postfix(data)
print(ans)
g310:pD. 甜甜圈大對決(Donut)

Code

可AC的

n=int(input())
shop1=list(map(int,input().split()))
shop2=list(map(int,input().split()))
d1=d2=win=0
while 1:
    if shop1[d1]>=shop2[d2]:
        d2+=1
        if d2==n:
            break
    else:
        win+=1
        d1+=1
        if d1==n:
            break
        d2+=1
        if d2==n:
            break
print(win)

會TLE的

因為每個都要重頭跑,很浪費時間,所以會TLE

#n=3
#shop1=[60,80,100]
#shop2=[50,70,90]
n=int(input())
shop1=list(map(int,input().split()))
shop2=list(map(int,input().split()))
win=0
#取shop2最小可超過「shop1的d1」的d2
for d1 in range(len(shop1)):
    for d2 in range(len(shop2)):
        if shop2[d2]>shop1[d1]:
            win+=1
            shop2[d2]=-1
            #print("win=",win)
            #print(shop1,shop2)
            break
#print("final win=",win)
print(win)
f832:隕石 (Meteorite)

題目大意

捕捉器數值代表最多裝到哪種重量的隕石,不是最多能裝多重

解題思路

最大的捕捉器(背包)要發揮最大效能,所以由大到小排列。如果捕捉器太小則換下個較小的隕石看裝不裝得進去

Code

#n,m=4,3#隕石、捕捉器
#ws=[23,45,67,99]#隕石重量 
#bags=[46,67,100]#每個背包最多裝到哪種重量的隕石
n,m=map(int,input().split())
ws=list(map(int,input().split()))
bags=list(map(int,input().split()))
ws.sort(reverse=True)
bags.sort(reverse=True)
wi=bi=total=0
#print(ws,bags)
while(wi!=n and bi!=m):
    if(ws[wi]<=bags[bi]):
        total+=ws[wi]
        wi+=1
        bi+=1
    else:#裝不進去
        wi+=1
print(total)
APCS 10503 三角形辨別
sides=list(map(int,input().split()))
sides.sort()
print(*sides)
a,b,c=sides[0],sides[1],sides[2]
if((a+b)<=c):
  print("No")
elif((a*a+b*b)>c*c):
  print("Acute")
elif((a*a+b*b)==c*c):
  print("Right")
else:
  print("Obtuse")
APCS 10503 成績指標
#10
#0 11 22 33 55 66 77 99 88 44
# output:最高不及格,沒有不及格:best case<endl>最低及格,沒有及格:worst case
n=int(input())
scores=list(map(int,input().split()))
best=-1
worst=101
scores.sort()
print(*scores)
for score in scores:
    if best<score<60:
        best=score
    elif 60<=score<worst:
        worst=score
if(best!=-1):
    print(best)
else:
    print("best case")
if(worst!=101):
    print(worst)
else:
    print("worst case")
d904:換零錢

題目

https://zerojudge.tw/ShowProblem?problemid=d904

解題思路

  1. dp
  2. 把值一路跑過去 (image credit:碁峰資訊)

注意的地方

  1. c,n分別代表的意義,不要寫反!
  2. w的陣列大小要1000*10(+1)–w[10001]

Code

#include<bits/stdc++.h>
using namespace std;
int main(){
  
  int c,n;//要給的錢總值、硬幣種類數
  int a[11]={},w[10001]={};//幣值、錢的總值
  while(cin>>c>>n){
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    memset(w,0x6f,sizeof(w));
    w[0]=0;
    for(int i=0;i<n;i++){
        for(int j=a[i];j<=c;j++){
            if(w[j-a[i]]+1<w[j]){
                w[j]=w[j-a[i]]+1;
            }
        }
    }
    cout<<w[c]<<endl;
  } 
}
APCS 10503第2題:矩陣轉換

在寫的時候卡住的點:

  1. row是橫列數量,相當於直行的長度;col是直行數量,相當於橫列的長度
  2. 題目要求為「恢復」,或是說「回推」。(是b->a而不是a->b)
    所以衍生出第三點🔻
  3. 給的指令要反著做

覺得可以沿用的方法:

  1. 很混亂的時候代測資數字
  2. 拿紙筆寫下來!

Code

Function可改善處

  1. flip其實可以用reverse就好
    def flip(data):
     data.reverse()
     return data
    
    或用
    output=[]
    for i in data[::-1]:
     output.append(i)
    
    也可以

Complete Code

#data=[[1, 1], [3,1],[1,2]]
#ddata=[[1,2,3],[4,5,6]]
#print("init=",data)
def flip(data):
    row=len(data)#有幾個橫列(直行長度),2
    col=len(data[0])# 3
    for i in range(col):
        for j in range(row//2):
            data[j][i],data[row-1-j][i]=data[row-1-j][i],data[j][i]
    #print("data=",data)
    return data
def rotate(data):
    row=len(data)#有幾個橫列(直行長度),2
    col=len(data[0])# 3
    data2=[[0]*row for _ in range(col)]
    #print(data2)
    for i in range(row):#2,用r命名會比較清楚
        for j in range(col):#3,用c命名會比較清楚
            data2[j][i]=data[i][col-1-j]
            #print("data2=",data2)
            #或用data2[col-j-1][i]=data[i][j]
    return(data2)
#ddata=rotate(ddata)
#ddata=rotate(ddata)
#ddata=flip(ddata)
#print(ddata)
r,c,m=map(int,input().split())
data=[list(map(int,input().split())) for _ in range(r)]
commands=list(map(int,input().split()))
for i in range(len(commands)-1,-1,-1):
    if commands[i]==0:
        data=rotate(data)
        #print("nc,nr",col,row)
    if commands[i]==1:
        data=flip(data)
print(len(data),len(data[0]))
for i in range(len(data)):
    print(*data[i])
APCS 考古題:數字龍捲風

Code

main function: 輸入邊長、開始方向,製造1dlist,記錄每步的方向

#n=5
#d=0#left
#3 4 2 1 4
#4 2 3 8 9
#2 1 9 5 6
#4 2 3 7 8
#1 2 6 4 3
###
#3
#1
#4 1 2
#3 0 5
#6 7 8
#012587634
#order list,input:方向、邊長;output:1dlist_每步的方向[0,1,2,2,3,3,0,0,0,1,1,1,2,2,2,2,3,3,3,3,0,0,0,0]
def order(r,d):
    odlist=[]
    direction=(d+4-1)%4 #1.下面下面迴圈會換方向(+1)所以要先-1 2.像是4可以被歸0
    count=1 #單方向走幾步。如果走n-1步已經是最多了,不用n*n和len(odlist)比 **這種方法會算不到追加
    while(count<=n-1):
        for _ in range(2):#每個長度走2次
            direction=(direction+4)%4
            odlist.append(direction)
    count+=1
    #最後一個長度會走3次,要再追加
    direction=(direction+4)%4
    for _ in range(n-1):
        odlist.append(direction)
    return odlist

complete code

def order(r,d):
    odlist=[]
    direction=(d+4-1)%4
    count=1 
    while(count<=n-1):
        for _ in range(2):
            direction=(direction+4)%4
            odlist.append(direction)
        count+=1
    direction=(direction+4)%4
    for _ in range(n-1):
        odlist.append(direction)
return odlist

r=int(input())
d=int(input())
datas=[]#2d
x,y=r//2,r//2
for i in range n:
    data=list(map(int,input().split()))
    datas.append(data)
steps=order(r,d)
print(datas[x][y])
for step in steps:#注意x是直的,y是橫的!
    if step==0:
        y-=1 #不能只print(datas[x-1][y]),會記錄不到x,y變化
    if step==1:
        x-=1
    if step==2:
        y+=1
    if step==3:
        x+=1
    print(datas[x][y],end="")