{"id":91,"date":"2022-12-15T18:30:42","date_gmt":"2022-12-15T10:30:42","guid":{"rendered":"https:\/\/www.vcoco.top\/?p=91"},"modified":"2025-05-19T13:48:59","modified_gmt":"2025-05-19T05:48:59","slug":"gplt-2021cccc%e5%a4%a9%e6%a2%af%e8%b5%9b%e9%a2%98%e8%a7%a3","status":"publish","type":"post","link":"https:\/\/www.vcoco.top\/index.php\/2022\/12\/15\/gplt-2021cccc%e5%a4%a9%e6%a2%af%e8%b5%9b%e9%a2%98%e8%a7%a3\/","title":{"rendered":"GPLT 2021CCCC\u5929\u68af\u8d5b\u9898\u89e3"},"content":{"rendered":"\n<ul class=\"wp-block-list\">\n<li>\u975e\u5b98\u65b9\u94fe\u63a5\uff1a<a href=\"https:\/\/www.acwing.com\/activity\/content\/punch_the_clock\/22\/\" target=\"_blank\" rel=\"noreferrer noopener\">https:\/\/www.acwing.com\/activity\/content\/punch_the_clock\/22\/<\/a><\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">L1-\u4eba\u4e0e\u795e<\/h3>\n\n\n\n<p><strong>\u89e3\u9898\u601d\u8def<\/strong><br>\u76f4\u63a5\u8f93\u51fa<code>To iterate is human, to recurse divine.<\/code>\u5373\u53ef<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;iostream&gt;\n\nusing namespace std;\n\nint main()\n{\n    cout&lt;&lt;\"To iterate is human, to recurse divine.\"&lt;&lt;endl;\n    return 0;\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">L1-\u4e24\u5c0f\u65f6\u5b66\u5b8cC\u8bed\u8a00<\/h3>\n\n\n\n<p><strong>\u89e3\u9898\u601d\u8def<\/strong><br>\u5df2\u770b\u7684\u5b57\u6570: $k\\cdot{m}$.<br>\u603b\u5b57\u6570: $N$.<br>\u7b54\u6848\uff08\u5269\u4f59\u5b57\u6570\uff09: $N-k\\cdot{m}$.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;iostream&gt;\n\nusing namespace std;\n\nconst int N=100010;\n\nint n,k,m;\n\nint main()\n{\n    cin&gt;&gt;n&gt;&gt;k&gt;&gt;m;\n    cout&lt;&lt;n-k*m&lt;&lt;endl;\n    return 0;\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">L1-\u5f3a\u8feb\u75c7<\/h3>\n\n\n\n<p><strong>\u89e3\u9898\u601d\u8def<\/strong><br>\u5b57\u7b26\u4e32\u5904\u7406\u95ee\u9898\uff0c<code>s.substr(i,j)<\/code> \u8868\u793a\u4ece\u5b57\u7b26\u4e32s\u7684\u7b2ci\u4f4d\u5f00\u59cb\u5f80\u540e\u622a\u53d6j\u4f4d\u7684\u65b0\u5b57\u7b26\u4e32<br>\u5206\u522b\u5904\u74064\u4f4d\u548c6\u4f4d\u7684\u60c5\u51b5\u5373\u53ef\uff0c\u8be6\u7ec6\u89c1\u4ee3\u7801<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;iostream&gt;\n\nusing namespace std;\n\nint main()\n{\n    string s; cin&gt;&gt;s;\n    if(s.size()==4) {\n        int t=stoi(s.substr(0,2));\n        if(t&lt;22) t=20;\n        else t=19;\n        cout&lt;&lt;to_string(t)+s.substr(0,2)+'-'+s.substr(2)&lt;&lt;endl;\n    } else {\n        cout&lt;&lt;s.substr(0,4)+'-'+s.substr(4)&lt;&lt;endl;\n    }\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">L1-\u964d\u4ef7\u63d0\u9192\u673a\u5668\u4eba<\/h3>\n\n\n\n<p><strong>\u89e3\u9898\u601d\u8def<\/strong><br>\u8f93\u51fa\u6240\u6709\u5c0f\u4e8em\u7684\u503c\uff0c\u683c\u5f0f\u5316\u8f93\u51fa\uff0c\u4fdd\u7559\u4e00\u4f4d\u5c0f\u6570<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;iostream&gt;\n\nusing namespace std;\n\nint n;\ndouble m;\n\nint main()\n{\n    cin&gt;&gt;n&gt;&gt;m;\n    while(n--)\n    {\n        double x; cin&gt;&gt;x;\n        if(x&lt;m) printf(\"On Sale! %.1f\\n\", x);\n    }\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">L1-\u5927\u7b28\u949f\u7684\u5fc3\u60c5<\/h3>\n\n\n\n<p><strong>\u89e3\u9898\u601d\u8def<\/strong><br>\u54c8\u5e0c\u6bcf\u4e00\u4e2a\u65f6\u523b\u7684\u5fc3\u60c5\u6307\u6570\uff0c\u5224\u65ad Yes\/No \u8f93\u51fa<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;iostream&gt;\n\nusing namespace std;\n\nconst int N=110;\n\nint st&#91;N];\n\nint main()\n{\n    for(int i=0;i&lt;24;i++) cin&gt;&gt;st&#91;i];\n    int k; \n    while(cin&gt;&gt;k, k&gt;=0 &amp;&amp; k&lt;=23)\n    {\n        cout&lt;&lt;st&#91;k]&lt;&lt;(st&#91;k]&gt;50?\" Yes\":\" No\")&lt;&lt;endl;    \n    }\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">L1-\u5409\u8001\u5e08\u7684\u56de\u5f52<\/h3>\n\n\n\n<p><strong>\u89e3\u9898\u601d\u8def<\/strong><br>\u5224\u65ad\u6bcf\u4e00\u4e2a\u9898\u76ee\u4e2d\u6709\u65e0<code>\"easy\"<\/code>\u548c<code>\"qiandao\"<\/code>\uff0c\u65e0\u5219\u7d2f\u52a0\u6b21\u6570\uff0c\u6700\u540e\u5224\u65ad\u8f93\u51fa<br><code>s.find(t)<\/code>\u8868\u793a\u5728\u5b57\u7b26\u4e32s\u4e2d\u67e5\u627e\u5b57\u7b26\u4e32t\uff0c\u5e38\u91cf <code>string::npos<\/code> \u8868\u793a\u6ca1\u6709\u67e5\u627e\u5230<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;iostream&gt;\n\nusing namespace std;\n\nconst int N=50;\n\nint n, m;\n\nint main()\n{\n    cin&gt;&gt;n&gt;&gt;m;\n    getchar();\n    int k=0;\n    for(int i=1;i&lt;=n;i++)\n    {\n        string s; getline(cin, s);\n        if(s.find(\"qiandao\")==string::npos &amp;&amp; s.find(\"easy\")==string::npos) { \/\/\u4e24\u4e2a\u90fd\u4e0d\u5b58\u5728\n            k++;\n            if(k&gt;m) {\n                cout&lt;&lt;s&lt;&lt;endl;\n                break;\n            }\n        }\n    }\n\n    if(k&lt;=m) cout&lt;&lt;\"Wo AK le\"&lt;&lt;endl;\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">L1-\u5929\u68af\u8d5b\u7684\u5584\u826f<\/h3>\n\n\n\n<p><strong>\u89e3\u9898\u601d\u8def<\/strong><br>\u7528\u4e24\u4e2a\u53d8\u91cf\u5b58\u4e00\u4e2a\u6700\u5927\u503c\u548c\u6700\u5c0f\u503c\uff0c\u518d\u5faa\u73af\u4e00\u904d\u8ba1\u7b97\u7b54\u6848<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;iostream&gt;\n\nusing namespace std;\n\nconst int N=20010;\n\nint n, a&#91;N];\n\nint main()\n{\n    cin&gt;&gt;n;\n    int minv=1e9, maxv=0;\n    for(int i=1;i&lt;=n;i++) \n    {\n        scanf(\"%d\", &amp;a&#91;i]);\n        minv=min(minv, a&#91;i]);\n        maxv=max(maxv, a&#91;i]);\n    }\n\n    int res1=0, res2=0;\n    for(int i=1;i&lt;=n;i++) \n    {\n        if(a&#91;i]==minv) res1++;\n        if(a&#91;i]==maxv) res2++;\n    }\n\n    cout&lt;&lt;minv&lt;&lt;' '&lt;&lt;res1&lt;&lt;endl;\n    cout&lt;&lt;maxv&lt;&lt;' '&lt;&lt;res2&lt;&lt;endl;\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">L1-\u4e58\u6cd5\u53e3\u8bc0\u5e8f\u5217<\/h3>\n\n\n\n<p><strong>\u89e3\u9898\u601d\u8def<\/strong><br>\u52a8\u6001\u5904\u7406\uff0c\u6bcf\u6b21\u4e58\u79ef\u6700\u5927\u662f81\uff0c\u4e24\u4f4d\u6570<br>\u4e00\u76f4\u5904\u7406\u5230\u5e8f\u5217\u957f\u5ea6\u8fbe\u5230n\u4e3a\u6b62<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;bits\/stdc++.h&gt;\n\nusing namespace std;\n\nint n;\n\nint main()\n{\n    int a1, a2; cin&gt;&gt;a1&gt;&gt;a2&gt;&gt;n;\n    vector&lt;int&gt; res({a1, a2});\n    for(int i=0;res.size()&lt;n;i++)\n    {\n        int m=res&#91;i]*res&#91;i+1];\n        if(m&gt;=10) res.push_back(m\/10);\n        res.push_back(m%10);\n    }\n\n    cout&lt;&lt;res&#91;0];\n    for(int i=1;i&lt;n;i++) cout&lt;&lt;' '&lt;&lt;res&#91;i];\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">L2-\u5305\u88c5\u673a<\/h3>\n\n\n\n<p><strong>\u89e3\u9898\u601d\u8def<\/strong><br>\u6a21\u62df\uff0c\u6ce8\u610f\u4e00\u4e9b\u7ec6\u8282\u5904\u7406<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;bits\/stdc++.h&gt;\n#define x first\n#define y second\n#define all(x) x.begin(),x.end()\nusing namespace std;\ntypedef long long LL;\ntypedef unsigned long long ULL;\ntypedef pair&lt;int,int&gt; PII;\ntypedef pair&lt;LL,int&gt; PLI;\nconst int INF=0x3f3f3f3f,MOD=1000000007,P=131,N=110;\n\nint n,m,S;\nstring orbit&#91;N];\nstack&lt;int&gt; basket;\nstring res;\n\nint main()\n{\n    cin&gt;&gt;n&gt;&gt;m&gt;&gt;S;\n    for(int i=1;i&lt;=n;i++) \n    {\n        cin&gt;&gt;orbit&#91;i];\n        reverse(all(orbit&#91;i]));\n    }\n    int x;\n    while(cin&gt;&gt;x, x!=-1)\n    {\n        if(x==0 &amp;&amp; basket.size()&gt;0) \n        {\n            res.push_back(basket.top());\n            basket.pop();\n        }\n        if(orbit&#91;x].size()&gt;0)\n        {\n            if(basket.size()==S) \n            {\n                res.push_back(basket.top());\n                basket.pop();\n            }\n            basket.push(orbit&#91;x].back());\n            orbit&#91;x].pop_back();\n        }\n    }\n\n    cout&lt;&lt;res&lt;&lt;endl;\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">L2-\u75c5\u6bd2\u6714\u6e90<\/h3>\n\n\n\n<p><strong>\u89e3\u9898\u601d\u8def<\/strong><br>\u9996\u5148\u5206\u6790\u9898\u76ee\uff0c\u6bcf\u79cd\u75c5\u6bd2\u53ea\u80fd\u7531\u4e00\u79cd\u75c5\u6bd2\u53d8\u5f02\u800c\u6765\uff0c\u6240\u4ee5\u662f\u6811\u7ed3\u6784\u3002\u7136\u540edfs\u904d\u5386\u4e00\u904d\u3002\u8981\u4ece\u6839\u8282\u70b9\u51fa\u53d1\uff08\u5165\u5ea6\u4e3a0\u7684\u70b9: <code>d[root]=0<\/code>\uff09\uff0c\u957f\u5ea6\u76f8\u540c\u8981\u6ce8\u610f\u5b57\u5178\u5e8f\u6700\u5c0f\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;bits\/stdc++.h&gt;\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 &lt;= r; i++)\nusing namespace std;\ntypedef long long LL;\ntypedef unsigned long long ULL;\ntypedef pair&lt;int,int&gt; PII;\ntypedef pair&lt;LL,int&gt; PLI;\nconst int INF=0x3f3f3f3f,MOD=1000000007,P=131,N=10010,M=1000010;\n\nint h&#91;N], e&#91;M], ne&#91;M], idx;\nint n, d&#91;N];\nint nex&#91;N];\n\nvoid add(int a, int b)\n{\n    e&#91;idx]=b, ne&#91;idx]=h&#91;a], h&#91;a]=idx++;\n}\n\nint dfs(int u)\n{\n    int res=0, val=-1;\n    for(int i=h&#91;u];~i;i=ne&#91;i])\n    {\n        int j=e&#91;i];\n        int t=dfs(j);\n        if(t&gt;res || (t==res &amp;&amp; j&lt;val)) nex&#91;u]=j, res=t, val=j; \n    }\n\n    return res+1;\n}\n\n\nint main()\n{\n    cin&gt;&gt;n;\n    memset(h, -1, sizeof h);\n    memset(nex, -1, sizeof nex);\n\n    for(int i=0;i&lt;n;i++)\n    {\n        int num; scanf(\"%d\", &amp;num);\n        while(num--)\n        {\n            int x; scanf(\"%d\", &amp;x);\n            add(i, x);\n            d&#91;x]++;\n        }\n    }\n\n    int root=-1;\n    for(int i=0;i&lt;n;i++) \n        if(d&#91;i]==0) \n        {\n            root=i;\n            break;\n        }\n\n    dfs(root);\n    vector&lt;int&gt; res({root});\n    while(nex&#91;root]!=-1)\n    {\n        res.push_back(nex&#91;root]);\n        root=nex&#91;root];\n    }\n\n    cout&lt;&lt;res.size()&lt;&lt;'\\n'&lt;&lt;res&#91;0];\n    for(int i=1;i&lt;res.size();i++) cout&lt;&lt;' '&lt;&lt;res&#91;i];\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">L2-\u6e05\u70b9\u4ee3\u7801\u5e93<\/h3>\n\n\n\n<p><strong>\u89e3\u9898\u601d\u8def<\/strong><br><strong>\u505a\u6cd51<\/strong>\uff1a\u53ef\u4ee5\u7528<code>map<\/code>\u505a\uff0c\u4f1a\u6bd4\u8f83\u597d\u5199\uff0ckey\u503c\u662f\u6bcf\u4e00\u4e2a\u5e8f\u5217\uff0c\u7528<code>vector<\/code>\u5b58\u50a8\uff0c\u9ed8\u8ba4\u6309<code>vector<\/code>\u91cc\u6bcf\u4e00\u4e2a\u9879\u7684\u503c\u6765\u6392\u5e8f\u3002value\u662f\u51fa\u73b0\u7684\u6b21\u6570\u3002\u6700\u540e\u6392\u5e8f\u4e00\u904d\u8f93\u51fa\u3002<br><strong>\u505a\u6cd52<\/strong>\uff1a<code>unnordered_map<\/code> + \u81ea\u5b9a\u4e49\u6392\u5e8f\u89c4\u5219\u4e5f\u53ef\u4ee5\u505a\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;bits\/stdc++.h&gt;\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 &lt;= r; i++)\n#define nep(i, r, l) for (int i = r; i &gt;= l; i--)\nusing namespace std;\ntypedef long long LL;\ntypedef unsigned long long ULL;\ntypedef pair&lt;int,int&gt; PII;\ntypedef pair&lt;LL,int&gt; PLI;\nconst int INF=0x3f3f3f3f,MOD=1000000007,P=18869,N=10010,M=110;\n\nint n, m;\nmap&lt;vector&lt;int&gt;, int &gt; mp;\nvector&lt;pair&lt;int, vector&lt;int&gt;&gt; &gt; ans;\n\nint main()\n{\n    cin&gt;&gt;n&gt;&gt;m;\n    rep(i,1,n)\n    {\n        vector&lt;int&gt; t;\n        rep(j,1,m) \n        {\n            int x; scanf(\"%d\", &amp;x);\n            t.push_back(x);\n        }\n        mp&#91;t]++;\n    }\n\n    for(auto val: mp) ans.push_back({-val.y, val.x});\n\n    sort(all(ans));\n    cout&lt;&lt;ans.size()&lt;&lt;endl;\n    for(int i=0;i&lt;ans.size();i++)\n    {\n        printf(\"%d\", -ans&#91;i].x);\n        for(auto x: ans&#91;i].y) printf(\" %d\", x);\n        puts(\"\");\n    }\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">L2-\u54f2\u54f2\u6253\u6e38\u620f<\/h3>\n\n\n\n<p><strong>\u89e3\u9898\u601d\u8def<\/strong><br>\u4e5f\u662f\u4e00\u9053\u6a21\u62df\u9898<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;bits\/stdc++.h&gt;\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 &lt;= r; i++)\nusing namespace std;\ntypedef long long LL;\ntypedef unsigned long long ULL;\ntypedef pair&lt;int,int&gt; PII;\ntypedef pair&lt;LL,int&gt; PLI;\nconst int INF=0x3f3f3f3f,MOD=1000000007,P=131,N=100010,M=2*N;\n\nint n, m;\nvector&lt;int&gt; plot&#91;N];\nint arch&#91;N];\n\nint main()\n{\n    cin&gt;&gt;n&gt;&gt;m;\n    rep(i,1,n)\n    {\n        int K; scanf(\"%d\",&amp;K);\n        while(K--) {\n            int x; scanf(\"%d\", &amp;x);\n            plot&#91;i].push_back(x);\n        }\n    }\n\n    int location=1;\n    while(m--)\n    {\n        int op,k;\n        scanf(\"%d%d\", &amp;op,&amp;k);\n        if(op==0) location=plot&#91;location]&#91;k-1];\n        else if(op==1){\n            printf(\"%d\\n\", location);\n            arch&#91;k]=location;\n        } else location=arch&#91;k];\n    }\n\n    cout&lt;&lt;location&lt;&lt;endl;\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\">L3-\u68ee\u68ee\u65c5\u6e38<\/h3>\n\n\n\n<p><strong>\u89e3\u9898\u601d\u8def<\/strong><br>\u56fe\u8bba\u9898<br><strong>\u505a\u6cd51<\/strong>\uff1a\u5206\u522b\u5b58\u4e00\u4e2a\u8d77\u70b9\u548c\u7ec8\u70b9\u5230\u6240\u6709\u70b9\u7684\u8ddd\u79bb\uff0c\u7528<code>dist1<\/code>\u548c<code>dist2<\/code>\u6765\u8868\u793a\uff0c\u7528dijkstra\u5904\u7406\u3002<br>\u56e0\u4e3a\u8981\u5728\u67d0\u4e00\u4e2a\u70b9\u5168\u90e8\u6362\u6210\u65c5\u6e38\u91d1\uff0c\u6240\u4ee5\u4ee5\u8fd9\u4e2a\u4e2d\u9014\u70b9\u4e3a\u5355\u4f4d\uff08\u6362\u6210\u65c5\u6e38\u91d1\uff09\u6c42\u4e00\u904d\u8d77\u70b9\u5230\u7ec8\u70b9\u7684\u8d39\u7528\uff0c\u653e\u8fdb\u5806\u4e2d\uff0c\u65b9\u4fbf\u6c42\u6700\u5c0f\u503c\u3002\u6bcf\u4e00\u4e2a\u4e2d\u9014\u70b9\u8ba1\u7b97\u8d77\u70b9\u5230\u7ec8\u70b9\u7684\u8d39\u7528\u4e3a\uff1a$$dist1[i]+(dist2[i]+a[i]-1)\/a[i]$$\uff0c\u52a0<code>a[i]-1<\/code>\u662f\u4e0a\u53d6\u6574\u3002<br>\u6700\u540e\u5904\u7406\u6bcf\u4e00\u4e2a\u6c47\u7387\u53d8\u5316\u5373\u53ef\u3002\u7531\u4e8e\u6bcf\u4e00\u6b21\u6c47\u7387\u53d8\u5316\u90fd\u653e\u8fdb\u5806\u91cc\uff0c\u6240\u4ee5\u53ef\u80fd\u5b58\u5728\u4e4b\u524d\u7684\u6c47\u7387\u6ca1\u6709\u5220\u9664\uff0c\u56e0\u6b64\u53d6\u5806\u9876\u7684\u65f6\u5019\u8981\u7279\u5224\u6bcf\u4e00\u4e2a\u6570\u636e\uff0c\u5982\u679c\u8ba1\u7b97\u51fa\u6765\u7684\u8d39\u7528\u4e0e\u5f53\u524d\u6c47\u7387\u8ba1\u7b97\u51fa\u6765\u7684\u4e0d\u4e00\u6837\uff0c\u5c31\u662f\u65e7\u6570\u636e\u3002<\/p>\n\n\n\n<p><strong>\u505a\u6cd52<\/strong>\uff1a\u7528pair\u5c06\u8d39\u7528\u548c\u8282\u70b9\u6346\u7ed1\u5904\u7406\uff0c\u518d\u7528set\u53bb\u91cd\uff0c\u8fd9\u6837 \u53ef\u4ee5\u5220\u9664\u539f\u5148\u7684\u6c47\u7387\uff0c\u7528<code>set<\/code>\u5185\u7f6e\u7684<code>find<\/code>\u51fd\u6570\u67e5\u627e\u5220\u9664\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;bits\/stdc++.h&gt;\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 &lt;= r; i++)\n#define nep(i, r, l) for (int i = r; i &gt;= l; i--)\nusing namespace std;\ntypedef long long LL;\ntypedef unsigned long long ULL;\ntypedef pair&lt;int,int&gt; PII;\ntypedef pair&lt;LL,int&gt; PLI;\nconst int INF=0x3f3f3f3f, MOD=1000000007,P=131,N=100010,M=4*N;\nconst LL LNF=0x3f3f3f3f3f3f3f3f;\n\nint h1&#91;N], h2&#91;N], e&#91;M], ne&#91;M], w&#91;M], idx;\nLL dist1&#91;N], dist2&#91;N];\nbool st&#91;N];\nint n, m, q;\nint a&#91;N];\npriority_queue&lt;PLI, vector&lt;PLI&gt;, greater&lt;PLI&gt;&gt; heap;\n\nvoid add(int a, int b, int c, int d)\n{\n    e&#91;idx]=b, w&#91;idx]=c, ne&#91;idx]=h1&#91;a], h1&#91;a]=idx++;\n    e&#91;idx]=a, w&#91;idx]=d, ne&#91;idx]=h2&#91;b], h2&#91;b]=idx++;\n}\n\nvoid dijkstra(LL dist&#91;], int s, int h&#91;])\n{\n    memset(st, 0, sizeof st);\n    memset(dist, 0x3f, sizeof dist1);\n    priority_queue&lt;PLI, vector&lt;PLI&gt;, greater&lt;PLI&gt;&gt; q;\n    q.push({0, s});\n    dist&#91;s]=0;\n    while(q.size())\n    {\n        PLI t=q.top(); q.pop();\n        if(st&#91;t.y]) continue;\n        st&#91;t.y]=true;\n\n        for(int i=h&#91;t.y];~i;i=ne&#91;i])\n        {\n            int j=e&#91;i];\n            if(st&#91;j]) continue;\n            dist&#91;j]=min(dist&#91;j], dist&#91;t.y]+w&#91;i]);\n            q.push({dist&#91;j], j});\n        }\n    }\n}\n\nint main()\n{\n    cin&gt;&gt;n&gt;&gt;m&gt;&gt;q;\n    memset(h1, -1, sizeof h1);\n    memset(h2, -1, sizeof h2);\n    while(m--)\n    {\n        int a, b, c, d; scanf(\"%d%d%d%d\", &amp;a, &amp;b, &amp;c, &amp;d);\n        add(a, b, c, d);\n    }\n\n    dijkstra(dist1, 1, h1);\n    dijkstra(dist2, n, h2);\n\n    rep(i,1,n) \n    {\n        scanf(\"%d\", &amp;a&#91;i]);\n        if(dist1&#91;i]!=LNF &amp;&amp; dist2&#91;i]!=LNF) \n            heap.push({dist1&#91;i]+(dist2&#91;i]+a&#91;i]-1)\/a&#91;i], i});\n    }\n\n    while(q--)\n    {\n        int x, aa; scanf(\"%d%d\", &amp;x, &amp;aa);\n        a&#91;x]=aa;\n        if(dist1&#91;x]!=LNF &amp;&amp; dist2&#91;x]!=LNF) heap.push({dist1&#91;x]+(dist2&#91;x]+aa-1)\/aa, x});\n        while(true)\n        {\n            PLI t=heap.top();\n            if((dist2&#91;t.y]+a&#91;t.y]-1)\/a&#91;t.y]+dist1&#91;t.y] != t.x){ \/\/\u6c47\u7387\u66f4\u6539\u4e86\n                heap.pop();\n                continue;\n            }\n            printf(\"%lld\\n\", t.x);\n            break;\n        }\n    }\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">L3-\u8fd8\u539f\u6587\u4ef6<\/h3>\n\n\n\n<p><strong>\u89e3\u9898\u601d\u8def<\/strong><br>\u66b4\u641c\uff0c\u867d\u8bf4\u662f\u66b4\u641c\uff0c\u4f46\u662f\u522b\u592a\u66b4\u529b\uff0c\u6bcf\u4e00\u7ec4\u5e8f\u5217\u54c8\u5e0c\u6210\u4e00\u4e2a\u503c\uff0c\u8fd9\u6837\u4e0d\u4f1aTLE\u3002<br>\uff0c\u6bcf\u4e00\u6b21\u641c\u7d22\u5224\u65ad\u54c8\u5e0c\u503c\u662f\u5426\u5339\u914d\u5373\u53ef\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;bits\/stdc++.h&gt;\n#define rep(i, l, r) for (int i = l; i &lt;= r; i++)\nusing namespace std;\ntypedef unsigned long long ULL;\nconst int INF=0x3f3f3f3f,MOD=1000000007,P=131,N=100010,M=110;\n\nULL hup&#91;N], p&#91;N], hdown&#91;M];\nint width&#91;M];\nint n, m, h&#91;N];\nint ans&#91;M];\nbool st&#91;M];\n\nULL get_hcode(int l, int r)\n{\n    return hup&#91;r]-hup&#91;l-1]*p&#91;r-l+1];\n}\n\nbool dfs(int u, int s)\n{\n    if(s==n) return true;\n    for(int i=1;i&lt;=m;i++)\n    {\n        int e=s+width&#91;i]-1;\n        if(st&#91;i]) continue;\n        if(e&lt;=n &amp;&amp; hdown&#91;i]==get_hcode(s, e)) {\n            st&#91;i]=true;\n            ans&#91;u]=i;\n            if(dfs(u+1, e)) return true;\n            st&#91;i]=false;\n        }\n    }\n\n    return false;\n}\n\nint main()\n{\n    cin&gt;&gt;n;\n    p&#91;0]=1;\n    rep(i,1,n) \n    {\n        scanf(\"%d\", &amp;h&#91;i]);\n        p&#91;i]=p&#91;i-1]*P;\n        hup&#91;i]=hup&#91;i-1]*P+h&#91;i];\n    }\n    cin&gt;&gt;m;\n    rep(i,1,m){\n        scanf(\"%d\", &amp;width&#91;i]);\n        rep(j,1,width&#91;i]) {\n            int x; scanf(\"%d\", &amp;x);\n            hdown&#91;i]=hdown&#91;i]*P+x;\n        }\n    }\n\n    dfs(1, 1);\n\n    printf(\"%d\", ans&#91;1]);\n    rep(i,2,m) printf(\" %d\", ans&#91;i]);\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">L3-\u53ef\u601c\u7684\u7b80\u5355\u9898<\/h3>\n\n\n\n<p><strong>\u89e3\u9898\u601d\u8def<\/strong><br>\u4e0d\u4f1a, 2333<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u603b\u7ed3<\/h3>\n\n\n\n<p>L1\u66f4\u504f\u5411\u8bed\u6cd5\u9898\uff0c\u89e3\u91ca\u8f83\u5c11\uff0c\u5c0f\u767d\u770b\u4e0d\u61c2\u7684\u8bed\u6cd5\u90e8\u5206\u53ef\u4ee5\u4e0a\u7f51\u641c\u7d22<br>L2\u591a\u5c5e\u6a21\u62df\u9898\u548c\u7b97\u6cd5\u9898<br>L3\u591a\u5c5e\u7b97\u6cd5\u9898<\/p>\n","protected":false},"excerpt":{"rendered":"<p>L1-\u4eba\u4e0e\u795e \u89e3\u9898\u601d\u8def\u76f4\u63a5\u8f93\u51faTo iterate is human, to recurse divine.\u5373 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":171,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12],"tags":[30,65,28,48,67,50,66],"class_list":["post-91","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-pta","tag-dfs","tag-dijkstra","tag-hash","tag-48","tag-67","tag-50","tag-66"],"_links":{"self":[{"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/posts\/91","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=91"}],"version-history":[{"count":3,"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/posts\/91\/revisions"}],"predecessor-version":[{"id":562,"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/posts\/91\/revisions\/562"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/media\/171"}],"wp:attachment":[{"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/media?parent=91"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/categories?post=91"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.vcoco.top\/index.php\/wp-json\/wp\/v2\/tags?post=91"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}