{"id":271,"date":"2021-09-06T15:29:10","date_gmt":"2021-09-06T07:29:10","guid":{"rendered":"https:\/\/aisumura.net\/blog\/?p=271"},"modified":"2021-09-20T23:23:58","modified_gmt":"2021-09-20T15:23:58","slug":"uva12218-an-industrial-spy","status":"publish","type":"post","link":"https:\/\/aisumura.net\/blog\/2021\/09\/06\/uva12218-an-industrial-spy\/","title":{"rendered":"[UVA]12218 An Industrial Spy"},"content":{"rendered":"\n<p style=\"font-size:22px\">\u672c\u4eba\u65bc\u8a72blog\u7684\u5168\u90e8\u6587\u7ae0\u8f49\u79fb\u81f3<a href=\"https:\/\/blog.kkwtech.com\/uva\/11536-smallest-sub-array\"><a href=\"https:\/\/blog.kkwtech.com\/uva\/12218-an-industrial-spy\">[UVA] 12218 An Industrial Spy &#8211; KKWBlog (kkwtech.com)<\/a><\/a>\u8a72\u7db2\u57df\u4e0b\uff0c\u5176\u5f8c\u6b64\u8655\u4e0d\u9032\u884c\u66f4\u65b0\uff0c\u4e00\u5f8b\u65bc\u65b0\u7ad9\u9ede\u66f4\u65b0\u3002<\/p>\n\n\n\n<p><a href=\"https:\/\/zerojudge.tw\/ShowProblem?problemid=f711\">f711. 12218 &#8211; An Industrial Spy &#8211; \u9ad8\u4e2d\u751f\u7a0b\u5f0f\u89e3\u984c\u7cfb\u7d71 (zerojudge.tw)<\/a><br>\u984c\u76ee\u91cd\u9ede:<br>\u7d66N\u500b\u6578\u5b57\u5f9e\u4e2d\u53d6K(K&lt;=N)\u500b\u6392\u5217\u4e26\u4e14\u7b97\u51fa\u6240\u6709\u6392\u5217\u6a39\u7684\u8cea\u6578\u7e3d\u548c\u3002<\/p>\n\n\n\n<p>\u89e3\u984c\u601d\u8def:<br>\u57fa\u672c\u4e0a\u4e0d\u96e3\u5c31\u662f\u4e00\u9053DP\u984c\uff0c\u53ea\u8981\u6703\u7d44\u5408\u3001\u6392\u5217\u3001\u8cea\u6578\u6aa2\u6e2c\u5c31\u80fd\u89e3\u51fa\u8a72\u984c\uff0c<br>\u4e0d\u904e\u770b\u4e86\u4e00\u4e0b\u5b98\u65b9\u7b54\u6848\uff0c\u679c\u7136\u9084\u662f\u5b58\u5728\u66f4\u5feb\u7684\u505a\u6cd5\u7684\u3002<br><br>\u9a57\u8b49\u8cea\u6578\u7684\u65b9\u5f0f:<br>\u6709\u5f88\u591a\u7a2e\u4f5c\u6cd5\u6211\u662f\u9078\u64c7Optimized&nbsp;School&nbsp;Method\uff0c\u8a72\u4f5c\u6cd5\u7c21\u55ae\u8aaa\u660e:\u5f9e(5,7)\u958b\u59cb\u4e0b\u4e00\u500b\u53ef\u80fd\u8cea\u6578\u5c0d\u70ba(5+6.5+6+2)\uff0c\u4e5f\u5c31\u662f(6n + 5, 6n + 7),n &gt;= 0\uff0c\u56e0\u6b64\u53ef\u4ee5\u7565\u904e\u5927\u90e8\u5206\u7684\u548c\u6578\u3002<br><br>\u7d44\u5408:<br>\u4f7f\u7528mask\u53ef\u4ee5\u53d6\u5f97\u6240\u6709\u53ef\u80fd\u7684\u7d44\u5408\u89e3\uff0c\u4e26\u4e14\u6642\u9593\u8907\u96dc\u5ea6\u53ea\u97002^(n.len())<br>ex: n = 123, mask = 2^0 = 001,\u5f97\u52303\u4e26\u4e14001 += 1 =&gt; 010<br>     mask = 010,\u5f97\u52302<br>\u4f9d\u6b64\u985e\u63a8\u53ef\u4ee5\u5f97\u51fa\u6240\u6709\u7684\u7d44\u5408<br><br>\u6392\u5217:<br>\u4f7f\u7528c++\u5167\u5efa\u7684next_permutaion\u5373\u53ef\u5f97\u5230\u6240\u6709\u6392\u5217\uff0c\u4f7f\u7528\u8a72\u65b9\u6cd5\u5f97\u6ce8\u610f\u539f\u5b57\u4e32\u9700\u5148\u6392\u5217<\/p>\n\n\n\n<pre title=\"\u7a0b\u5f0f\u78bc\" class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">#include&nbsp;&lt;iostream&gt;\n#include&nbsp;&lt;algorithm&gt;\n#include&nbsp;&lt;vector&gt;\n#include&nbsp;&lt;set&gt;\nusing&nbsp;namespace&nbsp;std;\n\/\/\u5224\u65b7\u8cea\u6578&nbsp;By&nbsp;Optimized&nbsp;School&nbsp;Method\nbool&nbsp;isprime&nbsp;(int&nbsp;number)&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;if(number&nbsp;&lt;=&nbsp;1)&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;false;\n&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;if(number&nbsp;&lt;=&nbsp;3)&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;true;\n&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;if(number&nbsp;%&nbsp;2&nbsp;==&nbsp;0&nbsp;||&nbsp;number&nbsp;%&nbsp;3&nbsp;==&nbsp;0)&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;false;\n&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;for(int&nbsp;i&nbsp;=&nbsp;5;&nbsp;i&nbsp;*&nbsp;i&nbsp;&lt;=&nbsp;number;&nbsp;i&nbsp;+=&nbsp;6)&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(number&nbsp;%&nbsp;i&nbsp;==&nbsp;0&nbsp;||&nbsp;number&nbsp;%&nbsp;(i&nbsp;+&nbsp;2)&nbsp;==&nbsp;0)&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;false;\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;true;\n}\n\/\/\u540c\u6642\u7d44\u5408\u53ca\u6392\u5217\u4e26\u78ba\u8a8d\u662f\u5426\u70ba\u8cea\u6578\nint&nbsp;CombPermThenCountPrime&nbsp;(string&nbsp;input)&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;set&nbsp;&lt;int&gt;&nbsp;res;\/\/set\u5b58\u653e\u89e3\u53ef\u4ee5\u907f\u514d\u91cd\u8907\n&nbsp;&nbsp;&nbsp;&nbsp;for(int&nbsp;i&nbsp;=&nbsp;1;&nbsp;i&nbsp;&lt;&nbsp;(1&nbsp;&lt;&lt;&nbsp;input.size());&nbsp;i++)&nbsp;{\/\/\u5efa\u7acbmask&nbsp;i\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;string&nbsp;tmp&nbsp;=&nbsp;\"\";\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(int&nbsp;j&nbsp;=&nbsp;0;&nbsp;j&nbsp;&lt;&nbsp;input.size();&nbsp;j++)&nbsp;{\/\/mask\u5f97\u51fa\u7d44\u5408\u7d50\u679c\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(i&nbsp;&amp;&nbsp;(1&nbsp;&lt;&lt;&nbsp;j))&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;tmp&nbsp;+=&nbsp;input[j];\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;do&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(isprime(stoi(tmp))&nbsp;==&nbsp;true)&nbsp;{\/\/\u9a57\u8b49\u8cea\u6578\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res.insert(stoi(tmp));\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}while(next_permutation(tmp.begin(),tmp.end()));\n&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;res.size();\n}\nint&nbsp;main&nbsp;()&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;n&nbsp;=&nbsp;0;\n&nbsp;&nbsp;&nbsp;&nbsp;cin&nbsp;&gt;&gt;&nbsp;n;\n&nbsp;&nbsp;&nbsp;&nbsp;string&nbsp;input;\n&nbsp;&nbsp;&nbsp;&nbsp;while(n--)&nbsp;{\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cin&nbsp;&gt;&gt;&nbsp;input;\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sort(input.begin(),input.end());\n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cout&nbsp;&lt;&lt;&nbsp;CombPermThenCountPrime(input)&nbsp;&lt;&lt;&nbsp;endl;\n&nbsp;&nbsp;&nbsp;&nbsp;}\n&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0;\n}<\/code><\/pre>\n\n\n\n<p>\u6642\u9593\u8907\u96dc\u5ea6:<br>\u5c0d\u65bc\u4e00\u8f38\u5165\u53e6N\u70ba\u8a72\u8f38\u5165\u9577\u5ea6<br>sort() * CombPermThenCountPrime()<br>= N*log<sub>2<\/sub>(N) * { 2^N * ( N + N! * sqrt(N) ) }<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u672c\u4eba\u65bc\u8a72blog\u7684\u5168\u90e8\u6587\u7ae0\u8f49\u79fb\u81f3[UVA] 12218 An Industrial Spy &#8211; K [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[25],"tags":[26],"_links":{"self":[{"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/posts\/271"}],"collection":[{"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/comments?post=271"}],"version-history":[{"count":4,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/posts\/271\/revisions"}],"predecessor-version":[{"id":342,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/posts\/271\/revisions\/342"}],"wp:attachment":[{"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/media?parent=271"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/categories?post=271"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/aisumura.net\/blog\/wp-json\/wp\/v2\/tags?post=271"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}