{"id":223704,"date":"2012-01-27T18:00:22","date_gmt":"2012-01-27T10:00:22","guid":{"rendered":"http:\/\/blog.yangzhe1991.org\/?p=223704"},"modified":"2014-03-14T19:58:10","modified_gmt":"2014-03-14T11:58:10","slug":"neuacm-2012-1-monthly","status":"publish","type":"post","link":"https:\/\/yangzhe1991.org\/blog\/2012\/01\/neuacm-2012-1-monthly\/","title":{"rendered":"NEUACM2012\u5e741\u6708\u6708\u8d5b\u51fa\u9898\u62a5\u544a"},"content":{"rendered":"

\u8fd9\u6b21\u7684\u7ed3\u679c\u5e94\u8be5\u5c31\u662f\u201c\u60c5\u7406\u4e4b\u5916\u610f\u6599\u4e4b\u4e2d\u201d\u5427\u3002\u610f\u6599\u4e4b\u4e2d\u662f\u56e0\u4e3a\u770b\u5230\u6211\u653e\u5728HDOJ\u4e0a\u7684\u7ec3\u4e60\u9898\u6709\u591a\u5c11\u4eba\u505a\u3001\u591a\u5c11\u4ebaAK\u5c31\u80fd\u5927\u81f4\u4f30\u8ba1\u51fa\u8fd9\u6b21\u4e0d\u4f1a\u6709\u592a\u591a\u65b0\u624b\u505a\u51fa\u9898\u6765\u3002\u4f46\u6211\u4e5f\u6ca1\u964d\u4f4e\u9898\u76ee\u7684\u96be\u5ea6\uff0c\u56e0\u4e3a\u6211\u4eec\u7684\u8981\u6c42\u662f\u4e0d\u4f1a\u964d\u4f4e\u7684\u3002\u843d\u540e\u4e8e\u6211\u4eec\u7684\u8981\u6c42\u53ef\u4ee5\u52aa\u529b\u53ef\u4ee5\u8ffd\u8d76\uff0c\u4f46\u5982\u679c\u5230\u4e864\u6708\u4f9d\u7136\u843d\u540e\u90a3\u5c31\u662f\u771f\u7684\u88ab\u6dd8\u6c70\u4e86\u3002\u53bb\u5e74\u6211\u4eec\u662f\u572811\u6708\u548c12\u6708\u8bb2\u56fe\u8bba\u7684\u7b97\u6cd5\uff0c\u800c\u5bd2\u5047\u5b8c\u5168\u653e\u517b\u3002\u540e\u6765\u53cd\u9988\u7684\u60c5\u51b5\u662f\u666e\u904d\u5bd2\u5047\u4e0d\u600e\u4e48\u505a\u9898\u7136\u540e12\u6708\u7684\u65f6\u5019\u542c\u4eba\u8bb2\u7b97\u6cd5\u4e5f\u542c\u4e0d\u660e\u767d\u3002\u4e8e\u662f\u6539\u4e3a\u73b0\u5728\u7684\u5f62\u5f0f\u3002\u4e0d\u77e5\u9053\u5230\u5e95\u6709\u591a\u5c11\u4eba\u5728\u770b\uff0c\u4f46\u53ef\u4ee5\u80af\u5b9a\u7684\u662f\u770b\u7684\u4eba\u6ca1\u770b\u660e\u767d\uff0c\u4e0d\u7136\u4e0d\u4f1a\u51fa\u73b0\u6700\u5c0f\u751f\u6210\u6811\u6a21\u677f\u9898\u4e5f\u4e0d\u4f1a\u505a\u7684\u60c5\u51b5\u3002\u81f3\u4e8e\u4e3a\u4ec0\u4e48\u6ca1\u770b\u660e\u767dppt\/\u4e66\u8fd8\u6ca1\u5728bbs\/QQ\u7fa4\u95ee\u522b\u4eba\uff0c\u6211\u5c31\u4e0d\u77e5\u9053\u4e86\u3002<\/p>\n

<\/p>\n

\u8fd9\u6b217\u9898\uff0c3\u9898\u738b\u5b50\u4e00\u51fa\u7684\uff0c3\u9898\u6211\u51fa\u7684\uff0c1\u9898\u662f\u536b\u6b23\u627e\u7684\u6570\u5b66\u9898\u7136\u540e\u6211\u6539\u63cf\u8ff0\u51fa\u6570\u636e\u3002\u5148\u539f\u6587\u7167\u642c\u738b\u5b50\u4e00\u7684\u9898\u89e3\u3002<\/p>\n

B Adventure of Dragon’s Mystery:
\n\u7b80\u5355DFS\uff0c\u7528used\u6570\u7ec4\u6807\u8bb0\u4f7f\u7528\u8fc7\u7684\u6280\u80fd\u5373\u53ef\u3002<\/p>\n

D ziyi’s plan:
\n0-1\u80cc\u5305,\u9898\u76ee\u8981\u6c42\u7684\u662f\u81f3\u5c11\u4e00\u6b21\u4ea4\u6613\u6210\u529f\u7684\u7684\u6700\u5927\u6982\u7387,\u6362\u4e2a\u89d2\u5ea6\u6c42\u90fd\u4e0d\u6210\u529f\u7684\u6700\u5c0f\u6982\u7387\u5373\u53ef,\u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b:f[j]=min(f[j],f[j-v[i]]*w[i]);\u5176\u4e2d,w[i]\u8868\u793a\u4e0d\u6210\u529f\u7684\u6982\u7387,(1-f[j])\u4e3a\u82b1\u8d39j\u5143\u4ea4\u6613\u6210\u529f\u7684\u6700\u5927\u6982\u7387\u3002<\/p>\n

F Bloody X:
\n\u6700\u591a\u53ea\u670910\u4e2aDNA\u7247\u6bb5\uff0c\u67092^10=1024\u79cd\u51fa\u73b0\u7684\u53ef\u80fd\uff0c\u6240\u4ee5\u5728AC\u81ea\u52a8\u673a\u4e0a\u505a\u72b6\u6001\u538b\u7f29dp,\u5b57\u7b26\u4e32\u7ed3\u5c3e\u72b6\u6001\u66f4\u65b0\u7528\u6216\u8fd0\u7b97\u5b9e\u73b0\uff0cd[i][j][k]\u5206\u522b\u8868\u793a\u5f53\u524d\u957f\u5ea6i\uff0c\u5b57\u7b26\u4e32\u7ed3\u5c3e\u72b6\u6001j\uff0c\u4e8c\u8fdb\u5236\u538b\u7f29\u72b6\u6001k\u3002\u5982\u679cd[i][j][k]=1\uff0c\u90a3\u4e48d[next][chd[j][k]][z|word[chd[j][k]]] = 1;\u6700\u540e\u4eced[l]\u7684\u6240\u6709\u72b6\u6001\u4e2d\u627e\u51fa\u6700\u5927\u503c\uff0c\u6700\u5927\u503c\u5c0f\u4e8e0\u5c31Bloody Monday\uff01\uff08AC\u81ea\u52a8\u673a\u6a21\u677f\u91c7\u7528HDU\u80e1\u6d69\u5927\u795e\u7684\u6a21\u677f\uff09<\/p>\n

\u6211\u63d2\u4e00\u53e5\u2026\u2026\u6709\u4e2a\u95ee\u9898\u9700\u8981\u6ce8\u610f\uff0c\u90a3\u5c31\u662f\u7ed9\u51fa\u7684\u5e8f\u5217\u5982\u679c\u90fd\u662f\u8d1f\uff0c\u4e0d\u4e00\u5b9a\u5c31\u5fc5\u6b7b\uff0c\u4f60\u53ef\u4ee5\u6784\u9020\u4e00\u4e2a\u4e0d\u51fa\u73b0\u90a3\u4e9b\u5e8f\u5217\u7684DNA\u4e32\uff0c\u7ed3\u679c\u5c31\u662f0.<\/p>\n

\u7136\u540e\u4ece\u5934\u8bf4\u3002<\/p>\n

A\u9898\u7684\u539f\u578b\u662f\u4ec0\u4e48\u7b2c\u56db\u5c4a\u767e\u5ea6\u676f\u51b3\u8d5b\uff0c\u4e0d\u77e5\u9053\u767e\u5ea6\u676f\u8ddf\u767e\u5ea6\u4e4b\u661f\u5565\u5173\u7cfb\uff0c\u603b\u4e4b\u4e0d\u5c11OJ\u6709\u8fd9\u5957\u9898\u3002\u4e0d\u8fc7\u65f6\u95f4\u8303\u56f4\u7ed9\u7684\u6bd4\u8f83\u5bbd\u677e\uff0c\u6807\u7a0b\u5927\u7ea6300ms\uff0c\u6309\u7167\u4e00\u822cOJ\u7684\u65f6\u95f4\u7ed9\u4e863\u79d2\uff0c\u4e8e\u662f\u67d0HDU\u5927\u725b\u597d\u50cf\u7528dijksra\u57282750ms\u8fc7\u53bb\u4e86\u2026\u2026\u4e25\u683c\u8bf4\u6765\u8fd9\u5e94\u8be5\u662f\u4e00\u90531\u79d2\u6216\u4e24\u79d2\u7684\u9898\u3002<\/p>\n

\u8fd9\u9898\u5982\u679c\u4e0d\u8003\u7387\u6bcf\u4e2a\u70b9\u4e0a\u7684\u6c61\u67d3\u503c\uff0c\u90a3\u4e48\u5c31\u662f\u4e2a\u5f88\u7b80\u5355\u7684floyd\u3002\u800c\u4e14\u6211\u4eec\u77e5\u9053\uff0cfloyd\u7684\u4e09\u5c42\u5faa\u73afk-i-j\u542b\u4e49\u4e3a\uff1a\u4ee50-k\u4e2d\u7684\u82e5\u5e72\u4e2a\u70b9\u4f5c\u4e3a\u4e2d\u95f4\u70b9\uff0ci\u5230j\u7684\u6700\u77ed\u8ddd\u79bb\u3002\u56e0\u6b64\u5b9e\u9645\u4e0a\u76f8\u5f53\u4e8e\u4e09\u7ef4\u7684\u7a7a\u95f4\uff0c\u800cf[i][j][k]\u53ea\u8ddff[i][k][k-1]\u548cf[k][j][k-1]\u6709\u5173\uff0c\u56e0\u6b64\u7528\u6eda\u52a8\u6570\u7ec4\u5c06\u7b2c\u4e09\u7ef4\u7701\u7565\u8282\u7701\u7a7a\u95f4\u3002\u800c\u5728\u6b64\u9898\uff0c\u56e0\u4e3a\u6bcf\u6761\u8def\u5f84\u6700\u5927\u6c61\u67d3\u503c\u4e0d\u786e\u5b9a\uff0c\u800c\u67e5\u8be2\u7684\u5fcd\u53d7\u503c\u53c8\u6709\u5f88\u591a\u79cd\uff0c\u56e0\u6b64\u9700\u8981\u4fdd\u7559\u8fd9\u4e00\u7ef4\u3002<\/p>\n

\u5f53\u7136\uff0c\u53ea\u4fdd\u5b58\u4e2d\u95f4\u7684\u7ed3\u679c\u4e0d\u80fd\u83b7\u5f97\u5168\u5c40\u6700\u4f18\uff0c\u56e0\u6b64\u9700\u8981\u5c06\u8fd9\u4e9b\u70b9\u6309\u7167\u6c61\u67d3\u503c\u4ece\u5c0f\u5230\u5927\u6392\u5e8f\uff0c\u56e0\u4e3a\u4e0d\u8981\u6c42\u8d77\u70b9\u548c\u7ec8\u70b9\u7684\u6c61\u67d3\u503c\u5728\u627f\u53d7\u7684\u8303\u56f4\u5185\uff0c\u53ea\u8981\u4fdd\u8bc1\u4e2d\u95f4\u70b9\u7684\u6700\u5927\u503c\u5c0f\u4e8e\u8981\u6c42\uff0c\u518d\u5728\u8fd9\u4e9b\u53ef\u80fd\u4e2d\u5bfb\u627e\u6700\u77ed\u5373\u53ef\u3002\u56e0\u6b64f[i][j][k]\u7684\u542b\u4e49\u4e3a\uff0c\u4ee5\u524dk\u5c0f\u7684\u6c61\u67d3\u70b9(\u4e3a\u65b9\u4fbf\u53ef\u4ee5\u8ba9k\u4ece1\u5230n)\u4e3a\u4e2d\u95f4\u70b9\uff0c\u4ecei\u5230j\u7684\u6700\u77ed\u8def\u5f84\u3002\u8fd9\u6837\u5176\u6700\u5927\u6c61\u67d3\u503c\u4e00\u5b9a\u662f\u7b2ck\u4e2a\u70b9\u7684\u6c61\u67d3\u503c\u3002\u8fd9\u6837\u67e5\u8be2u\u5230v\u53ea\u9700\u8981\u679a\u4e3en\u4e2a\u6392\u5e8f\u540e\u7684\u70b9\uff0c\u5047\u8bbe\u7b2cx\u4e2a\u70b9\u662f\u6ee1\u8db3\u627f\u53d7\u8303\u56f4\u7684\u70b9\u4e2d\u6c61\u67d3\u503c\u6700\u5927\u7684\uff0c\u90a3\u4e48f[u][v][x]\u5c31\u662f\u6240\u6c42\u3002<\/p>\n

 <\/p>\n

C\u9898\u771f\u7684\u5f88\u7b80\u5355\u2026\u2026USACO3.2\u5de6\u53f3\u90a3\u4e2a\u7ed9\u5976\u725b\u5403\u9ec4\u6cb9\u7684\u9898\u2026\u2026\u5f88\u660e\u663e\u662f\u5f88\u7a00\u758f\u7684\u56fe\uff0c\u6240\u4ee5\u7528floyd\u7684\u5c5e\u4e8e\u81ea\u6740\u884c\u4e3a\u3002\u5b9e\u9645\u4e0a\u5355\u6e90\u6700\u77ed\u8def\u5f84\u7528N\u6b21\u6548\u679c\u8ddffloyd\u662f\u4e00\u6837\u7684\uff0c\u56e0\u6b64\u53ea\u8981\u7528\u90a3\u79cd\u590d\u6742\u5ea6\u4e3b\u8981\u8ddf\u8fb9\u6570\u6709\u5173\u7684\u6700\u77ed\u8def\u6a21\u677f\u7528N\u6b21\u5c31\u80fd\u8fc7\uff0c\u6211\u662f\u7528\u5409\u5927\u90a3\u4e2aSTL\u7684dijkstra\u6a21\u677f\u8fc7\u7684\uff0c\u5f53\u7136\u9700\u8981\u624b\u52a8\u4fee\u6539\u6a21\u677f\u8ba9\u5176\u8fd0\u884cn\u6b21\u3002\u7406\u8bba\u4e0a\u7528SPFA\u6216\u8005bellman-ford\u6548\u679c\u5e94\u8be5\u66f4\u597d\u3002<\/p>\n

 <\/p>\n

E\u9898\u4e0d\u89e3\u91ca\u4e86\u2026\u2026\u8d64\u88f8\u88f8\u7684\u6700\u5c0f\u751f\u6210\u6811\uff0c\u968f\u4fbf\u5957\u6a21\u677f\uff0c\u8ddf\u6bd4\u4e0a\u4e2a\u6708\u8d5b\u9898\u8fd8\u7701\u4e8b\uff08\u4e0d\u7ed9\u5750\u6807\u81ea\u5df1\u6c42\u56fe\u800c\u662f\u76f4\u63a5\u7ed9\u56fe\uff09\u3002\u552f\u4e00\u9700\u8981\u6ce8\u610f\u7684\u662f\u8fd9\u9898\u5b58\u5728\u91cd\u8fb9\u548c\u81ea\u73af\u3002<\/p>\n

 <\/p>\n

G\u5c5e\u4e8e\u5178\u578b\u7684\u4f1a\u4e86\u4e0d\u96be\u7684\u9898\u3002\u6211\u4e2a\u4eba\u611f\u89c9\u89e3\u6cd5\u6700\u597d\u7684\u662f\u8fd9\u91cc\u7684<\/a>\u8fd9\u4e2a\u3002<\/p>\n

 <\/p>\n

\u603b\u4e4b\u8fd9\u5957\u9898\u4e0d\u7b97\u5f88\u96be\u3002\u5982\u679c\u518d\u591a\u4e24\u9053\u5927\u6c34\u9898\u6216\u8005\u6a21\u62df\u9898\u518d\u591a\u4e00\u9053\u4e2d\u7b49\u4ee5\u4e0a\u7684\u9898\u5c31\u8ddf\u7701\u8d5b\u96be\u5ea6\u5dee\u4e0d\u591a\u4e86\u3002\u4f46\u662f\u6211\u4eec\u4e0d\u80fd\u4ee5\u505a\u51fa\u7701\u8d5b\u6c34\u9898\u4e3a\u76ee\u6807\uff0c\u90a3\u6837\u8fde\u975e985\u975e211\u7684\u90fd\u5e72\u4e0d\u8fc7\u3002\u56e0\u6b64\u5e73\u65f6\u7684\u6bd4\u8d5b\u6ca1\u5fc5\u8981\u4e3a\u4e86\u533a\u5206\u51fa\u8c01\u6392\u7b2c20\u8c01\u6392\u7b2c30\u800c\u51fa\u4e00\u4e2a\u6bd4\u8c01\u6c34\u5f97\u5feb\u7684\u9898\uff0c\u80fd\u7559\u5230\u660e\u5e74\u6691\u5047\u7684\u52a0\u4e0a\u8001\u4eba\u4e5f\u5c31\u662f9-12\u4eba\u800c\u5df2\u3002\u660e\u5e745\u6708\u7684\u7701\u8d5b\u8fd8\u67093\u4e2a\u6708\u7684\u65f6\u95f4\uff0c\u5982\u679c\u8fd9\u534a\u4e2a\u6708\u6ca1\u5b66\u5230\u4ec0\u4e48\u4e1c\u897f\uff0c\u5982\u4f55\u80fd\u80af\u5b9a\u81ea\u5df1\u5728\u672a\u6765\u76846\u4e2a\u534a\u4e2a\u6708\u91cc\u5b66\u5230\u4e1c\u897f\u5462\uff1f\u5f00\u5b66\u4e4b\u540e\u80af\u5b9a\u4e0d\u4f1a\u8bb2\u8fd9\u4e9b\u4e1c\u897f\uff0c\u4e00\u5b9a\u662f\u6bd4\u8fd9\u4e9b\u8fd8\u96be\u53c8\u5f88\u96be\u81ea\u5b66\u7684\u3002\u800c\u81ea\u5b66\u8fd9\u4e9b\u4e1c\u897f\u4e0d\u5e94\u6210\u4e3a\u95ee\u9898\u3002\u7b80\u5355\u7684\u56fe\u8bba\u5c31\u662f\u5957\u6a21\u677f\uff0c\u4ee5\u81f3\u4e8e\u4e9a\u6d32\u8d5b\u4eca\u5e74\u4e3a\u4e86\u907f\u514d\u51fa\u6a21\u677f\u9898\u5f88\u591a\u90fd\u4e0d\u51fa\u56fe\u8bba\uff0c\u5acc\u6c34\u3002\u53ea\u8981\u597d\u597d\u770b\u4e66\/ppt\uff0c\u7406\u89e3\u57fa\u672c\u6982\u5ff5\uff0c\u7406\u89e3\u9898\u578b\uff0c\u4f1a\u5957\u6a21\u677f\u5c31\u591f\u4e86\u3002\u5f53\u7136\u77e5\u9053\u6a21\u677f\u7b97\u6cd5\u7684\u539f\u7406\u6700\u597d\uff0c\u4e0d\u7136\u662f\u4e0d\u53ef\u80fd\u505a\u51faA\u9898\u90a3\u6837\u7684\u9898\u7684\u3002<\/p>\n

\u672c\u6b21\u6bd4\u8d5b\u51a0\u519b\u662f\u4e00\u4e2a\u4e0d\u8ba4\u8bc6\u7684\u676d\u7535\u7684\u540c\u5b66\u2026\u2026\u800c\u4e14\u4ed6\u62ff\u4e864\u9898\u7684FB\u3002\u7b2c\u4e8c\u597d\u50cf\u662f\u5ddd\u5927\u7684\u59b9\u5b50\uff1f\u7b2c\u4e09\u662f\u4e1c\u5927\u7684\u7f57\u8000\u71ca\uff0c\u62ffC\u9898\u7684FB\uff0c\u7b2c\u56db\u662f\u4e0a\u6b21\u7b2c\u4e00HIT\u5362\u5927\u725b\uff0c\u7b2c\u4e94\u662f\u4e1c\u5927\u7684\u674e\u79d1\u3002\u4ee5\u4e0a\u505a\u51fa5\u9898\u3002\u7b2c\u516d\u5b81\u7855\u540c\u5b66\u62ff\u4e86D\u9898\u7684FB\u3002\u606d\u559c\u4ee5\u4e0a\u5404\u4f4d\uff0c\u5e0c\u671b\u540e\u9762\u7684\u518d\u63a5\u518d\u5389\u3002\u65b0\u4e00\u671fNEUACM\u79ef\u5206\u699c\u968f\u540e\u653e\u51fa\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"

\u8fd9\u6b21\u7684\u7ed3\u679c\u5e94\u8be5\u5c31\u662f\u201c\u60c5\u7406\u4e4b\u5916\u610f\u6599\u4e4b\u4e2d\u201d\u5427\u3002\u610f\u6599\u4e4b\u4e2d\u662f\u56e0\u4e3a\u770b\u5230\u6211\u653e\u5728HDOJ\u4e0a\u7684\u7ec3\u4e60\u9898\u6709\u591a\u5c11\u4eba\u505a\u3001\u591a\u5c11\u4ebaAK\u5c31\u80fd […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[9],"_links":{"self":[{"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/posts\/223704"}],"collection":[{"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/comments?post=223704"}],"version-history":[{"count":1,"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/posts\/223704\/revisions"}],"predecessor-version":[{"id":224630,"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/posts\/223704\/revisions\/224630"}],"wp:attachment":[{"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/media?parent=223704"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/categories?post=223704"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/yangzhe1991.org\/blog\/wp-json\/wp\/v2\/tags?post=223704"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}