有2009張卡片,每張卡片一面為金色,另一面為黑色,且在一張長桌子上排成一排.開始時,所有卡片的金色面朝上.兩個玩家站在桌子的同側,且交替地進行操作.每次操作規則如下:選擇相鄰的5O張卡片,且最左邊的一張卡片的金色面朝上,其翻轉卡片,使得金色面朝上的變為黑色面朝上,黑色面朝上的變為金色面朝上,並規定最後一個按上述規則操作的玩家獲勝.問:(1)操作是否一定會結束?(2)先操作的玩家是否有取勝策略?
A、是,是
B、是,否
C、否,是
D、否,否
區間[1,n]內有n個數字。現在按順序進行n次操作,操作有以下兩種:
1.給你三個整數L,R,K。把[L,R]的數字都修改成k
2.給你兩個整數L,R。詢問[L,R]的數字之和
對於所有的L,R,K,有
1<=L<=R<=n
k為整數,且絕對值小於10的9次方
訪問或修改一個數字需要消耗1個單位的時間
現在要求設計一種效率儘可能高的演算法來正確回答所有的操作2。
效率高的演算法要求隨著n規模增長,所花時間T的增長儘可能慢。
如T與n^2成正比的演算法,效率就要低於T與n成正比的演算法。
那麼最優情況下,T與下列哪個選項成正比?
提示:可以使用額外的空間來記錄信息。
A、n^3
B、n^2
C、n*sqrt(n) (sqrt表示平方根)
D、n*log(n) (由於不考慮正比係數,所以log的底數可以忽略)
E、n
F、sqrt(n)
G、log(n)
H、1
新浪微博 70,000+
移動應用