绗竴椤?/p>
鍏卞洓椤?/p>
NOIP 2003
鏅強缁勮瘯棰樸�婃爤鐨勮鏁般�嬭В棰樻姤鍛?/p>
缂栬�呮寜锛?/p>
鏈枃鍗佸垎璇︾粏鐨勪粙缁嶄簡銆婃爤鐨勮鏁般�?/p>
杩欓鐨勪袱绉嶉�掓帹绠楁硶锛屽浘鏂囧苟鑼傦紝
鍗佸垎閫傚悎鍒濆鑰?/p>
闃呰锛屽苟浠庝腑棰嗕細娓呮櫚銆佷弗瀵嗙殑鍒嗘瀽鎬濊矾銆傚彟澶栵紝闅忔枃闄勫甫鐨勭▼搴忓崄鍒嗙畝娲侊紝鍊煎緱瀛︿範銆?/p>
浣滀负鏅強缁勭殑璇曢锛?/p>
鍑洪鑰呯殑鎰忓浘鍙兘浠呬粎甯屾湜鑰冨療閫夋墜瀵规悳绱㈠拰閫掓帹绠楁硶鐨勬帉鎻★紝
浣?/p>
鏄紝鏈浣滀负缁勫悎鏁板
Catalan
鏁扮殑缁忓吀妯″瀷锛屽彲浠ョ敤缁勫悎鏁板鐨勬柟娉曞揩鎹烽珮鏁堢殑姹傝В銆傜被
浼肩殑鍒╃敤
Catalan
鏁版眰瑙ｇ殑闂鏈?/p>
NOI2001
绂忓缓缁勯槦璧涖�婄悆杩疯喘绁ㄩ棶棰樸�嬬瓑锛岀被浼肩殑閫掓帹闂?/p>
棰樿繕鏈?/p>
NOI2000
绂忓缓缁勯槦璧涖�婅溅鐨帓搴忛棶棰樸�嬬瓑锛屽笇鏈涙湁鑳藉姏鐨勫悓瀛︾户缁爺绌躲�?/p>
鎽樿锛?/p>
绠楁硶涓�
绠楁硶浜?/p>
绠楁硶涓?/p>
绠楁硶
閫掓帹
閫掓帹
Catalan
鏁?/p>
鏃堕棿澶嶆潅搴?/p>
O(n
2
)
O(n
2
)
O(n)
绌洪棿澶嶆潅搴?/p>
O(n)
O(n
2
)
O(1)
闂杞堪锛?/p>
姹備竴鍒楀叡
n
杈嗙殑鐏溅鎸夐『搴忛�氳繃涓�涓爤鎵�浜х敓鐨勬帓鍒楁�绘暟銆?/p>
鍒嗘瀽锛?/p>
杩欎竴绫荤粍鍚堣鏁伴鐩樉鐒朵笉鑳界敤鎼滅储鐨勬柟娉曟妸鎵�鏈夊彲鑳界殑绉诲姩鏂规閮界┓涓惧嚭鏉ュ啀缁熻
鎬绘暟鈹�鈹�杩欐牱鍋氭椂闂村鏉傚害鏋佸ぇ銆傝繖閬撻涓庣粡鍏哥殑
HANOI
闂寰堢浉浼硷紝鎵�浠ュ簲褰撴牴鎹棶棰?/p>
鏈韩鐨勬�ц川锛屽埄鐢ㄧ粍鍚堟暟瀛︾殑鍘熺悊锛屽皢鍘熼棶棰樿浆鍖栦负閫掑綊褰㈠紡锛屾壘鍒拌绠楁�绘暟鐨勯�掑綊鏂圭▼锛?/p>
鍐嶈繘琛岃绠椼�?/p>
绠楁硶涓�锛?/p>
鎴戜滑涓嶅Θ鐩存帴璁?/p>
n
杈嗙伀杞︿骇鐢熺殑鎺掑垪鎬绘暟涓?/p>
f(n)
銆傜湅鐪嬭兘涓嶈兘鎵惧埌涓�浜涜寰嬨�?/p>
濡傚浘
,n
鍒楃伀杞﹂�氳繃鏍?/p>
,
璧峰杞﹀ご鍦ㄨ溅鍒楁渶鍓嶇銆?/p>
缁忚繃绉诲姩鍚?/p>
,
杞﹀ご澶勫湪浜嗙
a+1
浣?/p>
,
杞﹀ご
鍓嶆湁
a
杈嗚溅
,
杞﹀ご鍚庢湁
b
杈嗚溅
(a>=0,b>=0)
銆傚垯
n=a+b+1,b=n-a-1
銆?/p>