{"id":108,"date":"2018-07-28T10:39:14","date_gmt":"2018-07-28T10:39:14","guid":{"rendered":"http:\/\/nocriz.com\/?p=108"},"modified":"2021-09-08T20:20:07","modified_gmt":"2021-09-08T12:20:07","slug":"cf1009g-allowed-letters-%e9%a2%98%e8%a7%a3","status":"publish","type":"post","link":"https:\/\/nocriz.com\/?p=108","title":{"rendered":"CF1009G Allowed Letters \u9898\u89e3"},"content":{"rendered":"

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

\u8fd9\u4e00\u9053\u9898\u9898\u9762\u5927\u6982\u662f\u6709\u4e00\u4e2a\u5305\u542ba,b,c,d,e,f\u516d\u79cd\u5b57\u7b26\u7684\u5b57\u7b26\u4e32\uff08\u957f\u5ea6\u4e3an\uff09\uff0c\u8981\u6c42\u5b83\u7684\u4e00\u4e2a\u91cd\u65b0\u6392\u5217\u7684\u5b57\u7b26\u4e32\uff0c\u5176\u4e2d\u6709m\u4f4d\u53ef\u80fd\u6709\u5bf9\u586b\u5199\u7684\u5b57\u6bcd\u7684\u9650\u5236\u3002\u5176\u4e2d\u4fdd\u8bc1<\/p>\n

  <\/span>   <\/span>\"\[n,m\leq10^5\]\"<\/p>\n

\u8981\u6c42\u8f93\u51fa\u5b57\u5178\u5e8f\u6700\u5c0f\u7684\u53ef\u80fd\u89e3\uff0c\u5982\u679c\u65e0\u89e3\u8f93\u51fa”Impossible”\u3002<\/p>\n

<\/p>\n

\u5f88\u5bb9\u6613\u60f3\u5230\u7684\u57fa\u672c\u601d\u8def\u5c31\u662f\uff0c\u5bf9\u4e8e\u6bcf\u4e00\u4f4d\u5b57\u6bcd\uff0c\u4ecea\u5230f\u679a\u4e3e\u662f\u5426\u80fd\u591f\u586b\u5728\u8fd9\u4e00\u4f4d\uff0c\u5982\u679c\u80fd\u591f\u586b\uff0c\u5c31\u586b\u5b57\u6bcd\u3002\u5982\u679c\u679a\u4e3e\u5230f\uff0c\u7136\u800c\u4ecd\u7136\u6ca1\u80fd\u627e\u5230\u53ef\u80fd\u7684\u89e3\uff0c\u5219\u8f93\u51fa\u65e0\u89e3\u3002\u8fd9\u6837\u5b57\u5178\u5e8f\u5c31\u4f1a\u6700\u5c0f\u3002<\/p>\n

\u4e8e\u662f\u95ee\u9898\u7684\u5173\u952e\u4fbf\u8f6c\u5316\u4e3a\u5982\u4f55\u5224\u65ad\u5bf9\u4e8e\u67d0\u4e00\u4f4d\u586b\u5199\u67d0\u4e2a\u5b57\u6bcd\u4e4b\u540e\uff0c\u5269\u4e0b\u7684\u4f4d\u80fd\u4e0d\u80fd\u5168\u90e8\u6210\u529f\u627e\u5230\u5339\u914d\uff0c\u800c\u8fd9\u4e2a\u95ee\u9898\u53c8\u80fd\u591f\u8f6c\u5316\u4e3a\u56fe\u7684\u5339\u914d\u3002<\/p>\n

\u8f6c\u5316\u4e3a\u56fe\u7684\u5339\u914d\u4e4b\u540e\uff0c\u95ee\u9898\u5c31\u80fd\u591f\u4f7f\u7528\u970d\u5c14\u5b9a\u7406\u6765\u89e3\u51b3\u4e86\u3002<\/p>\n

\u590d\u4e60\u970d\u5c14\u5b9a\u7406\uff1a<\/p>\n

\u4e8c\u90e8\u56feG\u4e2d\u7684\u4e24\u90e8\u5206\u9876\u70b9\u7ec4\u6210\u7684\u96c6\u5408\u5206\u522b\u4e3a<\/p>\n

  <\/span>   <\/span>\"\[X = \{x_1 , x_2 ,...,x_m\}, Y = \{y_1 ,y_2 , ... , y_n \}\]\"<\/p>\n

,G\u4e2d\u6709\u4e00\u7ec4\u65e0\u516c\u5171\u70b9\u7684\u8fb9\uff0c\u4e00\u7aef\u6070\u597d\u4e3a\u7ec4\u6210X\u7684\u70b9\u7684\u5145\u5206\u5fc5\u8981\u6761\u4ef6\u662f\uff1aX\u4e2d\u7684\u4efb\u610fk\u4e2a\u70b9\u81f3\u5c11\u4e0eY\u4e2d\u7684k\u4e2a\u70b9\u76f8\u90bb\u3002(1\u2264k\u2264m)\u3002<\/p>\n

\u800c\u5728\u672c\u9898\u4e2d\uff0c\u5219\u662f\u4ee3\u8868\u5728\u5982\u540e\u9762\u7684\u5c1a\u672a\u586b\u5145\u7684\u5b57\u6bcd\u4f4d\u4e2d\u7684\u4efb\u610fk\u4e2a\u90fd\u80fd\u591f\u627e\u5230\u81f3\u5c11k\u4e2a\u80fd\u591f\u586b\u5199\u7684\u539f\u5b57\u7b26\u4e32\u4e2d\u5c1a\u672a\u4f7f\u7528\u7684\u5b57\u7b26\uff0c\u5c31\u4ee3\u8868\u540e\u9762\u5c1a\u672a\u586b\u5199\u7684\u5b57\u7b26\u4e00\u5b9a\u6709\u4e00\u79cd\u65b9\u6cd5\u80fd\u591f\u586b\u5199\u3002<\/strong><\/p>\n

\u6700\u7ec8\u4e0a\u4ee3\u7801\u3002<\/p>\n

\/\/ Author : WangZhikun\n\/\/ Date   : 2018.07.27\n\n#include <cstdio>\n#include <vector>\n#include <cstring>\n#include <iostream>\n#include <algorithm>\n\nusing namespace std;\n\nint n,m,msk[100020],p,fn[80] = {0},gn[80] = {0},ccnt[10] = {0};\nchar s[100020],cm[10],ans[100020];\n\nint main() {\n\tios::sync_with_stdio(false);\n\tcin.tie(0);\n\tfor(int i=0;i<100010;i++)msk[i] = 63;\n\tcin>>s;\n\tn = (int)strlen(s);\n\tcin>>m;\n\t\n\tfor(int i=0;i<m;i++){\n\t\tcin>>p>>cm;\n\t\tp-=1;\n\t\tmsk[p] = 0;\n\t\tfor(int i=0;i<strlen(cm);i++) \n\t\t\tif(cm[i]>='a' && cm[i]<='f')\n\t\t\t\tmsk[p]+=1<<(cm[i]-'a');\n\t}\n\tfor(int i=0;i<n;i++){\n\t\tfn[msk[i]]++;\n\t\tccnt[s[i]-'a']+=1;\n\t}\n\tfor(int i=0;i<64;i++){\n\t\tfor(int j=0;j<64;j++)if((i&j) == j)gn[i]+=fn[j];\n\t}\n\tfor(int po=0;po<n;po++){\n\t\tans[po] = 'u';\n\t\tfor(int i=0;i<64;i++)if((i&msk[po]) == msk[po])gn[i]-=1;\n\t\tfor(int c = 0;c<6;c++){\n\t\t\tif((msk[po] & (1<<c)) == 0)continue;\n\t\t\tccnt[c]-=1;\n\t\t\tint co = 1,ccn = 0;\n\t\t\tfor(int i=0;i<64;i++){\n\t\t\t\tccn = 0;\n\t\t\t\tfor(int j=0;j<6;j++)if(i&(1<<j))ccn+=ccnt[j];\n\t\t\t\tif(ccn<gn[i]){\n\t\t\t\t\tco = 0;\n\t\t\t\t\tbreak;\n\t\t\t\t}\n\t\t\t}\n\t\t\tif(co){\n\t\t\t\tans[po] = 'a'+c;\n\t\t\t\tbreak;\n\t\t\t}\n\t\t\telse{\n\t\t\t\tccnt[c]+=1;\n\t\t\t}\n\t\t}\n\t\tif(ans[po] == 'u'){\n\t\t\tcout<<\"Impossible\"<<endl;\n\t\t\treturn 0;\n\t\t}\n\t}\n\tcout<<ans<<endl;\n\treturn 0;\n}<\/pre>\n
 <\/p>\n
[latex]<\/p>\n ","protected":false},"excerpt":{"rendered":"
\u9898\u76ee\u94fe\u63a5 \u8fd9\u4e00\u9053\u9898\u9898\u9762\u5927\u6982\u662f\u6709\u4e00\u4e2a\u5305\u542ba,b,c,d,e,f\u516d\u79cd\u5b57\u7b26\u7684\u5b57\u7b26\u4e32\uff08\u957f\u5ea6\u4e3an\uff09\uff0c\u8981\u6c42\u5b83\u7684\u4e00\u4e2a\u91cd\u65b0\u6392\u5217 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2,5],"tags":[],"_links":{"self":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/108"}],"collection":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=108"}],"version-history":[{"count":1,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/108\/revisions"}],"predecessor-version":[{"id":771,"href":"https:\/\/nocriz.com\/index.php?rest_route=\/wp\/v2\/posts\/108\/revisions\/771"}],"wp:attachment":[{"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=108"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=108"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nocriz.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=108"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}