筆記國度

在這裡放著一些我自己的筆記

[CPE培訓] 2014-02-18

| Comments

杭州電子科技大學 HDU 帳號對應表

CPE 考試

  • 報名期間:2014/03/11 (二) 14:25 ~ 2014/03/21 (五) 18:00
  • 考試時間:2014/03/25 (二)
    • 17:30-17:40 報到, 18:00 之後不得入場
    • 17:40-18:30 練習
    • 18:40-21:40 考試
  • 網址:http://cpe.cse.nsysu.edu.tw/newest.php

題目練習網站

本學期將使用杭州電子科技大學的網站來進行線上練習。請先註冊帳號,然後把帳號回報給我。

  • 點選註冊

  • 填寫資料

  • 註冊後登入

  • 點此瀏覽自訂比賽清單

  • 搜尋比賽

  • 輸入 taichunmin,並選擇 User Name 後,按 Go 送出

熱身賽題目

  1. Ancient Cipher (密碼學)
  2. Sum of Consecutive Prime Numbers (質數 + 建表)
  3. Integer Inquiry (大數)
  4. Parencodings (模擬)
  5. Martian Mining (動態規劃)

PHP 型態比較與 empty, isset 判斷

| Comments

這個是一個小程式,用來幫助釐清 PHP 內的型態比較,以及 empty, isset 的行為。

<pre>
0==0: <?=intval(0==0)?>

0==false: <?=intval(0==false)?>

0=="": <?=intval(0=="")?>

0==null: <?=intval(0==null)?>

0==array(): <?=intval(0==array())?>



0===0: <?=intval(0===0)?>

0===false: <?=intval(0===false)?>

0==="": <?=intval(0==="")?>

0===null: <?=intval(0===null)?>

0===array(): <?=intval(0===array())?>



empty(0): <?php $a=0;?><?=intval(empty($a))?>

empty(false): <?php $a=false;?><?=intval(empty($a))?>

empty(""): <?php $a="";?><?=intval(empty($a))?>

empty(null): <?php $a=null;?><?=intval(empty($a))?>

empty(array()): <?php $a=array();?><?=intval(empty($a))?>



isset(0): <?php $a=0;?><?=intval(isset($a))?>

isset(false): <?php $a=false;?><?=intval(isset($a))?>

isset(""): <?php $a="";?><?=intval(isset($a))?>

isset(null): <?php $a=null;?><?=intval(isset($a))?>

isset(array()): <?php $a=array();?><?=intval(isset($a))?>

</pre>

執行結果

0==0: 1
0==false: 1
0=="": 1
0==null: 1
0==array(): 0


0===0: 1
0===false: 0
0==="": 0
0===null: 0
0===array(): 0


empty(0): 1
empty(false): 1
empty(""): 1
empty(null): 1
empty(array()): 1


isset(0): 1
isset(false): 1
isset(""): 1
isset(null): 0
isset(array()): 1

[SPOJ] 379. Ambiguous Permutations.py

| Comments

題目網址:連結

解題報告

  • 使用 enumerate()for ... in ... : 中使用 list 的 Key 和 Value
while True:
    n = int(input())
    if not n:
        break
    ar1, ar2 = [int(i) for i in input().split(' ')], [0]*n
    for ki, vi in enumerate(ar1):
        ar2[vi-1] = ki+1
    if ar1==ar2:
        print('ambiguous')
    else:
        print('not ambiguous')

[SPOJ] 902. Hangover.py

| Comments

題目網址:連結

解題報告

  • 浮點數與 比較 (包含誤差)
    def fzero(fa):
        delta = 1e-5
        return -1 if fa < -delta else ( fa > delta )
    
from sys import stdin

def fzero(fa):
    delta = 1e-5
    return -1 if fa < -delta else ( fa > delta )

ar1, ln1 = [.0]*300, 1
while ln1<300 and fzero(ar1[ln1-1]-5.20)<1:
    ar1[ln1],ln1 = ar1[ln1-1]+1/(ln1+1), ln1+1
ar1[ln1],ln1 = 10.0, ln1+1
while True:
    fa = float(stdin.readline())
    if not fzero(fa):
        break
    for i in range(ln1):
        if fzero(fa-ar1[i])<0:
            print(i,'card(s)')
            break

正規表示法範例

| Comments

資料來源

  1. 37 Tested PHP, Perl, and JavaScript Regular Expressions
  2. 常用正則表達式範例
  3. Sample Regular Expressions

好文

  1. [正規式] 複習 (?:) (?=) (?!) 的使用
  2. Linux grep 基礎正規表示法, 鳥哥
  3. Comparison of regular expression engines
  4. 正規表示式 wiki
  5. http://regexlib.com/ - - - # 範例
  • 主流信用卡
    /^(?:4[0-9]{12}(?:[0-9]{3})?|5[1-5][0-9]{14}|6011[0-9]{12}|622((12[6-9]|1[3-9][0-9])|([2-8][0-9][0-9])|(9(([0-1][0-9])|(2[0-5]))))[0-9]{10}|64[4-9][0-9]{13}|65[0-9]{14}|3(?:0[0-5]|[68][0-9])[0-9]{11}|3[47][0-9]{13})*$/

  • 美國運通信用卡
    /^(3[47][0-9]{13})*$/

  • MasterCard
    /^(5[1-5][0-9]{14})*$/

  • Visa 卡
    /^(4[0-9]{12}(?:[0-9]{3})?)*$/

  • 日期 (MM/DD/YYYY)
    /^((0?[1-9]|1[012])[- /.](0?[1-9]|[12][0-9]|3[01])[- /.](19|20)?[0-9]{2})*$/

  • 日期 (YYYY/MM/DD)
    /^(((?:19|20)[0-9]{2})[- /.](0?[1-9]|1[012])[- /.](0?[1-9]|[12][0-9]|3[01]))*$/

  • 電子郵件
    以下的範例並沒有相容 RFC5322 規範,但是已經可以驗證大多數的電子郵件。
    /^([a-zA-Z0-9._%-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,4})*$/

  • IPv4
    /^((?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?))*$/

  • 密碼
    高強度密碼,6 位數以上,並且至少包含 大寫字母、小寫字母、數字、符號 各一
    /^(?=.*[^a-zA-Z0-9])(?=.*[A-Z])(?=.*[a-z])(?=.*\d).{6,}$/

  • 台灣手機號碼
    /^09\d{2}-?\d{3}-?\d{3}$/

  • URL 網址
    允許 http, https, ftp 協定,並且可取出 Protocol, Domain, Path, Query
    /^(?:(https?|ftp):\/\/)?((?:[a-zA-Z0-9.\-]+\.)+(?:[a-zA-Z0-9]{2,4}))((?:/[\w+=%&.~\-]*)*)\??([\w+=%&.~\-]*)$/

  • 取代重複行
    搜尋:/^(.*)(\n\1)+$/
    取代:\1

  • 中文 (Unicode)
    [\u4e00-\u9fa5]

  • 刪除空白行
    搜尋:/^\s*$/m
    取代:

  • 刪除行首行尾空白
    搜尋:^\s*|\s*$
    取代:

  • 驗證使用者帳號
    第一個字不為數字,只接受 大小寫字母、數字及底線
    /^[a-zA-Z]\w*$/

  • 簡易驗證台灣身份證
    仍然需要一些進階的檢查,如 驗證檢查碼,或前往 內政部戶政司 驗證
    /^[A-Za-z][1-2]\d{8}$/

  • 正整數
    /^\+?\d+$/

  • 整數
    /^[+-]?\d+$/

  • float
    /^[-+]?[0-9]*\.?[0-9]+([eE][-+]?[0-9]+)?$/

[SPOJ] 7974. What’s Next.py

| Comments

題目網址:連結

判斷等差或等比,並輸出下一項,本題公差和公比均為非 整數。

解題報告

  • 題目輸入包含負數,故不可使用 ia+ib+ic==0 判斷結束
  • 使用 (ia,ib,ic) == (0,0,0)tuple 比較方式取代 ia==0 and ib==0 and ic==0
from sys import stdin

while True:
    ia,ib,ic = [int(i) for i in stdin.readline().split(' ')]
    if (ia,ib,ic) == (0,0,0):
        break
    if ia+ic == ib*2:
        print('AP',ic+ib-ia)
    else:
        print('GP',ib//ia*ic)

[SPOJ] 4300. Rectangles.py

| Comments

題目網址:連結

解題報告

  • 使用 tuple 快速指定變數
  • 建表法求質數 is_prime(), build_prime()
  • 質因數分解程式碼 prime_factor()
from sys import stdin

p,p[:4],p_cnt = [0]*100,[2,3,5,7],4

def is_prime(n):
    for i in range(p_cnt):
        if p[i]*p[i]>n:
            break
        if n%p[i]==0:
            return False
    return (n>=2)

def build_prime(prime_max):
    global p_cnt
    prime_max,i,j = int(prime_max**0.5),11,2
    while p[p_cnt-1]<=prime_max:
        if is_prime(i):
            p[p_cnt], p_cnt = i, p_cnt+1
        i,j = i+j,6-j

def prime_factor(n):
    pf = []
    for i in range(p_cnt):
        if p[i]*p[i]>n:
            break
        if n%p[i]==0:
            n,cnt = n//p[i],1
            while n%p[i]==0:
                n,cnt = n//p[i], cnt+1
            pf.append([ p[i], cnt ])
    if n>1:
        pf.append([n,1])
    return pf

build_prime(10**4)
# print(p_cnt)


ans=0
for i in range(1, int(stdin.readline())+1 ):
    pf1,ia = prime_factor(i),1
    for pf_i in pf1:
        ia *= (pf_i[1]+1)
    ans+=ia//2+ia%2
print(ans)

[SPOJ] 1025. Fashion Shows.py

| Comments

題目網址:連結

解題報告

  • split() 後的 list 不能使用 sort(),必須使用 sorted()
  • sorted()sort() 加上 reverse=True 參數後可以由大排到小 [參考資料]
from sys import stdin
for t1 in range(int(stdin.readline())):
    ia = int(stdin.readline())
    # 這裡只能用 sorted,因為還沒有變數可用 sort()

    ar1 = sorted([int(i) for i in stdin.readline().split(' ')], reverse=True)
    ar2 = sorted([int(i) for i in stdin.readline().split(' ')], reverse=True)
    ans = 0
    for i in range(len(ar1)):
        ans += ar1[i] * ar2[i]
    print(ans)

[SPOJ] 400. To and Fro.py

| Comments

題目連結:連結

解題報告

  • 使用 strip() 去除 readline() 最後的 \n 符號
  • 使用 list("abc")string 轉換成 char list
  • 使用 ''.join()char list 轉換成 string
  • 使用 sa[5:10] = sa[9:4:-1]char list 進行部份 reverse
  • 使用 print(,end='') 避免 print 自動換行
from sys import stdin
while True:
    ia = int(stdin.readline())
    if not ia:
        break
    sa = list(stdin.readline().strip())
    for i in range( len(sa)//(2*ia) + (len(sa)%(2*ia)!=0) ):
        sa[ 2*i*ia+ia : 2*(i+1)*ia ] = sa[ 2*(i+1)*ia-1 : 2*i*ia+ia-1 : -1 ]
    for i in range(ia):
        print(''.join(sa[i::ia]),end='')
    print()

[SPOJ] 2. Prime Generator.py

| Comments

題目連結:http://www.spoj.com/problems/PRIME1/

題目

給予 and ,輸出這個範圍內的所有質數。

解題報告

果然不出所料,噴了一個 TLE 給我,囧。

# TLE

from sys import stdin
from math import sqrt

p = [2,3,5,7]

def is_prime(ia):
    if ia<2:
        return False
    for prime in p:
        if prime*prime > ia:
            break
        if ia % prime == 0:
            return False
    return True

def build_prime(prime_max):
    prime_max = int(sqrt(prime_max))
    i = 11
    j = 2
    while p[-1]<=prime_max:
        if is_prime(i):
            p.append(i)
        i+=j
        j=6-j

build_prime(10**9)
# print(len(p))

# print(p)


for t1 in range(int(stdin.readline())):
    inp = [int(i) for i in stdin.readline().split(' ')]
    if t1 != 0:
        print()
    for i in range(inp[0],inp[1]+1):
        if is_prime(i):
            print(i)

上網找了別人的程式碼 連結,發現還可以利用 buffer 的方式加速,於是,開始動手修改:

# TLE

from sys import stdin
from math import sqrt

p = [2,3,5,7]
output=''

def is_prime(ia):
    if ia<2:
        return False
    for prime in p:
        if prime*prime > ia:
            break
        if ia % prime == 0:
            return False
    return True

def build_prime(prime_max):
    prime_max = int(sqrt(prime_max))
    i = 11
    j = 2
    while p[-1]<=prime_max:
        if is_prime(i):
            p.append(i)
        i+=j
        j=6-j

build_prime(10**9)
# print(len(p))

# print(p)


for t1 in range(int(stdin.readline())):
    m,n = [int(i) for i in stdin.readline().split(' ')]
    if t1 != 0:
        output+='\n'
    if m<=2<=n:
        output+='2\n'
    m += (m%2==0)
    n -= (n%2==0)
    for i in range(m,n+1,2):
        if is_prime(i):
            output+=str(i)+'\n'
print(output,end='')

結果仍然是 TLE,看來要繼續加速!根據 Colin Su 的建議,改成使用 array 來建表,並且預先配置記憶體,避免在執行期間不停的重新配置。

# TLE

from sys import stdin
from math import sqrt
from array import *

p = array('l',[0]*3402)
p[:4] = array('l',[2,3,5,7])
p_cnt = 4
output=''

def is_prime(ia):
    global p_cnt
    if ia<2:
        return False
    for i in range(p_cnt):
        if p[i]*p[i] > ia:
            break
        if ia % p[i] == 0:
            return False
    return True

def build_prime(prime_max):
    global p_cnt
    prime_max = int(sqrt(prime_max))
    i = 11
    j = 2
    while p[p_cnt-1]<=prime_max:
        if is_prime(i):
            p[p_cnt]=i
            p_cnt+=1
        i+=j
        j=6-j

build_prime(10**9)
# print(len(p))


for t1 in range(int(stdin.readline())):
    m,n = [int(i) for i in stdin.readline().split(' ')]
    if t1 != 0:
        output+='\n'
    if m<=2<=n:
        output+='2\n'
    m += (m%2==0)
    n -= (n%2==0)
    for i in range(m,n+1,2):
        if is_prime(i):
            output+=str(i)+'\n'
print(output,end='')

又一次的 TLE,看來這題真的無法偷懶,一定只能用篩法…老實說沒練過篩法的程式,所以寫了超久…好在終於 AC

# AC

from sys import stdin
from math import sqrt
from array import *

p = array('l',[0]*3402)
p[:4] = array('l',[2,3,5,7])
p_cnt = 4
output=''

def is_prime(ia):
    global p_cnt
    if ia<2:
        return False
    for i in range(p_cnt):
        if p[i]*p[i] > ia:
            break
        if ia % p[i] == 0:
            return False
    return True

def build_prime(prime_max):
    global p_cnt
    prime_max = int(sqrt(prime_max))
    i = 11
    j = 2
    while p[p_cnt-1]<=prime_max:
        if is_prime(i):
            p[p_cnt]=i
            p_cnt+=1
        i+=j
        j=6-j

build_prime(10**9)
# print(len(p))


for t1 in range(int(stdin.readline())):
    m,n = [int(i) for i in stdin.readline().split(' ')]
    if t1:
        output += '\n'
    if m<2:
        m = 2
    sign = array('b',[1]*(n-m+1))
    for i in range(p_cnt):
        if p[i]*p[i]>n:
            break
        start = p[i]+p[i]-m
        if start<0:
            start %= p[i]
        sign[start::p[i]] = array('b',[0]*len(sign[start::p[i]]))
    for i in range(m,n+1):
        if sign[i-m]:
            output += str(i)+'\n'
print(output,end='')