{"id":145,"date":"2023-05-12T22:16:54","date_gmt":"2023-05-12T14:16:54","guid":{"rendered":"https:\/\/forelink.top\/?p=145"},"modified":"2023-05-12T22:16:55","modified_gmt":"2023-05-12T14:16:55","slug":"%e4%b8%89%e9%a2%98%ef%bc%88week-12%ef%bc%89","status":"publish","type":"post","link":"https:\/\/forelink.top\/index.php\/2023\/05\/12\/%e4%b8%89%e9%a2%98%ef%bc%88week-12%ef%bc%89\/","title":{"rendered":"\u4e09\u9898\uff08week 12\uff09"},"content":{"rendered":"\n

T1 \u5b9d\u7269\u7b5b\u9009\uff08P1776\uff09<\/h2>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n

\u672a\u4f18\u5316\uff0c\u5f53\u6210\u591a\u91cd\u80cc\u5305\u505a\u3002<\/p>\n\n\n\n

#include <iostream>\r\n#include <stdio.h>\r\nusing namespace std;\r\nint v[1005],w[1005],s[1005],dp[1005];\r\nint main(){\r\n\tfreopen(\"P1776_4.in\",\"r\",stdin);\r\n\tint N,V;\r\n\tcin>>N>>V;\r\n\tfor(int i=1;i<=N;i++){\r\n\t\tcin>>w[i]>>v[i]>>s[i];\r\n\t}\r\n\tfor(int i=1;i<=N;i++){\r\n\t\tfor(int k=V;k>=1;k--){\r\n\t\t\tfor(int l=0;l<=s[i]&&l*v[i]<=k;l++){\r\n\t\t\t\tcout<<k<<' '<<k-l*v[i]<<' ';\r\n\t\t\t\tdp[k]=max(dp[k],dp[k-l*v[i]]+l*w[i]);\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n\tcout<<dp[V];\r\n\treturn 0;\r\n}<\/code><\/pre>\n\n\n\n
\u4e8c\u8fdb\u5236\u4f18\u5316\u540e\uff08\u8282\u7701\u4e86\u5927\u91cf\u7a7a\u95f4\uff09<\/p>\n\n\n\n
#include <iostream>\r\n#include <stdio.h>\r\nusing namespace std;\r\nconst int maxx=1e7+5;\r\nint N,V;\r\nint v[12005],w[12006],dp[maxx];\r\nint main(){\r\n\/\/\tfreopen(\"P1776_4.in\",\"r\",stdin);\r\n\tcin>>N>>V;\r\n\tint count=0;\r\n\t\/\/\u5206\u62102^0(1),2^1(2),2^2(4),2^3(8)...\u4f59\u6570\u7ec4\u3002\r\n\t\/\/O(n^3)->O(n^2logS\uff09\r\n\tfor(int i=1;i<=N;++i){\r\n\t\tint z,x,c;\r\n\t\tcin>>z>>x>>c;\r\n\t\tfor(int k=1;k<=c;k*=2){\r\n\t\t\tcount++;\r\n\t\t\tv[count]=x*k;\/\/fu gai.?\r\n\t\t\tw[count]=z*k;\r\n\t\t\tc-=k;\r\n\t\t}\r\n\t\tif(c>0){\r\n\t\t\tcount++;\r\n\t\t\tv[count]=x*c;\r\n\t\t\tw[count]=z*c;\r\n\t\t}\r\n\t}\r\n\t\/\/\u62ff1024\u6b21\u82f9\u679c\u6216\u8005\u62ff10\u6b21\u3002\uff087\u6b21\uff1f\r\n\tfor(int i=1;i<=count;++i){\r\n\t\tfor(int k=V;k>=1;k--){\r\n\t\t\tif(k>=v[i])\r\n\t\t\tdp[k]=max(dp[k],dp[k-v[i]]+w[i]);\r\n\t\t}\r\n\t}\r\n\tcout<<dp[V];\r\n\treturn 0;\r\n}<\/code><\/pre>\n\n\n\n
\n\n\n\n
T2 \u5c34\u5c2c\u7684\u6570\u5b57\uff08P1555\uff09<\/h2>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <iostream>\r\nusing namespace std;\r\nstring a,b;\r\nint cvs(string x){\r\n\tint yu,temp=0;\r\n\tfor(int i=0;i<x.length();i++){\r\n\t\tyu=x[i]-'0';\r\n\t\ttemp*=10;\r\n\t\ttemp+=yu;\r\n\t}\r\n\treturn temp;\r\n}\/\/\u8f6c\u6362\u6570\u636e\u7c7b\u578b\r\nstring er_shi(string x){\r\n\tint len=x.length(),baka;\r\n\tint i=0;\r\n\tif(x[i]!='0')\r\n\t\tbaka=x[0]-'0';\r\n\telse{\r\n\t\tbaka=x[1]-'0';\r\n\t\ti++;\r\n\t}\r\n\ti++;\r\n\tfor(;i<len;i++){\r\n\t\tbaka*=2;\r\n\t\tbaka+=x[i]-'0';\r\n\t}\r\n\tstring back;\r\n\tchar temp;\r\n\twhile(baka){\r\n\t\ttemp=(baka%10)+'0';\r\n\t\tback=temp+back;\r\n\t\tbaka\/=10;\r\n\t}\r\n\treturn back;\r\n}\/\/\u4e8c\u8fdb\u5236\u8f6c\u5341\u8fdb\u5236\r\nstring shi_san(string x){\r\n\tstring back;\r\n\tint num=cvs(x);\/\/\r\n\tint yu;\r\n\tchar temp;\r\n\twhile(num){\r\n\t\tyu=num%3;\r\n\t\ttemp=yu+'0';\r\n\t\tback=temp+back;\r\n\t\tnum\/=3;\r\n\t}\r\n\treturn back;\r\n}\/\/\u5341\u8fdb\u5236\u8f6c\u4e09\u8fdb\u5236\r\nbool cmp(string x){\r\n\tif(x.length()!=b.length())\r\n\t\treturn false;\r\n\tint cnt=0;\r\n\tfor(int i=0;i<b.length();i++){\r\n\t\tif(x[i]!=b[i])\r\n\t\t\tcnt++;\r\n\t}\r\n\tif(cnt==1) return true;\r\n\treturn false;\r\n}\/\/\u5224\u65ad\u51fd\u6570\r\nvoid change(int x){\r\n\tif(a[x]=='1') a[x]='0';\r\n\telse a[x]='1';\r\n}\r\nint main(){\r\n\tcin>>a>>b;\r\n\tfor(int i=0;i<a.length();i++){\r\n\t\tif(i==0){\r\n\t\t\tchange(i);\r\n\t\t}\r\n\t\telse{\r\n\t\t\tchange(i-1);\r\n\t\t\tchange(i);\r\n\t\t}\/\/\u66f4\u6362\u6570\u5b57\r\n\t\t\/\/\u6b64\u65f6\u662f\u4e8c\u8fdb\u5236\u5b57\u7b26\u4e32\r\n\t\tint ans=-1;\r\n\t\tans=cvs(er_shi(a));\/\/\u4fdd\u5b58\u7b54\u6848\r\n\t\tif(cmp(shi_san(er_shi(a)))){\r\n\t\t\tcout<<ans;\r\n\t\t\treturn 0;\r\n\t\t}\r\n\t\telse continue;\r\n\t}\r\n\treturn 0;\r\n}<\/code><\/pre>\n\n\n\n
\n\n\n\n
T3 \u5c0f\u5361\u548c\u8d28\u6570\uff08P8845\uff09<\/h2>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
#include <iostream>\r\nint main(){\r\n\tint t,a,b;\r\n\tstd::cin>>t;\r\n\twhile(t--){\r\n\t\tstd::cin>>a>>b;\r\n\t\tif((a==1&&b==2)||(a==2&&b==1)) std::cout<<\"Yes\"<<std::endl;\r\n\t\telse std::cout<<\"No\"<<std::endl;\r\n\t}\r\n\treturn 0;\r\n}<\/code><\/pre>\n\n\n\n
\n","protected":false},"excerpt":{"rendered":"
T1 \u5b9d\u7269\u7b5b\u9009\uff08P1776\uff09 \u672a\u4f18\u5316\uff0c\u5f53\u6210\u591a\u91cd\u80cc\u5305\u505a\u3002 \u4e8c\u8fdb\u5236\u4f18\u5316\u540e\uff08\u8282\u7701\u4e86\u5927\u91cf\u7a7a\u95f4\uff09 T2 \u5c34\u5c2c\u7684\u6570\u5b57\uff08P1 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","footnotes":""},"categories":[3,1],"tags":[],"class_list":["post-145","post","type-post","status-publish","format-standard","hentry","category-3","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts\/145","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/comments?post=145"}],"version-history":[{"count":1,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts\/145\/revisions"}],"predecessor-version":[{"id":149,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts\/145\/revisions\/149"}],"wp:attachment":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/media?parent=145"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/categories?post=145"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/tags?post=145"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}