{"id":399,"date":"2018-11-10T21:54:10","date_gmt":"2018-11-10T13:54:10","guid":{"rendered":"http:\/\/SmokeyDays.top\/wordpress\/?p=399"},"modified":"2018-11-10T21:54:10","modified_gmt":"2018-11-10T13:54:10","slug":"noip2018-%e8%b4%a7%e5%b8%81%e7%b3%bb%e7%bb%9f","status":"publish","type":"post","link":"http:\/\/SmokeyDays.top\/wordpress\/2018\/11\/10\/noip2018-%e8%b4%a7%e5%b8%81%e7%b3%bb%e7%bb%9f\/","title":{"rendered":"NOIP2018 \u8d27\u5e01\u7cfb\u7edf"},"content":{"rendered":"

\u4e00\u9053\u770b\u8d77\u6765\u50cf\u6570\u8bba\u9898\u7684\u5b8c\u5168\u80cc\u5305\u95ee\u9898\u3002
\n\u5e78\u597d\u6211\u524d\u4e00\u5929\u6ca1\u6709\u4ed4\u7ec6\u770b\u6570\u8bba\uff0c\u4f7f\u5f97\u6211\u60f3\u7684\u662f\u5199\u66b4\u529b…\u8981\u4e0d\u7136\u6211\u53ef\u80fd\u771f\u7684\u4f1a\u63a8\u4e00\u4e2a\u5c0f\u65f6\u7684\\(EXGCD\\)\u6216\\(CRT\\)\u6216\u8005\u9ad8\u65af\u6d88\u5143\u4e4b\u7c7b\u7684\u4e1c\u897f\u3002
\n\u603b\u4e4b\u662f\u5c0f\u51ef\u7684\u7591\u60d1\u8ff7\u60d1\u4e86\u6211\uff0c\u4ee5\u4e3a\u662f\u4e00\u9053\u6570\u8bba\u9898\uff0c\u6240\u4ee5\u5230\u6700\u540e\u6211\u90fd\u4ee5\u4e3a\u81ea\u5df1\u5199\u7684\u662f\u66b4\u529b\u3002
\n\u7ed3\u679c\u53d1\u73b0\u5176\u5b9e\u662f\u6b63\u89e3\u601d\u8def\u7684\uff0c\u5df2\u7ecf\u5199\u5230\u4e86\u6b63\u89e3\u7684\u5012\u6570\u7b2c\u4e8c\u6b65\uff0c\u968f\u4fbf\u4e00\u4f18\u5316\u5c31\u901a\u8fc7\u4e86\u3002
\n\u4f46\u662f\u59cb\u7ec8\u4ee5\u4e3a\u662f\u6253\u66b4\u529b\u3002
\n\u679c\u7136\u8fd8\u662f\u592a\u83dc\u4e86\u3002
\n\u9898\u610f\u7b80\u8ff0\uff1a\u4f60\u6709\\(n\\)\u4e2a\u6b63\u6574\u6570\uff0c\u8981\u6c42\uff0c\u786e\u5b9a\u4e00\u4e2a\u6700\u5c0f\u7684\\(m\\)\uff0c\u4f7f\u5f97\u7528\\(m\\)\u79cd\u6b63\u6574\u6570\u6570\u80fd\u591f\u8868\u793a\u7684\u6570\u96c6\u4e0e\u9898\u76ee\u7ed9\u51fa\u6570\u80fd\u591f\u8868\u793a\u7684\u6570\u96c6\u7684\u5b8c\u5168\u4e00\u81f4\u3002
\n\u9996\u5148\u6211\u4eec\u8bc1\u660e\u4e00\u4e2a\u5b9a\u7406\uff1a\u7b54\u6848\u7684\\(m\\)\u4e2a\u6570\u4e00\u5b9a\u662f\u539f\u6709\u6570\u7684\u5b50\u96c6\u3002
\n\u4e0b\u9762\u6211\u4eec\u5206\u4e24\u7c7b\u8003\u8651\u8fd9\u4e2a\u95ee\u9898\u3002
\n\u5982\u679c\u65b0\u7684\u6570\u53ef\u4ee5\u88ab\u539f\u6709\u6570\u8868\u793a\uff0c\u90a3\u4e48\u663e\u7136\u5b83\u662f\u6ca1\u6709\u610f\u4e49\u7684\u3002
\n\u5982\u679c\u65b0\u7684\u6570\u4e0d\u80fd\u88ab\u539f\u6709\u6570\u8868\u793a\uff0c\u90a3\u4e48\u663e\u7136\u5b83\u662f\u4e0d\u5408\u6cd5\u7684\u3002
\n\u90a3\u4e48\u6211\u4eec\u53ea\u9700\u8981\u8003\u8651\u5220\u9664\u54ea\u4e9b\u6570\u5373\u53ef\u3002
\n\u6211\u4eec\u53d1\u73b0\uff0c\u4e00\u4e2a\u6570\u9700\u8981\u5220\u9664\uff0c\u5f53\u4e14\u4ec5\u5f53\u5b83\u53ef\u4ee5\u88ab\u5176\u4ed6\u6570\u8868\u8fbe\u51fa\u6765\u3002
\n\u53cd\u8bc1\u6cd5\uff1a\u5982\u679c\u5b83\u4e0d\u53ef\u88ab\u5176\u4ed6\u6570\u8868\u793a\u7684\u8bdd\uff0c\u90a3\u4e48\u5220\u9664\u5b83\u4ee5\u540e\u5b83\u5c31\u65e0\u6cd5\u8868\u793a\u51fa\u6765\u4e86\u3002
\n\u5e76\u4e14\uff0c\u6211\u4eec\u53ef\u4ee5\u53d1\u73b0\uff0c\u8fd9\u4e2a\u95ee\u9898\u6ee1\u8db3\u6700\u4f18\u5b50\u7ed3\u6784\uff1a\u5982\u679c\u4e00\u4e2a\u6570\u53ef\u4ee5\u88ab\u5f53\u524d\u7684\u7cfb\u7edf\u8868\u8fbe\u51fa\u6765\uff0c\u90a3\u4e48\u5220\u9664\u5f53\u524d\u7cfb\u7edf\u4e2d\u4efb\u610f\u4e00\u4e9b\u53ef\u4ee5\u88ab\u8868\u8fbe\u51fa\u6765\u7684\u6570\uff0c\u90fd\u4e0d\u4f1a\u5bfc\u81f4\u8fd9\u4e2a\u6570\u4e0d\u80fd\u88ab\u8868\u8fbe\u51fa\u6765\u3002
\n\u6545\u800c\uff0c\u5148\u5220\u54ea\u4e2a\u5176\u5b9e\u90fd\u4e0d\u5f71\u54cd\u7b54\u6848\u7684\u6b63\u786e\u6027\u3002
\n\u56e0\u6b64\u6211\u4eec\u53ef\u4ee5\u4ece\u5c0f\u5f80\u5927\u5220\uff08\u53ef\u80fd\u53ef\u4ee5\u8282\u7701\u65f6\u95f4\uff09
\n\u66b4\u529b\u5730\u8003\u8651\uff0c\u6211\u4eec\u9700\u8981\u679a\u4e3e\u503c\u57df\u5185\u6bcf\u4e00\u4e2a\u5df2\u7ecf\u53ef\u4ee5\u88ab\u8868\u8fbe\u51fa\u6765\u7684\u6570\uff0c\u7136\u540e\u5c06\u8fd9\u4e2a\u6570\u52a0\u4e0a\u5f53\u524d\u6570\u7684\u4efb\u610f\u500d\uff08\u503c\u57df\u8303\u56f4\u5185\uff09
\n\u8fd9\u4e48\u505a\u6700\u574f\u53ef\u80fd\u662f\\(O(T*n*a^2)\\)\u7684\u3002
\n\u8003\u8651\u4f18\u5316\u3002\u7528\u6b27\u62c9\u7b5b\u7684\u601d\u60f3\uff0c\u5bf9\u4e8e\u6bcf\u4e00\u4e2a\u6570\uff0c\u6211\u4eec\u53ea\u9700\u8981\u52a0\u4e0a\u5f53\u524d\u6570\u7684\u4e00\u500d\u5373\u53ef\u3002
\n\u56e0\u4e3a\uff0c\u5982\u679c\u52a0\u4e0a\u5f53\u524d\u6570\u7684\u4e24\u500d\u7684\u8bdd\uff0c\u5c31\u4f1a\u5728\u4e4b\u540e\u518d\u4e00\u6b21\u8bbf\u95ee\u5230\u8fd9\u4e2a\u6570\uff0c\u8fd9\u65f6\u5019\u5c31\u4ea7\u751f\u4e86\u8bbf\u95ee\u6b21\u6570\u4e0a\u7684\u6d6a\u8d39\u3002
\n\u8fd9\u6837\u505a\u662f\\(O(T*n*a)\\)\u3002
\n\u90a3\u5c31\u505a\u5b8c\u4e86\u3002<\/p>\n

#include<cstdio>\r\n#include<iostream>\r\n#include<algorithm> \r\n#include<cstring>\r\n\r\nint n,a[105];\r\nbool usf[25005];\r\nvoid init(){\r\n\tstd::memset(usf,0,sizeof(usf));\r\n\tscanf(\"%d\",&n);\r\n\tfor(int i=1;i<=n;++i){\r\n\t\tscanf(\"%d\",a+i);\r\n\t}\r\n\tif(n==1){\r\n\t\tputs(\"1\");\r\n\t\treturn;\r\n\t}\r\n\tstd::sort(a+1,a+1+n);\r\n\tint cnt=n;\r\n\tusf[0]=1;\r\n\tfor(int i=1;i*a[1]<=25000;++i){\r\n\t\tusf[i*a[1]]=1;\r\n\t}\r\n\tfor(int i=2;i<=n;++i){\r\n\t\tif(usf[a[i]]){\r\n\t\t\ta[i]=0;\r\n\t\t\t--cnt;\r\n\t\t}else{\r\n\t\t\tfor(int j=0;j+a[i]<=25000;++j){\r\n\t\t\t\tif(!usf[j]){\r\n\t\t\t\t\tcontinue;\r\n\t\t\t\t}else{\r\n\t\t\t\t\tusf[j+a[i]]=1;\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n\tprintf(\"%d\\n\",cnt);\r\n}\r\nint main(){\r\n\tint T;\r\n\tscanf(\"%d\",&T);\r\n\twhile(T--){\r\n\t\tinit();\r\n\t}\r\n\treturn 0;\r\n}<\/code><\/pre>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
\u4e00\u9053\u770b\u8d77\u6765\u50cf\u6570\u8bba\u9898\u7684\u5b8c\u5168\u80cc\u5305\u95ee\u9898\u3002 \u5e78\u597d\u6211\u524d\u4e00\u5929\u6ca1\u6709\u4ed4\u7ec6\u770b\u6570\u8bba\uff0c\u4f7f\u5f97\u6211\u60f3\u7684\u662f\u5199\u66b4\u529b…\u8981\u4e0d\u7136\u6211\u53ef\u80fd\u771f … <\/p>\n
\u7ee7\u7eed\u9605\u8bfb\u201cNOIP2018 \u8d27\u5e01\u7cfb\u7edf\u201d<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10,34,24,27,6,5],"tags":[],"_links":{"self":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/399"}],"collection":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/comments?post=399"}],"version-history":[{"count":1,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/399\/revisions"}],"predecessor-version":[{"id":400,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/posts\/399\/revisions\/400"}],"wp:attachment":[{"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/media?parent=399"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/categories?post=399"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/SmokeyDays.top\/wordpress\/wp-json\/wp\/v2\/tags?post=399"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}