{"id":207,"date":"2010-04-03T14:06:00","date_gmt":"2010-04-03T06:06:00","guid":{"rendered":"http:\/\/localhost\/?p=207"},"modified":"2010-04-03T14:06:00","modified_gmt":"2010-04-03T06:06:00","slug":"haoi2008_toy_named","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=207","title":{"rendered":"[HAOI2008]\u73a9\u5177\u53d6\u540d"},"content":{"rendered":"\n

[HAOI2008]\u73a9\u5177\u53d6\u540d<\/p>\n

Time Limit:10000MS  Memory Limit:165536K
Total Submit:45 Accepted:34
Case Time Limit:1000MS<\/p>\n

Description <\/strong><\/p>\n

\u67d0\u4eba\u6709\u4e00\u5957\u73a9\u5177\uff0c\u5e76\u60f3\u6cd5\u7ed9\u73a9\u5177\u547d\u540d\u3002\u9996\u5148\u4ed6\u9009\u62e9WING\u56db\u4e2a\u5b57\u6bcd\u4e2d\u7684\u4efb\u610f\u4e00\u4e2a\u5b57\u6bcd\u4f5c\u4e3a\u73a9\u5177\u7684\u57fa\u672c\u540d\u5b57\u3002\u7136\u540e\u4ed6\u4f1a\u6839\u636e\u81ea\u5df1\u7684\u559c\u597d\uff0c\u5c06\u540d\u5b57\u4e2d\u4efb\u610f\u4e00\u4e2a \u5b57\u6bcd\u7528\u201cWING\u201d\u4e2d\u4efb\u610f\u4e24\u4e2a\u5b57\u6bcd\u4ee3\u66ff\uff0c\u4f7f\u5f97\u81ea\u5df1\u7684\u540d\u5b57\u80fd\u591f\u6269\u5145\u5f97\u5f88\u957f\u3002
\u73b0\u5728\uff0c\u4ed6\u60f3\u8bf7\u4f60\u731c\u731c\u67d0\u4e00\u4e2a\u5f88\u957f\u7684\u540d\u5b57\uff0c\u6700\u521d\u53ef\u80fd\u662f\u7531\u54ea\u51e0\u4e2a\u5b57\u6bcd\u53d8\u5f62\u8fc7\u6765\u7684\u3002 <\/p>\n

Input <\/strong><\/p>\n

\u7b2c\u4e00\u884c\u56db\u4e2a\u6574\u6570W\u3001I\u3001N\u3001G\u3002\u8868\u793a\u6bcf\u4e00\u4e2a\u5b57\u6bcd\u80fd\u7531\u51e0\u79cd\u4e24\u4e2a\u5b57\u6bcd\u6240\u66ff\u4ee3\u3002
\u63a5\u4e0b\u6765W\u884c\uff0c\u6bcf\u884c\u4e24\u4e2a\u5b57\u6bcd,\u8868\u793aW\u53ef\u4ee5\u7528\u8fd9\u4e24\u4e2a\u5b57\u6bcd\u66ff\u4ee3\u3002
\u63a5\u4e0b\u6765I\u884c\uff0c\u6bcf\u884c\u4e24\u4e2a\u5b57\u6bcd,\u8868\u793aI\u53ef\u4ee5\u7528\u8fd9\u4e24\u4e2a\u5b57\u6bcd\u66ff\u4ee3\u3002
\u63a5\u4e0b\u6765N\u884c\uff0c\u6bcf\u884c\u4e24\u4e2a\u5b57\u6bcd,\u8868\u793aN\u53ef\u4ee5\u7528\u8fd9\u4e24\u4e2a\u5b57\u6bcd\u66ff\u4ee3\u3002
\u63a5\u4e0b\u6765G\u884c\uff0c\u6bcf\u884c\u4e24\u4e2a\u5b57\u6bcd,\u8868\u793aG\u53ef\u4ee5\u7528\u8fd9\u4e24\u4e2a\u5b57\u6bcd\u66ff\u4ee3\u3002
\u6700\u540e\u4e00\u884c\u4e00\u4e2a\u957f\u5ea6\u4e0d\u8d85\u8fc7Len\u7684\u5b57\u7b26\u4e32\u3002\u8868\u793a\u8fd9\u4e2a\u73a9\u5177\u7684\u540d\u5b57\u3002 <\/p>\n

Output <\/strong><\/p>\n

\u4e00\u884c\u5b57\u7b26\u4e32\uff0c\u8be5\u540d\u5b57\u53ef\u80fd\u7531\u54ea\u4e9b\u5b57\u6bcd\u53d8\u5f62\u800c\u5f97\u5230\u3002\uff08\u6309\u7167WING\u7684\u987a\u5e8f\u8f93\u51fa\uff09
\u5982\u679c\u7ed9\u7684\u540d\u5b57\u4e0d\u80fd\u7531\u4efb\u4f55\u4e00\u4e2a\u5b57\u6bcd\u53d8\u5f62\u800c\u5f97\u5230\u5219\u8f93\u51fa\u201cThe name is wrong!\u201d <\/p>\n

Sample Input <\/strong><\/p>\n

1 1 1 1
II
WW
WW
IG
IIII<\/p>\n

Sample Output <\/strong><\/p>\n

IN<\/p>\n

Hint <\/strong><\/p>\n

W\u53ef\u4ee5\u53d8\u6210II\u6240\u4ee5IIII\u53ef\u4ee5\u7f29\u6210WW
IN\u5747\u80fd\u53d8\u6210WW\u6240\u4ee5WW\u53c8\u53ef\u4ee5\u7f29\u6210I\u6216\u8005N
\u6240\u4ee5\u6700\u7ec8\u7b54\u6848\u5e94\u8be5\u6309\u7167\u201cWING\u201d\u7684\u987a\u5e8f\u8f93\u51faIN <\/p>\n

[\u6570\u636e\u8303\u56f4]
30%\u6570\u636e\u6ee1\u8db3Len<=20\uff0cW\u3001I\u3001N\u3001G<=6
100%\u6570\u636e\u6ee1\u8db3Len<=200\uff0cW\u3001I\u3001N\u3001G<=16 <\/p>\n

Source
<\/strong>\u6c34\u9898\u554a\u3002\u3002\u76f4\u63a5Dp\u5c31\u53ef\u4ee5\u4e86\uff0cCheck\uff08l\uff0cr\uff0ca\uff09\u8868\u793a\u7b2cl\u4e2a\u5230\u7b2cr\u80fd\u5426\u7528\u7b2ca\u4e2a\u5b57\u6bcd\u6269\u5145\u51fa\u6765
Code\uff1a
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxl=200+1;
int Map[256],D[4],L[4][16],R[4][16];
char Name[10]="WING";
char str[maxl];
bool S[maxl][maxl][4]={0};
bool Dp[maxl][maxl][4];
bool Check(int l,int r,int a)
{
bool&x=Dp[l][r][a];
if(S[l][r][a]) return x;
S[l][r][a]=true;
if(l==r) return x=(str[l]==Name[a]);
for(int k=l;k<r;k++)
rep(i,D[a]) if(Check(l,k,L[a][i])&&Check(k+1,r,R[a][i])) return x=true;
return x=false;
}
int main()
{
\/\/freopen("in","r",stdin);
Map[‘W’]=0;Map[‘I’]=1;Map[‘N’]=2;Map[‘G’]=3;
rep(i,4)cin>>D[i];char l,r;
rep(i,4)rep(j,D[i]) cin>>l>>r,L[i][j]=Map[l],R[i][j]=Map[r];
cin>>str;int len=strlen(str);bool c=false;
rep(i,4)if(Check(0,len-1,i))cout<<Name[i],c=true;
if(!c)cout<<"The name is wrong!";
}<\/p>\n","protected":false},"excerpt":{"rendered":"

[HAOI2008]\u73a9\u5177\u53d6\u540d Time Limit:10000MS  Memory Limit:165536KTotal Submit:45 Accepted:34 Case Time Limit:1000MS Description \u67d0\u4eba\u6709\u4e00\u5957\u73a9\u5177\uff0c\u5e76\u60f3\u6cd5\u7ed9\u73a9\u5177\u547d\u540d\u3002\u9996\u5148\u4ed6\u9009\u62e9WING\u56db\u4e2a\u5b57\u6bcd\u4e2d\u7684\u4efb\u610f\u4e00\u4e2a\u5b57\u6bcd\u4f5c\u4e3a\u73a9\u5177\u7684\u57fa\u672c\u540d\u5b57\u3002\u7136\u540e\u4ed6\u4f1a\u6839\u636e\u81ea\u5df1\u7684\u559c\u597d\uff0c\u5c06\u540d\u5b57\u4e2d\u4efb\u610f\u4e00\u4e2a \u5b57\u6bcd\u7528\u201cWING\u201d\u4e2d\u4efb\u610f\u4e24\u4e2a\u5b57\u6bcd\u4ee3\u66ff\uff0c\u4f7f\u5f97\u81ea\u5df1\u7684\u540d\u5b57\u80fd\u591f\u6269\u5145\u5f97\u5f88\u957f\u3002 \u73b0\u5728\uff0c\u4ed6\u60f3\u8bf7\u4f60\u731c\u731c\u67d0\u4e00\u4e2a\u5f88\u957f\u7684\u540d\u5b57\uff0c\u6700\u521d\u53ef\u80fd\u662f\u7531\u54ea\u51e0\u4e2a\u5b57\u6bcd\u53d8\u5f62\u8fc7\u6765\u7684\u3002 Input \u7b2c\u4e00\u884c\u56db\u4e2a\u6574\u6570W\u3001I\u3001N\u3001G\u3002\u8868\u793a\u6bcf\u4e00\u4e2a\u5b57\u6bcd\u80fd\u7531\u51e0\u79cd\u4e24\u4e2a\u5b57\u6bcd\u6240\u66ff\u4ee3\u3002 \u63a5\u4e0b\u6765W\u884c\uff0c\u6bcf\u884c\u4e24\u4e2a\u5b57\u6bcd,\u8868\u793aW\u53ef\u4ee5\u7528\u8fd9\u4e24\u4e2a\u5b57\u6bcd\u66ff\u4ee3\u3002 \u63a5\u4e0b\u6765I\u884c\uff0c\u6bcf\u884c\u4e24\u4e2a\u5b57\u6bcd,\u8868\u793aI\u53ef\u4ee5\u7528\u8fd9\u4e24\u4e2a\u5b57\u6bcd\u66ff\u4ee3\u3002 \u63a5\u4e0b\u6765N\u884c\uff0c\u6bcf\u884c\u4e24\u4e2a\u5b57\u6bcd,\u8868\u793aN\u53ef\u4ee5\u7528\u8fd9\u4e24\u4e2a\u5b57\u6bcd\u66ff\u4ee3\u3002 \u63a5\u4e0b\u6765G\u884c\uff0c\u6bcf\u884c\u4e24\u4e2a\u5b57\u6bcd,\u8868\u793aG\u53ef\u4ee5\u7528\u8fd9\u4e24\u4e2a\u5b57\u6bcd\u66ff\u4ee3\u3002 \u6700\u540e\u4e00\u884c\u4e00\u4e2a\u957f\u5ea6\u4e0d\u8d85\u8fc7Len\u7684\u5b57\u7b26\u4e32\u3002\u8868\u793a\u8fd9\u4e2a\u73a9\u5177\u7684\u540d\u5b57\u3002 Output \u4e00\u884c\u5b57\u7b26\u4e32\uff0c\u8be5\u540d\u5b57\u53ef\u80fd\u7531\u54ea\u4e9b\u5b57\u6bcd\u53d8\u5f62\u800c\u5f97\u5230\u3002\uff08\u6309\u7167WING\u7684\u987a\u5e8f\u8f93\u51fa\uff09 \u5982\u679c\u7ed9\u7684\u540d\u5b57\u4e0d\u80fd\u7531\u4efb\u4f55\u4e00\u4e2a\u5b57\u6bcd\u53d8\u5f62\u800c\u5f97\u5230\u5219\u8f93\u51fa\u201cThe name is wrong!\u201d Sample Input 1 1 1 1IIWWWWIGIIII Sample Output IN Hint W\u53ef\u4ee5\u53d8\u6210II\u6240\u4ee5IIII\u53ef\u4ee5\u7f29\u6210WW IN\u5747\u80fd\u53d8\u6210WW\u6240\u4ee5WW\u53c8\u53ef\u4ee5\u7f29\u6210I\u6216\u8005N \u6240\u4ee5\u6700\u7ec8\u7b54\u6848\u5e94\u8be5\u6309\u7167\u201cWING\u201d\u7684\u987a\u5e8f\u8f93\u51faIN [\u6570\u636e\u8303\u56f4] 30%\u6570\u636e\u6ee1\u8db3Len<=20\uff0cW\u3001I\u3001N\u3001G<=6 100%\u6570\u636e\u6ee1\u8db3Len<=200\uff0cW\u3001I\u3001N\u3001G<=16 Source\u6c34\u9898\u554a\u3002\u3002\u76f4\u63a5Dp\u5c31\u53ef\u4ee5\u4e86\uff0cCheck\uff08l\uff0cr\uff0ca\uff09\u8868\u793a\u7b2cl\u4e2a\u5230\u7b2cr\u80fd\u5426\u7528\u7b2ca\u4e2a\u5b57\u6bcd\u6269\u5145\u51fa\u6765Code\uff1a#include<cstdio>#include<iostream>#include<algorithm>#include<string>#include<vector>#include<cstring>#define rep(i,n) for(int i=0;i<n;i++)#define pb push_backusing namespace std;const int inf=~0U>>1,maxl=200+1;int Map[256],D[4],L[4][16],R[4][16];char Name[10]="WING";char […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/207"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=207"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/207\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=207"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=207"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=207"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}