http:\/\/codeforces.com\/gym\/100159<\/a> <\/p>\n \u3002\u3002\u6211\u4eec\u5b9a\u4e49\u5230 (m, n) \u7684\u7ecf\u8fc7 (a, b) \u7684 2 \u683c\u70b9\u8def\u5f84\u4e3a\u3002\u3002\u3002 … \u9884\u5904\u7406 D[x] \u8868\u793a\u5230\u8fbe\u7ec4\u5408\u6570 x \u6240\u9700\u8981\u7684\u6700\u5c11\u6b65\u6570\u3002\u3002 … \u4e25\u683c\u6309\u7167\u9898\u76ee\u7684\u8981\u6c42\u9012\u5f52\u4e0b\u53bb\u5c31\u597d\u4e86\u3002\u3002\uff09<\/p>\n … \u66b4\u529b DP \u3002\u3002\u6ce8\u610f\u6a21\u6570\u8d85 int\u3002\u3002<\/p>\n External link: http:\/\/codeforces.com\/gym\/100159 http:\/\/www.facebook.com\/hackercup\/scoreboard?round=225705397509134<\/p>\n","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":[109],"tags":[],"class_list":["post-671","post","type-post","status-publish","format-standard","hentry","category-facebook-hacker-cup"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-aP","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/671","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=671"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/671\/revisions"}],"predecessor-version":[{"id":672,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/671\/revisions\/672"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=671"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=671"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=671"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nhttp:\/\/www.facebook.com\/hackercup\/scoreboard?round=225705397509134<\/a><\/p>\nProblem A. Checkpoint<\/h2>\n
Brief description: <\/h3>\n
\n\u3002\u4ece (0, 0) \u51fa\u53d1\u5230 (a, b) \u518d\u5230 (m, n) \u7684\u8def\u5f84\u3002\u3002(a <= m, b <= n)\u3002\u3002\n\u73b0\u5728\u8be2\u95ee\u65b9\u6848\u6570\u7b49\u4e8e S \u7684\u4e8c\u9636\u683c\u70b9\u8def\u5f84\u6700\u5c11\u6709\u591a\u5c11\u6b65\u3002\u3002\u3002\u3002\n\n\n\nAnalysis: <\/h3>\n
\n\u3002\u3002\u4e4b\u540e\u5c06 s \u5206\u89e3\u6210 a * b \u5373\u53ef\u3002\uff08\u3002O(sqrt(s))<\/p>\n\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int N = int(1e7);\r\nint D[N+1];\r\nint s;\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n freopen("in.txt", "r", stdin);\r\n \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n REP_1(i, N) D[i] = i;\r\n\r\n FOR(i, 2, 30){ \/\/ C(j, i) .. .\r\n LL x = 1; for (int j=i;x<=N;++j,x=x*j\/(j-i)){\r\n checkMin(D[x], j);\r\n }\r\n }\r\n\r\n Rush{\r\n int res = RD(s)+1; for (int a=1;sqr(a)<=s;++a){\r\n int b=s\/a; if (a*b!=s) continue;\r\n checkMin(res, D[a]+D[b]);\r\n }\r\n OT(res);\r\n }\r\n}\r\n<\/pre>\nProblem B. Recover the Sequence<\/h2>\n
Note: <\/h3>\n
\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int N = int(1e4) + 9;\r\nint R[N], P[N];\r\nint n;\r\n\r\nvoid gao(int l, int r){\r\n if (l+1 >= r) return;\r\n int m = l + r >> 1;\r\n gao(l, m), gao(m, r);\r\n\r\n int a = l, b = m, i = l;\r\n while (a < m && b < r){\r\n if (RC() == '1') P[i++] = R[a++];\r\n else P[i++] = R[b++];\r\n }\r\n while (a < m) P[i++] = R[a++];\r\n while (b < r) P[i++] = R[b++];\r\n\r\n FOR(i, l, r) R[i] = P[i];\r\n}\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n freopen("in.txt", "r", stdin);\r\n \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n Rush{\r\n REP_C(i, RD(n)) R[i] = i; gao(0, n); REP(i, n) P[R[i]] = i+1;\r\n int res = 1; REP(i, n) MUL(res, 31), INC(res, P[i]);\r\n OT(res);\r\n }\r\n}\r\n<\/pre>\nProblem C. Squished Status<\/h2>\n
Note: <\/h3>\n
\r\nint Case; template<class T> inline void OT(const T &x){\r\n printf("Case #%d: %u\\n", ++Case, x);\r\n \/\/printf("%.2lf\\n", x);\r\n \/\/printf("%d\\n", x);\r\n \/\/cout << x << endl;\r\n}\r\n\/\/}\r\n\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst UINT MOD = 0xfaceb00c;\r\ninline void INC(UINT &a, UINT b){LL aa = a; aa += b; if (aa >= MOD) aa -= MOD; a = aa;}\r\n\r\nconst int N = 1009;\r\nchar str[N]; UINT dp[N], n, m;\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n freopen("in.txt", "r", stdin);\r\n \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n Rush{\r\n RD(m); n = strlen(RS(str));\r\n REP_S(cur, str) *cur -= '0';\r\n RST(dp), dp[0] = 1; REP(i, n) if (dp[i] && str[i]){\r\n int x = 0; FOR(j, i, n){\r\n x *= 10, x += str[j]; if (x > m) break;\r\n INC(dp[j+1], dp[i]);\r\n }\r\n }\r\n OT(dp[n]);\r\n }\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"