{"id":172,"date":"2019-04-29T02:30:12","date_gmt":"2019-04-28T18:30:12","guid":{"rendered":"http:\/\/wwwwodddd.com\/?p=172"},"modified":"2019-05-03T22:49:12","modified_gmt":"2019-05-03T14:49:12","slug":"gcj-2019-r1b","status":"publish","type":"post","link":"https:\/\/wwwwodddd.com\/wordpress\/gcj-2019-r1b\/","title":{"rendered":"Google Code Jam 2019 Round 1B"},"content":{"rendered":"<p><!--more--><\/p>\n<p>\u5b89\u5168\u9a7e\u9a76\uff0c\u5c0f\u5fc3\u7ffb\u8f66\u3002<br \/>\nR1A\u7ffb\u8f66\u4e86\uff0cR1B\u518d\u8d70\u4e00\u904d\u3002<\/p>\n<p>T3\u5c45\u7136\u6ca1\u60f3\u51fa\u6765\uff0c\u96be\u8fc7\u3002<\/p>\n<h2>T1<\/h2>\n<p>\u968f\u4fbf\u7edf\u8ba1\u4e00\u4e0b\u5c31\u53ef\u4ee5\u4e86<\/p>\n<pre><code class=\"language-cpp line-numbers\">#include &lt;bits\/stdc++.h&gt;\nusing namespace std;\nint t, n, m;\nint a[100020];\nint b[100020];\nint main() {\n    cin &gt;&gt; t;\n    for (int tt = 1; tt &lt;= t; tt++) {\n        cin &gt;&gt; n &gt;&gt; m;\n        int x, y;\n        char c;\n        for (int i = 0; i &lt;= m; i++) {\n            a[i] = 0;\n            b[i] = 0;\n        }\n        for (int i = 0; i &lt; n; i++) {\n            cin &gt;&gt; x &gt;&gt; y &gt;&gt; c;\n            if (c == 'W') {\n                a[0]++;\n                a[x]--;\n            } else if (c == 'E') {\n                a[x + 1]++;\n            } else if (c == 'S') {\n                b[0]++;\n                b[y]--;\n            } else if (c == 'N') {\n                b[y + 1]++;\n            }\n        }\n        for (int i = 1; i &lt;= m; i++) {\n            a[i] += a[i - 1];\n            b[i] += b[i - 1];\n        }\n        int pa = max_element(a, a + m + 1) - a;\n        int pb = max_element(b, b + m + 1) - b;\n        printf(\"Case #%d: %d %d\\n\", tt, pa, pb);\n    }\n    return 0;\n}\n<\/code><\/pre>\n<h2>T2<\/h2>\n<p>\u5927\u6982\u5c31\u662f\u53ea\u80fd\u8be2\u95ee2\u6b21\uff0c\u505a\u6cd5\u662d\u7136\u82e5\u63ed\u3002<\/p>\n<pre><code class=\"language-cpp line-numbers\">#include &lt;bits\/stdc++.h&gt;\nusing namespace std;\nint t, w;\nint main() {\n    cin &gt;&gt; t &gt;&gt; w;\n    for (int tt = 0; tt &lt; t; tt++) {\n        cout &lt;&lt; 200 &lt;&lt; endl;\n        fflush(stdout);\n        long long x;\n        cin &gt;&gt; x;\n        int r4 = x &gt;&gt; 50 &amp; 127;\n        int r5 = x &gt;&gt; 40 &amp; 127;\n        int r6 = x &gt;&gt; 33 &amp; 127;\n        cout &lt;&lt; 50 &lt;&lt; endl;\n        fflush(stdout);\n        long long y;\n        cin &gt;&gt; y;\n        y -= r4 &lt;&lt; (50 \/ 4);\n        y -= r5 &lt;&lt; (50 \/ 5);\n        y -= r6 &lt;&lt; (50 \/ 6);\n        int r1 = y &gt;&gt; 50 &amp; 127;\n        int r2 = y &gt;&gt; 25 &amp; 127;\n        int r3 = y &gt;&gt; 16 &amp; 127;\n        cout &lt;&lt; r1 &lt;&lt; ' ' &lt;&lt; r2 &lt;&lt; ' ' &lt;&lt; r3 &lt;&lt; ' ' &lt;&lt; r4 &lt;&lt; ' ' &lt;&lt; r5 &lt;&lt; ' ' &lt;&lt; r6 &lt;&lt; endl;\n        fflush(stdout);\n        int z;\n        cin &gt;&gt; z;\n    }\n    return 0;\n}\n<\/code><\/pre>\n<h2>T3<\/h2>\n<p>\u8fd9\u4e2a\u505a\u6cd5\u662f\u66b4\u529b\uff0c\u6b63\u89e3\u5f85\u8865\u2026\u2026<\/p>\n<pre><code class=\"language-cpp line-numbers\">#include &lt;bits\/stdc++.h&gt;\nusing namespace std;\nint t, n, m;\nint c[1020][1020];\nint d[1020][1020];\nint main() {\n    cin &gt;&gt; t;\n    for (int tt = 1; tt &lt;= t; tt++) {\n        cin &gt;&gt; n &gt;&gt; m;\n        for (int i = 0; i &lt; n; i++) {\n            cin &gt;&gt; c[i][i];\n        }\n        for (int i = 0; i &lt; n; i++) {\n            for (int j = i + 1; j &lt; n; j++) {\n                c[i][j] = max(c[i][j-1], c[j][j]);\n            }\n        }\n        for (int i = 0; i &lt; n; i++) {\n            cin &gt;&gt; d[i][i];\n        }\n        for (int i = 0; i &lt; n; i++) {\n            for (int j = i + 1; j &lt; n; j++) {\n                d[i][j] = max(d[i][j-1], d[j][j]);\n            }\n        }\n        int ans = 0;\n        for (int i = 0; i &lt; n; i++) {\n            for (int j = i; j &lt; n; j++) {\n                if (abs(c[i][j] - d[i][j]) &lt;= m) {\n                    ans++;\n                }\n            }\n        }\n        printf(\"Case #%d: %d\\n\", tt, ans);\n    }\n    return 0;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-172","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/posts\/172","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/comments?post=172"}],"version-history":[{"count":0,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/posts\/172\/revisions"}],"wp:attachment":[{"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/media?parent=172"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/categories?post=172"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wwwwodddd.com\/wordpress\/wp-json\/wp\/v2\/tags?post=172"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}