{"id":1082,"date":"2014-12-01T11:07:43","date_gmt":"2014-12-01T03:07:43","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=1082"},"modified":"2014-12-01T13:33:54","modified_gmt":"2014-12-01T05:33:54","slug":"2014-acmicpc-asia-beijing-regional-contest-onsite","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/2014-acmicpc-asia-beijing-regional-contest-onsite\/","title":{"rendered":"2014 ACM\/ICPC Asia Beijing Regional Contest Onsite"},"content":{"rendered":"<p><!--more--><br \/>\n<a href=\"http:\/\/acmicpc.info\/archives\/1850\">http:\/\/acmicpc.info\/archives\/1850<\/a><\/p>\n<h2>Problem D. Dire Wolf<\/h2>\n<h3>Brief description: <\/h3>\n<p>\u7565\uff09<\/p>\n<h3>Analysis: <\/h3>\n<p>\u6b63\u96be\u5219\u53cd\u3002\uff09<br \/>\n<a href=\"http:\/\/acm.hust.edu.cn\/vjudge\/contest\/viewSource.action?id=3048048\">http:\/\/acm.hust.edu.cn\/vjudge\/contest\/viewSource.action?id=3048048<\/a><\/p>\n<h2>Problem E. Everlasting L<\/h2>\n<h3>Brief description: <\/h3>\n<p>\u7565\uff09<\/p>\n<h3>Analysis: <\/h3>\n<p>\u6ce8\u610f\u5230\u5750\u6807\u8303\u56f4\u8f83\u5c0f\u3002\u3002\u53ef\u4ee5\u626b\u63cf\u7ebf + \u679a\u4e3e\u3002<\/p>\n<p>\u9884\u5904\u7406\uff1a<br \/>\nD[d][n]: <= n \u4e14\u4e0e d \u4e92\u8d28\u7684\u6570\u6709\u591a\u5c11\u4e2a\u3002\u3002\u3002\nup\uff0crt\uff1a\u5411\u4e0a\u548c\u5411\u53f3\u6700\u8fdc\u53ef\u4ee5\u5ef6\u4f38\u7684\u8ddd\u79bb\u3002\u3002\n\n\n\u4ece\u5de6\u5411\u53f3\u626b\u63cf\u7ebf\u3002\u3002\u3002O(n3) \u5927\u679a\u4e3e\u3002\u3002\u3002\u5206\u4e09\u7c7b\u8ba8\u8bba\u3002\n\uff081. \u518d\u5de6\u8fb9\u4e14\u4e0d\u53ef\u80fd\u4e0e\u4e4b\u76f8\u4ea4\u3002\u3002\n\uff082. \u518d\u5de6\u8fb9\u4e14\u4e0e\u4e4b\u76f8\u4ea4\u3002\u3002\n\uff083. \u540c\u4e00\u5217\u3002\u3002\n\n\u5176\u4e2d 2 \u548c 3 \u53ef\u4ee5\u653e\u5728\u4e00\u8d77\u5904\u7406\u3002\u3002\u3002\u603b\u590d\u6742\u5ea6 $$O(n3)$$\n\n\n[cpp]\n\/\/}\/* .................................................................................................................................. *\/\n\nconst int N = int(2e2) + 9;\n\nint A[N][N], up[N][N], rt[N][N]; int D[N][N]; VII E[N];\n\nint C[N];\n\n\nint main(){\n\n#ifndef ONLINE_JUDGE\n    freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\n    \/\/freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);\n#endif\n\n    \/\/ &lt;= 2 ... 1\n\n    FOR(i, 1, N){\n        FOR(j, 1, N){\n            D[i][j] = D[i][j-1] + (gcd(i, j) == 1);\n        }\n    }\n\n    Rush{\n        RST(A); FLC(up, rt, -1);\n        Rush{int x, y; RD(x, y); A[x][y] = 1;}\n\n        DWN(i, N-1, 0){\n            DWN(j, N-1, 0){\n                rt[i][j] = A[i][j] ? rt[i][j+1] + 1 : -1;\n                up[i][j] = A[i][j] ? up[i+1][j] + 1 : -1;\n            }\n        }\n\n        RST(C); REP(j, N) E[j].clear();\n\n        LL z = 0, pre = 0; REP(j, N){\n\n            ECH(it, E[j]) C[it-&gt;fi] -= it-&gt;se;\n\n            DWN(i, N, 0){\n\n                LL ex = C[i]; REP_1(uu, up[i][j]){\n                    ex += C[i+uu]; int d =  D[uu][rt[i][j]];\n                    z += (pre-ex)*d; C[i] += d, pre += d; ex += d;\n                }\n\n                REP_1(rr, rt[i][j]) E[j+rr+1].PB(MP(i, D[rr][up[i][j]]));\n            }\n        }\n\n        OT(z*2);\n    }\n\n}\n[\/cpp]\n<\/p>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-1082","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-hs","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1082","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=1082"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1082\/revisions"}],"predecessor-version":[{"id":1084,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1082\/revisions\/1084"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1082"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1082"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1082"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}