\u8fd9\u9898<\/a>\u3002\u3002
\n\u3002\u8f7b\u91cd\u94fe\u6811\u94fe\u5256\u5206\u3002\u3002\u6216\u8005 LCA() + DFS() \u90fd\u53ef\u884c\u3002\u3002\uff09<\/p>\nProblem D. Metro Scheme:
\n\u3002\u3002\u8c8c\u4f3c\u6700\u591a\u7684\u5c31\u662f\u8fb9\u6570\u3002\u3002\u4e8e\u662f\u6700\u5c0f\u7684\u600e\u4e48\u6c42 \u3002\u30020w0\uff1f\u3002\u3002
\n\u6211\u5c31\u53bb\u770b\u4e86\u4e00\u773c bjin \u7684\u4ee3\u7801\u3002\u3002\u53d1\u73b0\u53ea\u8981\u5148\u7edf\u8ba1\u4e0b\u6b27\u62c9\u8def\u5f84\u7684\u6570\u76ee\u3002\u3002\u518d\u5728\u539f\u56fe\u4e0a\u627e\u73af\u5c31\u884c\u4e86\u3002\u3002\u3002
\n\u524d\u8005\u7edf\u8ba1\u4e0b\u5947\u6570\u5ea6\u5b9a\u70b9\u6570\u76ee \/ 2 \u3002\u3002\u3002\u540e\u8005\u53ef\u4ee5\u76f4\u63a5\u5728\u56fe\u4e0a\u7f29\u73af\u3002\u30020w0\u3002\u3002\u590d\u6742\u5ea6 O(n)\u3002\u3002\u3002<\/p>\n
Problem E. Thwarting Demonstrations:
\n\u4e8c\u4efd\u7b54\u6848\u5224\u5b9a\uff0c\u5219\u5b50\u95ee\u9898\u4e3a\uff0c\u5927\u4e8e\u7b49\u4e8e x \u7684\u533a\u95f4\u548c\u7684\u6570\u91cf\u8d85\u8fc7 k \u5417\uff1f
\n\u8fd9\u4e2a\u7ecf\u5178\u7684\u5b50\u95ee\u9898\u89e3\u51b3\u529e\u6cd5\u6709\u5f88\u591a\uff0c\u8fd9\u91cc\u7528\u5b9e\u73b0\u6700\u5bb9\u6613\u7684\u6811\u72b6\u6570\u7ec4\u3002
\n\u5927\u6982\u662f\u8fd9\u4e2a\u6837\u5b50\u3002\u3002<\/p>\n
\r\nbool f(LL x, LL k) {\r\n RST(C); REP(i, n){\r\n Add(lower_bound(a, a + n, s[i]) - a + 1, 1);\r\n k -= Sum(lower_bound(a, a + n, s[i+1] - x + 1) - a);\r\n if (k <= 0) return true;\r\n }\r\n return false;\r\n}\r\n<\/pre>\n\u3002\u3002\u3002\u3002<\/p>\n
\r\nint G[26][26], n;\r\n\r\nint main(){\r\n\r\n while (scanf("%d", &n) != EOF && n){\r\n\r\n string s; REP(i, n){\r\n cin >> s; int a = s[0] - 'a', b = s[SZ(s)-1] - 'a';\r\n REP(i, 26) if (G[i][a]) checkMax(G[i][b], G[i][a] + SZ(s));\r\n checkMax(G[a][b], SZ(s));\r\n }\r\n\r\n int ans = 0; REP(i, 26){\r\n checkMax(ans, G[i][i]);\r\n }\r\n\r\n cout << ans << endl;\r\n }\r\n}\r\n<\/pre>\n\r\nconst int N = 100009;\r\n\r\nint A[N], O[N]; LL B;\r\nint n, k;\r\n\r\nbool comp(int a, int b){\r\n return A[a] > A[b] || A[a] == A[b] && a < b;\r\n}\r\n\r\nbool f(int x){\r\n\r\n x = O[x];\r\n\r\n int i = 0, t = k - 1; LL b = B;\r\n\r\n while (t){\r\n if (O[i] == x) ++i;\r\n b -= A[O[i]];\r\n ++i, --t;\r\n }\r\n\r\n return b < A[x];\r\n}\r\n\r\nint main(){\r\n\r\n RD(n, k); cin >> B; REP(i, n) RD(A[i]), O[i] = i; A[n-1] = 0;\r\n sort(O, O + n, comp);\r\n\r\n if (!f(0)){\r\n cout << n << endl;\r\n return 0;\r\n }\r\n\r\n int l = 0, r = n - 2;\r\n\r\n while (l < r){\r\n int m = (l + r + 1) \/ 2;\r\n if (f(m)) l = m;\r\n else r = m - 1;\r\n }\r\n\r\n REP(i, n) if (A[i] >= A[O[l]]){\r\n cout << i + 1 << endl;\r\n return 0;\r\n }\r\n}\r\n<\/pre>\n\r\nconst int N = 100009, M = 2 * N;\r\n\r\nint l[N], r[N], p[N], w0[N], w1[N], delay[N]; bool rt[N];\r\n\/\/ Link-cut tree\r\nint hd[N], nxt[M], a[M], b[M];\r\n\/\/ Adjacent list\r\n\r\nint n, ans;\r\n\r\n#define lx l[x]\r\n#define rx r[x]\r\n\r\n\/\/ private:\r\n\r\ninline void Inc(int x, int d){\r\n if (x == 0) return;\r\n w0[x] += d, w1[x] += d, delay[x] += d;\r\n}\r\n\r\ninline void Release(int x){\r\n if (x == 0) return;\r\n\r\n if (delay[x]){\r\n Inc(lx, delay[x]), Inc(rx, delay[x]);\r\n delay[x] = 0;\r\n }\r\n}\r\n\r\ninline void Update(int x){\r\n w1[x] = w0[x] + w1[lx] + w1[rx];\r\n}\r\n\r\ninline void Set(int l[], int y, int x){\r\n l[y] = x, p[x] = y;\r\n}\r\n\r\n#define z p[y]\r\ninline void Rotate(int x){\r\n int y = p[x];\r\n\r\n if (!rt[y]) Release(z), Set(y == l[z] ? l : r, z, x);\r\n else p[x] = z;\r\n\r\n Release(y), Release(x);\r\n\r\n if (x == l[y]) Set(l, y, rx), Set(r, x, y);\r\n else Set(r, y, lx), Set(l, x, y);\r\n\r\n if (rt[y]) rt[y] = false, rt[x] = true;\r\n Update(y);\r\n}\r\n\r\ninline void Splay(int x){\r\n while (!rt[x]) Rotate(x);\r\n}\r\n\r\ninline int Access(int x){\r\n int y = 0; do{\r\n Splay(x), Release(x);\r\n rt[rx] = true, rt[rx = y] = false, Update(x);\r\n x = p[y = x];\r\n } while (x);\r\n return y;\r\n}\r\n\r\n\/\/ public:\r\n\r\nvoid Query(int x, int y){\r\n Access(y), y = 0; do{\r\n Splay(x); Release(x); if (!p[x]) OT(w1[rx] + w1[y]);\r\n rt[rx] = true, rt[rx = y] = false; Update(x);\r\n x = p[y = x];\r\n\r\n } while (x);\r\n}\r\n\r\nvoid Modify(int x, int y, int w){\r\n Access(y); y = 0; do{\r\n Splay(x), Release(x); if (!p[x]) Inc(rx, w), Inc(y, w);\r\n rt[rx] = true, rt[rx = y] = false, Update(x);\r\n x = p[y = x];\r\n } while (x);\r\n}\r\n\r\n#define v b[i]\r\ninline void dfs(int u = 1){\r\n for(int i=hd[u];i;i=nxt[i]) if (!p[v]){\r\n p[v] = u, dfs(v);\r\n }\r\n}\r\n\r\n\r\nint main(){\r\n\r\n#ifdef LOCAL\r\n \/\/freopen("in01.txt", "r", stdin);\r\n#endif\r\n\r\n FOR_C(i, 2, _RD(n) << 1){\r\n RD(a[i], b[i]), a[i|1] = b[i], b[i|1] = a[i];\r\n nxt[i] = hd[a[i]], hd[a[i]] = i; ++i;\r\n nxt[i] = hd[a[i]], hd[a[i]] = i;\r\n }\r\n\r\n FLC(rt, true), p[1] = -1, dfs(), p[1] = 0;\r\n\r\n int x, y; DO_C(RD()){\r\n RD(x, y); Modify(x, y, 1);\r\n }\r\n\r\n FOR(i, 1, n) Query(a[i<<1], b[i<<1]);\r\n}\r\n<\/pre>\n\r\nconst int N = 100009;\r\nVI adj[N];\r\nint n, m, ans;\r\n\r\nint main() {\r\n\r\n#ifndef ONLINE_JUDGE\r\n\tfreopen("in.txt", "r", stdin);\r\n#endif\r\n\r\n int a, b; RD(n, m); REP(i, m){\r\n RD(a, b), --a, --b, adj[a].PB(b), adj[b].PB(a);\r\n }\r\n\r\n#define deg(x) SZ(adj[x])\r\n\r\n REP(i, n) if (deg(i)&1) ++ans;\r\n ans >>= 1;\r\n\r\n REP(i, n) if (deg(i) == 2){\r\n a = adj[i][0], b = adj[i][1];\r\n if (a == b){\r\n CLR(adj[a]);\r\n ++ans;\r\n }\r\n else {\r\n adj[a][adj[a][0] == i ? 0 : 1] = b;\r\n adj[b][adj[b][0] == i ? 0 : 1] = a;\r\n }\r\n }\r\n\r\n printf("%d %d\\n", ans, m);\r\n}\r\n<\/pre>\n\r\nconst int N = 100009;\r\nint C[N]; LL s[N], a[N];\r\nint n; LL k;\r\n\r\nvoid Add(int x, int d){\r\n for (int i=x;i<=n;i+=low_bit(i)) C[i] += d;\r\n}\r\n\r\nLL Sum(int x){\r\n LL res = 0; for(int i=x;i;i^=low_bit(i)) res += C[i];\r\n return res;\r\n}\r\n\r\nbool f(LL x, LL k) {\r\n RST(C); REP(i, n){\r\n Add(lower_bound(a, a + n, s[i]) - a + 1, 1);\r\n k -= Sum(lower_bound(a, a + n, s[i+1] - x) - a);\r\n if (k <= 0) return true;\r\n\t}\r\n\treturn false;\r\n}\r\n\r\n\/\/((s[r] - s[l-1]) >= x)\r\n\/\/s[l-1] <= s[r] - x ...\r\n\r\nint main() {\r\n\r\n#ifndef ONLINE_JUDGE\r\n\tfreopen("in.txt", "r", stdin);\r\n#endif\r\n\r\n\tscanf("%d %I64d", &n, &k);\r\n\t\/\/scanf("%d %lld", &n, &k);\r\n\r\n\tREP(i, n) s[i+1] = s[i] + RD();\r\n REP(i, n) a[i] = s[i]; sort(a, a + n);\r\n\r\n\tLL l = -1e14 - 1, r = 1e14 - 1;\r\n\twhile (l <= r) {\r\n\t\tLL m = (l + r) \/ 2;\r\n\t\tif (f(m, k)) l = m + 1;\r\n else r = m - 1;\r\n\t}\r\n\r\n\tprintf("%I64d\\n", l);\r\n\t\/\/printf("%lld\\n", l - 1);\r\n}\r\n<\/pre>\nExternal link: <\/h3>\n
http:\/\/www.codeforces.com\/contest\/191\/room\/1
\n<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"Brief description: Problem A. Dynasty Puzzles \u7565\u3002\uff08.G[a][b] \u8868\u793a\u4ee5 a \u5f00\u59cb b \u7ed3\u5c3e\u7684\u6700\u957f\u4e32\u7684\u957f\u5ea6\u3002\u3002\u6700\u540e\u7edf\u8ba1\u6240\u6709 G[a][a] ….<\/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":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[18],"tags":[],"class_list":["post-235","post","type-post","status-publish","format-standard","hentry","category-codeforces"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-3N","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/235","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=235"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/235\/revisions"}],"predecessor-version":[{"id":236,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/235\/revisions\/236"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=235"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=235"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=235"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}