ç¬¬ä¸€é¢˜æ˜¯è®¡ç®—å‡ ä½•é¢˜ï¼Œæˆ‘çš„æž„å›¾æ˜¯è¿™æ ·çš„ï¼šæ¯æ¡çº¿æ®µç»™æœ€ç»ˆçš„å›¾è´¡çŒ®å‡ ä¸ªé¡¶ç‚¹ï¼Œä¸¤ç«¯ç‚¹ã€æ‰€æœ‰äº¤ç‚¹ã€ç¦»ç»ˆç‚¹æœ€è¿‘的点,出自åŒä¸€æ¡çº¿æ®µçš„点互相之间的æƒå€¼ä¸ºè·ç¦»ï¼Œå‡ºè‡ªä¸åŒçº¿æ®µä½†äº‹å®žä¸Šé‡åˆçš„点(比如说交点事实上出现两次)之间æƒå€¼ä¸ºé›¶ï¼Œå…¶ä»–æƒå€¼å‡ä¸ºæ£æ— 穷,起点也在图ä¸ï¼Œåœ¨å“ªæ¡çº¿æ®µä¸Šå°±ä¸Žè¿™æ¡çº¿æ®µè´¡çŒ®çš„æ‰€æœ‰é¡¶ç‚¹è¿žè¾¹ã€‚ç„¶åŽåšä¸€æ¬¡Dijkstra,求出所有点到起点的è·ç¦»ï¼Œæœ€åŽæŒ‰ç…§æ¥è¡Œè·ç¦»ä¸ºç¬¬ä¸€å…³é”®å—,行驶è·ç¦»ä¸ºç¬¬äºŒå…³é”®å—找到最å°å€¼å³å¯ã€‚需è¦ç”¨åˆ°çš„è®¡ç®—å‡ ä½•å†…å®¹æœ‰ï¼šåˆ¤ç›¸äº¤ã€æ±‚交点ã€åˆ¤ç‚¹åœ¨çº¿æ®µä¸Šã€æ±‚点与线段的最近点,有些东西我甚至是现å¦çš„,好在时间充裕。 ç¬¬äºŒé¢˜æˆ‘æ¯”è¾ƒæ™•ï¼Œå¦‚æžœæ˜¯å®Œå…¨åˆæ³•çš„robots.txt我的程åºè‚¯å®šèƒ½è§£æžï¼Œä½†æœ€åŽç»“æžœåˆ°åº•æ˜¯æ€Žä¹ˆæ ·è¿˜å¾—çœ‹æ•°æ®ã€‚我忽略了所有的大å°å†™ï¼Œè¿˜å¿½ç•¥äº†æ‰€æœ‰’/’与’\’çš„åŒºåˆ«ã€‚ä¸€å¼€å§‹ç«Ÿç„¶å¿˜è®°å¤„ç†æ³¨é‡Šï¼Œè¿˜å¥½æœ€åŽåŠ ä¸Šäº†ã€‚ ç¬¬ä¸‰é¢˜æ±‚è¾ƒä¼˜è§£ï¼Œæˆ‘çš„ç®—æ³•æ˜¯ä¸€æ¬¡è´ªå¿ƒåŠ ä¸€æ¬¡è´ªå¿ƒçš„è°ƒæ•´ã€‚é¦–å…ˆé€‰æ‹©èƒ½å¤Ÿå¯¹æ•´ä½“å°½é‡ç¬¦åˆçš„关键å—ï¼Œç„¶åŽæ ¹æ®æœ€ä¸åŒ¹é…çš„é‚£ä¸ªäººçš„æƒ…å†µè¿›è¡Œä¸€äº›è°ƒæ•´ã€‚åŠ äº†å¡æ—¶ï¼Œåº”该能ä¿è¯æ¯ä¸ªç‚¹éƒ½æœ‰åˆ†å§ã€‚æœ¬æ¥æƒ³å¯¹äºŽæ‰€æœ‰çš„å—符串进行hashæ¥åˆ¤é‡ï¼Œä½†åˆè§‰å¾—太ä¸ä¿é™©ï¼Œå°±é‡‡ç”¨äº†é¡ºåºæ¯”较æ¥åˆ¤é‡çš„æ–¹æ³•,为了ä¿è¯ä¸è¶…时,如果当å‰çš„è¯æ±‡å¤ªå¤šçš„è¯å°±å¿½ç•¥å‰©ä¸‹çš„æ‰€æœ‰è¯ã€‚è€ƒå®Œäº†ä»¥åŽæ‰æƒ³åˆ°ï¼Œå…¶å®žè›®å¯ä»¥ä½¿ç”¨hash进行第一æ¥çš„判é‡ï¼Œç„¶åŽå†å®žé™…判é‡ï¼Œè¿™æ ·ä¼šå¤§å¤§æé«˜æ•ˆçŽ‡ï¼Œè‚¯å®šå°±ä¸éœ€è¦é‡‡ç”¨é‚£ä¸ªå¯èƒ½ä½¿è§£çš„è´¨é‡å¤§æ‰“折扣的剪æžäº†ã€‚或者使用STL里é¢çš„map也å¯ä»¥å‘€ï¼Œéƒ½æ˜¯å¦OIå¦çš„æŠŠè¿™äº›è‹¥å¹²ä¸ªæœˆå‰è¿˜ç†Ÿç¨”于心的东西都忘完了。 ç¬¬å››é¢˜è¿˜æ˜¯è¾ƒä¼˜è§£ï¼Œç®—æ³•æ˜¯æ¯æ¬¡è¿›è¡ŒBFS,æ¯ä¸ªç»´ä¿®é˜Ÿéƒ½å‘最近的公å¸åŽ»ä¿®ã€‚ä¸€ä¸ªå‰ªæžæ˜¯å½“å‰å·²ç»å®Œå…¨æ²¡æœ‰å¯èƒ½ä¿®å¤çš„å…¬å¸å°±æ”¾å¼ƒï¼ˆåœ¨ç¨‹åºä¸å°±æ˜¯å½“作已ç»å®Œå…¨ä¿®å¤å¤„ç†ï¼‰ã€‚è¿˜æ˜¯ç”¨å¡æ—¶çš„æ‰‹æ®µæ¥ä¿è¯æœ‰åˆ†ï¼Œä¹Ÿå°±æ˜¯å¿«è¶…时了就全部REST。 题目还是ä¸é”™çš„ï¼Œç¬¬ä¸€é¢˜è€ƒå¯Ÿç®—æ³•åŸºæœ¬åŠŸï¼ˆä½†ä¸ºä»€ä¹ˆå°±è€ƒåˆ°äº†æˆ‘æœ€è–„å¼±çš„è®¡ç®—å‡ ä½•â€¦â€¦ï¼‰ï¼Œç¬¬äºŒé¢˜è€ƒå¯Ÿå·¥ç¨‹åŠŸåº•ï¼ˆè¿™ç‚¹æˆ‘ç›®å‰è¿˜ç›¸å½“差……),第三题和第四题都是ä¸é”™çš„算法设计题。我估计第一题和第四题会分比较多,第二题完全看数æ®äº†ï¼Œç¬¬ä¸‰é¢˜å¤šå°‘会得点分。目å‰è¿›å¤èµ›çš„æœŸæœ›æ¯”考å‰é«˜äº†ä¸€äº›ã€‚
å¤èµ›åå•:http://astar.baidu.com/main/id.htm 我在Då—头里é¢ã€‚ 分数太惨了,一个18ã€ä¸€ä¸ª23……也ä¸çŸ¥é“是é å“ªä¸ªè¿›çš„ã€‚è¿›å†³èµ›ä¼°è®¡æ— æœ›äº†ã€‚ä¸è¿‡æœ‰ä¸ªTShirt也ä¸é”™ã€‚ è¿™ä¸¤å¤©æ²¡äº‹çš„æ—¶å€™å†™ä¸ªä¸æ–‡å—符串的库算了。
郑é‡å£°æ˜Žï¼šæœ¬äººå¹¶ä¸è‡ªè®¤ä¸ºâ€œä¼šâ€æ¤é¢˜ï¼Œåªæ˜¯AC了,说说自己程åºçš„æ€è·¯è€Œå·²ã€‚ 原题:http://hi.baidu.com/astar/blog/item/fe22ab18c3c54b0635fa4192.htm 首先è¦å¯¹è¾“入的数æ®è¿›è¡Œé¢„处ç†ï¼ŒæŒ‰ç…§â€œæœ‰è¿žç»çš„X个颜色为Yçš„å°çƒâ€çš„æ ¼å¼ï¼Œå°†è¿žç»çš„åŒè‰²å°çƒä¸€èµ·è€ƒè™‘。s[i]表示第i组å°çƒçš„æ•°é‡ï¼Œtype[i]表示第i组å°çƒçš„类型。注æ„,所有连ç»çš„大于ç‰äºŽM个å°çƒï¼Œéƒ½å¯ä»¥ç‰ä»·åœ°å½“作M-1个å°çƒæ¥å¤„ç†ã€‚ 设计状æ€ä¸ºv[i,j,k1,k2],表示第i组å°çƒåˆ°ç¬¬j组å°çƒçš„左边多了k1个与s[i]åŒè‰²çš„å°çƒå³è¾¹å¤šäº†k2个与s[j]åŒè‰²çš„å°çƒæ—¶è¢«å®Œå…¨æ¶ˆåŽ»çš„æœ€å°ä»£ä»·ã€‚平凡的状æ€åŒ…括:i>j时,状æ€çš„值为0ï¼›s[i]+k1>=M时,状æ€çš„值为v[i+1,j,0,k2]ï¼›s[j]+k2>=M时,状æ€çš„值为v[i,j-1,k1,0]ï¼›i==j时,状æ€çš„值为M-(s[i]+k1)。 对于éžå¹³å‡¡çš„状æ€ï¼Œåªéœ€è¦è€ƒè™‘最左边的一组å°çƒæˆ–最å³è¾¹çš„一组å°çƒå¦‚何处ç†ã€‚以左边的这组å°çƒä¸ºä¾‹ï¼Œå¯å–çš„ç–略有两ç§ï¼šä½¿ç”¨M-(s[i]+k1)个å°çƒå°†å®ƒä»¬å•独消去;设s[i]与s[x]åŒè‰²ï¼Œåœ¨[i+1..x-1]这个åºåˆ—被先行消除åŽï¼Œå°†è¿™ç»„å°çƒä¸Žs[x]åˆå¹¶åŽå†æ¶ˆé™¤ã€‚å³è¾¹çš„å°çƒä¹Ÿå¯ä»¥åŒæ ·å®šä¹‰è¿™ä¸¤ç§ç–略。还有一ç§ç–略就是,当s[i]与s[j]åŒè‰²æ—¶ï¼Œå°†[i+1..j-1]这个åºåˆ—先行消除,å†å°†s[i]ã€s[j]以åŠk1+k2个å°çƒåŒæ—¶æ¶ˆé™¤ã€‚状æ€è½¬ç§»æ–¹ç¨‹å¦‚下: v[i,j,k1,k2]=min{ M-(s[i]+k2) + v[i+1,j,0,k2]; M-(s[j]+k2)+v[i,j-1,k1,0]; v[i+1,x,0,0]+v[x,j,s[i]+k1,k2] (if type[x]=type[i]); v[i,x,k1,s[j]+k2]+v[x+1,j-1,0,0] (if type[x]=type[j]); v[i+1,j-1,0,0] (if type[i]=type[j]&&s[i]+s[j]+k1+k2>=M); v[i+1,j-1,0,0]+(M-(s[i]+s[j]+k1+k2)) (if type[i]=type[j]&&s[i]+s[j]+k1+k2<M); }(i<x<j) 很麻烦å§â€¦â€¦æˆ‘也觉得很麻烦。 如果è°èƒ½ç®€åŒ–一下那真是太好了。 è¿™æ ·çš„è¯ï¼Œä¸€å…±æœ‰O(N^2*M^2)个 状æ€ï¼Œæ¯ç»„状æ€çš„转移需è¦O(N)çš„æ—¶é—´ï¼Œæ€»å¤æ‚度是O(N^3*M^2),ä¸å°±ä¸¥é‡TLEäº†ä¹ˆâ€¦â€¦è¯æ˜¯è¿™ä¹ˆè¯´ï¼Œä¹Ÿè®¸è¿™é“题就能告诉我们Big Oè¿™ç§å…³äºŽå¤æ‚åº¦ä¸Šç•Œçš„åˆ†æžæœ‰æ—¶æ˜¯ä¼šä¸é 谱的。 具体实现时一定è¦é‡‡ç”¨è‡ªé¡¶å‘下的DP实现,也就是所谓的记忆化æœç´¢äº†ã€‚è¿™æ—¶ä½ ä¼šå‘现,实际需è¦è®¡ç®—出æ¥çš„状æ€åªå æ€»çŠ¶æ€æ•°çš„一å°éƒ¨åˆ†ã€‚我对这题的4320个数æ®åšäº†ç®€å•的统计,需è¦è®¡ç®—çš„éžå¹³å‡¡çжæ€çš„æ•°é‡å¹³å‡ä¸º2057.766ä¸ªï¼Œå…¶ä¸æ¤æ•°é‡ä¸º0~1000的有2244个,1001~5000的有1541个,5001~10000的有393个, 10001~20000的有139个,20000ä»¥ä¸Šçš„åªæœ‰3个,最多的需è¦è®¡ç®—26621个状æ€ã€‚ 我想这个题应该å¯ä»¥å¾—到一个比O(N^2*M^2)更好的需è¦è®¡ç®—çš„éžå¹³å‡¡çŠ¶æ€æ•°çš„ä¸Šç•Œï¼Œå¯æœ¬äººç®—法分æžçš„能力有é™ï¼Œå¸Œæœ›æœ‰é«˜äººèƒ½å¤Ÿåœ¨è¿™ä¸€ç‚¹ä¸ŠæŒ‡æ•™ä¸€äºŒã€‚ 最åŽè¯´ä¸€ä¸‹ç©ºé—´é—®é¢˜ï¼Œå¦‚果开一个200x200x20x20的四维数组的è¯ä¼¼ä¹Žå¤ªæµªè´¹ç©ºé—´äº†ï¼Œå¦å¤–,由于“内å˜åˆ†é¡µâ€ç‰æˆ‘也ä¸å¤ªç†è§£çš„åŽŸå› ï¼Œç¨‹åºçš„空间用é‡å¯¹å®žé™…è¿è¡Œæ—¶é—´ï¼ˆå¹¶éžâ€œç”¨æˆ·æ—¶é—´â€æˆ–CPU时间)是有影å“çš„ã€‚æˆ‘é‡‡ç”¨çš„æ–¹æ³•æ˜¯æ¯æ¬¡åЍæ€åˆ†é…一个N*N*M*Mçš„ä¸€ç»´æ•°ç»„ï¼Œç”¨æ¥æ¨¡æ‹Ÿå››ç»´æ•°ç»„。例如状æ€v[i,j,k1,k2]在这个数组ä¸çš„ä¸‹æ ‡å°±åº”è¯¥æ˜¯((i*N+j)*M+k1)*M+k2。当然,也å¯ä»¥å°†å®ƒç†è§£æˆä¸€ç§æ²¡æœ‰å†²çªçš„hash——将å–值有é™åˆ¶çš„å››å…ƒç»„æ˜ å°„ä¸ºä¸€ä¸ªæ•´æ•°ã€‚å¯¹äºŽæœ¬é¢˜çš„æ•°æ®æ¥è¯´ï¼Œæˆ‘çš„ç¨‹åºæœ€å¤šæ—¶ç”¨äº†4128KB的空间。 于是,这é“题的4320个数æ®å°±è¢«æ¯”è¾ƒå®Œç¾Žçš„è§£å†³äº†ã€‚æ³¨æ„æˆ‘并䏿˜¯è¯´è¿™é“é¢˜è¢«å®Œç¾Žçš„è§£å†³äº†ï¼Œå› ä¸ºç®—æ³•çš„ç†è®ºå¤æ‚度ä»ç„¶å¾ˆé«˜ï¼Œä¸èƒ½ä¿è¯æ— 法设计出达到ç†è®ºå¤æ‚度上界的数æ®ã€‚ 欢迎批评指æ£ã€‚ zuma.rar 这是我åšçš„cena评测包,内有我的程åºï¼Œæ•°æ®ç”±é™ˆå¯å³°æä¾›ï¼Œå…±10组输入输出文件,æ¯ä¸ªè¾“入文件ä¸å«432组数æ®ã€‚