请教做ACM的常用算法..还是菜鸟 你好，我是新手，不太了解这些，想请教下，DP 是什么意思，还...
\u8bf7\u6559\u5b66\u4e60ACM\u5165\u95e8\u7684\u65b9\u6cd5\u521a\u521a\u63a5\u89e6\u4fe1\u606f\u5b66\u9886\u57df\u7684\u540c\u5b66\u5f80\u5f80\u5b58\u5728\u5f88\u591a\u56f0\u60d1\uff0c\u4e0d\u77e5\u9053\u4ece\u4f55\u5165\u624b\u5b66\u4e60\uff0c\u5728\u8fd9\u7bc7\u6587\u7ae0\u91cc\uff0c\u6211\u5e0c\u671b\u80fd\u5c06\u81ea\u5df1\u4e0d\u591a\u7684\u7ecf\u9a8c\u4e0e\u5927\u5bb6\u5206\u4eab\uff0c\u5e0c\u671b\u5bf9\u5404\u4f4d\u6709\u6240\u5e2e\u52a9\u3002
\u4e00\u3001\u8bed\u8a00\u662f\u6700\u91cd\u8981\u7684\u57fa\u672c\u529f
\u65e0\u8bba\u4fa7\u91cd\u4e8e\u4ec0\u4e48\u65b9\u9762\uff0c\u53ea\u8981\u662f\u901a\u8fc7\u8ba1\u7b97\u673a\u7a0b\u5e8f\u53bb\u6700\u7ec8\u5b9e\u73b0\u7684\u7ade\u8d5b\uff0c\u8bed\u8a00\u90fd\u662f\u5927\u5bb6\u8981\u8fc7\u7684\u7b2c\u4e00\u9053\u5173\u3002\u4e9a\u6d32\u8d5b\u533a\u7684\u6bd4\u8d5b\u652f\u6301\u7684\u8bed\u8a00\u5305\u62ecC/C++\u4e0eJAVA\u3002\u7b14\u8005\u9996\u5148\u8bf4\u8bf4JAVA\uff0c\u4f17\u6240\u5468\u77e5\uff0c\u4f5c\u4e3a\u9762\u5411\u5bf9\u8c61\u7684\u738b\u724c\u8bed\u8a00\uff0cJAVA\u5728\u5927\u578b\u5de5\u7a0b\u7684\u7ec4\u7ec7\u4e0e\u5b89\u5168\u6027\u65b9\u9762\u6709\u7740\u81ea\u5df1\u72ec\u7279\u7684\u4f18\u52bf\uff0c\u4f46\u662f\u5bf9\u4e8e\u4fe1\u606f\u5b66\u6bd4\u8d5b\u7684\u5177\u4f53\u573a\u5408\uff0cJAVA\u5219\u663e\u5f97\u4e0d\u90a3\u4e48\u5408\u9002\uff0c\u5b83\u5bf9\u4e8e\u8f93\u5165\u8f93\u51fa\u6d41\u7684\u64cd\u4f5c\u76f8\u6bd4\u4e8eC++\u8981\u7e41\u6742\u5f88\u591a\uff0c\u66f4\u4e3a\u91cd\u8981\u7684\u662fJAVA\u7a0b\u5e8f\u7684\u8fd0\u884c\u901f\u5ea6\u8981\u6bd4C++\u616210\u500d\u4ee5\u4e0a\uff0c\u800c\u7ade\u8d5b\u4e2d\u5bf9\u4e8eJAVA\u7a0b\u5e8f\u7684\u8fd0\u884c\u65f6\u9650\u5374\u5f80\u5f80\u5f97\u4e0d\u5230\u540c\u7b49\u6bd4\u4f8b\u7684\u653e\u5bbd\uff0c\u8fd9\u65e0\u7591\u5bf9\u7b97\u6cd5\u8bbe\u8ba1\u63d0\u51fa\u4e86\u66f4\u9ad8\u7684\u8981\u6c42\uff0c\u662f\u76f8\u5f53\u4e0d\u5229\u7684\u3002\u5176\u5b9e\uff0c\u7b14\u8005\u5e76\u4e0d\u4e3b\u5f20\u5927\u5bb6\u5728\u8fd9\u79cd\u573a\u5408\u8fc7\u591a\u5730\u8fd0\u7528\u9762\u5411\u5bf9\u8c61\u7684\u7a0b\u5e8f\u8bbe\u8ba1\u601d\u7ef4\uff0c\u56e0\u4e3a\u5bf9\u4e8e\u5c0f\u7a0b\u5e8f\u6765\u8bf4\u8fd9\u4e0d\u65e6\u9700\u8981\u82b1\u8d39\u66f4\u591a\u7684\u65f6\u95f4\u53bb\u7f16\u5199\u4ee3\u7801\uff0c\u4e5f\u4f1a\u964d\u4f4e\u7a0b\u5e8f\u7684\u6267\u884c\u6548\u7387\u3002
\u63a5\u7740\u8bf4C\u548cC++\u3002\u8bb8\u591a\u73b0\u5728\u53c2\u52a0\u8bb2\u5ea7\u7684\u540c\u5b66\u8fd8\u5728\u4e0a\u5927\u4e00\uff0cC\u7684\u57fa\u7840\u77e5\u8bc6\u521a\u521a\u5b66\u5b8c\uff0c\u8fd8\u6ca1\u6709\u63a5\u89e6\u8fc7C++\uff0c\u5176\u5b9e\u5728\u8d5b\u573a\u4e0a\u4f7f\u7528\u7eafC\u7684\u9009\u624b\u8fd8\u662f\u5927\u6709\u4eba\u5728\u7684\uff0c\u5b83\u4eec\u4e3b\u8981\u662f\u770b\u91cd\u4e86\u7eafC\u5728\u6548\u7387\u4e0a\u7684\u4f18\u52bf\uff0c\u6240\u4ee5\u8fd9\u90e8\u5206\u540c\u5b66\u5982\u679c\u65f6\u95f4\u6709\u9650\uff0c\u5e76\u4e0d\u9700\u8981\u6025\u7740\u53bb\u5b66\u4e60\u65b0\u7684\u8bed\u8a00\uff0c\u53ea\u8981\u63d0\u9ad8\u4e86\u81ea\u5df1\u5728\u7b97\u6cd5\u8bbe\u8ba1\u4e0a\u7684\u9020\u8be3\uff0c\u7eafC\u4e00\u6837\u80fd\u53d1\u6325\u5de8\u5927\u7684\u5a01\u529b\u3002
\u800cC++\u76f8\u5bf9\u4e8eC\uff0c\u5728\u8f93\u5165\u8f93\u51fa\u6d41\u4e0a\u7684\u5c01\u88c5\u5927\u5927\u65b9\u4fbf\u4e86\u6211\u4eec\u7684\u64cd\u4f5c\uff0c\u540c\u65f6\u964d\u4f4e\u4e86\u51fa\u9519\u7684\u53ef\u80fd\u6027\uff0c\u5e76\u4e14\u80fd\u591f\u5f88\u597d\u5730\u5b9e\u73b0\u6807\u51c6\u6d41\u4e0e\u6587\u4ef6\u6d41\u7684\u5207\u6362\uff0c\u65b9\u4fbf\u4e86\u8c03\u8bd5\u7684\u5de5\u4f5c\u3002\u5982\u679c\u6709\u4e9b\u540c\u5b66\u6bd4\u8f83\u5728\u610f\u8fd9\u70b9\uff0c\u53ef\u4ee5\u5c1d\u8bd5C\u548cC++\u7684\u6df7\u7f16\uff0c\u6bd5\u7adf\u4ec5\u4ec5\u5b66\u4e60C++\u7684\u6d41\u64cd\u4f5c\u8fd8\u662f\u4e0d\u82b1\u4ec0\u4e48\u65f6\u95f4\u7684\u3002
C++\u7684\u53e6\u4e00\u4e2a\u652f\u6301\u6765\u6e90\u4e8e\u6807\u51c6\u6a21\u7248\u5e93\uff08STL\uff09\uff0c\u5e93\u4e2d\u63d0\u4f9b\u7684\u5bf9\u4e8e\u57fa\u672c\u6570\u636e\u7ed3\u6784\u7684\u7edf\u4e00\u63a5\u53e3\u64cd\u4f5c\u548c\u57fa\u672c\u7b97\u6cd5\u7684\u5b9e\u73b0\u53ef\u4ee5\u7f29\u51cf\u6211\u4eec\u7f16\u5199\u4ee3\u7801\u7684\u957f\u5ea6\uff0c\u8fd9\u53ef\u4ee5\u8282\u7701\u4e00\u4e9b\u65f6\u95f4\u3002\u4f46\u662f\uff0c\u4e0e\u6b64\u76f8\u5bf9\u7684\uff0c\u4f7f\u7528STL\u8981\u5728\u6548\u7387\u4e0a\u505a\u51fa\u4e00\u4e9b\u727a\u7272\uff0c\u5bf9\u4e8e\u8f93\u5165\u89c4\u6a21\u5f88\u5927\u7684\u9898\u76ee\uff0c\u6709\u65f6\u5019\u5fc5\u987b\u653e\u5f03STL\uff0c\u8fd9\u610f\u5473\u7740\u6211\u4eec\u4e0d\u80fd\u5b58\u5728\u201c\u6709\u4e86STL\u5c31\u53ef\u4ee5\u4e0d\u53bb\u7ba1\u57fa\u672c\u7b97\u6cd5\u7684\u5b9e\u73b0\u201d\u7684\u60f3\u6cd5\uff1b\u53e6\u5916\uff0c\u719f\u7ec3\u548c\u6070\u5f53\u5730\u4f7f\u7528STL\u5fc5\u987b\u7ecf\u8fc7\u4e00\u5b9a\u65f6\u95f4\u7684\u79ef\u7d2f\uff0c\u51c6\u786e\u5730\u4e86\u89e3\u5404\u79cd\u64cd\u4f5c\u7684\u65f6\u95f4\u590d\u6742\u5ea6\uff0c\u5207\u5fcc\u5bf9STL\u4e2d\u4e0d\u719f\u6089\u7684\u90e8\u5206\u6ee5\u7528\uff0c\u56e0\u4e3a\u8fd9\u5176\u4e2d\u8574\u6db5\u7740\u8bb8\u591a\u521d\u5b66\u8005\u4e0d\u6613\u53d1\u73b0\u7684\u9677\u9631\u3002
\u901a\u8fc7\u4ee5\u4e0a\u7684\u5206\u6790\uff0c\u6211\u4eec\u53ef\u4ee5\u770b\u51fa\u4ec5\u5c31\u4fe1\u606f\u5b66\u7ade\u8d5b\u800c\u8a00\uff0c\u5bf9\u8bed\u8a00\u7684\u638c\u63e1\u5e76\u4e0d\u8981\u6c42\u5341\u5206\u5168\u9762\uff0c\u4f46\u662f\u5bf9\u4e8e\u7ecf\u5e38\u7528\u5230\u7684\u90e8\u5206\uff0c\u5fc5\u987b\u5341\u5206\u719f\u7ec3\uff0c\u4e0d\u5141\u8bb8\u6709\u534a\u70b9\u4e0d\u6e05\u695a\u7684\u5730\u65b9\uff0c\u4e0b\u9762\u6211\u4e3e\u4e2a\u771f\u5b9e\u7684\u4f8b\u5b50\u6765\u8bf4\u660e\u8fd9\u4e2a\u9053\u7406\u2014\u2014\u5373\u4f7f\u662f\u4e00\u70b9\u5f88\u7ec6\u5fae\u7684\u8bed\u8a00\u969c\u788d\uff0c\u90fd\u6709\u53ef\u80fd\u917f\u6210\u9519\u8bef\uff1a
\u5728\u53bb\u5e74\u6e05\u534e\u7684\u8d5b\u533a\u4e0a\uff0c\u6709\u4e00\u4e2a\u961f\u5728\u505aF\u9898\u7684\u65f6\u5019\u4f7f\u7528\u4e86cout\u548cprintf\u7684\u6df7\u5408\u8f93\u51fa\uff0c\u7531\u4e8e\u4e00\u4e2a\u5e26\u7f13\u51b2\u4e00\u4e2a\u4e0d\u5e26\uff0c\u6240\u4ee5\u8f93\u51fa\u4e00\u957f\u5c31\u6df7\u4e71\u4e86\u3002\u53ea\u662f\u56e0\u4e3a\u5f53\u65f6judge team\u4e2d\u8d1f\u8d23F\u9898\u7684\u4eba\u773c\u775b\u5c16\uff0c\u770b\u51fa\u7b54\u6848\u6ca1\u9519\u53ea\u662f\u987a\u5e8f\u4e0d\u5bf9\uff08\u7b54\u6848\u6709\u4e00\u9875\u591a\uff0c\u662f\u6240\u6709\u9898\u76ee\u4e2d\u6700\u957f\u7684\u4e00\u4e2a\u8f93\u51fa\uff09\uff0c\u53c8\u770b\u4e86\u770b\u7a0b\u5e8f\u53d1\u73b0\u53ea\u662f\u8f93\u51fa\u95ee\u9898\u5c31\u7ed9\u4e86\u4e2aPresentation error\uff08\u683c\u5f0f\u9519\uff09\u3002\u5982\u679c\u5ba1\u9898\u7684\u4eba\u4e0d\u662f\u8fd9\u6837\u800c\u662f\u76f4\u63a5\u7ed9\u4e00\u4e2a Wrong Answer\uff0c\u76f8\u4fe1\u8fd9\u4e2a\u961f\u662f\u5f88\u96be\u67e5\u5230\u81ea\u5df1\u9519\u5728\u4ec0\u4e48\u5730\u65b9\u7684\u3002
\u73b0\u5728\u6211\u4eec\u8f6c\u5165\u7b2c\u4e8c\u4e2a\u65b9\u9762\u7684\u8ba8\u8bba\uff0c\u57fa\u7840\u5b66\u79d1\u77e5\u8bc6\u7684\u79ef\u7d2f\u3002
\u4e8c\u3001\u4ee5\u6570\u5b66\u4e3a\u4e3b\u7684\u57fa\u7840\u77e5\u8bc6\u5341\u5206\u91cd\u8981
\u867d\u7136\u88ab\u5b9a\u6027\u4e3a\u7a0b\u5e8f\u8bbe\u8ba1\u7ade\u8d5b\uff0c\u4f46\u662f\u53c2\u8d5b\u9009\u624b\u6240\u9047\u5230\u7684\u95ee\u9898\u66f4\u591a\u7684\u662f\u6ca1\u6709\u89e3\u51b3\u95ee\u9898\u7684\u601d\u8def\uff0c\u800c\u4e0d\u662f\u6709\u4e86\u601d\u8def\u5374\u6b7b\u6d3b\u4e0d\u80fd\u5b9e\u73b0\uff0c\u8fd9\u5c31\u662f\u5e73\u65f6\u79ef\u7d2f\u7684\u57fa\u7840\u77e5\u8bc6\u4e0d\u591f\u3002\u4eca\u5e74World Final\u7684\u603b\u51a0\u519b\u662f\u6ce2\u5170\u534e\u6c99\u5927\u5b66\uff0c\u5176\u6210\u5458\u51fa\u81ea\u4e8e\u6570\u5b66\u7cfb\u800c\u975e\u8ba1\u7b97\u673a\u7cfb\uff0c\u8fd9\u5c31\u662f\u4e00\u4e2a\u9c9c\u6d3b\u7684\u4f8b\u5b50\u3002\u7ade\u8d5b\u4e2d\u5bf9\u4e8e\u57fa\u7840\u5b66\u79d1\u7684\u6d89\u53ca\u4e3b\u8981\u96c6\u4e2d\u4e8e\u6570\u5b66\uff0c\u6b64\u5916\u5bf9\u4e8e\u7269\u7406\u3001\u7535\u8def\u7b49\u7b49\u4e5f\u53ef\u80fd\u6709\u4e00\u5b9a\u5e94\u7528\uff0c\u4f46\u662f\u4e0d\u591a\u3002\u56e0\u6b64\uff0c\u5927\u4e00\u7684\u540c\u5b66\u4e5f\u4e0d\u5fc5\u4e3a\u81ea\u5df1\u8fd8\u6ca1\u5b66\u6570\u636e\u7ed3\u6784\u800c\u611f\u5230\u4e0d\u77e5\u4ece\u4f55\u5165\u624b\u63d0\u9ad8\uff0c\u628a\u6570\u5b66\u6361\u8d77\u6765\u5427\uff01\u4e0b\u9762\u6211\u6765\u8c08\u8c08\u5728\u7ade\u8d5b\u4e2d\u5e94\u7528\u7684\u6570\u5b66\u7684\u4e3b\u8981\u5206\u652f\u3002
1\u3001\u79bb\u6563\u6570\u5b66\u2014\u2014\u4f5c\u4e3a\u8ba1\u7b97\u673a\u5b66\u79d1\u7684\u57fa\u7840\uff0c\u79bb\u6563\u6570\u5b66\u662f\u7ade\u8d5b\u4e2d\u6d89\u53ca\u6700\u591a\u7684\u6570\u5b66\u5206\u652f\uff0c\u5176\u91cd\u4e2d\u4e4b\u91cd\u53c8\u5728\u4e8e\u56fe\u8bba\u548c\u7ec4\u5408\u6570\u5b66\uff0c\u5c24\u5176\u662f\u56fe\u8bba\u3002
\u56fe\u8bba\u4e4b\u6240\u4ee5\u8fd0\u7528\u6700\u591a\u662f\u56e0\u4e3a\u5b83\u7684\u53d8\u5316\u6700\u591a\uff0c\u800c\u4e14\u53ef\u4ee5\u8f7b\u6613\u5730\u7ed3\u5408\u57fa\u672c\u6570\u636e\u7ed3\u6784\u548c\u8bb8\u591a\u7b97\u6cd5\u7684\u57fa\u672c\u601d\u60f3\uff0c\u8f83\u591a\u7528\u5230\u7684\u77e5\u8bc6\u5305\u62ec\u8fde\u901a\u6027\u5224\u65ad\u3001DFS\u548cBFS\uff0c\u5173\u8282\u70b9\u548c\u5173\u952e\u8def\u5f84\u3001\u6b27\u62c9\u56de\u8def\u3001\u6700\u5c0f\u751f\u6210\u6811\u3001\u6700\u77ed\u8def\u5f84\u3001\u4e8c\u90e8\u56fe\u5339\u914d\u548c\u7f51\u7edc\u6d41\u7b49\u7b49\u3002\u867d\u7136\u8fd9\u90e8\u5206\u7684\u6bd4\u91cd\u5f88\u5927\uff0c\u4f46\u662f\u5f80\u5f80\u4e5f\u662f\u7ade\u8d5b\u4e2d\u7684\u96be\u9898\u6240\u5728\uff0c\u5982\u679c\u6709\u521d\u5b66\u8005\u5bf9\u4e8e\u8fd9\u90e8\u5206\u7684\u67d0\u4e9b\u5177\u4f53\u5185\u5bb9\u6682\u65f6\u611f\u5230\u529b\u4e0d\u4ece\u5fc3\uff0c\u4e5f\u4e0d\u5fc5\u7740\u6025\uff0c\u53ef\u4ee5\u6162\u6162\u79ef\u7d2f\u3002
\u7ade\u8d5b\u4e2d\u8bbe\u8ba1\u7684\u7ec4\u5408\u8ba1\u6570\u95ee\u9898\u5927\u90fd\u9700\u8981\u7528\u7ec4\u5408\u6570\u5b66\u6765\u89e3\u51b3\uff0c\u7ec4\u5408\u6570\u5b66\u4e2d\u7684\u77e5\u8bc6\u76f8\u6bd4\u4e8e\u56fe\u8bba\u8981\u7b80\u5355\u4e00\u4e9b\uff0c\u5f88\u591a\u77e5\u8bc6\u5bf9\u4e8e\u5c0f\u5b66\u4e0a\u8fc7\u5965\u6821\u7684\u540c\u5b66\u6765\u8bf4\u5df2\u7ecf\u5341\u5206\u719f\u6089\uff0c\u4f46\u662f\u4e5f\u6709\u4e00\u4e9b\u90e8\u5206\u9700\u8981\u5148\u5bf9\u4ee3\u6570\u7ed3\u6784\u4e2d\u7684\u7fa4\u8bba\u6709\u521d\u6b65\u4e86\u89e3\u624d\u80fd\u8fdb\u884c\u5b66\u4e60\u3002\u7ec4\u5408\u6570\u5b66\u5728\u7ade\u8d5b\u4e2d\u5f88\u5c11\u4ee5\u96be\u9898\u7684\u5f62\u5f0f\u51fa\u73b0\uff0c\u4f46\u662f\u5982\u679c\u79ef\u7d2f\u4e0d\u591f\uff0c\u4efb\u4f55\u4e00\u9053\u8fd9\u65b9\u9762\u7684\u9898\u76ee\u5374\u90fd\u6709\u53ef\u80fd\u6210\u4e3a\u96be\u9898\u3002
2\u3001\u6570\u8bba\u2014\u2014\u4ee5\u7d20\u6570\u5224\u65ad\u548c\u540c\u4f59\u4e3a\u6a21\u578b\u6784\u9020\u51fa\u6765\u7684\u9898\u76ee\u5f80\u5f80\u9700\u8981\u8f83\u591a\u7684\u6570\u8bba\u77e5\u8bc6\u6765\u89e3\u51b3\uff0c\u8fd9\u90e8\u5206\u5728\u7ade\u8d5b\u4e2d\u7684\u6bd4\u91cd\u5e76\u4e0d\u5927\uff0c\u4f46\u53ea\u8981\u6765\u4e0a\u4e00\u9053\uff0c\u4e5f\u8db3\u4ee5\u4f7f\u77e5\u8bc6\u4e0d\u8db3\u7684\u4eba\u51a5\u601d\u82e6\u60f3\u4e0a\u4e00\u9635\u65f6\u95f4\u3002\u7d20\u6570\u5224\u65ad\u548c\u540c\u4f59\u6700\u5e38\u89c1\u7684\u662f\u5728\u4ee5\u5bc6\u7801\u5b66\u4e3a\u80cc\u666f\u7684\u9898\u76ee\u4e2d\u51fa\u73b0\uff0c\u5728\u8fd0\u7528\u5bc6\u7801\u5b66\u5e38\u8bc6\u786e\u5b9a\u5927\u6982\u7684\u8fc7\u7a0b\u4e4b\u540e\uff0c\u6838\u5fc3\u7b97\u6cd5\u5f80\u5f80\u8981\u6d89\u53ca\u6570\u8bba\u7684\u5185\u5bb9\u3002
3\u3001\u8ba1\u7b97\u51e0\u4f55\u2014\u2014\u8ba1\u7b97\u51e0\u4f55\u76f8\u6bd4\u4e8e\u5176\u5b83\u90e8\u5206\u6765\u8bf4\u662f\u6bd4\u8f83\u72ec\u7acb\u7684\uff0c\u5c31\u662f\u8bf4\u5b83\u548c\u5176\u5b83\u7684\u77e5\u8bc6\u70b9\u5f88\u5c11\u6709\u8fc7\u591a\u7684\u7ed3\u5408\uff0c\u8f83\u5e38\u7528\u5230\u7684\u90e8\u5206\u5305\u62ec\u2014\u2014\u7ebf\u6bb5\u76f8\u4ea4\u7684\u5224\u65ad\u3001\u591a\u8fb9\u5f62\u9762\u79ef\u7684\u8ba1\u7b97\u3001\u5185\u70b9\u5916\u70b9\u7684\u5224\u65ad\u3001\u51f8\u5305\u7b49\u7b49\u3002\u8ba1\u7b97\u51e0\u4f55\u7684\u9898\u76ee\u96be\u5ea6\u4e0d\u4f1a\u5f88\u5927\uff0c\u4f46\u4e5f\u6c38\u8fdc\u4e0d\u4f1a\u6210\u4e3a\u6700\u5f31\u7684\u9898\u3002
4\u3001\u7ebf\u6027\u4ee3\u6570\u2014\u2014\u5bf9\u7ebf\u6027\u4ee3\u6570\u7684\u5e94\u7528\u90fd\u662f\u56f4\u7ed5\u77e9\u9635\u5c55\u5f00\u7684\uff0c\u4e00\u4e9b\u8868\u9762\u4e0a\u662f\u6a21\u62df\u7684\u9898\u76ee\u5f80\u5f80\u53ef\u4ee5\u501f\u52a9\u4e8e\u77e9\u9635\u6765\u627e\u5230\u66f4\u597d\u7684\u7b97\u6cd5\u3002
5\u3001\u6982\u7387\u8bba\u2014\u2014\u7ade\u8d5b\u662f\u4ee5\u9ed1\u7bb1\u6765\u5224\u5377\u7684\uff0c\u8fd9\u5c31\u662f\u8bf4\u4f60\u51e0\u4e4e\u4e0d\u80fd\u52a8\u4f7f\u7528\u6982\u7387\u7b97\u6cd5\u7684\u5ff5\u5934\uff0c\u4f46\u8fd9\u4e5f\u5e76\u4e0d\u662f\u8bf4\u6982\u7387\u5c31\u6ca1\u6709\u7528\u3002\u5173\u4e8e\u8fd9\u4e00\u70b9\uff0c\u53ea\u6709\u901a\u8fc7\u4e00\u5b9a\u7684\u7ec3\u4e60\u624d\u80fd\u4f53\u4f1a\u3002
6\u3001\u521d\u7b49\u6570\u5b66\u4e0e\u89e3\u6790\u51e0\u4f55\u2014\u2014\u8fd9\u4e3b\u8981\u5c31\u662f\u4e2d\u5b66\u7684\u77e5\u8bc6\u4e86\uff0c\u7528\u7684\u4e0d\u591a\uff0c\u4f46\u662f\u81f3\u5c11\u6bd4\u9ad8\u7b49\u6570\u5b66\u591a\uff0c\u6211\u89c9\u5f97\u719f\u6089\u4e00\u4e0b\u6570\u5b66\u624b\u518c\u4e0a\u7684\u76f8\u5173\u5185\u5bb9\uff0c\u81f3\u5c11\u8981\u77e5\u9053\u5728\u54ea\u513f\u80fd\u67e5\u5230\uff0c\u8fd8\u662f\u5fc5\u8981\u7684\u3002
7\u3001\u9ad8\u7b49\u6570\u5b66\u2014\u2014\u7eaf\u7cb9\u8fd0\u7528\u9ad8\u7b49\u6570\u5b66\u6765\u89e3\u51b3\u7684\u9898\u76ee\u6211\u63a5\u89e6\u7684\u53ea\u6709\u4e00\u9053\uff0c\u4f46\u662f\u4e00\u4e9b\u9898\u76ee\u7684\u53d9\u8ff0\u80cc\u666f\u5f80\u5f80\u9700\u8981\u548c\u8fd9\u90e8\u5206\u6709\u4e00\u5b9a\u8054\u7cfb\uff0c\u638c\u63e1\u5f97\u7262\u56fa\u4e00\u4e9b\u603b\u5f52\u6ca1\u6709\u574f\u5904\u3002
\u4ee5\u4e0a\u5c31\u662f\u7ade\u8d5b\u6240\u6d89\u53ca\u7684\u6570\u5b66\u9886\u57df\uff0c\u53ef\u4ee5\u8bf4\u8303\u56f4\u662f\u76f8\u5f53\u5e7f\u7684\u3002\u6211\u8ba4\u8bc6\u7684\u8bb8\u591a\u4eba\u53bb\u641e\u4fe1\u606f\u5b66\u7684\u7ade\u8d5b\u5c31\u662f\u4e3a\u4e86\u903c\u7740\u81ea\u5df1\u591a\u5b66\u4e00\u70b9\u6570\u5b66\uff0c\u56e0\u4e3a\u6570\u5b66\u662f\u4e00\u5207\u4e00\u5207\u7684\u57fa\u7840\u3002
\u4e09\u3001\u6570\u636e\u7ed3\u6784\u4e0e\u7b97\u6cd5\u662f\u771f\u6b63\u7684\u6838\u5fc3
\u867d\u7136\u6570\u5b66\u5341\u5206\u5341\u5206\u91cd\u8981\uff0c\u4f46\u662f\u5982\u679c\u8ba9\u4e09\u4e2a\u53ea\u4f1a\u6570\u5b66\u7684\u4eba\u53c2\u52a0\u6bd4\u8d5b\uff0c\u6211\u76f8\u4fe1\u591a\u6570\u60c5\u51b5\u4e0b\u4f1a\u6bd4\u4e09\u4e2a\u53ea\u4f1a\u6570\u636e\u7ed3\u6784\u4e0e\u7b97\u6cd5\u7684\u4eba\u5f97\u5230\u66f4\u4e3a\u60b2\u60e8\u7684\u7ed3\u5c40\u3002
\u5148\u8bf4\u8bf4\u6570\u636e\u7ed3\u6784\u3002\u638c\u63e1\u961f\u5217\u3001\u5806\u6808\u548c\u56fe\u7684\u57fa\u672c\u8868\u8fbe\u4e0e\u64cd\u4f5c\u662f\u5fc5\u9700\u7684\uff0c\u81f3\u4e8e\u6811\uff0c\u6211\u4e2a\u4eba\u89c9\u5f97\u9700\u8981\u5efa\u6811\u7684\u95ee\u9898\u6709\u4f46\u662f\u5e76\u4e0d\u591a\u3002\uff08\u4f46\u662f\u6811\u5f80\u5f80\u662f\u5f88\u91cd\u8981\u7684\u5206\u6790\u5de5\u5177\uff09\u9664\u6b64\u4e4b\u5916\uff0c\u6392\u5e8f\u548c\u67e5\u627e\u5e76\u4e0d\u9700\u8981\u5bf9\u6240\u6709\u65b9\u5f0f\u90fd\u80fd\u5f88\u719f\u7ec3\u7684\u638c\u63e1\uff0c\u4f46\u4f60\u5fc5\u987b\u4fdd\u8bc1\u81ea\u5df1\u5bf9\u4e8e\u5404\u79cd\u60c5\u51b5\u90fd\u6709\u4e00\u4e2a\u5728\u65f6\u95f4\u590d\u6742\u5ea6\u4e0a\u6ee1\u8db3\u6700\u4f4e\u8981\u6c42\u7684\u89e3\u51b3\u65b9\u6848\u3002\u8bf4\u5230\u65f6\u95f4\u590d\u6742\u5ea6\uff0c\u5c31\u53c8\u8be5\u8bf4\u8bf4\u54c8\u5e0c\u8868\u4e86\uff0c\u7ade\u8d5b\u65f6\u5bf9\u65f6\u95f4\u7684\u9650\u5236\u8fdc\u8fdc\u591a\u4e8e\u5bf9\u7a7a\u95f4\u7684\u9650\u5236\uff0c\u8fd9\u8981\u6c42\u5927\u5bb6\u5c3d\u5feb\u638c\u63e1\u201c\u4ee5\u7a7a\u95f4\u6362\u65f6\u95f4\u201d\u7684\u539f\u5219\u7b56\u7565\uff0c\u80fd\u7528\u54c8\u5e0c\u8868\u6765\u5b58\u50a8\u7684\u6570\u636e\u4e00\u5b9a\u4e0d\u8981\u5230\u65f6\u5019\u518d\u53bb\u67e5\u627e\uff0c\u5982\u679c\u5b9e\u5728\u4e0d\u80fd\u5efa\u54c8\u5e0c\u8868\uff0c\u518d\u770b\u770b\u80fd\u5426\u5efa\u4e8c\u53c9\u67e5\u627e\u6811\u7b49\u7b49\u2014\u2014\u8fd9\u90fd\u662f\u4e89\u53d6\u65f6\u95f4\u7684\u7b56\u7565\uff0c\u638c\u63e1\u8fd9\u4e9b\u6280\u5de7\u9700\u8981\u5927\u5bb6\u5bf9\u6570\u636e\u7ed3\u6784\u5c24\u5176\u662f\u7b97\u6cd5\u590d\u6742\u5ea6\u6709\u6bd4\u8f83\u5168\u9762\u7684\u7406\u6027\u548c\u611f\u6027\u8ba4\u8bc6\u3002
\u63a5\u7740\u8bf4\u8bf4\u7b97\u6cd5\u3002\u7b97\u6cd5\u4e2d\u6700\u57fa\u672c\u548c\u5e38\u7528\u7684\u662f\u641c\u7d22\uff0c\u4e3b\u8981\u662f\u56de\u6eaf\u548c\u5206\u652f\u9650\u754c\u6cd5\u7684\u4f7f\u7528\u3002\u8fd9\u91cc\u8981\u8bf4\u7684\u662f\uff0c\u6709\u4e9b\u521d\u5b66\u8005\u5728\u5b66\u4e60\u8fd9\u4e9b\u641c\u7d22\u57fa\u672c\u7b97\u6cd5\u662f\u4e0d\u592a\u6ce8\u610f\u526a\u679d\uff0c\u8fd9\u662f\u5341\u5206\u4e0d\u53ef\u53d6\u7684\uff0c\u56e0\u4e3a\u6240\u6709\u641c\u7d22\u7684\u9898\u76ee\u7ed9\u4f60\u7684\u6d4b\u8bd5\u7528\u4f8b\u90fd\u4e0d\u4f1a\u6709\u5f88\u5927\u7684\u89c4\u6a21\uff0c\u4f60\u5f80\u5f80\u5bdf\u89c9\u4e0d\u51fa\u7a0b\u5e8f\u8fd0\u884c\u7684\u65f6\u95f4\u95ee\u9898\uff0c\u4f46\u662f\u771f\u6b63\u7684\u6d4b\u8bd5\u6570\u636e\u4e00\u5b9a\u80fd\u8fc7\u6ee4\u51fa\u90a3\u4e9b\u6ca1\u6709\u526a\u679d\u7684\u7b97\u6cd5\u3002\u5b9e\u9645\u4e0a\u53c2\u8d5b\u9009\u624b\u57fa\u672c\u4e0a\u90fd\u4f1a\u4f7f\u7528\u5e38\u7528\u7684\u641c\u7d22\u7b97\u6cd5\uff0c\u9898\u76ee\u7684\u533a\u5206\u5ea6\u5f80\u5f80\u5c31\u662f\u5efa\u7acb\u5728\u8bf8\u5982\u526a\u679d\u4e4b\u7c7b\u7684\u4f18\u5316\u4e0a\u4e86\u3002
\u5e38\u7528\u7b97\u6cd5\u4e2d\u7684\u53e6\u4e00\u7c7b\u662f\u4ee5\u201c\u76f8\u4f3c\u6216\u76f8\u540c\u5b50\u95ee\u9898\u201d\u4e3a\u6838\u5fc3\u7684\uff0c\u5305\u62ec\u9012\u63a8\u3001\u9012\u5f52\u3001\u8d2a\u5fc3\u6cd5\u548c\u52a8\u6001\u89c4\u5212\u3002\u8fd9\u5176\u4e2d\u6bd4\u8f83\u96be\u4e8e\u638c\u63e1\u7684\u5c31\u662f\u52a8\u6001\u89c4\u5212\uff0c\u5982\u4f55\u62bd\u8c61\u51fa\u91cd\u590d\u7684\u5b50\u95ee\u9898\u662f\u5f88\u591a\u9898\u76ee\u7684\u96be\u70b9\u6240\u5728\uff0c\u7b14\u8005\u5efa\u8bae\u521d\u5b66\u8005\u4ed4\u7ec6\u7406\u89e3\u56fe\u8bba\u4e2d\u4e00\u4e9b\u4ee5\u52a8\u6001\u89c4\u5212\u4e3a\u57fa\u672c\u601d\u60f3\u6240\u5efa\u7acb\u8d77\u6765\u7684\u57fa\u672c\u7b97\u6cd5\uff08\u6bd4\u5982Floyd-Warshall\u7b97\u6cd5\uff09\uff0c\u5e76\u4e14\u591a\u9605\u8bfb\u4e00\u4e9b\u5b9a\u7406\u7684\u8bc1\u660e\uff0c\u8fd9\u867d\u7136\u4e0d\u80fd\u6709\u4ec0\u4e48\u76f4\u63a5\u7684\u5e2e\u52a9\uff0c\u4f46\u662f\u957f\u671f\u575a\u6301\u5c31\u4f1a\u5bf9\u601d\u7ef4\u5f88\u6709\u5e2e\u52a9\u3002
\u56db\u3001\u56e2\u961f\u914d\u5408
\u901a\u8fc7\u4ee5\u4e0a\u7684\u4ecb\u7ecd\u5927\u5bb6\u4e5f\u53ef\u4ee5\u770b\u51fa\uff0c\u4fe1\u606f\u5b66\u7ade\u8d5b\u5bf9\u4e8e\u77e5\u8bc6\u9762\u8986\u76d6\u7684\u975e\u5e38\u5e7f\uff0c\u60f3\u51ed\u4e00\u5df1\u4e4b\u529b\u5168\u90e8\u6d88\u5316\u8fd9\u4e9b\u4e1c\u897f\u5b9e\u5728\u662f\u76f8\u5f53\u56f0\u96be\u7684\uff0c\u8fd9\u5c31\u8981\u6c42\u6211\u4eec\u5c3d\u53ef\u80fd\u5730\u53d1\u6325\u56e2\u961f\u534f\u4f5c\u7684\u7cbe\u795e\u3002\u540c\u7ec4\u6210\u5458\u4e4b\u95f4\u7684\u719f\u7ec3\u914d\u5408\u548c\u9ed8\u5951\u7684\u5f62\u6210\u9700\u8981\u65f6\u95f4\uff0c\u5177\u4f53\u7684\u60c5\u51b5\u56e0\u6210\u5458\u7684\u7ec4\u6210\u4e0d\u540c\u800c\u4e0d\u540c\uff0c\u8fd9\u91cc\u6211\u5c31\u4e0d\u518d\u591a\u8bf4\u4e86\u3002
\u4e94\u3001\u7ec3\u4e60\u3001\u7ec3\u4e60\u3001\u518d\u7ec3\u4e60
\u77e5\u8bc6\u7684\u79ef\u7d2f\u56fa\u7136\u91cd\u8981\uff0c\u4f46\u662f\u4fe1\u606f\u5b66\u7ec8\u7a76\u4e0d\u662f\u770b\u51fa\u6765\u7684\uff0c\u800c\u662f\u7ec3\u51fa\u6765\u7684\uff0c\u8fd9\u662f\u591a\u5c11\u524d\u4eba\u6700\u6df1\u7684\u4e00\u70b9\u4f53\u4f1a\uff0c\u53ea\u6709\u901a\u8fc7\u5177\u4f53\u9898\u76ee\u7684\u5206\u6790\u548c\u5b9e\u8df5\uff0c\u624d\u80fd\u771f\u6b63\u638c\u63e1\u6570\u5b66\u7684\u4f7f\u7528\u548c\u7b97\u6cd5\u7684\u5e94\u7528\uff0c\u5e76\u5728\u4e0d\u65ad\u7684\u7ec3\u4e60\u4e2d\u589e\u52a0\u7f16\u7a0b\u7ecf\u9a8c\u548c\u6280\u5de7\uff0c\u63d0\u9ad8\u5bf9\u65f6\u95f4\u590d\u6742\u5ea6\u7684\u611f\u6027\u8ba4\u8bc6\uff0c\u4f18\u5316\u65f6\u95f4\u7684\u5206\u914d\uff0c\u52a0\u5f3a\u56e2\u961f\u7684\u914d\u5408\u3002\u603b\u4e4b\uff0c\u5728\u8fd9\u91cc\u5149\u6709\u7eb8\u4e0a\u8c08\u5175\u662f\u7edd\u5bf9\u4e0d\u884c\u7684\uff0c\u5fc5\u987b\u8981\u901a\u8fc7\u5b9e\u6218\u6765\u953b\u70bc\u81ea\u5df1\u3002
\u5927\u5bb6\u4e00\u5b9a\u8981\u95ee\uff0c\u6211\u4eec\u53bb\u54ea\u91cc\u627e\u9898\u505a\uff0c\u53c8\u5982\u4f55\u68c0\u9a8c\u7a0b\u5e8f\u662f\u5426\u6b63\u786e\u5462\uff1f\u8fd9\u5927\u53ef\u4e0d\u5fc5\u62c5\u5fc3\uff0c\u73b0\u5728\u5df2\u7ecf\u6709\u4e86\u5f88\u591a\u7f51\u4e0a\u505a\u9898\u7684\u7ad9\u70b9\uff0c\u8fd9\u4e9b\u7ad9\u70b9\u63d0\u4f9b\u4e86\u5927\u91cf\u7684\u9898\u5e93\u5e76\u652f\u6301\u5728\u7ebf\u5224\u5377\uff0c\u4f60\u53ea\u9700\u8981\u628a\u7a0b\u5e8f\u6e90\u7801\u63d0\u4ea4\u4e0a\u53bb\uff0c\u9a6c\u4e0a\u5c31\u53ef\u4ee5\u77e5\u9053\u81ea\u5df1\u7684\u7a0b\u5e8f\u662f\u5426\u6b63\u786e\uff0c\u8fd0\u884c\u6240\u4f7f\u7528\u7684\u65f6\u95f4\u4ee5\u53ca\u6d88\u8017\u7684\u5185\u5b58\u7b49\u7b49\u72b6\u51b5\u3002\u4e0b\u9762\u6211\u7ed9\u5927\u5bb6\u63a8\u8350\u51e0\u4e2a\u7ad9\u70b9\uff0c\u7b14\u8005\u4e0d\u5efa\u8bae\u5927\u5bb6\u5728\u6240\u6709\u8fd9\u4e9b\u7ad9\u70b9\u4e0a\u505a\u9898\uff0c\u9009\u62e9\u4e00\u4e2a\u5c31\u53ef\u4ee5\u4e86\uff0c\u56e0\u4e3a\u6bcf\u4e2a\u7ad9\u70b9\u7684\u9898\u90fd\u6709\u4e00\u5b9a\u7684\u96be\u6613\u6bd4\u4f8b\uff0c\u7cfb\u7edf\u5730\u505a\u4e00\u5957\u9898\u5e93\u53ef\u4ee5\u4f7f\u4f60\u5bf9\u5404\u79cd\u96be\u5ea6\u3001\u5404\u79cd\u7c7b\u578b\u7684\u9898\u90fd\u6709\u6240\u8ba4\u8bc6\u3002
1\u3001Ural\uff1a
Ural\u662f\u4e2d\u56fd\u5b66\u751f\u5bf9\u4fc4\u7f57\u65af\u7684Ural\u5dde\u7acb\u5927\u5b66\u7684\u7b80\u79f0 \uff0c\u90a3\u91cc\u8bbe\u7acb\u4e86\u4e00\u4e2aUral Online Problem Set\uff0c\u5e76\u4e14\u652f\u6301Online Judge\u3002Ural\u7684\u4e0d\u5c11\u9898\u76ee\u7b97\u6cd5\u6027\u548c\u8da3\u95fb\u6027\u90fd\u5f88\u5f3a\uff0c\u5f97\u5230\u4e86\u56fd\u5185\u5e7f\u5927\u5b66\u751f\u7684\u539a\u7231\u3002\u6839\u636e\u201c\u4fe1\u606f\u5b66\u521d\u5b66\u8005\u4e4b\u5bb6\u201d\u7f51\u7ad9\u7684\u7edf\u8ba1\uff0cUral\u7684\u9898\u76ee\u7c7b\u578b\u5927\u6982\u5448\u5982\u4e0b\u7684\u5206\u5e03\uff1a
\u9898\u578b
\u641c\u7d22
\u52a8\u6001\u89c4\u5212
\u8d2a\u5fc3
\u6784\u9020
\u56fe\u8bba
\u8ba1\u7b97\u51e0\u4f55
\u7eaf\u6570\u5b66\u95ee\u9898
\u6570\u636e\u7ed3\u6784
\u5176\u5b83
\u6240\u5360\u6bd4\u4f8b
\u7ea610%
\u7ea615%
\u7ea65%
\u7ea65%
\u7ea610%
\u7ea65%
\u7ea620%
\u7ea65%
\u7ea625%
\u8fd9\u548c\u5b9e\u9645\u6bd4\u8d5b\u4e2d\u7684\u9898\u578b\u5206\u5e03\u4e5f\u662f\u5927\u4f53\u76f8\u5f53\u7684\u3002\u6709\u5174\u8da3\u7684\u670b\u53cb\u53ef\u4ee5\u53bb\u770b\u770b\u3002
2\u3001UVA\uff1a
UVA\u4ee3\u8868\u897f\u73ed\u7259Valladolid\u5927\u5b66(University de Valladolid)\u3002\u8be5\u5927\u5b66\u6709\u4e00\u4e2a\u90a3\u91cc\u8bbe\u7acb\u4e86\u4e00\u4e2aPROBLEM SET ARCHIVE with ONLINE JUDGE \uff0c\u5e76\u4e14\u652f\u6301ONLINE JUDGE\uff0c\u5f62\u5f0f\u548cUral\u5927\u5b66\u7684\u9898\u5e93\u7c7b\u4f3c\u3002\u4e0d\u8fc7\u548cUral\u4e0d\u540c\u7684\u662f\uff0cUVA\u9898\u76ee\u591a\u7684\u591a\uff0c\u800c\u4e14\u6bd4\u8f83\u6742\uff0c\u800c\u4e14\u6709\u4e9b\u9898\u76ee\u7684\u6d4b\u8bd5\u6570\u636e\u6bd4\u8f83\u5201\u94bb\u3002\u8fd9\u4f7f\u5f97\u521a\u5230\u90a3\u91cc\u505a\u9898\u7684\u670b\u53cb\u5f80\u5f80\u611f\u89c9\u5230\u65e0\u6240\u9002\u4ece\uff0c\u8981\u4e48\u96be\u4ee5\u627e\u5230\u5408\u9002\u7684\u9898\u76ee\uff0c\u8981\u4e48Wrong Answer\u4e86\u5f88\u591a\u6b21\u4ee5\u540e\u4ecd\u7136\u4e0d\u77e5\u9053\u9519\u5728\u90a3\u91cc\u3002 \u5982\u679c\u8bf4\u505aUral\u9898\u76ee\u4e3b\u8981\u662f\u4e3a\u4e86\u8bad\u7ec3\u7b97\u6cd5\uff0c\u90a3\u4e48UVA\u9898\u76ee\u53ef\u4ee5\u8bad\u7ec3\u5168\u65b9\u4f4d\u7684\u57fa\u672c\u529f\u548c\u4e00\u4e9b\u5fc5\u8981\u7684\u7f16\u7a0b\u7d20\u8d28\u3002UVA\u548c\u8bb8\u591a\u4e16\u754c\u77e5\u540d\u5927\u5b66\u8054\u5408\u529e\u6709\u540c\u6b65\u7f51\u4e0a\u6bd4\u8d5b\uff0c\u56e0\u6b64\u90a3\u91cc\u5f3a\u4eba\u65e0\u6570\uff0c\u4e0d\u8fc7\u4f60\u5148\u8981\u4f7f\u81ea\u5df1\u5177\u6709\u542c\u61c2\u4ed6\u4eec\u5728\u8bf4\u4ec0\u4e48\u7684\u7d20\u8d28\uff1a\uff09
3\u3001ZOJ\uff1a
ZOJ\u662f\u6d59\u6c5f\u5927\u5b66\u5efa\u7acb\u7684ONLINE JUDGE\uff0c\u662f\u4e2d\u56fd\u5927\u5b66\u5efa\u7acb\u7684\u7b2c\u4e00\u4e2a\u540c\u7c7b\u7ad9\u70b9\uff0c\u4e5f\u662f\u6700\u597d\u548c\u4eba\u6c14\u6700\u9ad8\u7684\u4e00\u4e2a\uff0c\u7b14\u8005\u548c\u8bb8\u591a\u73ed\u91cc\u7684\u540c\u5b66\u5c31\u662f\u5728\u8fd9\u91cc\u7ec3\u4e60\u3002ZOJ\u867d\u7136\u4e5f\u5b9a\u4f4d\u4e3a\u4e00\u4e2a\u82f1\u6587\u7f51\u7ad9\uff0c\u4f46\u662f\u8fd9\u91cc\u7684\u4e2d\u56fd\u5b66\u751f\u6bd4\u8f83\u591a\uff0c\u56e0\u6b64\u8ba9\u4eba\u89c9\u5f97\u5f88\u4eb2\u5207\u3002\u8fd9\u91cc\u76ee\u524d\u6709500\u591a\u9053\u9898\u76ee\uff0c\u96be\u6613\u5206\u914d\u9002\u4e2d\uff0c\u4e14\u6db5\u76d6\u4e86\u5404\u5927\u6d32\u7684\u9898\u76ee\u7c7b\u578b\u5e76\u914d\u6709\u7d22\u5f15\uff0c\u9664\u6b64\u4e4b\u5916\uff0cZOJ\u7684JUDGE\u7cfb\u7edf\u662f\u51e0\u4e2a\u7f51\u7ad9\u4e2d\u8868\u73b0\u5f97\u6bd4\u8f83\u597d\u7684\u4e00\u4e2a\uff0c\u5f88\u5c11\u51fa\u73b0Wrong Answer\u548cPresentation error\u6df7\u6dc6\u7684\u60c5\u51b5\u3002\u8fd9\u91cc\u6bcf\u6708\u4e5f\u529e\u6709\u4e00\u6b21\u7f51\u4e0a\u6bd4\u8d5b\uff0c\u53ea\u8981\u662f\u6ce8\u518c\u7684\u7528\u6237\u90fd\u53ef\u4ee5\u53c2\u52a0\u3002
\u8bf4\u8d77\u4e2d\u56fd\u7684ONLINE JUDGE\uff0c\u53bb\u5e74\u624d\u5f00\u59cb\u53c2\u52a0ACM\u7ade\u8d5b\u7684\u5317\u4eac\u5927\u5b66\u73b0\u5728\u4e5f\u5efa\u7acb\u4e86\u81ea\u5df1\u7684\u63d0\u4ea4\u7cfb\u7edf\uff1b\u800c\u6211\u4eec\u5b66\u6821\u4e5f\u662f\u53bb\u5e74\u5f00\u59cb\u53c2\u52a0\u6bd4\u8d5b\uff0c\u73b0\u5728\u4e5f\u6709\u53ef\u80fd\u63a8\u51fa\u81ea\u5df1\u7684\u63d0\u4ea4\u7cfb\u7edf\uff0c\u5982\u679c\u80fd\u591f\u505a\u6210\uff0c\u5230\u65f6\u5019\u5927\u5bb6\u5c31\u53ef\u4ee5\u53bb\u4e0a\u9762\u505a\u9898\u4e86\u3002\u540c\u7c7b\u7f51\u7ad9\u7684\u98de\u901f\u53d1\u5c55\u6807\u5fd7\u7740\u6709\u8d8a\u6765\u8d8a\u591a\u7684\u540c\u5b66\u6709\u5174\u8da3\u8fdb\u5165\u4fe1\u606f\u5b66\u7684\u9886\u57df\u63a2\u7d22\uff0c\u8fd9\u662f\u4e00\u4ef6\u597d\u4e8b\uff0c\u540c\u65f6\u4e5f\u610f\u5473\u7740\u66f4\u6fc0\u70c8\u7684\u7ade\u4e89\u3002
\u770b\u770b\u90a3\u6709\u6ca1\u6709\u5e2e\u52a9\uff0c\u6211\u4e5f\u662f\u65b0\u624b\u5165\u95e8\u2026\u2026
DP\u662f\u52a8\u6001\u89c4\u5212\u3002\u3002\u662facm\u4e2d\u4e00\u4e2a\u975e\u5e38\u975e\u5e38\u91cd\u8981\u7684\u7b97\u6cd5\u3002\u3002
\u6211\u4eec\u8001\u5e08\u8bf4 \u4e0d\u4f1aDP\u548c\u641c\u7d22 \u6c38\u8fdc\u662f\u83dc\u9e1f\u3002\u3002\u3002
DP\u662f\u4e00\u79cd\u601d\u60f3\uff0c\u5c31\u662f\u628a\u590d\u6742\u7684\u95ee\u9898 \u5206\u89e3\u6210\u5f88\u591a\u7b80\u5355\u5b50\u95ee\u9898\uff0c\u89e3\u51b3\u4e86\u6240\u6709\u5b50\u95ee\u9898\u5c31\u76f8\u5f53\u4e8e\u89e3\u51b3\u4e86\u5927\u95ee\u9898\u3002\u3002\u3002
\u5173\u4e8eacm\u3002\u3002
\u5148\u5b66\u4e00\u95e8\u8bed\u8a00\u3002\u3002\u5b8c\u4e86\u53bb\u5404\u5927OJ\u5237\u6c34\u9898\uff08\u5c31\u662f\u505a\u7b80\u5355\u9898\uff0c\u51e0\u4e4e\u4e0d\u7275\u626f\u7b97\u6cd5\u7684\u9898\u3002\uff09\uff0c\u953b\u70bc\u903b\u8f91\u601d\u7ef4\uff0c\u953b\u70bc\u601d\u7ef4\u7684\u7f1c\u5bc6\uff0c\u953b\u70bc\u4ee3\u7801\u80fd\u529b\u3002\u3002
\u6211\u4eec\u8001\u5e08\u8bf4\u5148\u5237500\u9053\u6c34\u9898\u5728\u5b66\u7b97\u6cd5\u3002= =~\uff01 \u89c9\u5f97\u6709\u70b9\u2026\u2026\u3002\u3002
\uff08\u5c31\u662f\u544a\u8bc9\u6211\u4eec\u5148\u591a\u5237\u6c34\u9898\u3002\u3002\u3002\uff09
\u6c34\u9898\u676d\u7535OJ \u5f88\u591a\uff0811\u9875\u548c16\u9875\u6709\u4e2d\u6587\u6c34\u9898\uff0c\u9002\u5408\u65b0\u624b\uff09\u3002\u3002http://acm.hdu.edu.cn
\u6c34\u9898\u5237\u7684\u5dee\u4e0d\u591a\u4e86\uff0c\u5728\u5b66 \u7b97\u6cd5\uff0c\u6570\u636e\u7ed3\u6784\u3002\u3002
\u7b97\u6cd5 \u5148\u770b \u7b97\u6cd5\u5bfc\u8bba\u3002\u3002\u4e4b\u540e\u518d\u770b\u770b\u5218\u6c5d\u4f73\u7684 \u9ed1\u4e66\uff08\u7b97\u6cd5\u827a\u672f\u4e0e\u4fe1\u606f\u5b66\u7ade\u8d5b\uff09\u3002
\u9ed1\u4e66 \u5bf9\u65b0\u624b\u6765\u8bf4\u5f88\u96be\uff0c\u6240\u4ee5\u5148\u770b \u7b97\u6cd5\u5bfc\u8bba\u3002\u3002\u3002
\u8981\u662f\u628a\u8fd9\u4e24\u672c\u4e66\u770b\u597d\u4e86 \u90a3\u4f60\u4e5f\u7b97\u662f\u4e00\u53ea\u725b\u4e86\u3002\u3002
\u5173\u952e\u8fd8\u662f\u5237\u9898\u3002\u3002
一.基本算法:
(1)枚举. (poj1753,poj2965)
(2)贪心(poj1328,poj2109,poj2586)
(3)递归和分治法.
(4)递推.
(5)构造法.(poj3295)
(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.图算法:
(1)图的深度优先遍历和广度优先遍历.
(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
(3)最小生成树算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
(4)拓扑排序 (poj1094)
(5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)
(6)最大流的增广路算法(KM算法). (poj1459,poj3436)
三.数据结构.
(1)串 (poj1035,poj3080,poj1936)
(2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)
(3)简单并查集的应用.
(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
(5)哈夫曼树(poj3253)
(6)堆
(7)trie树(静态建树、动态建树) (poj2513)
四.简单搜索
(1)深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.动态规划
(1)背包问题. (poj1837,poj1276)
(2)型如下表的简单DP(可参考lrj的书 page149):
1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列)
(poj3176,poj1080,poj1159)
3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)
六.数学
(1)组合数学:
1.加法原理和乘法原理.
2.排列组合.
3.递推关系.
(POJ3252,poj1850,poj1019,poj1942)
(2)数论.
1.素数与整除问题
2.进制位.
3.同余模运算.
(poj2635, poj3292,poj1845,poj2115)
(3)计算方法.
1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)
七.计算几何学.
(1)几何公式.
(2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)
(3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)
(poj1408,poj1584)
(4)凸包. (poj2187,poj1113)
中级:
一.基本算法:
(1)C++的标准模版库的应用. (poj3096,poj3007)
(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)
二.图算法:
(1)差分约束系统的建立和求解. (poj1201,poj2983)
(2)最小费用最大流(poj2516,poj2516,poj2195)
(3)双连通分量(poj2942)
(4)强连通分支及其缩点.(poj2186)
(5)图的割边和割点(poj3352)
(6)最小割模型、网络流规约(poj3308, )
三.数据结构.
(1)线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)
(2)静态二叉检索树. (poj2482,poj2352)
(3)树状树组(poj1195,poj3321)
(4)RMQ. (poj3264,poj3368)
(5)并查集的高级应用. (poj1703,2492)
(6)KMP算法. (poj1961,poj2406)
四.搜索
(1)最优化剪枝和可行性剪枝
(2)搜索的技巧和优化 (poj3411,poj1724)
(3)记忆化搜索(poj3373,poj1691)
五.动态规划
(1)较为复杂的动态规划(如动态规划解特别的施行商问题等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
(2)记录状态的动态规划. (POJ3254,poj2411,poj1185)
(3)树型动态规划(poj2057,poj1947,poj2486,poj3140)
六.数学
(1)组合数学:
1.容斥原理.
2.抽屉原理.
3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).
4.递推关系和母函数.
(2)数学.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率问题. (poj3071,poj3440)
3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)
(3)计算方法.
1.0/1分数规划. (poj2976)
2.三分法求解单峰(单谷)的极值.
3.矩阵法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
(4)随机化算法(poj3318,poj2454)
(5)杂题.
(poj1870,poj3296,poj3286,poj1095)
七.计算几何学.
(1)坐标离散化.
(2)扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用).
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
(3)多边形的内核(半平面交)(poj3130,poj3335)
(4)几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)
高级:
一.基本算法要求:
(1)代码快速写成,精简但不失风格
(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
(2)保证正确性和高效性. poj3434
二.图算法:
(1)度限制最小生成树和第K最短路. (poj1639)
(2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
(3)最优比率生成树. (poj2728)
(4)最小树形图(poj3164)
(5)次小生成树.
(6)无向图、有向图的最小环
三.数据结构.
(1)trie图的建立和应用. (poj2778)
(2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和 在线算法
(RMQ+dfs)).(poj1330)
(3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的
目的). (poj2823)
(4)左偏树(可合并堆).
(5)后缀树(非常有用的数据结构,也是赛区考题的热点).
(poj3415,poj3294)
四.搜索
(1)较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)
(2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
(3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286)
五.动态规划
(1)需要用数据结构优化的动态规划.
(poj2754,poj3378,poj3017)
(2)四边形不等式理论.
(3)较难的状态DP(poj3133)
六.数学
(1)组合数学.
1.MoBius反演(poj2888,poj2154)
2.偏序关系理论.
(2)博奕论.
1.极大极小过程(poj3317,poj1085)
2.Nim问题.
七.计算几何学.
(1)半平面求交(poj3384,poj2540)
(2)可视图的建立(poj2966)
(3)点集最小圆覆盖.
(4)对踵点(poj2079)
八.综合题.
(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)
Dp状态设计与方程总结
1.不完全状态记录
<1>青蛙过河问题
<2>利用区间dp
2.背包类问题
<1> 0-1背包，经典问题
<2>无限背包，经典问题
<3>判定性背包问题
<4>带附属关系的背包问题
<5> + -1背包问题
<6>双背包求最优值
<7>构造三角形问题
<8>带上下界限制的背包问题(012背包)
3.线性的动态规划问题
<1>积木游戏问题
<2>决斗（判定性问题）
<3>圆的最大多边形问题
<4>统计单词个数问题
<5>棋盘分割
<6>日程安排问题
<7>最小逼近问题(求出两数之比最接近某数/两数之和等于某数等等)
<8>方块消除游戏(某区间可以连续消去求最大效益)
<9>资源分配问题
<10>数字三角形问题
<11>漂亮的打印
<12>邮局问题与构造答案
<13>最高积木问题
<14>两段连续和最大
<15>2次幂和问题
<16>N个数的最大M段子段和
<17>交叉最大数问题
4.判定性问题的dp(如判定整除、判定可达性等)
<1>模K问题的dp
<2>特殊的模K问题，求最大(最小)模K的数
<3>变换数问题
5.单调性优化的动态规划
<1>1-SUM问题
<2>2-SUM问题
<3>序列划分问题(单调队列优化)
6.剖分问题(多边形剖分/石子合并/圆的剖分/乘积最大)
<1>凸多边形的三角剖分问题
<2>乘积最大问题
<3>多边形游戏(多边形边上是操作符,顶点有权值)
<4>石子合并(N^3/N^2/NLogN各种优化)
7.贪心的动态规划
<1>最优装载问题
<2>部分背包问题
<3>乘船问题
<4>贪心策略
<5>双机调度问题Johnson算法
8.状态dp
<1>牛仔射击问题(博弈类)
<2>哈密顿路径的状态dp
<3>两支点天平平衡问题
<4>一个有向图的最接近二部图
9.树型dp
<1>完美服务器问题(每个节点有3种状态)
<2>小胖守皇宫问题
<3>网络收费问题
<4>树中漫游问题
<5>树上的博弈
<6>树的最大独立集问题
<7>树的最大平衡值问题
<8>构造树的最小环
初期:
一.基本算法:
(1)枚举. (poj1753,poj2965)
(2)贪心(poj1328,poj2109,poj2586)
(3)递归和分治法.
(4)递推.
(5)构造法.(poj3295)
(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.图算法:
(1)图的深度优先遍历和广度优先遍历.
(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
(3)最小生成树算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
(4)拓扑排序 (poj1094)
(5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)
(6)最大流的增广路算法(KM算法). (poj1459,poj3436)
三.数据结构.
(1)串 (poj1035,poj3080,poj1936)
(2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)
(3)简单并查集的应用.
(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
(5)哈夫曼树(poj3253)
(6)堆
(7)trie树(静态建树、动态建树) (poj2513)
四.简单搜索
(1)深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.动态规划
(1)背包问题. (poj1837,poj1276)
(2)型如下表的简单DP(可参考lrj的书 page149):
1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列)
(poj3176,poj1080,poj1159)
3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)
六.数学
(1)组合数学:
1.加法原理和乘法原理.
2.排列组合.
3.递推关系.
(POJ3252,poj1850,poj1019,poj1942)
(2)数论.
1.素数与整除问题
2.进制位.
3.同余模运算.
(poj2635, poj3292,poj1845,poj2115)
(3)计算方法.
1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)
七.计算几何学.
(1)几何公式.
(2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)
(3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)
(poj1408,poj1584)
(4)凸包. (poj2187,poj1113)
中级:
一.基本算法:
(1)C++的标准模版库的应用. (poj3096,poj3007)
(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)
二.图算法:
(1)差分约束系统的建立和求解. (poj1201,poj2983)
(2)最小费用最大流(poj2516,poj2516,poj2195)
(3)双连通分量(poj2942)
(4)强连通分支及其缩点.(poj2186)
(5)图的割边和割点(poj3352)
(6)最小割模型、网络流规约(poj3308, )
三.数据结构.
(1)线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)
(2)静态二叉检索树. (poj2482,poj2352)
(3)树状树组(poj1195,poj3321)
(4)RMQ. (poj3264,poj3368)
(5)并查集的高级应用. (poj1703,2492)
(6)KMP算法. (poj1961,poj2406)
四.搜索
(1)最优化剪枝和可行性剪枝
(2)搜索的技巧和优化 (poj3411,poj1724)
(3)记忆化搜索(poj3373,poj1691)
五.动态规划
(1)较为复杂的动态规划(如动态规划解特别的施行商问题等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
(2)记录状态的动态规划. (POJ3254,poj2411,poj1185)
(3)树型动态规划(poj2057,poj1947,poj2486,poj3140)
六.数学
(1)组合数学:
1.容斥原理.
2.抽屉原理.
3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).
4.递推关系和母函数.
(2)数学.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率问题. (poj3071,poj3440)
3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)
(3)计算方法.
1.0/1分数规划. (poj2976)
2.三分法求解单峰(单谷)的极值.
3.矩阵法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
(4)随机化算法(poj3318,poj2454)
(5)杂题.
(poj1870,poj3296,poj3286,poj1095)
七.计算几何学.
(1)坐标离散化.
(2)扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用).
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
(3)多边形的内核(半平面交)(poj3130,poj3335)
(4)几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)
高级:
一.基本算法要求:
(1)代码快速写成,精简但不失风格
(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
(2)保证正确性和高效性. poj3434
二.图算法:
(1)度限制最小生成树和第K最短路. (poj1639)
(2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
(3)最优比率生成树. (poj2728)
(4)最小树形图(poj3164)
(5)次小生成树.
(6)无向图、有向图的最小环
三.数据结构.
(1)trie图的建立和应用. (poj2778)
(2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和 在线算法
(RMQ+dfs)).(poj1330)
(3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的
目的). (poj2823)
(4)左偏树(可合并堆).
(5)后缀树(非常有用的数据结构,也是赛区考题的热点).
(poj3415,poj3294)
四.搜索
(1)较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)
(2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
(3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286)
五.动态规划
(1)需要用数据结构优化的动态规划.
(poj2754,poj3378,poj3017)
(2)四边形不等式理论.
(3)较难的状态DP(poj3133)
六.数学
(1)组合数学.
1.MoBius反演(poj2888,poj2154)
2.偏序关系理论.
(2)博奕论.
1.极大极小过程(poj3317,poj1085)
2.Nim问题.
七.计算几何学.
(1)半平面求交(poj3384,poj2540)
(2)可视图的建立(poj2966)
(3)点集最小圆覆盖.
(4)对踵点(poj2079)
八.综合题.
(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)
以及补充
Dp状态设计与方程总结
1.不完全状态记录
<1>青蛙过河问题
<2>利用区间dp
2.背包类问题
<1> 0-1背包，经典问题
<2>无限背包，经典问题
<3>判定性背包问题
<4>带附属关系的背包问题
<5> + -1背包问题
<6>双背包求最优值
<7>构造三角形问题
<8>带上下界限制的背包问题(012背包)
3.线性的动态规划问题
<1>积木游戏问题
<2>决斗（判定性问题）
<3>圆的最大多边形问题
<4>统计单词个数问题
<5>棋盘分割
<6>日程安排问题
<7>最小逼近问题(求出两数之比最接近某数/两数之和等于某数等等)
<8>方块消除游戏(某区间可以连续消去求最大效益)
<9>资源分配问题
<10>数字三角形问题
<11>漂亮的打印
<12>邮局问题与构造答案
<13>最高积木问题
<14>两段连续和最大
<15>2次幂和问题
<16>N个数的最大M段子段和
<17>交叉最大数问题
4.判定性问题的dp(如判定整除、判定可达性等)
<1>模K问题的dp
<2>特殊的模K问题，求最大(最小)模K的数
<3>变换数问题
5.单调性优化的动态规划
<1>1-SUM问题
<2>2-SUM问题
<3>序列划分问题(单调队列优化)
6.剖分问题(多边形剖分/石子合并/圆的剖分/乘积最大)
<1>凸多边形的三角剖分问题
<2>乘积最大问题
<3>多边形游戏(多边形边上是操作符,顶点有权值)
<4>石子合并(N^3/N^2/NLogN各种优化)
7.贪心的动态规划
<1>最优装载问题
<2>部分背包问题
<3>乘船问题
<4>贪心策略
<5>双机调度问题Johnson算法
8.状态dp
<1>牛仔射击问题(博弈类)
<2>哈密顿路径的状态dp
<3>两支点天平平衡问题
<4>一个有向图的最接近二部图
9.树型dp
<1>完美服务器问题(每个节点有3种状态)
<2>小胖守皇宫问题
<3>网络收费问题
<4>树中漫游问题
<5>树上的博弈
<6>树的最大独立集问题
<7>树的最大平衡值问题
<8>构造树的最小环
做acm的话入门比较难,水平提升更加困难,要做好充足的准备哦
我的建议是:
1.可以先做一些简单的不涉及算法知识,简单的水题上手,oj上通过率很高做的人很多的就是啦
2.上手了以后可以针对特定算法进行练习,网上有很多的题目分类,你可以对着分类练习算法,最简单的贪心算法,到动态规划,搜索等等,计算机专业有一门课叫做计算机算法设计与分析,里面介绍的知识都是acm的常用算法.推荐几本书给你〈计算机算法设计与分析〉王晓东编著
<算法导论>
<国际大学生程序设计竞赛试题>
都是经典!!!
3.数据结构很重要在算法优化当中,特别是树和图
4.组合数学和数论的题目碰到蛮多的
5.还有计算几何 ps:这个我一直没怎么学
做acm很辛苦也很快乐,祝你顺利......
好贴。顶一下。
先要学习一门计算机语言，然后学 数据结构和算法
最后，还要自己多锻炼的
数学不好就别想在acm上有什么前途。计算机算法都建立在数学理论基础上，不是臆想出来的。
绛旓細1.鍙互鍏堝仛涓浜涚畝鍗曠殑涓嶆秹鍙婄畻娉曠煡璇,绠鍗曠殑姘撮涓婃墜,oj涓婇氳繃鐜囧緢楂鍋鐨勪汉寰堝鐨勫氨鏄暒2.涓婃墜浜嗕互鍚庡彲浠ラ拡瀵圭壒瀹氱畻娉曡繘琛岀粌涔,缃戜笂鏈夊緢澶氱殑棰樼洰鍒嗙被,浣犲彲浠ュ鐫鍒嗙被缁冧範绠楁硶,鏈绠鍗曠殑璐績绠楁硶,鍒板姩鎬佽鍒,鎼滅储绛夌瓑,璁＄畻鏈轰笓涓氭湁涓闂ㄨ鍙仛璁＄畻鏈虹畻娉曡璁′笌鍒嗘瀽,閲岄潰浠嬬粛鐨勭煡璇嗛兘鏄acm鐨勫父鐢ㄧ畻娉.鎺ㄨ崘鍑犳湰涔︾粰浣犮堣...
绛旓細Prim,Kruskal绠楁硶锛堝嵆鏈灏忕敓鎴愭爲绠楁硶锛夌孩榛戞爲 a-B鍓灊娉 娣便佸箍搴︽悳绱 鎷撴墤鎺掑簭 寮鸿繛閫氬垎閲 Dijkstra,Bellman-Ford,Floyd-Warashall绠楁硶锛堟渶鐭矾寰勭畻娉曪級璁＄畻鍑犱綍锛堢嚎娈电浉浜わ紝鍑稿寘锛屾渶杩戠偣瀵癸級
绛旓細(6)妯℃嫙娉.(poj1068,poj2632,poj1573,poj2993,poj2996)浜.鍥绠楁硶:(1)鍥剧殑娣卞害浼樺厛閬嶅巻鍜屽箍搴︿紭鍏堥亶鍘.(2)鏈鐭矾寰勭畻娉(dijkstra,bellman-ford,floyd,heap+dijkstra)(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)(3)鏈灏忕敓鎴愭爲绠楁硶(prim,kruskal)(poj1789,poj2485,poj1258,poj3026)(4)鎷...
绛旓細鏈鍩烘湰鐨勩佷篃鏄渶鏍稿績鐨勶紝鎺屾彙鍚勭鏁版嵁缁撴瀯鍙婂叾瀵瑰簲鐨勯珮鏁堢畻娉曪紝姣斿绾挎х粨鏋勶紙椤哄簭琛ㄣ侀摼琛ㄧ瓑锛夌殑鏌ユ壘銆鎺掑簭绠楁硶锛屾爲锛堜簩鍙夋爲銆佹悳绱㈡爲锛夌殑鍘熺悊銆佸熀纭鐨勯亶鍘嗐佹煡鎵剧畻娉曪紝鍥剧殑鍘熺悊銆佺畻娉曘佸簲鐢ㄥ満鏅傚瀹屼箣鍚庡氨鍙互寮濮嬪埌鍚勭OJ鍒烽浜嗐
绛旓細浜 绠楁硶 1锛鎺掑簭绠楁硶锛堝啋鎶涙硶锛屾彃鍏ユ帓搴忥紝鍚堝苟鎺掑簭锛屽揩閫熸帓 搴忥紝鍫嗘帓搴忥級2锛屾煡鎵撅紙椤哄簭鏌ユ壘锛屼簩鍒嗗彂锛3锛屽洖婧畻娉 4锛岄掑綊绠楁硶 5锛屽垎娌荤畻娉 6锛屾ā鎷熸硶 7锛岃椽蹇冩硶 8锛岀畝鍗曟悳绱㈢畻娉曪紙娣卞害浼樺厛锛屽箍搴︿紭鍏堬級锛屾悳绱腑鐨 鍓灊锛孉*绠楁硶 9锛屽姩鎬佽鍒掔殑鎬濇兂鍙婂熀鏈畻娉 10锛岄珮绮惧害杩愮畻 涓夈丄CM绔炶禌鐨勯鍨...
绛旓細锛1锛夊熀鏈绠楁硶: 浜屽垎,鍒嗘不锛岃椽蹇 锛2锛 绂绘暎鏁板绂绘暎鏁板鍔ㄦ佽鍒 锛3锛 鎼滅储绠楁硶锛氭繁搴︿紭鍏 鎼滅储锛屽箍搴︿紭鍏堟悳 A*绠楁硶 锛岄樋灏旀硶璐濆鍓灊 锛4锛夋暟鎹粨鏋: 绾挎鏍, 鏍戠姸鏁扮粍锛屽苟鏌ラ泦,Trie鍥 锛5锛夊浘璁洪棶棰橈細鏈灏忕敓鎴愭爲 鏈鐭矾 寮鸿繛閫氬垎閲忋佹ˉ鍜屽壊鐐 锛6锛夌綉缁滄祦绠楁硶锛氬熀鏈殑缃戠粶娴佺畻娉曪紝Dinic绠楁硶...
绛旓細4. 鍥捐闂锛氳繖浜涢棶棰樹富瑕佹秹鍙婂浘璁绠楁硶锛屽Dijkstra銆丗loyd銆丳rime銆丅ellman-Ford绠楁硶锛屼互鍙婃渶澶ф祦銆佷簩鍒嗗尮閰嶇瓑銆傚浜庣啛鎮ACM鐨浜烘潵璇达紝杩欎簺绠楁硶搴旇閮戒笉闅俱5. 璁＄畻鏈虹畻娉曡璁￠棶棰橈細杩欏寘鎷姩鎬佽鍒掋佸洖婧悳绱佸垎娌汇佸垎鏀畾鐣屾硶锛堢敤浜庢眰瑙ｆ暣鏁拌В锛夌瓑绠楁硶璁捐銆6. 鏈浼樺寲鐞嗚鐨勯潪缁忓吀绠楁硶锛氬寘鎷ā鎷熼鐏硶...
绛旓細涓 绠楁硶(Algorithm)1 妯℃嫙绠楁硶 2 鎼滅储绠楁硶 2.1 鏋氫妇鎼滅储(Enumeration)2.2 娣卞害浼樺厛(Depth First Search)2.3 骞垮害浼樺厛(Breadth First Search)2.4 鍚彂寮忔悳绱(Heuristic Search)3 浠モ滅浉浼兼垨鐩稿悓瀛愰棶棰樷濅负鏍稿績鐨勭畻娉 3.1 閫掓帹 3.2 閫掑綊(Recursion)3.3 璐績娉(Greedy)3.4 鍔ㄦ佽鍒(Dynamic ...
绛旓細璁粌杩ACM绛夌▼搴忚璁＄珵璧涚殑浜哄湪绠楁硶涓婃湁杈冨ぇ鐨勪紭鍔匡紝杩欏氨璇存槑褰撲綘缂栫▼鑳藉姏鎻愰珮涔嬪悗锛屼富瑕佹椂闂存槸鑺卞湪鎬濊冪畻娉曚笂锛屼笉鏄姳鍦ㄥ啓绋嬪簭涓巇ebug涓娿備笅闈㈢粰涓鍒掍綘缁冪粌锛氱涓闃舵锛氱粌缁忓吀甯哥敤绠楁硶锛屼笅闈㈢殑姣忎釜绠楁硶缁欐垜鎵撲笂鍗佸埌浜屽崄閬嶏紝鍚屾椂鑷繁绮剧畝浠ｇ爜锛屽洜涓哄お甯哥敤锛屾墍浠ヨ缁冨埌鍐欐椂涓嶇敤鎯筹紝10-15鍒嗛挓鍐呮墦瀹岋紝...
绛旓細鈶 姣旇禌鐨勬椂鍊欏厑璁稿甫绾歌川鏉愭枡锛屼篃灏辨槸璇达紝鍙互鎶婃墍鏈夌幇鎴愮殑绠楁硶浠ｇ爜涔︾睄甯﹁繘鍘伙紝闇瑕佺殑鏃跺欑洿鎺ョ洰褰曠储寮曞埌锛屾妱涓婂幓锛堝浜庢瘡鍒嗛挓300涓嫳鏂囧瓧姣嶇殑鐩叉墦閫熷害锛2鍒嗛挓灏辫兘鍐欏畬涓涓畻娉曪紝鍓╀笅鐨勫氨鏄拡瀵归鐩紝鎶绠楁硶鍋涓涓紭鍖栧拰澶勭悊骞剁粨鍚堝叾浠栫畻娉曪紝瑙ｅ喅棰樼洰锛夈傗憽 涓鑸甯哥敤鐨勫氨鏄帓搴忋佹暟鎹粨鏋勩佹悳绱㈢畻娉曪紝...
