發表新討論
#40337: python，有沒有辦法加速


qaz0978564615@gmail.com (EVIN K)

學校 : 不指定學校
編號 : 255629
來源 : [59.127.158.243]
最後登入時間 ：
2024-10-22 11:44:46
c440. Bert Love QQ ! | From: [203.204.110.174] | 發表日期 : 2024-05-11 14:56
def main():
    n = input()
    Q = 0
    AQ = [i for i in n if i == 'A' or i == 'Q']
    for i, x in enumerate(AQ):
        if x == 'A':
            lq, rq = 0, 0
            for j in range(i):
                if AQ[j] == 'Q':
                    lq += 1
            for k in range(i + 1, len(AQ)):
                if AQ[k] == 'Q':
                    rq += 1
            Q += lq * rq
    print(Q)
main()
 
#41439: Re: python，有沒有辦法加速


h9512218@gmail.com (賴譽毫)

學校 : 國立臺灣師範大學
編號 : 108800
來源 : [111.250.233.167]
最後登入時間 ：
2024-07-28 09:18:30
c440. Bert Love QQ ! | From: [111.250.237.169] | 發表日期 : 2024-07-26 22:05
def main():
    n = input()
    Q = 0
    AQ = [i for i in n if i == 'A' or i == 'Q']
    for i, x in enumerate(AQ):
        if x == 'A':
            lq, rq = 0, 0
            for j in range(i):
                if AQ[j] == 'Q':
                    lq += 1
            for k in range(i + 1, len(AQ)):
                if AQ[k] == 'Q':
                    rq += 1
            Q += lq * rq
    print(Q)
main()

從程式來看時間複雜度是n*n，每遇到A的話，都會往左到底、往右到底，但這樣發現會有多次計算重複。

要加速的話需要另外開兩個list，left_Q，right_Q，分別算各index當下，左邊有幾個Q、右邊有幾個Q，這邊用到DP(動態規劃的概念)。

實作：設定一個變數Q_N=0，從左邊開始讀，left_Q[i]=Q_N，然後當是Q的時候Q_N要再加1，記得+1放後面。

同樣右邊一個變數Q_N=0，從右邊開始讀，right_Q[i]=Q_N，然後當是Q的時候Q_N要再加1，記得+1放後面。

舉例QQAQ

左邊開始讀 ，
left_Q[0]=0，Q_N++

left_Q[1]=1，Q_N++

left_Q[2]=2

left_Q[3]=2，Q_N++

右邊開始讀

right_Q[3]=0，Q_N++

right_Q[2]=1，Q_N++

right_Q[1]=1

right_Q[0]=2，Q_N++

之後再遍歷字串，遇到A的時候，從index查表，取得left_Q、right_Q的值相乘、累加就是答案

 
#41440: Re: python，有沒有辦法加速


h9512218@gmail.com (賴譽毫)

學校 : 國立臺灣師範大學
編號 : 108800
來源 : [111.250.233.167]
最後登入時間 ：
2024-07-28 09:18:30
c440. Bert Love QQ ! | From: [111.250.237.169] | 發表日期 : 2024-07-26 22:05
def main():
    n = input()
    Q = 0
    AQ = [i for i in n if i == 'A' or i == 'Q']
    for i, x in enumerate(AQ):
        if x == 'A':
            lq, rq = 0, 0
            for j in range(i):
                if AQ[j] == 'Q':
                    lq += 1
            for k in range(i + 1, len(AQ)):
                if AQ[k] == 'Q':
                    rq += 1
            Q += lq * rq
    print(Q)
main()

從程式來看時間複雜度是n*n，每遇到A的話，都會往左到底、往右到底，但這樣發現會有多次計算重複。

要加速的話需要另外開兩個list，left_Q，right_Q，分別算各index當下，左邊有幾個Q、右邊有幾個Q，這邊用到DP(動態規劃的概念)。

實作：設定一個變數Q_N=0，從左邊開始讀，left_Q[i]=Q_N，然後當是Q的時候Q_N要再加1，記得+1放後面。

同樣右邊一個變數Q_N=0，從右邊開始讀，right_Q[i]=Q_N，然後當是Q的時候Q_N要再加1，記得+1放後面。

舉例QQAQ

左邊開始讀 ，
left_Q[0]=0，Q_N++

left_Q[1]=1，Q_N++

left_Q[2]=2

left_Q[3]=2，Q_N++

右邊開始讀

right_Q[3]=0，Q_N++

right_Q[2]=1，Q_N++

right_Q[1]=1

right_Q[0]=2，Q_N++

之後再遍歷字串，遇到A的時候，從index查表，取得left_Q、right_Q的值相乘、累加就是答案

 
ZeroJudge Forum