{"id":82,"date":"2022-11-14T20:31:53","date_gmt":"2022-11-14T12:31:53","guid":{"rendered":"https:\/\/blog.myownweb.vip\/?p=82"},"modified":"2022-11-14T20:33:41","modified_gmt":"2022-11-14T12:33:41","slug":"stlweek4","status":"publish","type":"post","link":"https:\/\/forelink.top\/index.php\/2022\/11\/14\/stlweek4\/","title":{"rendered":"\u7ebf\u6027\u6570\u636e\u7ed3\u6784 \uff08Week 3\uff09"},"content":{"rendered":"\n

\u53ea\u5b66\u4e86\u94fe\u8868<\/strong>\uff0c\u6808<\/strong>\uff0c\u548c map<\/strong>\u3002\uff08\u7406\u76f4\u6c14\u58ee\uff09<\/p>\n\n\n\n

T1 \u961f\u5217\u5b89\u6392<\/h2>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n

\u8981\u7528\u624b\u5199\u4e00\u79cd\u5f88\u65b0\u7684\u4e1c\u897f\u5b58\u6570\u636e\u3002
\u6bcf\u4e2a\u540c\u5b66\u81ea\u5e26\u5de6\u624b\u548c\u53f3\u624b\uff0c\u4e8e\u662f\u7528\u94fe\u8868\u5b8c\u6210\u5bf9\u961f\u5217\u7684\u64cd\u4f5c\u3002<\/p>\n\n\n\n

\u4ee3\u7801\u5982\u4e0b\u3002<\/p>\n\n\n\n

#include <iostream>\nusing namespace std;\nconst int N=1e6+5;\nstruct hand{\n\tint l,r;\n};\/\/\u540c\u5b66\u7684\u5de6\u624b\u548c\u53f3\u624b\u3002\nhand stu[N]={0};\nvoid add(int i,int j,int f){\/\/\u628aj\u540c\u5b66\u63d2\u5165\u3002\n\tif(f==0){\/\/j\u662f\u63d2\u5165\u7684\u540c\u5b66 j i x\u7684\u60c5\u51b5\u3002j\u5728i\u5de6\u8fb9\u3002\n\t\tstu[j].r=i;\n\t\tstu[j].l=stu[i].l;\n\t\tstu[stu[i].l].r=j;\n\t\tstu[i].l=j;\n\t}\n\telse{\/\/ i j x\u7684\u60c5\u51b5\u3002j\u5728i\u53f3\u8fb9\u3002\n\t\tstu[j].l=i;\n\t\tstu[j].r=stu[i].r;\n\t\tstu[stu[i].r].l=j;\n\t\tstu[i].r=j;\n\t}\n}\nvoid del(int x){\/\/\u5220\u9664\u7f16\u53f7\u4e3ax\u7684\u540c\u5b66\u3002\n\tif(stu[x].l==0&&stu[x].r==0) return;\/\/\u6ca1\u6709\u8fd9\u4e2a\u540c\u5b66\u3002\n\telse{\n\t\tstu[stu[x].l].r=stu[x].r;\n\t\tstu[stu[x].r].l=stu[x].l;\n\t\tstu[x].l=0,stu[x].r=0;\/\/\u5220\u6389\u3002\n\t}\n}\nint main(){\n\tint n; cin>>n;\/\/n\u4e2a\u540c\u5b66\u3002\n\t\/\/\u975e\u5e38\u91cd\u8981\u3002\n\tstu[0].l=0,stu[0].r=0;\/\/\u8bbe\u7b2c\u96f6\u4e2a\u540c\u5b66\u81ea\u5df1\u62b1\u4f4f\u81ea\u5df1\u3002\n\tadd(0,1,1);\/\/\u5148\u628a\u7b2c\u4e00\u4e2a\u540c\u5b66\u63d2\u5165\u3002\n\tint num,op;\/\/\u6307\u6709num\u4e2a\u540c\u5b66\uff0cop\u662f\u64cd\u4f5c\u7c7b\u578b\uff080\/1\uff09\n\tfor(int i=2;i<=n;i++){\n\t\tcin>>num>>op;\n\t\tadd(num,i,op);\/\/\u8fdb\u884c\u63d2\u5165\u64cd\u4f5c\u3002 \n\t}\n\t\/\/\u5220\u9664\u64cd\u4f5c\u3002\n\tint cnt; cin>>cnt;\/\/\u8fdb\u884ccnt\u6b21\u5220\u9664\u64cd\u4f5c\u3002\u3002\n\tfor(int i=1;i<=cnt;i++){\n\t\tint ds; cin>>ds;\n\t\tdel(ds);\n\t}\n\tfor(int i=stu[0].r;i;i=stu[i].r){\/\/\u9047\u52300\u540c\u5b66\u7684\u65f6\u5019\u5c31\u505c\u6b62\u4e86\u3002\n\t\tcout<<i<<' ';\n\t}\n\tcout<<endl;\/\/\u884c\u672b\u6362\u884c\u3002\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
\u5f53\u7136\u4e5f\u53ef\u4ee5\u7528\u6807\u8bb0\u7684\u65b9\u5f0f\u51b3\u5b9a\u8f93\u4e0d\u8f93\u51fa\u8fd9\u4e2a\u540c\u5b66\uff0c\uff08\u8981\u662f\u6362\u4e86\u4e00\u9053\u9898\u6709\u8981\u6c42\u7684\u8fd8\u662f\u5f97\u4e56\u4e56\u5199hh\u3002<\/p>\n\n\n\n
\n\n\n\n
T2 \u62ec\u53f7\u5339\u914d<\/h2>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u5728\u53d1\u73b0\u5b57\u7b26\u4e32\u957f\u5ea6\u4e0d\u8d85\u8fc7100\u540e\u3002<\/p>\n\n\n\n
\"\"<\/div>
bully\u3002<\/figcaption><\/figure>\n\n\n\n
#include <bits\/stdc++.h>\nusing namespace std;\nbool vis[105]={false};\nint main(){\n\tstring a; cin>>a;\n\tfor(int i=0;i<a.length();i++){\n\t\tif(a[i]==')'||a[i]==']'){\/\/\u5982\u679c\u9047\u5230\u4e86\u53f3\u62ec\u53f7\u3002\n\t\t\tfor(int l=i-1;l>=0;l--){\/\/\u67e5\u627e\u53f3\u62ec\u53f7\u5de6\u8fb9\u7684\u5de6\u62ec\u53f7\u3002\n\t\t\t\tif((a[l]=='('||a[l]=='[')&&vis[l]==false){\/\/\u627e\u5230\u6700\u8fd1\u7684\u6ca1\u88ab\u67e5\u627e\u8fc7\u7684\u5de6\u62ec\u53f7\u3002\n\t\t\t\t\tif((a[l]=='('&&a[i]==')')||(a[l]=='['&&a[i]==']')){\n\t\t\t\t\t\tvis[i]=true,vis[l]=true;\n\t\t\t\t\t\tbreak;\/\/\u914d\u5bf9\u6210\u529f\u3002\n\t\t\t\t\t}\n\t\t\t\t\telse break;\/\/\u914d\u5bf9\u5931\u8d25\u3002\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\tfor(int i=0;i<a.length();i++){\n\t\tif(vis[i]==true){\n\t\t\tcout<<a[i];\n\t\t}\n\t\telse{\n\t\t\tif(a[i]=='('||a[i]==')') cout<<\"()\";\n\t\t\tif(a[i]=='['||a[i]==']') cout<<\"[]\";\n\t\t}\n\t}\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
\u5176\u5b9e\u8fd9\u9053\u9898\u662f\u8bd5\u56fe\u8ba9\u6211\u4eec\u7528\u6808\u89e3\u5427\u3002\uff09\uff09<\/p>\n\n\n\n
\n\n\n\n
T3 \u540e\u7f00\u8868\u8fbe\u5f0f<\/h2>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u662f\u4e00\u9053\u597d\u9898 \u7528\u6808\u5b58\u6570\u636e\u7684\u597d\u9898\u3002<\/p>\n\n\n\n
#include <iostream>\n#include <stack>\n#include <string>\nusing namespace std;\nint main(){\n\tstack<int> num;\/\/\u5b58\u6570\u5b57\u3002\n\tstack<char> op;\/\/\u5b58\u8fd0\u7b97\u7b26\u3002\n\tchar a;\n\tint x=0;\n\twhile(cin>>a&&a!='@'){\n\t\tif(a=='.'){\/\/\u9047\u5230 . \u65f6\u3002\n\t\t\tnum.push(x);\/\/\u628a\u6570\u5b57\u5b58\u5165\u6808\u4e2d\u3002\n\t\t\tx=0;\/\/\u91cd\u65b0\u521d\u59cb\u5316x\u3002\n\t\t}\/\/\u9047\u5230\u70b9\u5427\u6570\u5b57\u538b\u5165\u6808\u4e2d\u3002\n\t\tif(a>='0'&&a<='9'){\n\t\t\tx*=10; x+=a-'0';\n\t\t}\/\/\u8bfb\u53d6\u6570\u5b57\n\t\t\/\/\u52a0\u51cf\u4e58\u9664\u2014\u2014\u2014\u2014\u3002\uff08\u611f\u89c9\u5199\u7684\u597d\u7b28\uff09\n\t\tif(a=='+'){\n\t\t\tint x1,x2;\n\t\t\tx1=num.top();\n\t\t\tnum.pop();\n\t\t\tx2=num.top();\n\t\t\tnum.pop();\n\t\t\tx1+=x2;\n\t\t\tnum.push(x1);\n\t\t}\n\t\telse if(a=='-'){\n\t\t\tint x1,x2;\n\t\t\tx1=num.top();\n\t\t\tnum.pop();\n\t\t\tx2=num.top();\n\t\t\tnum.pop();\n\t\t\tx2-=x1;\n\t\t\tnum.push(x2);\n\t\t}\n\t\telse if(a=='*'){\n\t\t\tint x1,x2;\n\t\t\tx1=num.top();\n\t\t\tnum.pop();\n\t\t\tx2=num.top();\n\t\t\tnum.pop();\n\t\t\tx2*=x1;\n\t\t\tnum.push(x2);\n\t\t}\n\t\telse if(a=='\/'){\n\t\t\tint x1,x2;\n\t\t\tx1=num.top();\n\t\t\tnum.pop();\n\t\t\tx2=num.top();\n\t\t\tnum.pop();\n\t\t\tx2\/=x1;\n\t\t\tnum.push(x2);\n\t\t}\n\t}\n\tcout<<num.top();\/\/\u6700\u540e\u7684\u4e00\u679a\u6570\u5b57\u5c31\u662f\u7ecf\u8fc7n\u6b21\u8fd0\u7b97\u540e\u7684\u7b54\u6848\u4e86\u3002\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
\n\n\n\n
T4 \u5bc4\u5305\u67dc<\/h2>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u8fd9\u9898\u67dc\u5b50\u91cc\u8fd8\u6709\u683c\u5b50\uff0c\u5982\u679c\u7528\u4e8c\u7ef4\u6570\u7ec4\u7684\u8bdd\u4f1aM\uff0c\u5982\u679c\u641c\u7d22\u7684\u8bdd\u4f1aT\u3002\u4f20\u7edf\u7684\u8fde\u7eed\u987a\u5e8f\u8868\u5728\u8fd9\u91cc\u7528\u8d77\u6765\u975e\u5e38\u5c34\u5c2c\u3002<\/p>\n\n\n\n
\u4e8e\u662f\uff08\u770b\u9898\u89e3\u540e\uff09\u53bb\u5b66\u4e86\u5f3a\u5927\u7684Map<\/strong>\u3002
Map<\/strong>\u5b58\u50a8\u7684\u6570\u636e\u7c7b\u578b\u662fpair<\/strong>\uff0c\u53ef\u4ee5\u5b58\u5f88\u591apair<\/strong>\u3002
Pair<\/strong>\u662f<key\uff0cvalue><\/strong>\u7684\u952e\u503c\u5bf9\uff0c\u662f\u5b58\u50a8\u4e00\u4e2a\u952e<\/strong>\u4e0e\u952e\u6620\u5c04\u7684\u4e00\u4e2a\u503c<\/strong>\u7684\u6570\u636e\u7c7b\u578b\uff0c\u5176\u4e2dkey<\/strong>\u548cvalue<\/strong>\u53ef\u4ee5\u662f\u81ea\u5e26\u7684\u4efb\u610f\u4e00\u79cd\u6570\u636e\u7c7b\u578b\uff0c\u4e5f\u53ef\u4ee5\u662f\u81ea\u5b9a\u4e49\u7684\u7ed3\u6784\u4f53\uff0c\u5176\u4e2dkey<\/strong>\u7684\u503c\u4f1a\u7528const<\/strong>\u4fee\u9970\uff0c\u4e5f\u5c31\u662f\u8bf4\u4ed6\u662f\u4e0d\u53ef\u66f4\u53d8\u7684<\/strong>\u503c\u3002<\/p>\n\n\n\n
Map\u5e38\u7528\u7684\u51fd\u6570\u6709\uff1a<\/p>\n\n\n\n
\u2460 .insert()<\/strong>
\u7528\u6cd5\uff1amap\u53d8\u91cf\u540d.insert\uff08{key,value}\uff09\uff1b<\/strong>
\u2461 .erase()<\/strong>
\u7528\u6cd5\uff1amap\u53d8\u91cf\u540d.erase\uff08key\uff09\uff1b<\/strong>
\u4f1a\u5220\u9664map<\/strong>\u4e2d\u952e<\/strong>\u4e3akey<\/strong>\u7684pair<\/strong><\/p>\n\n\n\n
\u5728\u7ecf\u8fc7\u4e00\u4e9bmap\u7684\u5c0f\u5b9e\u9a8c\u540e\uff0c\u8fc7\u6b64\u9898\u7b80\u76f4\u5982\u6709\u795e\u52a9\u3002\uff09<\/p>\n\n\n\n
#include <iostream>\n#include <map>\/\/\u8981\u5305\u542b\u5934\u6587\u4ef6map\uff01\nusing namespace std;\nint main(){\n\tmap<pair<int,int>,int> m;\n\t\/\/\u5b9a\u4e49\u4e00\u4e2amap\u5bb9\u5668\u3002\n\t\/\/key\u4e3a\u67dc\u5b50\u548c\u683c\u5b50\uff0cvalue\u4e3a\u7269\u54c1\u3002\n\tint n,q;\/\/\u6709n\u4e2a\u67dc\u5b50\uff0cq\u6b21\u64cd\u4f5c\u3002\n\tcin>>n>>q;\n\tfor(int i=1;i<=q;i++){\n\t\tint op;\n\t\tcin>>op;\n\t\t\/\/\u5b58\u5165\u64cd\u4f5c\u3002\n\t\tif(op==1){\n\t\t\tint x1,x2,x3;\n\t\t\tcin>>x1>>x2>>x3;\n\t\t\tif(x3!=0)\n\t\t\tm.insert({{x1,x2},x3});\n\t\t\telse\/\/\u5751\u70b9\uff1a\u7269\u54c1\u4e3a0\u65f6\u8981\u62ff\u51fa\u6765\u3002\u3002\n\t\t\tm.erase({x1,x2});\n\t\t}\n\t\t\/\/\u8bbf\u95ee\u64cd\u4f5c\u3002\n\t\telse{\n\t\t\tint x1,x2;\n\t\t\tcin>>x1>>x2;\n\t\t\tcout<<m[{x1,x2}]<<endl;\n\t\t\t\/\/\u8bbf\u95ee\u7684\u65f6\u5019\u8981 m[key]\u3002\n\t\t}\n\t}\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
\u53ef\u4ee5\u8bf4\u662f\u975e\u5e38\u7b80\u5355\uff08bu\uff09\uff1b<\/p>\n\n\n\n
\u4f46\u662f\u5173\u4e8emap\u7684\u8ba4\u8bc6\u4e5f\u53ea\u505c\u7559\u5728\u8fc7 T4<\/strong> \u7684\u7a0b\u5ea6\u3002<\/p>\n\n\n\n
\u5176\u4ed6\u7684\u51fd\u6570\uff0c\u6211\u8fd8\u6ca1\u7528\u8fc7\uff08\u4e4b\u540e\u4f1a\u5b66\u7684\uff01\uff09
\u5982
.find()
.begin() \/ .rbegin()
.end()   \/ .rend()
.empty()
.clear()
.size()
.swap()
.count()<\/strong> \/\/\u4e0d\u80fd\u58f0\u660ecount\u4e3a\u53d8\u91cf\u540d\u7684\u5143\u51f6<\/strong>\uff1f\uff09<\/p>\n\n\n\n
\n\n\n\n
\u603b\u7ed3\uff1a<\/h2>\n\n\n\n
\u603b\u7ed3\u662f<\/p>\n\n\n\n
\u2460\u94fe\u8868<\/strong>\u554a\u6808<\/strong>\u554aMap<\/strong>\u554a\u5f88\u597d\u7528 \u4f46\u662f\u5bf9\u4f7f\u7528\u6761\u4ef6\u9002\u7528\u8303\u56f4\u4e0d\u662f\u975e\u5e38\u719f\u7ec3\u3002<\/p>\n\n\n\n
\u2461\u6211\u662f\u4e0d\u662f\u770b\u592a\u591a\u9898\u89e3<\/strong>\u4e86\uff1f\uff09\uff08\u53cd\u6b63\u5b66\u5230\u4e86\u65b0\u4e1c\u897f\u8bf6\u563f\u3002\uff09<\/p>\n\n\n