{"id":378,"date":"2020-04-25T14:53:26","date_gmt":"2020-04-25T06:53:26","guid":{"rendered":"http:\/\/bytew.net\/?p=378"},"modified":"2021-09-08T20:20:07","modified_gmt":"2021-09-08T12:20:07","slug":"cf-div-1-637-%e9%a2%98%e8%a7%a3-%e5%ae%9e%e5%bd%95","status":"publish","type":"post","link":"https:\/\/bytew.net\/?p=378","title":{"rendered":"CF Div 1 637 \u9898\u89e3\/\u5b9e\u5f55"},"content":{"rendered":"\n

\u524d\u5929\u665a\u4e0a\u6211\u6253\u4e86Codeforces Div1 637\uff0c\u7136\u540e\u722c\u4e86\u2026\u2026\u60e8\u60e8\uff0c\u6389\u4e86\u597d\u591a\u5206\u3002<\/p>\n\n\n\n

\u672c\u6765\u6628\u5929\u76f8\u5f53\u6ca1\u5fc3\u60c5\u5199\u8bb0\u5f55\u3002\u56e0\u4e3a\u6211\u53ea\u60f3\u51fa\u6765\u4e86ABCD\uff0c\u4f1a\u4e86F\uff0c\u7ed3\u679cE\u6839\u672c\u6beb\u65e0\u5934\u7eea\uff0c\u60f3\u4e0d\u4e86\u3002\u7ed3\u679c\u4eca\u5929CF\u4e0a\u8bf4E\u9898\u5047\u4e86\uff0c\u90a3\u573a\u6bd4\u8d5b\u7684Div1\u8981unrated\u4e86\uff0c\u6211\u5c31\u6765\u8bb0\u5f55\u4e00\u4e0b\u81ea\u5df1\u662f\u600e\u4e48\u722c\u7684\uff0c\u987a\u4fbf\u5199\u4e00\u4e0b\u9898\u89e3\u3002\u3002<\/p>\n\n\n\n\n\n\n\n

A. Nastya and Strange Generator<\/h2>\n\n\n\n

\u4e00\u53e5\u8bdd\u9898\u610f\uff1a\u7ed9\u4f60\u4e00\u4e2a\u5e8f\u5217\uff0c\u95ee\u4f60\u662f\u4e0d\u662f\u6309\u7167\u67d0\u4e2a\u89c4\u5219\u751f\u6210\u7684<\/p>\n\n\n\n

\u8fd9\u6837\u7684\u5e8f\u5217\u7684\u4ea7\u751f\u65b9\u5f0f\uff0c\u4e00\u5b9a\u662f\u7531\u82e5\u5e72\u4e2a\u4e0a\u5347\u7684\u6bb5\u7ec4\u6210\u7684\uff0c\u6bcf\u4e2a\u6bb5\u7684\u6570\u662f\u8fde\u7eed\u7684\uff0c\u6700\u53f3\u9762\u7684\u6bb5\u7684\u6570\u5b57\u6700\u5c0f\u3002\u3002\u66b4\u529b\u5224\u4e00\u4e0b<\/p>\n\n\n\n

\u8fd9\u4e2a\u9898\u8fd8\u6ca1\u6709\u722c\uff0c\u4e94\u5206\u949f\u8fc7\u4e86\u3002\u3002<\/p>\n\n\n\n

int T;\nint main() {\n\tread(T);\n\twhile(T--){\n\t\tint n;\n\t\tread(n);\n\t\tvector<int> p(n+2,0),rp(n+2,0),vis(n+2,0);\n\t\tfor(int i=1;i<=n;i++){\n\t\t\tread(p[i]);\n\t\t\trp[p[i]] = i;\n\t\t}\n\t\tint ok = 1;\n\t\tfor(int i=1;i<=n;i++){\n\t\t\tint cp = rp[i];\n\t\t\tif(vis[cp])continue;\n\t\t\tfor(int j=cp;!vis[j] && j<=n;j++){\n\t\t\t\tvis[j] = 1;\n\t\t\t\tok&=(p[j] == p[cp]+j-cp);\n\t\t\t}\n\t\t}\n\t\tcout<<(ok?\"Yes\":\"No\")<<\"\\n\";\n\t}\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
B. Nastya and Scoreboard<\/h2>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
\u4e00\u53e5\u8bdd\u9898\u610f\uff1a\u7ed9\u4f60n\u4e2a\u6570\u5b57\u706f\u7684\u72b6\u51b5\u3002\u8ba9\u4f60\u518d\u70b9\u4eae\u6070\u597dk\u4e2a\uff0c\u6700\u540e\u7684\u6570\u5b57\u6700\u5927\u4e3a\u591a\u5c11\uff1f\u53ef\u4ee5\u524d\u5bfc0. n k 2000<\/p>\n\n\n\n
\u8fd9\u4e2a\u5927\u6982\u5c31\u662f\u8fdb\u884cdp\uff0cdp[i][j]\u8bb0\u5f55\u7b2ci\u4e2a\u706f\u4e4b\u524d\u70b9\u4eae\u4e86j\u6b21\uff0c\u5728\u6240\u6709\u7b2ci\u4e2a\u706f\u4e2d\u662f\u7b2c\u51e0\u5927\u7684\u3002\u8bb0\u5f55\u8f6c\u79fb\u7684\u6765\u6e90\uff0c\u6bcf\u6b21\u6392\u5e8f\u79bb\u6563\u5316\u5373\u53ef\u3002\"O(n^2 \log n)\"<\/p>\n\n\n\n
\u8fd9\u4e2a\u9898\u76ee\u6211\u82b1\u4e86\u5341\u516b\u5206\u949f\uff0c\u5176\u4e2d\u6709\u4e00\u4e2a\u539f\u56e0\u5c31\u662f\u6211\u6ca1\u6709\u53d1\u73b0\u9898\u9762\u4e2d\u7ed9\u51fa\u4e86\u6bcf\u4e00\u4e2a\u6570\u5b57\u7684\u7f16\u7801\u3002<\/p>\n\n\n\n
int a[10] = {119,18,93,91,58,107,111,82,127,123};\nint n,k,c[2020],dp[2020][2020],fr[2020][2020],bcnt[2020];\nint main() {\n\tfor(int i=0;i<200;i++)bcnt[i] = __builtin_popcount(i);\n\tmemset(fr,7,sizeof(fr));\n\tread(n,k);\n\tfor(int i=1;i<=n;i++){\n\t\tstring cc;\n\t\tcin>>cc;\n\t\tfor(int j=0;j<7;j++){\n\t\t\tc[i] = c[i]*2+cc[j]-'0';\n\t\t}\n\t}\n\tdp[1][0] = 1;\n\tfor(int i=1;i<=n;i++){\n\t\tfor(int j=0;j<=k;j++){\n\t\t\tif(!dp[i][j])continue;\n\t\t\tfor(int ch=0;ch<10;ch++){\n\t\t\t\tif((a[ch]&c[i]) == c[i] && dp[i][j]*10+ch>dp[i+1][j+bcnt[a[ch]]-bcnt[c[i]]]){\n\t\t\t\t\tdp[i+1][j+bcnt[a[ch]]-bcnt[c[i]]] = dp[i][j]*10+ch;\n\t\t\t\t\tfr[i+1][j+bcnt[a[ch]]-bcnt[c[i]]] = ch;\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\tvector<int> U;\n\t\tU.PB(0);\n\t\tfor(int j=0;j<=k;j++)U.PB(dp[i+1][j]);\n\t\tsort(all(U));\n\t\tU.erase(unique(all(U)),U.end());\n\t\tfor(int j=0;j<=k;j++)dp[i+1][j] = lower_bound(all(U),dp[i+1][j])-U.begin();\n\t}\n\tif(fr[n+1][k]<10000){\n\t\tstring S;\n\t\tint cp = k;\n\t\tfor(int i=n+1;i>1;i--){\n\t\t\tS+='0'+fr[i][cp];\n\t\t\tcp-=bcnt[a[fr[i][cp]]]-bcnt[c[i-1]];\n\t\t}\n\t\treverse(all(S));\n\t\tcout<<S<<endl;\n\t}else{\n\t\tcout<<-1<<endl;\n\t}\n\treturn 0;\n}\n<\/code><\/pre>\n\n\n\n
C. Nastya and Unexpected Guest<\/h2>\n\n\n\n
0,1,…,n\u4e2a\u70b9\u6784\u6210\u7684\u6570\u8f74\u79f0\u4e3a\u9053\u8def\u3002\u5c0fD\u57280\u70b9\uff0c\u4ed6\u60f3\u5230\u8fbe\"n (n \le 10^6)\"\u53f7\u70b9\u3002\u6709\"m(m \le 10^4)\"\u4e2a\u4e0d\u540c\u4f4d\u7f6e\u662f\u5b89\u5168\u5c9b\uff0c\u4e3a\"d_1,\ldots,d_m\"\u30020\u548cn\u90fd\u662f\u5b89\u5168\u5c9b\u3002\u7ea2\u7eff\u706f\u7effg\u79d2\u7ea2r\u79d2\u5faa\u73af\uff0c\u53ea\u6709\u7eff\u65f6\u5019\u624d\u80fd\u8d70\uff0c\u7ea2\u7684\u65f6\u5019\u5fc5\u987b\u5728\u5b89\u5168\u5c9b\u3002r,g <2000<\/p>\n\n\n\n
  • \u5f53\u7eff\u706f\u4eae\u7740\u65f6\uff0c\u4ed6\u5fc5\u987b\u59cb\u7ec8\u79fb\u52a8<\/li>
  • \u4ed6\u53ea\u80fd\u5728\u5b89\u5168\u5c9b\u4e0a\u66f4\u6539\u65b9\u5411\uff08\u56e0\u4e3a\u5b83\u5f88\u5b89\u5168\uff09<\/li>
  • \u5728\u7ea2\u706f\u4eae\u8d77\u7684\u90a3\u4e00\u523b\uff0c\u7537\u5b69\u5fc5\u987b\u5728\u5b89\u5168\u5c9b\u4e4b\u4e00\u4e0a\u3002\u7eff\u706f\u4eae\u65f6\uff0c\u4ed6\u53ef\u4ee5\u7ee7\u7eed\u5411\u4efb\u4f55\u65b9\u5411\u79fb\u52a8\u3002<\/li>
  • \u4efb\u4f55\u65f6\u5019\u5230n\u53f7\u70b9\u5c31\u8d62\u4e86<\/li><\/ul>\n\n\n\n
    \u8fd9\u4e2a\u9898\u6211\u722c\u4e86\u2026\u2026\u6211\u5199\u4e86\u4e2abitset\uff0c\u7528\u4e8635\u5206\u949f\u3002\u82b1\u4e8618\u5206\u949f\u8ba9bitset\u6210\u529f\u8fd0\u884c\uff0c\u7ed3\u679ctle\u4e86\u3002\u82b1\u4e8645\u5206\u949f\u5199\u4e86\u4e2adijkstra\uff0c\u8fd8\u662ftle\u4e86\uff0c\u6700\u540e\u7528\u4e8615\u5206\u949f\u53d8\u6210\u4e0d\u7528\u4f18\u5148\u961f\u5217\u7684\u4e86\uff0c\u624d\u901a\u8fc7\u3002\u6bd4\u8d5b\u5c31\u7ed3\u675f\u4e86\u3002\u9898\u76ee\u5e76\u4e0d\u96be\u2026\u2026\u53ea\u662f\u6211\u592a\u722c\u4e86\u3002<\/p>\n\n\n\n
    \u9996\u5148\u6211\u4eec\u89c2\u5bdf\u5230\u7b54\u6848\u6700\u591a\u662f\u5343\u4e07\u7ea7\u522b\u7684(\u6211\u4e00\u5f00\u59cb\u7b97\u6210\u4e861e9\u5bfc\u81f4\u81ea\u5df1\u5931\u8d25)\u3002\u539f\u56e0\u662f\u6211\u4eec\u81f3\u591a\u8bbf\u95eem\u4e2a\u5b89\u5168\u5c9b\uff0c\u6bcf\u4e24\u4e2a\u4e4b\u95f4\u6700\u591ar+g=2000\u79d2\u3002\u7136\u540e\u6211\u4eec\u5c31\u53ef\u4ee5\u8dd1\u4e00\u4e2a\u7c7b\u4f3cdijkstra\u7684\u4e1c\u897f\u2026\u2026\u590d\u6742\u5ea6\"O(ans+m*g)\"\u3002<\/p>\n\n\n\n
    \nconst int N = 2020;\nint n,m,d[10010],g,r;\n\nbool vis[11000010];\nll mdi[11000010];\nll ans = 1e18;\n\nvector<int> Q[2020];\nint main() {\n\tread(n,m);\n\tfor(int i=0;i<m;i++)read(d[i]);\n\tsort(d,d+m);\n\tread(g,r);\n\tmemset(mdi,7,sizeof(mdi));\n\tmdi[g] = 0;\n\tQ[0].PB(g);\n\tint cnt = 1,cd = 0,cp = 0;\n\twhile(cnt){\n\t\tfor(auto ech:Q[cp]){\n\t\t\tif(vis[ech])continue;\n\t\t\tvis[ech] = 1;\n\t\t\tmdi[ech] = cd;\n\t\t\tint a = ech\/(g+1),b = ech%(g+1);\n\t\t\tif(a!=m-1 && b>=d[a+1]-d[a]){\n\t\t\t\tint tgt = ech+g+1-(d[a+1]-d[a]);\n\t\t\t\tif(!vis[tgt]){\n\t\t\t\t\tQ[(cp+d[a+1]-d[a])%N].PB(tgt);\n\t\t\t\t\tcnt++;\n\t\t\t\t}\n\t\t\t}\n\t\t\tif(a && b>=d[a]-d[a-1]){\n\t\t\t\tint tgt = ech-g-1-(d[a]-d[a-1]);\n\t\t\t\tif(!vis[tgt]){\n\t\t\t\t\tQ[(cp+d[a]-d[a-1])%N].PB(tgt);\n\t\t\t\t\tcnt++;\n\t\t\t\t}\n\t\t\t}\n\t\t\tif(a == m-1){\n\t\t\t\tcout<<cd<<endl;\n\t\t\t\treturn 0;\n\t\t\t}\n\t\t\tif(b == 0){\n\t\t\t\tQ[(cp+r)%N].PB(ech+g);\n\t\t\t\tcnt++;\n\t\t\t}\n\t\t}\n\t\tcnt-=Q[cp].size();\n\t\tQ[cp].clear();\n\t\tcd++;\n\t\tcp = (cp+1)%N;\n\t}\n\tcout<<-1<<endl;\n\treturn 0;\n}\n<\/code><\/pre>\n\n\n\n
    D. Nastya and Time Machine<\/h2>\n\n\n\n
    \u8fd9\u4e2a\u9898\u8d28\u91cf\u8fd8\u4e0d\u9519\u3002\u8d5b\u540e\u505a\u7684\uff0c\u6211\u7684\u505a\u6cd5\u8fd8\u633a\u7b80\u5355\u3002<\/p>\n\n\n\n
    \u9898\u89e3\uff1a\u7ed9\u4f60\u4e00\u9897\u6811\u3002\u4f60\u9700\u8981\u6784\u9020\u4e00\u4e2a\u5e8f\u5217(v,t)\uff0c\u4f7f\u5f97\u76f8\u90bb\u4e24\u4e2a\u72b6\u6001\u8981\u4e0d\u7136t’=t+1,v’\u548cv\u76f8\u90bb\uff0c\u8981\u4e0d\u7136v’=v,t'<t\u3002\u8981\u6c42\u6bcf\u4e2a\u72b6\u6001\u4e0d\u8d85\u8fc7\u4e00\u6b21\u8bbf\u95ee\uff0c\u6811\u4e2d\u6240\u6709\u8282\u70b9\u90fd\u8bbf\u95ee\u8fc7\uff0c\u800c\u4e14\u6700\u5927\u7684t\u8981\u6700\u5c0f\u3002<\/p>\n\n\n\n
    \u8fd9\u4e2a\u9898\u7684\u505a\u6cd5\u5982\u4e0b\uff1a\u9996\u5148\u6211\u4eec\u6ce8\u610f\u5230\uff0c\u5982\u679c\u4e00\u4e2a\u8282\u70b9\u6709n\u4e2a\u513f\u5b50\uff0c\u8fd9\u4e2a\u8282\u70b9\u53c8\u4e0d\u662f\u6839\u8282\u70b9\uff0c\u90a3\u4e48\u8fd9\u4e2a\u8282\u70b9\u4e00\u5b9a\u8981\u8bbf\u95een+1\u6b21\u3002\u7136\u540e\u5982\u679c\u6211\u4eec\u8fd8\u9700\u8981\u6709\u4e00\u6b21\u65f6\u95f4\u7a7f\u68ad\uff0c\u5c31\u9700\u8981\u8bbf\u95een+2\u6b21\u3002\u6bd4\u5982\u4e00\u4e2a4\u4e2a\u513f\u5b50\u7684\u8282\u70b9\uff0c\u7236\u4eb2\u8bbf\u95ee\u4ed6\u7684\u65f6\u5019\u65f6\u95f4\u662f3\uff0c\u90a3\u4e48\u8fd9\u4e2a\u8282\u70b9\u7684\u8bbf\u95ee\u65f6\u95f4\u5e8f\u5217\u6211\u4eec\u5c31\u8ba9\u4ed6\u662f3-(\u5b50\u8282\u70b9)-4-(\u5b50\u8282\u70b9)-5-(\u65f6\u95f4\u7a7f\u68ad)-0-(\u5b50\u8282\u70b9)-1-(\u5b50\u8282\u70b9)-2\uff0c\u8fd9\u6837\u6211\u4eec\u77e5\u9053\u4ed6\u7684\u7236\u4eb2\u8bbf\u95ee\u4ed6\u4e4b\u524d\u65f6\u95f4\u662f2\uff0c\u4ed6\u56de\u53bb\u7684\u65f6\u95f4\u662f3\uff0c\u6070\u597d\u5dee1\u3002\u8fd9\u79cd\u6784\u9020\u65b9\u6cd5\u53ef\u4ee5\u4fdd\u8bc1\u7b54\u6848\u6700\u4f18\uff0c\u7531\u4e8e\u6211\u6253\u5b57\u6253\u7d2f\u4e86\uff0c\u8bc1\u660e\u7559\u7ed9\u8bfb\u8005\u3002<\/p>\n\n\n\n
    int n,u,v;\nvector<int> G[100010];\n\nvector<pii> Q;\nvoid dfs(int num,int t,int fa = -1){\n\tint orit = t;\n\tQ.PB(MP(num,t));\n\tint rem = G[num].size()-(fa!=-1);\n\tfor(auto ct:G[num]){\n\t\tif(ct == fa)continue;\n\t\tif(orit>rem && t>=orit && t!=0){\n\t\t\tt = orit-rem-1;\n\t\t\tQ.PB(MP(num,t));\n\t\t}\n\t\tt+=1;\n\t\tdfs(ct,t,num);\n\t\tQ.PB(MP(num,t));\n\t\trem--;\n\t}\n\tif(fa!=-1 && t!=orit-1) Q.PB(MP(num,orit-1));\n}\n\nint main() {\n\tread(n);\n\tfor(int i=1;i<n;i++){\n\t\tread(u,v);\n\t\tG[u].PB(v);\n\t\tG[v].PB(u);\n\t}\n\tdfs(1,0);\n\tcout<<Q.size()<<endl;\n\tfor(auto ct:Q)cout<<ct.F<<' '<<ct.S<<endl;\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
    E. Nastya and Bees<\/h2>\n\n\n\n
    \u8fd9\u9053\u9898\uff0c\u5982\u679c\u6ca1\u6709\u5047\u51fa\u9898\u4eba\u5c06\u7edd\u6740\uff0c\u53ef\u60dc\u7684\u786e\u5047\u4e86\u3002<\/p>\n\n\n\n
    \uff08\u6316\u4e2a\u5751\uff0c\u867d\u7136\u5047\u9898\u6211\u8fd8\u662f\u60f3\u89c2\u6469\u4e00\u4e0b\uff09<\/p>\n\n\n\n
    F. Nastya and CBS<\/h2>\n\n\n\n
    \u4e00\u53e5\u8bdd\u9898\u610f\uff1a\u4e00\u4e2a\u4efb\u610f\u591a\u79cd\u62ec\u53f7\u7684\u62ec\u53f7\u5e8f\u5217\uff0c\u652f\u6301\u4fee\u6539\u548c\u8be2\u95ee\u67d0\u4e00\u6bb5\u5408\u6cd5\u4e0d\u5408\u6cd5\u3002<\/p>\n\n\n\n
    \u6211\u8fd8\u6ca1\u6709\u5199\u8fd9\u4e2a\u9898\uff0c\u4f46\u662f\u6211\u9605\u8bfb\u4e86\u4e00\u4efdjiangly<\/font><\/b>\u7684AC\u4ee3\u7801\uff08\u8fd9\u662f\u771f\u7684LGM\uff0corz\uff01\uff09\u3002<\/p>\n\n\n\n
    :(\u5b9e\u5728\u5199\u4e0d\u52a8\u4e86\uff0c\u60f3\u4e86\u89e3\u7684\u81ea\u5df1\u53bb\u770b\u5427\uff0c\u6211\u4f30\u8ba1\u505aDiv1F\u7684\u4eba\u4e5f\u6ca1\u51e0\u4e2a\uff0c\u4e0d\u4f1a\u770b\u6211\u5199\u9898\u89e3\u7684\u3002<\/p>\n ","protected":false},"excerpt":{"rendered":"
    \u524d\u5929\u665a\u4e0a\u6211\u6253\u4e86Codeforces Div1 637\uff0c\u7136\u540e\u722c\u4e86\u2026\u2026\u60e8\u60e8\uff0c\u6389\u4e86\u597d\u591a\u5206\u3002 \u672c\u6765\u6628\u5929\u76f8\u5f53\u6ca1\u5fc3\u60c5\u5199\u8bb0\u5f55 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[26,22,25],"_links":{"self":[{"href":"https:\/\/bytew.net\/index.php?rest_route=\/wp\/v2\/posts\/378"}],"collection":[{"href":"https:\/\/bytew.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/bytew.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/bytew.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/bytew.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=378"}],"version-history":[{"count":2,"href":"https:\/\/bytew.net\/index.php?rest_route=\/wp\/v2\/posts\/378\/revisions"}],"predecessor-version":[{"id":380,"href":"https:\/\/bytew.net\/index.php?rest_route=\/wp\/v2\/posts\/378\/revisions\/380"}],"wp:attachment":[{"href":"https:\/\/bytew.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=378"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/bytew.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=378"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/bytew.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=378"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}