{"id":109,"date":"2022-12-17T22:32:03","date_gmt":"2022-12-17T14:32:03","guid":{"rendered":"https:\/\/www.vcoco.top\/?p=109"},"modified":"2022-12-28T15:14:12","modified_gmt":"2022-12-28T07:14:12","slug":"atcoder-beginner-contest-282","status":"publish","type":"post","link":"https:\/\/www.vcoco.top\/index.php\/2022\/12\/17\/atcoder-beginner-contest-282\/","title":{"rendered":"AtCoder Beginner Contest 282"},"content":{"rendered":"\n

\u9898\u76ee\u94fe\u63a5\uff1ahttps:\/\/atcoder.jp\/contests\/abc282\/tasks<\/p>\n\n\n\n

A – Generalized ABC<\/strong><\/h3>\n\n\n\n
#include <bits\/stdc++.h>\n#define x first\n#define y second\n#define all(x) x.begin(),x.end()\n#define rep(i, l, r) for (int i = l; i <= r; i++)\n#define nep(i, r, l) for (int i = r; i >= l; i--)\nusing namespace std;\ntypedef long long LL;\ntypedef unsigned long long ULL;\ntypedef pair<int,int> PII;\ntypedef pair<LL,int> PLI;\nconst int INF=0x3f3f3f3f,MOD=998244353,P=131,N=15, M=20010;\n\nint n, m;\n\nvoid solve()\n{\n    cin>>n;\n    for(int i=0;i<n;i++)\n    {\n        printf(\"%c\",i+'A');\n    }\n}\n \n \n \nint main()\n{\n    #ifdef LOCAL\n        freopen(\"D:\\\\Procedure\\\\vs_code\\\\in.txt\",\"r\",stdin);\n    #endif\n    solve();\n    return 0;\n}\n<\/code><\/pre>\n\n\n\n
B – Let’s Get a Perfect Score<\/strong><\/h3>\n\n\n\n
#include <bits\/stdc++.h>\n#define x first\n#define y second\n#define all(x) x.begin(),x.end()\n#define rep(i, l, r) for (int i = l; i <= r; i++)\n#define nep(i, r, l) for (int i = r; i >= l; i--)\nusing namespace std;\ntypedef long long LL;\ntypedef unsigned long long ULL;\ntypedef pair<int,int> PII;\ntypedef pair<LL,int> PLI;\nconst int INF=0x3f3f3f3f,MOD=998244353,P=131,N=110, M=20010;\n\nint n, m;\nstring s[N];\n\nvoid solve()\n{\n    cin>>n>>m;\n    rep(i,1,n) cin>>s[i];\n\n    int res=0;\n    rep(i,1,n){\n        rep(j,i+1,n){\n            bool f=true;\n            rep(k,0,s[i].size()-1){\n                if(s[i][k]=='o' || s[j][k]=='o') continue;\n                else{\n                    f=false;\n                    break;\n                } \n            }\n            if(f) res++;\n        }\n    }\n\n    cout<<res<<endl;\n}\n \n \n \nint main()\n{\n    #ifdef LOCAL\n        freopen(\"D:\\\\Procedure\\\\vs_code\\\\in.txt\",\"r\",stdin);\n    #endif\n    solve();\n    return 0;\n}\n<\/code><\/pre>\n\n\n\n
C – String Delimiter<\/strong><\/h3>\n\n\n\n
#include <bits\/stdc++.h>\n#define x first\n#define y second\n#define all(x) x.begin(),x.end()\n#define rep(i, l, r) for (int i = l; i <= r; i++)\n#define nep(i, r, l) for (int i = r; i >= l; i--)\nusing namespace std;\ntypedef long long LL;\ntypedef unsigned long long ULL;\ntypedef pair<int,int> PII;\ntypedef pair<LL,int> PLI;\nconst int INF=0x3f3f3f3f,MOD=998244353,P=131,N=110, M=20010;\n\nint n, m;\nstring s;\n\nvoid solve()\n{\n    cin>>n>>s;\n    int res=0;\n    bool f=false;\n    for(int i=0;i<s.size();i++){\n        if(s[i]=='\"') {\n            if(f) f=false;\n            else f=true;\n            continue;\n        }\n\n        if(!f && s[i]==',') {\n            s[i]='.';\n        }\n    }\n\n    cout<<s<<endl;\n}\n \n \n \nint main()\n{\n    #ifdef LOCAL\n        freopen(\"D:\\\\Procedure\\\\vs_code\\\\in.txt\",\"r\",stdin);\n    #endif\n    solve();\n    return 0;\n}\n<\/code><\/pre>\n\n\n\n
D – Make Bipartite 2<\/strong><\/h3>\n\n\n\n
\u9898\u89e3<\/strong>\uff1a\u7ed9\u4f60\u4e00\u5f20\u56fe\uff0c\u8ba9\u4f60\u6c42\u52a0\u4e00\u6761\u8fb9\u4f7f\u5176\u6210\u4e3a\u4e8c\u5206\u56fe\u7684\u65b9\u6848\u6570\u3002\uff08\u56fe\u6709\u53ef\u80fd\u4e0d\u8fde\u901a\u6216\u8005\u672c\u8eab\u5c31\u4e0d\u662f\u4e8c\u5206\u56fe\uff09<\/p>\n\n\n\n
\u8003\u8651\u6bcf\u4e00\u4e2a\u8054\u901a\u7684\u5757\u6765\u8ba1\u7b97\u3002col[i]<\/code> \u6570\u7ec4\u8868\u793a\u989c\u8272\u4e3a v<\/code> \u7684\u70b9\u6570\uff0c\u7531\u4e8e\u540c\u4e00\u4e2a\u4e8c\u5206\u56fe\u6700\u591a\u5c31\u53ea\u6709\u4e24\u79cd\u989c\u8272\uff0c\u56e0\u6b64\u603b\u70b9\u6570\u4e3a $col[i]+col[i+1]$\u3002<\/p>\n\n\n\n
    \n
  1. \u5728\u4e00\u4e2a\u8fde\u901a\u5757\u5185\u52a0\u8fb9\uff0c\u52a0\u8fb9\u65b9\u6848\u6570=\u4e8c\u5206\u56fe\u4e24\u8fb9\u70b9\u6570\u91cf\u76f8\u4e58-\u8fb9\u6570\u3002\u516c\u5f0f\u8868\u793a\u4e3a\uff1a$$S_1=col[i]*col[i+1]-cnt$$\uff0c\u7531\u4e8e\u8fb9\u6570\u6700\u7ec8\u4e4b\u548c\u4e3a $m$\uff0c\u6240\u4ee5\u53ef\u4ee5\u7b49\u6700\u540e\u518d\u51cf m<\/code> \u5c31\u884c\u4e86<\/li>\n\n\n\n
  2. \u5728\u8fde\u901a\u5757\u4e4b\u95f4\u52a0\u8fb9\uff0c\u52a0\u8fb9\u65b9\u6848\u6570=\u8be5\u8054\u901a\u5757\u5185\u70b9\u6570*\uff08\u603b\u70b9\u6570-\u8be5\u8054\u901a\u5757\u5185\u70b9\u6570\uff09\u516c\u5f0f\u8868\u793a\u4e3a\uff1a$$S_2=(col[i]+col[i+1])*n$$\uff08ps\uff1a\u524d\u9762\u8ba1\u7b97\u8fc7\u7684\u5c31\u4e0d\u7528\u8ba1\u7b97\u4e86\uff0c\u6bd4\u5982a\u8fdeb\uff0cb\u8fdea\u662f\u540c\u4e00\u79cd\u65b9\u6848\u3002\n
      \n
    • <\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n
        \n
      • \u7528\u8fd9\u79cd\u65b9\u6cd5\u4e00\u5b9a\u8981col<\/code>\u6570\u7ec4\u4e00\u5b9a\u8981\u5f00\u4e24\u500d\u70b9\u6570\u7684\u5927\u5c0f\uff0c\u8840\u7684\u6559\u8bad\uff01\uff01\uff01<\/li>\n<\/ul>\n\n\n\n
        #include <bits\/stdc++.h>\n#define x first\n#define y second\n#define all(x) x.begin(),x.end()\n#define rep(i, l, r) for (int i = l; i <= r; i++)\n#define nep(i, r, l) for (int i = r; i >= l; i--)\nusing namespace std;\ntypedef long long LL;\ntypedef unsigned long long ULL;\ntypedef pair<int,int> PII;\ntypedef pair<LL,int> PLI;\nconst int INF=0x3f3f3f3f,MOD=998244353,P=131,N=200010, M=2*N;\n\nint n, m;\nint e[M], ne[M], h[N], idx;\nint st[N];\nLL col[2*N]; \n\nvoid add(int a, int b)\n{\n    e[idx]=b, ne[idx]=h[a], h[a]=idx++;\n}\n\nbool dfs(int u, int fa, int v) \/\/\u67d3\u8272\u6cd5\n{\n    if(st[u]!=-1 && v!=st[u]) return false;\n    if(st[u]!=-1) return true;\n    st[u]=v, col[v]++;\n    for(int i=h[u];~i;i=ne[i])\n    {\n        int j=e[i];\n        if(j!=fa){\n            if(!dfs(j, u, v^1))\n                return false;\n        }\n    }\n\n    return true;\n}\n\nvoid solve()\n{\n    cin>>n>>m;\n    memset(h, -1, sizeof h);\n    memset(st, -1, sizeof st);\n    \n    rep(i,1,m){\n        int a,b; scanf(\"%d%d\", &a, &b);\n        add(a, b), add(b, a);\n    }\n\n    int f=1, pa=0;\n    for(int i=1;i<=n;i++)\n    {\n        if(st[i]==-1) {\n            f&=dfs(i, -1, pa);\n            pa+=2;\n        }\n    }\n\n    if(f) { \/\/\u5b58\u5728\n        LL s=0, res=0;\n        for(int i=0;i<pa;i+=2)\n        {\n            s+=col[i]*col[i+1]; \/\/\u5757\u5185\u65b9\u6848\n            n-=col[i]+col[i+1];\n            res+=(col[i]+col[i+1])*n; \/\/\u5757\u5916\u65b9\u6848\n        }\n        cout<<s-m+res<<endl;\n    } else puts(\"0\");\n}\n \n \nint main()\n{\n    #ifdef LOCAL\n        freopen(\"D:\\\\Procedure\\\\vs_code\\\\in.txt\",\"r\",stdin);\n    #endif\n    solve();\n    return 0;\n}\n<\/code><\/pre>\n\n\n\n
        E – Choose Two and Eat One<\/strong><\/h3>\n\n\n\n
          \n
        • \u8fd9\u9898\u6c14\u7684\u6211\u8111\u8840\u6813\uff0c\u770b\u51fa\u662f\u56fe\u8bba\u9898\uff1a\u8d70\u6240\u6709\u8fb9\u8d70\u4e00\u904d\u6c42\u6700\u957f\u8def\u3002\u7136\u800c\u4e00\u987f\u64cd\u4f5c\u5728\u7528dijkstra\u641e\u6700\u957f\uff08\u77ed\uff09\u8def\u3002\uff08\u4e0b\u610f\u8bc6\u4ee5\u4e3a\u6700\u957f\u7684\u4e00\u4e2adist\u5c31\u662f\u8d70\u5b8c\u6240\u6709\u8fb9\uff0c\u5ffd\u7565\u4e86\u751f\u6210\u6811\u8fd9\u832c\u4e86\uff09<\/li>\n<\/ul>\n\n\n\n
          \u9898\u89e3<\/strong><\/p>\n\n\n\n
          \u8bf4\u5230\u8fd9\u4efd\u4e0a\u4e86\uff0c\u53ef\u4ee5\u62bd\u8c61\u9898\u76ee\u51fa\u6765\u53d1\u73b0\u8981\u9009\u51fa n-1<\/code> \u4e2a\u70b9\uff0c\u6bcf\u6b21\u9009\u51fa\u90fd\u6709\u4e00\u4e2a\u6743\u503c\uff0c\u8981\u8ba9\u603b\u548c\u6700\u5927\uff0c\u5c31\u5bb9\u6613\u770b\u51fa\u662f\u6700\u5927\u751f\u6210\u6811\u95ee\u9898\u3002<\/p>\n\n\n\n
          #include <bits\/stdc++.h>\n#define x first\n#define y second\n#define all(x) x.begin(),x.end()\n#define rep(i, l, r) for (int i = l; i <= r; i++)\n#define nep(i, r, l) for (int i = r; i >= l; i--)\nusing namespace std;\ntypedef long long LL;\ntypedef unsigned long long ULL;\ntypedef pair<int,int> PII;\ntypedef pair<LL,int> PLI;\nconst int INF=0x3f3f3f3f,MOD=998244353,P=131,N=510, M=2*N;\n\nint n, m, a[N];\nLL dist[N];\nint pre[N], cnt;\n\nint find(int x)\n{\n    return x==pre[x]?x:pre[x]=find(pre[x]);\n}\n\nstruct Node\n{\n    int a, b, w;\n    bool operator < (const Node &oo)\n    {\n        return w>oo.w;\n    };\n}edge[N*N];\n\nint qmi(int a, int b)\n{\n    LL res=1;\n    while(b)\n    {\n        if(b&1) res=res*a%m;\n        a=(LL)a*a%m;\n        b>>=1;\n    }\n    return res%m;\n}\n\nvoid solve()\n{\n    cin>>n>>m;\n    rep(i,1,n) pre[i]=i;\n    rep(i,1,n){\n        scanf(\"%d\", &a[i]);\n        rep(j,1,i-1){\n            \/\/\u9884\u5904\u7406\u6bcf\u4e24\u4e2a\u70b9\u4e4b\u95f4\u7684\u8fb9\n            edge[cnt++]={i,j,(qmi(a[i], a[j])+qmi(a[j], a[i]))%m}; \n        }\n    }\n\n    sort(edge, edge+cnt);\n\n    LL res=0;\n    rep(i,0,cnt-1){\n        int pa=find(edge[i].a), pb=find(edge[i].b), w=edge[i].w;\n        if(pa!=pb){\n            pre[pa]=pb;\n            res+=w;\n        }\n    }\n\n    cout<<res<<endl;\n}\n \n \nint main()\n{\n    #ifdef LOCAL\n        freopen(\"D:\\\\Procedure\\\\vs_code\\\\in.txt\",\"r\",stdin);\n    #endif\n    solve();\n    return 0;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
          \u9898\u76ee\u94fe\u63a5\uff1ahttps:\/\/atcoder.jp\/contests\/abc282\/tasks A – […]<\/p>\n","protected":false},"author":1,"featured_media":167,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[70,31,71],"class_list":["post-109","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-atcoder","tag-70","tag-minimum-spanning-tree","tag-71"],"_links":{"self":[{"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/posts\/109","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/comments?post=109"}],"version-history":[{"count":8,"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/posts\/109\/revisions"}],"predecessor-version":[{"id":174,"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/posts\/109\/revisions\/174"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/media\/167"}],"wp:attachment":[{"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/media?parent=109"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/categories?post=109"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/tags?post=109"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}