{"id":1213,"date":"2014-09-05T16:52:29","date_gmt":"2014-09-05T08:52:29","guid":{"rendered":"http:\/\/wx.wosign.com\/?p=1213"},"modified":"2014-09-05T16:52:29","modified_gmt":"2014-09-05T08:52:29","slug":"hnu-10104-%e7%97%85%e6%af%92-ac%e8%87%aa%e5%8a%a8%e6%9c%badfs","status":"publish","type":"post","link":"https:\/\/wx.wosign.com\/?p=1213","title":{"rendered":"Hnu 10104 \u75c5\u6bd2 (AC\u81ea\u52a8\u673a+dfs)"},"content":{"rendered":"\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
\u75c5\u6bd2<\/strong><\/td>\n<\/tr>\n
Time Limit:\u00a0<\/strong>\u00a0<\/span>1000ms,\u00a0\u00a0<\/span>Special Time Limit:<\/strong>\u00a0<\/span>2500ms,\u00a0\u00a0<\/span>Memory Limit:<\/strong>\u00a0<\/span>32768KB<\/td>\n<\/tr>\n
Total submit users:<\/strong>\u00a0<\/span>41,\u00a0\u00a0<\/span>Accepted users:\u00a0<\/strong>\u00a0<\/span>23<\/td>\n<\/tr>\n
Problem 10104 :\u00a0<\/strong>\u00a0<\/span>No special judgement<\/td>\n<\/tr>\n
Problem description<\/strong><\/td>\n<\/tr>\n
\u4e8c\u8fdb\u5236\u75c5\u6bd2\u5ba1\u67e5\u59d4\u5458\u4f1a\u6700\u8fd1\u53d1\u73b0\u4e86\u5982\u4e0b\u7684\u89c4\u5f8b\uff1a\u67d0\u4e9b\u786e\u5b9a\u7684\u4e8c\u8fdb\u5236\u4e32\u662f\u75c5\u6bd2\u7684\u4ee3\u7801\u3002\u5982\u679c\u67d0\u6bb5\u4ee3\u7801\u4e2d\u4e0d\u5b58\u5728\u4efb\u4f55\u4e00\u6bb5\u75c5\u6bd2\u4ee3\u7801\uff0c\u90a3\u4e48\u6211\u4eec\u5c31\u79f0\u8fd9\u6bb5\u4ee3\u7801\u662f\u5b89\u5168\u7684\u3002\u73b0\u5728\u59d4\u5458\u4f1a\u5df2\u7ecf\u627e\u51fa\u4e86\u6240\u6709\u7684\u75c5\u6bd2\u4ee3\u7801\u6bb5\uff0c\u8bd5\u95ee\uff0c\u662f\u5426\u5b58\u5728\u4e00\u4e2a\u65e0\u9650\u957f\u7684\u5b89\u5168\u7684\u4e8c\u8fdb\u5236\u4ee3\u7801\u3002 \u4f8b\u5982\u5982\u679c{011, 11, 00000}\u4e3a\u75c5\u6bd2\u4ee3\u7801\u6bb5\uff0c\u90a3\u4e48\u4e00\u4e2a\u53ef\u80fd\u7684\u65e0\u9650\u957f\u5b89\u5168\u4ee3\u7801\u5c31\u662f010101\u2026\u3002\u5982\u679c{01, 11, 000000}\u4e3a\u75c5\u6bd2\u4ee3\u7801\u6bb5\uff0c\u90a3\u4e48\u5c31\u4e0d\u5b58\u5728\u4e00\u4e2a\u65e0\u9650\u957f\u7684\u5b89\u5168\u4ee3\u7801\u3002 \u4efb\u52a1\uff1a \u8bf7\u5199\u4e00\u4e2a\u7a0b\u5e8f\uff1a \u8bfb\u5165\u75c5\u6bd2\u4ee3\u7801\uff1b \u5224\u65ad\u662f\u5426\u5b58\u5728\u4e00\u4e2a\u65e0\u9650\u957f\u7684\u5b89\u5168\u4ee3\u7801\uff1b \u5c06\u7ed3\u679c\u8f93\u51fa\u3002<\/td>\n<\/tr>\n
Input<\/strong><\/td>\n<\/tr>\n
\u7b2c\u4e00\u884c\u5305\u62ec\u4e00\u4e2a\u6574\u6570n\uff0c\u8868\u793a\u75c5\u6bd2\u4ee3\u7801\u6bb5\u7684\u6570\u76ee\u3002\u4ee5\u4e0b\u7684n\u884c\u6bcf\u4e00\u884c\u90fd\u5305\u62ec\u4e00\u4e2a\u975e\u7a7a\u768401\u5b57\u7b26\u4e32\u2014\u2014\u5c31\u662f\u4e00\u4e2a\u75c5\u6bd2\u4ee3\u7801\u6bb5\u3002\u6240\u6709\u75c5\u6bd2\u4ee3\u7801\u6bb5\u7684\u603b\u957f\u5ea6\u4e0d\u8d85\u8fc730000\u3002<\/td>\n<\/tr>\n
Output<\/strong><\/td>\n<\/tr>\n
\u8f93\u51fa\u4e00\u4e2a\u5355\u8bcd\uff1a TAK\u2014\u2014\u5047\u5982\u5b58\u5728\u8fd9\u6837\u7684\u4ee3\u7801\uff1b NIE\u2014\u2014\u5982\u679c\u4e0d\u5b58\u5728<\/td>\n<\/tr>\n
Sample Input<\/strong><\/td>\n<\/tr>\n
<\/td>\n<\/tr>\n
Sample Output<\/strong><\/td>\n<\/tr>\n
\n
NIE<\/span><\/pre>\n<\/td>\n<\/tr>\n
Problem Source<\/strong><\/td>\n<\/tr>\n
Submit<\/a>\u00a0<\/span>Discuss<\/a>\u00a0<\/span>Judge Status<\/a>\u00a0<\/span>Problems<\/a>\u00a0<\/span>Ranklist<\/a><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

\u9898\u76ee\u94fe\u63a5<\/p>\n

http:\/\/acm.hnu.cn\/online\/?action=problem&type=show&id=10104<\/p>\n

\u601d\u8def\u5206\u6790\uff1a<\/p>\n

\u4ed4\u7ec6\u5206\u6790\u5c31\u4f1a\u53d1\u73b0\uff0c\u5982\u679c\u5728ac\u81ea\u52a8\u673a\u4e0a\u5b58\u5728\u4e00\u4e2a\u73af\uff0c\u4e14\u8fd9\u4e2a\u73af\u4e0a\u6ca1\u6709\u5355\u8bcd\u7684\u672b\u5c3e\u8282\u70b9\uff0c\u90a3\u4e48\u5c31\u53ef\u4ee5\u3002<\/p>\n

\u4e3a\u4ec0\u4e48\u8fde\u5355\u8bcd\u7684\u672b\u5c3e\u8282\u70b9\u4e5f\u4e0d\u884c\u3002<\/p>\n

\u56e0\u4e3aac\u81ea\u52a8\u673a\u4e0a\u7684next\u6307\u5411\u4e86\u7684\u662f\u4e0e\u5b83\u5177\u6709\u6700\u957f\u540e\u7f00\u7b49\u4e8e\u524d\u7f00\u7684\uff0c\u5982\u679c\u8fd9\u4e2a\u65f6\u5019\u540e\u7f00\u6307\u5411\u4e86\u5355\u8bcd\u672b\u5c3e\u8282\u70b9\u7684\u524d\u9762\uff0c\u4e5f\u5c31\u610f\u5473\u7740\u6709\u4e00\u4e2a\u524d\u7f00\u5728\u8fd9\u4e2a\u672b\u5c3e\u8282\u70b9\u7684\u524d\u9762\uff0c\u90a3\u4e48\u8fd9\u4e2a\u73af\u603b\u4f1a\u51fa\u73b0\u4e00\u4e2a\u5355\u8bcd\u8282\u70b9\u3002<\/p>\n

\u6240\u4ee5\u5728dfs\u7684\u65f6\u5019\uff0c\u8981\u907f\u5f00\u4e00\u5207\u7684\u5355\u8bcd\u672b\u5c3e\u8282\u70b9\u3002<\/p>\n

\u81f3\u4e8edfs\u7684\u65f6\u5019\uff0c\u6211\u4eec\u8981\u5224\u65ad\u7684\u4e5f\u662f\u4e00\u6761\u8fde\u7eed\u7684\u94fe\u4e0a\u7684\u73af\uff0c\u6240\u4ee5\u5728\u6df1\u641c\u7684\u65f6\u5019\u75281\u53bb\u6807\u8bb0\uff0c\u7136\u540e\u56de\u6eaf\u7684\u65f6\u5019\uff0c\u6807\u8bb0\u6210\u53e6\u5916\u4e00\u4e2a\u3002<\/p>\n

\u7136\u540e\u6ca1\u6709\u6807\u8bb0\u7684\u4e3a0.<\/p>\n

\u8fd9\u6837\u5c31\u53ef\u4ee5\u627e\u5230\u94fe\u4e0a\u6210\u73af\u7684\u8282\u70b9\u4e86\u3002<\/p>\n

#include <cstdio><\/span>\r\n#include <iostream><\/span>\r\n#include <cstring><\/span>\r\n#include <algorithm><\/span>\r\n#include <queue><\/span>\r\n#define N 105<\/span>\r\n#define maxn 30005<\/span>\r\nusing<\/span> namespace<\/span> std<\/span>;\r\ntypedef<\/span> long<\/span> long<\/span> ll;\r\nconst<\/span> int<\/span> mod = 100000<\/span>;\r\n\r\nconst<\/span> char<\/span> tab = '0'<\/span>;\r\nconst<\/span> int<\/span> max_next = 2<\/span>;\r\n\r\nint<\/span> next[maxn][max_next],fail[maxn],num[maxn],siz;\r\n\r\nint<\/span> newnode()\r\n{\r\nfor<\/span>(int<\/span> i=0<\/span>;i<max_next;i++)\r\nnext[siz][i]=0<\/span>;\r\nfail[siz]=num[siz]=0<\/span>;\r\nreturn<\/span> siz++;\r\n}\r\nvoid<\/span> init()\r\n{\r\nsiz=0<\/span>;\r\nnewnode();\r\n}\r\nvoid<\/span> Insert(char<\/span> *s,int<\/span> len)\r\n{\r\nint<\/span> p=0<\/span>;\r\nfor<\/span>(int<\/span> i=0<\/span>;i<len;i++)\r\n{\r\nint<\/span> &x=next[p][s[i]-tab];\r\np=x?x:x=newnode();\r\n}\r\nnum[p]++;\r\n}\r\n\r\nvoid<\/span> acbuild()\r\n{\r\nqueue<\/span><int<\/span>><\/span>Q;\r\nQ.push(0<\/span>);\r\nwhile<\/span>(!Q.empty())\r\n{\r\nint<\/span> temp=Q.front();\r\nQ.pop();\r\nfor<\/span>(int<\/span> i=0<\/span>;i<max_next;i++)\r\n{\r\nint<\/span> v=next[temp][i];\r\nif<\/span>(v==0<\/span>)next[temp][i]=next[fail[temp]][i];\r\nelse<\/span> Q.push(v);\r\nif<\/span>(temp!=0<\/span>)fail[v]=next[fail[temp]][i];\r\nif<\/span>(num[next[fail[temp]][i]])num[next[temp][i]]++;\r\n}\r\n}\r\n}\r\nint<\/span> vis[maxn];\r\nbool<\/span> dfs(int<\/span> now)\r\n{\r\nvis[now]=1<\/span>;\r\nfor<\/span>(int<\/span> j=0<\/span>;j<max_next;j++)\r\n{\r\nif<\/span>(num[next[now][j]])continue<\/span>;\r\nif<\/span>(vis[next[now][j]]==1<\/span>)return<\/span> true<\/span>;\r\nif<\/span>(vis[next[now][j]]==0<\/span> && dfs(next[now][j]))return<\/span> true<\/span>;\r\n}\r\nvis[now]=-1<\/span>;\r\nreturn<\/span> false<\/span>;\r\n}\r\n\r\nchar<\/span> word[30005<\/span>];\r\nint<\/span> main()\r\n{\r\nint<\/span> n,L;\r\nwhile<\/span>(scanf(\"%d\"<\/span>,&n)!=EOF)\r\n{\r\ninit();\r\nfor<\/span>(int<\/span> i=1<\/span>;i<=n;i++)\r\n{\r\nscanf(\"%s\"<\/span>,word);\r\nInsert(word,strlen(word));\r\n}\r\nacbuild();\r\nmemset(vis,0<\/span>,sizeof<\/span> vis);\r\nbool<\/span> ans=false<\/span>;\r\nfor<\/span>(int<\/span> i=0<\/span>;i<siz;i++)\r\nif<\/span>(!vis[i] && dfs(i))\r\n{\r\nans=true<\/span>;\r\nbreak<\/span>;\r\n}\r\nacdebug();\r\nif<\/span>(ans)puts(\"TAK\\n\"<\/span>);\r\nelse<\/span> puts(\"NIE\\n\"<\/span>);\r\n}\r\nreturn<\/span> 0<\/span>;\r\n}<\/pre>\n","protected":false},"excerpt":{"rendered":"
\u75c5\u6bd2 Time Limit:\u00a0\u00a01000ms,\u00a0\u00a0Special Time Limit:\u00a02500ms,\u00a0\u00a0M … Read more<\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[],"tags":[],"_links":{"self":[{"href":"https:\/\/wx.wosign.com\/index.php?rest_route=\/wp\/v2\/posts\/1213"}],"collection":[{"href":"https:\/\/wx.wosign.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wx.wosign.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wx.wosign.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/wx.wosign.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1213"}],"version-history":[{"count":1,"href":"https:\/\/wx.wosign.com\/index.php?rest_route=\/wp\/v2\/posts\/1213\/revisions"}],"predecessor-version":[{"id":1214,"href":"https:\/\/wx.wosign.com\/index.php?rest_route=\/wp\/v2\/posts\/1213\/revisions\/1214"}],"wp:attachment":[{"href":"https:\/\/wx.wosign.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1213"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wx.wosign.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1213"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wx.wosign.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1213"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}