{"id":32,"date":"2023-06-18T23:07:33","date_gmt":"2023-06-18T15:07:33","guid":{"rendered":"http:\/\/boyliang.com\/?p=32"},"modified":"2025-08-05T21:58:35","modified_gmt":"2025-08-05T13:58:35","slug":"%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84%ef%bc%88%e4%ba%8c%ef%bc%89","status":"publish","type":"post","link":"https:\/\/boyliang.com\/index.php\/2023\/06\/18\/%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84%ef%bc%88%e4%ba%8c%ef%bc%89\/","title":{"rendered":"\u6570\u636e\u7ed3\u6784\uff08\u4e8c\uff09"},"content":{"rendered":"\n

\u4e00\u3001Trie\u6811:<\/h3>\n\n\n\n

1.\u9ad8\u901f\u5b58\u50a8\u548c\u67e5\u8be2\u5b57\u7b26\u4e32\u96c6\u5408<\/h4>\n\n\n\n
#include<iosteam>\nusing namespace std;\nconst int N = 100010;\nint son[N][26],cnt[N],idx;\/\/\u4e0b\u8868\u662f0\u7684\u70b9\u65e2\u662f\u6839\u8282\u70b9\u53c8\u662f\u7a7a\u7ed3\u70b9\nchar str[N];\nvoid insert(char str[]){\n    int p=0;\/\/\u4ece\u6839\u8282\u70b9\u5f00\u59cb\u904d\u5386\n    for(int i=0;str[i];i++){\n        int u = str[i] - 'a';\n        if(!son[p][u])son[p][u] = ++idx;\n        p=son[p][u];\n    }\n    cnt[p]++;\n}\n\nint query(char str[]){\n    int p=0;\n    for(int i=0;str[i];i++){\n        int u=str[i]-'a';\n        if(!son[p][u])return 0;\n        p=son[p][u];\n    }\n    return cnt[p];\n}\nint main(){\n    int n;\n    scanf(\"%d\",&n);\n    while(n--){\n        char op[2];\n        scanf(\"%s%s\",op,str);\n        if(op[0]=='I')insert(str);\n        else printf(\"%d\\n\",query(str));\n    }\n    return 0;\n}<\/code><\/pre>\n\n\n\n
\u4e8c\u3001.\u5e76\u67e5\u96c6<\/h3>\n\n\n\n
1.\u5c06\u4e24\u4e2a\u96c6\u5408\u5408\u5e76<\/h4>\n\n\n\n
2.\u8be2\u95ee\u4e24\u4e2a\u5143\u7d20\u662f\u5426\u5728\u4e00\u4e2a\u96c6\u5408\u4e2d<\/h4>\n\n\n\n
\u57fa\u672c\u539f\u7406\uff1a\u6bcf\u4e00\u4e2a\u96c6\u5408\u7528\u4e00\u9897\u6811\u6765\u8868\u793a\u3002\u6811\u6839\u7684\u7f16\u53f7\u5c31\u662f\u6574\u4e2a\u96c6\u5408\u7684\u7f16\u53f7\u3002\u6bcf\u4e2a\u7ed3\u70b9\u5b58\u50a8\u5b83\u7684\u7236\u8282\u70b9\uff0cp[x]\u8868\u793ax\u7684\u7236\u8282\u70b9\u3002<\/p>\n\n\n\n
\u95ee\u98981\uff1a\u5982\u4f55\u5224\u65ad\u6811\u6839\uff1aif(p[x]==x)<\/p>\n\n\n\n
\u95ee\u98982\uff1a\u5982\u4f55\u6c42x\u7684\u96c6\u5408\u7f16\u53f7\uff1awhile(p[x]!=x)x=p[x];<\/p>\n\n\n\n
\u95ee\u98983\uff1a\u5982\u4f55\u5408\u5e76\u4e24\u4e2a\u96c6\u5408\uff1a px\u662fx\u7684\u96c6\u5408\u7f16\u53f7\uff0cpy\u662fy\u7684\u96c6\u5408\u7f16\u53f7\u3002 p[x]=y;<\/p>\n\n\n\n
#include<iostream>\nusing namespace std;\nconst int N = 100010;\nint n,m;\nint p[N];\n\nint find(int x){\/\/\u8fd4\u56dex\u7684\u7956\u5b97\u7ed3\u70b9+\u8def\u7ecf\u538b\u7f29\n    if(p[x]!=x)p[x]=find(p[x]);\n    return p[x];\n}\nint main(){\n    \n    scanf(\"%d%d\",&n,&m);\n    for(int i=0;i<m;i++){\n        p[i]=i;\n    }\n    while(m--){\n        char op[2];\n        int a,b;\n        scanf(\"%s%d%d\",op,&a,&b);\n        \n        if(op[0]=='M')p[find(a)==find(b)];\n        else{\n            if(find(a)==find(b))puts(\"Yes\");\n            else puts(\"No\");\n        }\n    }\n    return 0;\n}<\/code><\/pre>\n\n\n\n
#include<iostream>\nusing namespace std;\nconst int N = 100010;\nint p[N],size[N];\nint m,m;\nint find(int x){\n    while(p[x]\uff01=x)p[x]=find(p[x]);\n    return p[x];\n}\n\nint main(){\n    scanf(\"%d%d\",&n,&m);\n    for(int i = 0;i<m;i++){\n        p[i]=i;\n        size[i]=1;\n    }\n    while(m--){\n        char op[5];\n        int a,b;\n        scanf(\"%s\",op);\n        if(op[0]=='C'){\n            scanf(\"%d%d\",&a,&b);\n            if(find(a)==find(b))continue;\n            size[find(b)]+=size[find(a)];\n            p[find(b)]=find(b);\n        }else if(op[i]='Q1'){\n            scanf(\"%d%d\",&a,&b);\n            if(find(a)==find(b))puts(\"Yes\");\n            else puts(\"No\");\n        }else{\n            scanf(\"%d\",&a);\n            prinf(\"%d\\n\",size[find(a)]);\n        }\n    }\n    return 0;\n}<\/code><\/pre>\n\n\n\n
\u53d8\u578b\u9898\uff1a<\/p>\n","protected":false},"excerpt":{"rendered":"
\u4e00\u3001Trie\u6811: 1.\u9ad8\u901f\u5b58\u50a8\u548c\u67e5\u8be2\u5b57\u7b26\u4e32\u96c6\u5408 \u4e8c\u3001.\u5e76\u67e5\u96c6 1.\u5c06\u4e24\u4e2a\u96c6\u5408\u5408\u5e76 2.\u8be2\u95ee\u4e24\u4e2a\u5143\u7d20\u662f\u5426\u5728\u4e00\u4e2a\u96c6 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9],"tags":[],"class_list":["post-32","post","type-post","status-publish","format-standard","hentry","category-9"],"_links":{"self":[{"href":"https:\/\/boyliang.com\/index.php\/wp-json\/wp\/v2\/posts\/32","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/boyliang.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/boyliang.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/boyliang.com\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/boyliang.com\/index.php\/wp-json\/wp\/v2\/comments?post=32"}],"version-history":[{"count":1,"href":"https:\/\/boyliang.com\/index.php\/wp-json\/wp\/v2\/posts\/32\/revisions"}],"predecessor-version":[{"id":55,"href":"https:\/\/boyliang.com\/index.php\/wp-json\/wp\/v2\/posts\/32\/revisions\/55"}],"wp:attachment":[{"href":"https:\/\/boyliang.com\/index.php\/wp-json\/wp\/v2\/media?parent=32"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/boyliang.com\/index.php\/wp-json\/wp\/v2\/categories?post=32"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/boyliang.com\/index.php\/wp-json\/wp\/v2\/tags?post=32"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}