æ¯ä¸ªæˆ–æœ‰æˆ–æ— æ„义的开始,我都会å˜å¾—兴奋而èºåŠ¨ï¼Œä¸€äº›å¿˜å´æŠ›å¼ƒï¼Œä¸€äº›æ†§æ†¬æœŸè®¸ã€‚å°±åƒä»Šå¹´ä¸€æœˆæˆ‘æ— ç†ç”±åœ°åšå®šåœ°è®¤ä¸º2008å¹´æ˜¯ç¾Žå¥½çš„ä¸€å¹´ä¸€æ ·ï¼Œä¸ƒæœˆçš„æœ€åˆï¼Œæˆ‘åŒæ ·åšå®šåœ°åšå‡ºä¸ƒå…«æœˆçš„æš‘è®ã€ä»Šå¹´ä¸‹åŠå¹´ä»¥åŠæ•´ä¸ªå¤§ä¸€çš„一年时光都将美丽姣好的没有ç†ç”±çš„结论。——七月四日 过了二分之一的这个七月,给我的感觉ä¸åŒäºŽä»¥å¾€çš„任何一个时期。——æžåº¦ç¹å¤çš„åŒæ—¶ï¼Œä¹Ÿæžåº¦ç®€çº¦ã€‚æžåº¦ç«çƒçš„åŒæ—¶ï¼Œåˆæžåº¦å†·å¯‚ã€‚è´¯ç©¿æ¯æ—¥çš„主线是,一边拼命挣钱ã€ä¸€è¾¹æ‹¼å‘½èŠ±é’±ï¼Œä¸€è¾¹åŠªåŠ›å‡ºé¢˜ã€ä¸€è¾¹åŠªåŠ›åšé¢˜ï¼Œä¸€è¾¹å°½åŠ›æé«˜è‡ªå·±ã€ä¸€è¾¹å°½åŠ›æŒ‡å¯¼åˆ«äººã€‚å°±æ˜¯è¿™æ ·ï¼Œè‹¥éžäº²åŽ†å¾ˆéš¾ä½“ä¼šã€‚ 集è®å‰ä¸¤å‘¨æœŸå·²ç»ç»“æŸçš„å…åœºæ¯”èµ›éœ€è¦æ€»ç»“一下。 Contest 2 by Balloon 是没进行任何ACM/ICPCæœ‰å…³çš„æ´»åŠ¨å‡ å天之久åŽç¬¬ä¸€æ¬¡æ¯”赛,完全没状æ€ï¼ŒRank 12。ä¾åºçœ‹åˆ°D,便知é“该怎么åšäº†ï¼Œ19 min 1Y,是全场第一个ACæ¤é¢˜çš„。看到有两人AC了A,略æ€è€ƒä¾¿æƒ³åˆ°äº†è·ŸNOIæŸé¢˜ç±»ä¼¼çš„åšæ³•。当时认为,精度的缘故,需è¦å†™ä¸€ä¸ªåˆ†æ•°ç±»ï¼Œå¾ˆå¿«çš„æ•²å®Œäº†ã€‚åŽæ¥çš„äº‹å®žè¯æ˜Žï¼Œæˆ‘çŽ°åœºæ•²çš„åˆ†æ•°ç±»å¯¹è´Ÿæ•°çš„å¤„ç†æœ‰æžå¤§æ¼æ´žã€‚坿ˆ‘错误地估计了错误,一éé地在主程åºä¸å¯»æ‰¾bug,WAæ— æ•°æ¬¡æ‰æ„è¯†åˆ°æ˜¯åˆ†æ•°ç±»å†™å¾—æœ‰é—®é¢˜ã€‚åŽæ¥æˆ‘å‘现,åªè¦æŠŠæˆ‘第一次æäº¤çš„很垃圾的程åºåŠ ä¸Šä¸¤è¡Œè¡¥ä¸ï¼Œå°±å¯ä»¥AC。现场在66minäº¤åˆ°ç¬¬ä¹æ¬¡æ‰ACçš„åŽŸå› ï¼Œä¸€æ˜¯ä¸€å¼€å§‹é”™è¯¯åœ°ä¼°è®¡äº†bugçš„ä½ç½®ï¼ŒäºŒæ˜¯æ£ç¡®åœ°æ‰¾å‡ºbugä»¥åŽæ²¡æœ‰ä»”细æ€è€ƒå°±å¼€å§‹å†™è¾ƒä¸ºå¤æ‚的补ä¸ï¼Œè€Œæ²¡æœ‰çœ‹æ¸…错误的本质所在。这两个题水过以åŽï¼Œçœ‹ä¸ŠåŽ»å¯åšçš„题目有Bå’ŒE。对于B,我éžå¸¸æ€€ç–‘è‡ªå·±æ¤æ—¶çš„coding能力能å¦åº”对这个算法ä¸éš¾ä»£ç 似乎ä¸å¥½å†™çš„题目,于是看E,这个我最终交了13次也没AC的题目。交了4次E,完全ä¸çŸ¥é“为什么WA,放弃了。然åŽå¼€å§‹å¾ˆæ…¢çš„写Bï¼Œå†™ä¸€ç§æžåº¦éº»çƒ¦çš„算法,一直到145minæ‰äº¤äº†ä¸¤æ¬¡ACã€‚å†æ¬¡æ¦‚览剩下的题目,ä»ç„¶è®¤ä¸ºåªæœ‰Eå¯åšï¼Œæ‹¼å‘½æŸ¥é”™å’Œæäº¤ï¼Œä¸€ç›´åˆ°æ¯”赛结æŸéƒ½æ— æžœã€‚æœ€ç»ˆæ‰æ˜Žç™½ï¼ŒåŽŸæ¥Eæ˜¯å› ä¸ºè¯¯è§£äº†scanf且\n”çš„æ„æ€ï¼Œå¯¼è‡´è¯»å…¥å‡ºé”™äº†â€¦â€¦äº¤çš„第二个程åºçš„ç®—æ³•å°±æ˜¯å®Œå…¨æ— è¯¯çš„ã€‚å¦‚æžœèƒ½æ›´æ—©åœ°åšæŽ‰Eï¼Œæ˜¾ç„¶ä¸Žå®ƒçš„åŠ å¼ºç‰ˆF题ä¸å˜åœ¨AC的障ç¢ã€‚真没想到算法一点问题都没有还会败在输入上…… Contest 3 by Cannon 也是一场éƒé—·çš„æ¯”赛,Rank 8,虽然Rank有所上å‡ï¼Œä½†æ˜¯é¢˜æ•°ä¸Šéžå¸¸ä¸æ»¡æ„ï¼Œåªæœ‰ä¸¤é¢˜ï¼Œæ˜¯ç¬¬ä¸€å的三分之一。陷入两个大å‘,是åšè¿‡çš„æ‰€æœ‰æ¯”èµ›ä¸æœ€éƒé—·çš„一次。看了A就觉得å¯åšï¼Œä¸è¿‡å¤§æ¦‚由于慢çƒçš„缘故,26min时交到第4次æ‰ACï¼ŒåŽŸå› ä¸»è¦æ˜¯codingæ—¶æ¬ è€ƒè™‘å§ã€‚åˆçœ‹äº†Bå’ŒC,B觉得略有麻烦,Cä¼¼ä¹Žæ˜¯è£¸çš„é«˜ç²¾è€Œå·²ï¼Œå°±å¼€å§‹å†™å¤§æ•°ç±»ã€‚çœ‹æ¥æ˜¯å®Œå…¨æ²¡æœ‰å¸å–上次手写分数类的教è®ï¼Œå¯¹è‡ªå·±å½“下的coding能力认识ä¸è¶³ï¼Œå¤§æ•°ç±»ä¸æ˜¯å†™é”™å°±æ˜¯æ•ˆçŽ‡æœ‰é—®é¢˜ã€‚æœŸé—´æŽ¨äº†ä¸‹Bçš„å¼å,也AC了。在C还是没能AC的情况下,åˆé™·å…¥äº†F,记忆化æœç´¢ï¼ŒWAæ— æ•°ã€‚åŽæ¥å‘çŽ°ï¼Œæˆ‘çš„ç®—æ³•å’Œæ ‡ç¨‹ä¸ä¸€æ ·ï¼Œä½†ä¹Ÿæ²¡æ‰¾åˆ°å®žè´¨æ€§çš„错误。剩下的时间就是在疯狂地改和交Cå’ŒFï¼Œæ— æžœã€‚æ¯”èµ›ç»“æŸå‰20minæ„识到Cå¯ä»¥ç”¨æ¨¡æ¿ï¼Œå¯æƒœå¯¹å¦æ ¡çš„大数模æ¿å®Œå…¨ä¸ç†Ÿæ‚‰ï¼ŒC++ä¸stream相关的内容也基本忘了,输入输出都有点æžä¸å®šâ€¦â€¦çŽ°åœ¨çœ‹æ¥ï¼Œè¿™æ¬¡æ¯”èµ›AC é¢˜æ•°è¿‡å°‘çš„åŽŸå› ä¹‹ä¸€æ˜¯æˆ‘è¾ƒä¸ºç†Ÿæ‚‰å’Œæ“…é•¿çš„DP一题都没出。è§åˆ°çš„题目太少,略有些 ad hoc 的题目就会æžä¸å®šï¼Œè¿™æ˜¯ç›®å‰æœ€å¤§å¼±ç‚¹ã€‚ Contest 4 by Die 的感觉ç¨å¾®å¥½ä¸€ç‚¹ï¼ŒRank 5。35 min时一次AC了H,擅长的套路。然åŽ67min时用了三次æäº¤AC了G,算法完全æ£ç¡®ï¼Œé—®é¢˜åœ¨äºŽæ— 视了题目ä¸ä¸€ä¸ªæ¡ä»¶ï¼Œå¯¼è‡´ä¸¤æ¬¡WA。然åŽå°±çœ‹åˆ°å¾ˆå¤šäººè¿‡äº†B,便也很容易地AC了,在æ¤ä¹‹å‰çš„一次æäº¤ç«Ÿç„¶æ˜¯MLEâ€¦â€¦åŽŸå› æ˜¯å¿˜äº†è¾“å…¥å®Œæˆä»¥åŽbreak。下一é“é¢˜çš„ç›®æ ‡æˆ‘é€‰äº†E,交了9次基本都TLE以åŽï¼Œç¡®å®šè‡ªå·±çš„算法错了,就ä¸é€”离开机房åƒé¥åŽ»äº†ã€‚è¿™åœºæ¯”èµ›åšå¾—太急,导致ä¸ç»†å¿ƒã€‚èµ›åŽè§‰å¾—,如果更多地花点时间æ€è€ƒä¸‹D,是应该能æžå‡ºæ¥çš„,错误地估计了其难度与麻烦程度。 第一轮完毕以åŽï¼Œè®¡ç½šæ—¶å’Œä¸è®¡ç½šæ—¶çš„rank分别是9å’Œ11。 第二轮,从 Contest 5 by Balloon å¼€å§‹ï¼Œé€æ¥æœ‰äº†çжæ€ï¼ŒRank 3,比赛过程å¯ç§°é¡ºåˆ©ã€‚一开始看到了B,觉得是一般难度的DPï¼Œéšæ‰‹å†™äº†äº¤ä¸ŠåŽ»ï¼Œç„¶åŽWA。é™ä¸‹æ¥çœ‹ä¸€ä¸‹ï¼Œå‘现整个算法是错的,æ¢äº†æ£ç¡®çš„算法é‡å†™ï¼Œç»“æžœç–忽了一å¥ä¿æŒå•调性的è¯ï¼Œäº¤åˆ°ç¬¬ä¸‰éæ‰ACã€‚ä¸‹é¢æ˜¯E,éžç®—法题,比较熟练地用ç€STL,1Y了。Fåˆæ˜¯ä¸€ä¸ªDP,å¸å–æ•™è®ä»”细想清楚了æ‰å†™ï¼ŒåŒæ ·1Y。接下æ¥åšA的时候åˆå¡äº†ä¸€ä¸‹ã€‚最开始写的是æœç´¢ï¼Œæ²¡æœ‰ä¼°è®¡å¥½å¤æ‚度,TLE两次,第一次交TLE了以åŽè¿˜ä»¥ä¸ºæ˜¯è¢«å¡äº†å¸¸æ•°ï¼Œç¬¬äºŒæ¬¡TLEåŽç®—äº†ä¸‹å¤æ‚åº¦æ‰æ„è¯†åˆ°å¿…é¡»åŠ ä¸Šè®°å¿†åŒ–ã€‚åŠ è®°å¿†åŒ–çš„æ—¶å€™åˆå†™é”™äº†ä¸€æ¬¡ï¼Œç¬¬å››æ¬¡æ‰AC,属于失误。看到wanwei似乎很轻æ¾çš„1Y了winstyçš„å°è˜‘è‡é¢˜G,虽然明知自己对这ç§é¢˜ç›®æ ¹æœ¬ä¸æ“…长,但也没å‘现有别的å¯åšçš„é¢˜ç›®äº†ã€‚å†™äº†å¾ˆä¹…ï¼Œè°ƒäº†å¾ˆä¹…ï¼ŒèŠ±è´¹äº†è¿‘ä¸€ä¸ªå°æ—¶ï¼Œè¿˜å¥½1Y了。在这一段过程ä¸ä¸€ç›´éƒ½æ˜¯ç´§éšMurphy,排å第二,看到他过了C,就也去æžã€‚没想到一下å就看出了C的本质,用DP预处ç†ä¸€ä¸‹åŽï¼Œåˆ1Y了。这时,åªå‰©ä¸‹äº†ä¸€é“没人碰的蘑è‡é¢˜D,我怎么看都没信心,很累,åˆè®¡ç®—了一下å‘现åŽé¢çš„人ä¸å¤§å¯èƒ½è¶…过æ¥ï¼Œå°±å¾ˆé«˜å…´åœ°æå‰è¿‘ä¸€ä¸ªå°æ—¶å‡ºåŽ»åƒé¥äº†ã€‚åŽæ¥å¾—知Gçš„æ•°æ®æœ‰å°é—®é¢˜ï¼Œrejudge了以åŽrank 2çš„ä½ç½®å˜æˆäº†watashiã€‚åœ¨é¢˜æ•°ä¸Šï¼Œåº”è¯¥è¯´æ²¡æœ‰ä»»ä½•é—æ†¾ï¼Œ1Y率有æé«˜ï¼Œå¾ˆæ»¡æ„。 Contest 6 by Cannon 是目å‰ä½ç½®çš„æœ€å¥½æˆç»©ï¼ŒRank 2,但是ä¸åƒä¸Šæ¬¡ä¸€æ ·æ¯«æ— é—æ†¾ï¼Œå› 为是由于ä¸å¿…è¦çš„失误没得到Rank 1。å‰ä¸€å¤©æ™šä¸Šåªç¡äº†äº”ä¸ªå°æ—¶ä¸åˆ°å¯¼è‡´çжæ€å¾ˆå·®ã€‚开场先åšäº†çŸ©é˜µé¢˜G,打算秒æ€ä¹‹ï¼Œæ²¡æƒ³åˆ°ä¸€å¼€å§‹å°±å› 为矩阵乘法写得ä¸å¤ªå¥½è€ŒTLE两次,优化了效率以åŽåˆæŽ¥è¿žåœ°WA,è¦éƒé—·æ»äº†ã€‚到论å›é‡Œçœ‹äº†ç”ç–‘æ‰çŸ¥é“原æ¥è‡ªå·±æŠŠé¢˜æ„ç†è§£é”™äº†ï¼Œæ”¹ä¹‹å³AC。91min第7次æ‰AC这题,真是开场ä¸åˆ©ã€‚AC了G以åŽå¼€å§‹åšC,很è€çš„题,用匹é…åšï¼Œæ²¡æƒ³åˆ°ç«Ÿç„¶WA。难é“自己已ç»é€€åŒ–到连Hungaryè¿™æ ·ç®€å•的算法都会写错?很沮丧,就暂时放下了。看到A是ä¸éš¾çš„DP。哦……好å§ï¼Œå¯¹äºŽæˆ‘æ¥è¯´ä¸éš¾çš„DP,WA一次以åŽAC了,WAçš„åŽŸå› æ˜¯æ²¡çœ‹æ¸…é¢˜â€¦â€¦å¯’ã€‚æŠŠæ‰‹æ”¾åœ¨é”®ç›˜æ—的圣ç»ä¸Šï¼Œå®šç¥žäº†ä»¥åŽåšC,一个ä¸å¤ªéš¾çš„æœç´¢é¢˜ï¼Œç»ˆäºŽä¸€æ¬¡AC。接下æ¥çš„æ—¶é—´å°±åœ¨æžCï¼Œå‡ºå¾ˆå¤šç»„æ•°æ®æ¥æµ‹ï¼Œæ€Žä¹ˆéƒ½çœ‹ä¸å‡ºä¸ºä½•会WA……这时看到自己是Rank 2,3题的两人之一,但由于罚时太多太多åŽé¢çš„人很有å¯èƒ½è¶…过æ¥ã€‚å一点一刻的时候最åŽäº¤äº†ä¸€æ¬¡WAç»ˆäºŽæ”¾å¼ƒäº†ï¼Œå› ä¸ºå®žåœ¨æ˜¯æ‰¾ä¸åˆ°é”™è¯¯ï¼ŒåŠ ä¸Šæžå…¶çžŒç¡ï¼Œå°±è·‘掉了。没想到但是直到结æŸç«Ÿç„¶èƒ½ä¿æŒä½Rank 2çš„ä½ç½®ã€‚åŽæ¥å¾—知,Cæ˜¯å› ä¸ºè¾“å…¥å¤„ç†é”™äº†å¯¼è‡´ä¸æ–WAã€‚ç«Ÿç„¶åˆæ˜¯è¯¥æ»çš„scanf里é¢çš„”\n”,第三é“é¢˜äº†ï¼æ‰€ä»¥å¤ªé—憾了……真ä¸åº”该那么早离开的。以åŽå†é‡åˆ°è¿™ç§èŽ«å其妙的WA一定è¦ä»”细验è¯ä¸‹è¾“入输出。 Contest 7 by Die æ‰“ç ´äº†å‰äº”场Rankå•调递å‡çš„神è¯ï¼ŒRank 6。åšå¾—ä¸å¤Ÿå¥½ï¼Œç½šæ—¶å¤ªå¤šäº†ï¼Œè€Œä¸”ç–略有失误。开场以åŽå¤§è‡´çœ‹äº†ä¸€é题,å‘现A是å¯åšçš„DP,虽然有点麻烦。写了四å多分钟,交上去WA。惊讶地å‘现这时AC两题的都有了,都是Bå’ŒE,E有åå‡ ä¸ªAC的。æ„识到Eæ˜¯ç¬¬ä¸€éæ²¡çœ‹å‡ºæ¥çš„æžæ°´çš„é¢˜ï¼Œéšä¾¿ä¸€å†™å°±1Y了。åˆåŽ»åšA,åˆWA一次,å‘现没看清题,53min第三次æäº¤æ‰AC了。接下æ¥å½“然是åšB,åšçš„过程很ä¸é¡ºåˆ©ã€‚一开始å‘现æœç´¢å¯åšï¼Œç»åŽ†äº†MLEã€TLE和两次WA以åŽï¼Œå¯¹æœç´¢æœ‰äº›ç»æœ›äº†ã€‚惊奇地å‘现用匹é…å¯åšï¼Œç²˜è´´äº†ä»»æ„图匹é…的模æ¿ï¼Œç»ˆäºŽå¾ˆä¸å®¹æ˜“地AC了。事实上这题完全å¯ä»¥ç”¨æœç´¢ï¼Œæ˜¯æˆ‘一开始写丑了。接下æ¥çš„ç›®æ ‡æˆ‘é”定在D上,自以为对这类最优比率的题目éžå¸¸ç†Ÿæ‚‰ï¼Œä¸å°±æ˜¯äºŒåˆ†ç”案么。虽然写起æ¥ä¹Ÿæœ‰ç‚¹ç¹ï¼Œä¸è¿‡è¿˜æ˜¯å¾ˆæœ‰ä¿¡å¿ƒåœ°åœ¨å†™ã€‚写完以åŽï¼Œå°±æ€»æ˜¯WA,å‘现我的Bellman-Ford总是莫å其妙地找ä¸åˆ°è´ŸçŽ¯â€¦â€¦åœ¨é‚£è¾¹æ‹¼å‘½åœ°è°ƒå•Šæ”¹å•Šï¼ŒåŸºæœ¬ä¸Šå„ç§å¯èƒ½çš„错误返回都ç»åŽ†äº†ä¸€é,还是没能AC。期间å‘现比我多一题的都是AC了F,但是F使我éžå¸¸ä¸ç†Ÿæ‚‰çš„类型,完全没法形æˆå®Œæ•´çš„æ€è·¯ã€‚åˆ°äº†åªå‰©ä¸€ä¸ªå°æ—¶çš„æ—¶å€™ï¼Œæˆ‘终于放弃了æžäº†ä¸€ä¸ªåŠå°æ—¶çš„D,开始硬ç€å¤´çš®å†™æ€è·¯è¿˜æƒ³ä¸æ¸…楚的Fï¼ŒåŠ ä¸Šè¿™æ—¶å·²ç»å¾ˆç´¯äº†ï¼Œä¸€ç›´åˆ°æ¯”赛结æŸè¿˜æ²¡è°ƒå‡ºæ ·ä¾‹æ¥â€¦â€¦ç½šæ—¶å¤ªå¤šå°±ä¸è¯´äº†ï¼Œçœ‹é”™é¢˜å†™é”™ä»£ç 还å¯ä»¥è§£é‡Šæˆçжæ€ä¸å¥½ã€‚关键是,这场比赛的ç–略太失误了ï¼åƒA那么麻烦的DP显然ä¸åº”该作为第一é“题æ¥åšï¼Œè¦ç›¸ä¿¡è‚¯å®šä¼šæœ‰æ¯”这水的题嘛,这直接导致了Eå’ŒB的用时比æ£å¸¸å€¼å¤šå¤šäº†ã€‚至于Dï¼ŒåŽæ¥çŸ¥é“,应该用è¿ä»£æ³•åšçš„。自己ä¸ä¼šè¿™ä¸ªæ–¹æ³•,ACä¸äº†ï¼Œä¹Ÿæ²¡ä»€ä¹ˆä¸æ£å¸¸ã€‚但问题就在于,Dæžäº†é‚£ä¹ˆé•¿æ—¶é—´ï¼Œäº¤äº†24次,实在有些过于固执了。虽然E是我ä¸ç†Ÿæ‚‰çš„类型,但毕竟是éžå¸¸å¯åšçš„题,那么多人都AC了,åªè¦æœ‰æ—¶é—´æ…¢æ…¢æžåº”该ä¸å˜åœ¨é—®é¢˜çš„,至少完全å¯ä»¥å†™ä¸ªå¤æ‚度略高但好写很多的算法。唉,还是ç»éªŒå°‘,太莽撞。 第二轮结æŸä»¥åŽï¼Œè®¡ç½šæ—¶å’Œä¸è®¡ç½šæ—¶çš„Rank都是6。 ~~~~以下是三ã€å››è½®çš„æ€»ç»“~~~~〠Contest […]
About Me
-
Recent Posts
Categories
Tag Cloud
ACM-ICPC Avril blog Code Complete Emacs GCC GDB Linkin Park LLVM matrix67 NOI NOIP OI OIBHæ¯ OIBH队 Paul Potts PKU python Scheme SICP USACO wiki ZJU ä¹ é¢˜ ä¹¦ç± ä»£ç 伊朗åŒå¦ åˆç§Ÿ 北京 动æ€è§„划的æ€è€ƒè‰ºæœ¯ æ ¡èµ› æ•°å¦ æ•°è®º 笔记 算法 ç»„åˆæ•°å¦ 翻墙 çœé˜Ÿé›†è® çœé€‰ 百度之星 计划 诗 软件工程 éŸ³ä¹ éƒ‘å·žArchives