#!/usr/bin/env python3 """Move standalone C++ solutions out of lessons and insert core pseudocode. This is an idempotent course-layout migration. It identifies the nearest preceding VJudge problem link for each fenced block containing main(), writes the block to 参考实现//.cpp, and replaces it with concise Python-like pseudocode plus a relative attachment link. """ from __future__ import annotations import re from pathlib import Path PSEUDOCODE: dict[str, str] = { "POJ-2230": """for each road (u, v): add_arc(u, v); add_arc(v, u) stack = [1]; reversed_route = [] while stack: u = stack[-1] if u still has an unused outgoing arc: stack.append(take_one_arc(u)) else: reversed_route.append(stack.pop()) output reverse(reversed_route)""", "HDU-1116": """for each word: add directed edge first_letter -> last_letter update in_degree, out_degree, and undirected DSU connected = all nonzero-degree letters have one DSU root degree_ok = all differences are 0, or exactly one +1 and one -1 answer = connected and degree_ok""", "CodeForces-508D": """encode every length-2 string as a vertex for trigram xyz: add edge xy -> yz check directed Euler degree conditions and select start path = Hierholzer(start) if len(path) != edge_count + 1: print NO else: print first 2-char vertex, then append each later vertex's last char""", "CodeForces-723E": """answer = number of even-degree original vertices add dummy vertex 0 and edge 0-v for every odd-degree vertex v for every augmented connected component: follow an Euler circuit and orient each traversed original edge forward discard dummy edges and output recorded original orientations""", "CodeForces-427C": """components = Tarjan_SCC(graph) total_cost = 0; ways = 1 for component in components: best = minimum(cost[v] for v in component) total_cost += best ways *= count(v in component where cost[v] == best) (mod MOD)""", "POJ-1236": """component = Tarjan_SCC(graph) if there is only one component: output 1, 0 build condensation indegree and outdegree sources = count(indegree == 0) sinks = count(outdegree == 0) output sources, max(sources, sinks)""", "POJ-2186": """component = Tarjan_SCC(graph) compute every condensation component's size and outdegree sink_components = components with outdegree 0 if len(sink_components) != 1: output 0 else: output size of the unique sink component""", "CodeForces-1000E": """bridges = find_bridges_with_edge_ids(graph) component = flood_fill_while_ignoring(bridges) bridge_tree = contract_components_and_keep_bridges() a = farthest_vertex(bridge_tree, arbitrary_root) b, distance = farthest_vertex(bridge_tree, a) output distance""", "POJ-3177": """bridges = find_bridges_with_edge_ids(graph) component = flood_fill_while_ignoring(bridges) degree = degrees in the contracted bridge tree leaves = count(degree == 1) output ceil(leaves / 2)""", "CodeForces-732F": """find bridges and edge-biconnected components root = component with maximum number of original vertices inside each component: orient DFS-tree edges down and back edges up build the bridge tree rooted at root orient every bridge from child component toward parent component output size(root) and all orientations in input order""", "POJ-1144": """DFS(u, parent_edge): dfn[u] = low[u] = next_time() for each edge u-v except parent_edge: if v unvisited: DFS(v); low[u] = min(low[u], low[v]) if u is non-root and low[v] >= dfn[u]: mark u as cut else: low[u] = min(low[u], dfn[v]) root is cut iff it has at least two DFS children""", "CodeForces-962F": """during undirected Tarjan, push tree/back edge IDs on a stack when low[child] >= dfn[parent]: pop through the parent-child edge to obtain one vertex-biconnected block vertices = distinct endpoints of popped edges if number_of_edges == number_of_vertices: add every block edge to answer sort and output answer edge IDs""", "AtCoder-abc258_g": """neighbor[i] = bitset of vertices adjacent to i sum = 0 for every edge i-j with i < j: sum += popcount(neighbor[i] AND neighbor[j]) output sum / 3""", "CodeForces-1097F": """state[x][d] = parity of elements in multiset x divisible by d singleton(v): set exactly the divisor bits of v union(y, z): state[x] = state[y] XOR state[z] gcd_product(y, z): state[x] = state[y] AND state[z] query(v): parity = popcount(state[x] AND squarefree_multiple_mask[v]) mod 2""", "CodeForces-914F": """position[c] = bitset of indices currently containing c update(i, c): clear i in old character set; set i in c query(l, r, pattern): match = all_ones for offset, c in enumerate(pattern): match &= position[c] >> offset discard start positions outside [l, r-len(pattern)+1] return popcount(match)""", "POJ-3461": """pi = prefix_function(pattern) matched = answer = 0 for c in text: while matched > 0 and c != pattern[matched]: matched = pi[matched-1] if c == pattern[matched]: matched += 1 if matched == len(pattern): answer += 1; matched = pi[matched-1]""", "POJ-2406": """pi = prefix_function(s) period = len(s) - pi[-1] if len(s) is divisible by period: output len(s) / period else: output 1""", "CodeForces-432D": """pi = prefix_function(s) occ[pi[i]] += 1 for every position i for length from n down to 1: occ[pi[length-1]] += occ[length] occ[length] += 1 for each prefix's occurrence at position 0 borders = n, pi[n-1], pi[pi[n-1]-1], ... output reversed(borders) with occ[length]""", "CodeForces-471D": """if target length == 1: output source length text = adjacent_differences(source_heights) pattern = adjacent_differences(target_heights) output KMP_occurrence_count(pattern, text)""", "POJ-3974": """d1 = odd_palindrome_radii_by_Manacher(s) d2 = even_palindrome_radii_by_Manacher(s) answer = max(max(2*d1[i]-1), max(2*d2[i])) output answer""", "CodeForces-17E": """d1, d2 = Manacher(s) P = sum(d1) + sum(d2) for each center and radius: range_add all represented start positions range_add all represented end positions start, end = prefix_sums(the two difference arrays) disjoint = sum(start[i] * number_of_palindromes_ending_before_i) output choose(P, 2) - disjoint (mod MOD)""", "AtCoder-abc340_d": """for each stage i: add edge i -> i+1 with cost A[i] add edge i -> X[i] with cost B[i] dist = Dijkstra(graph, source=1) output dist[N]""", "AtCoder-abc277_e": """state = (vertex, currently_passable_edge_label) for original edge with label a: connect its endpoints in layer a with cost 1 for each switch vertex: connect its two layers with cost 0 dist = zero_one_BFS(start=(1, label_1)) output min(dist[(N,0)], dist[(N,1)])""", "CodeForces-449B": """train[v] = minimum train length to v run road-only Dijkstra with seeds (capital,0) and every finite train[v] mark v if some road u-v satisfies dist[u] + w == dist[v] needed = count(v where train[v] == dist[v] and v has no road predecessor) output total_trains - needed""", "CodeForces-59E": """BFS state is (previous_vertex, current_vertex); start = (0, 1) for neighbor next of current: skip if (previous, current, next) is forbidden visit state (current, next) and store parent state stop at first state whose current vertex is N follow parent states to restore the vertex path""", "CodeForces-229B": """run Dijkstra from planet 1 when finalizing u at time t (unless u is destination): binary-search t in u's sorted blocked times advance depart across the consecutive blocked run t,t+1,... relax every edge using depart + edge_weight output destination distance or -1""", "CodeForces-545E": """run Dijkstra from source on shorter distance to v: replace distance and parent edge on equal distance: replace parent edge only if its own weight is smaller because all weights are positive, chosen parents strictly decrease distance output sum and IDs of one chosen parent edge for every non-source vertex""", "POJ-3255": """first[source] = 0; second[*] = infinity pop a distance label d at u for edge u-v: candidate = d + weight if candidate < first[v]: swap(candidate, first[v]); push first[v] if first[v] < candidate < second[v]: set and push second[v] output second[destination]""", "POJ-3169": """convert every constraint to x[v] <= x[u] + weight and add edge u->v add order edges (i+1)->i with weight 0 if Bellman-Ford from a super-source finds a negative cycle: output -1 dist = Bellman-Ford(source=1) if N is unreachable: output -2 else: output dist[N], the tightest upper bound on x[N]-x[1]""", "AtCoder-arc076_b": """candidates = [] sort towns by x; add every adjacent pair sort towns by y; add every adjacent pair give each candidate its true min(|dx|, |dy|) cost output Kruskal(candidates)""", "CodeForces-1245D": """treat building station i as edge super_source-i with cost c[i] initialize Prim key[i] = c[i], parent[i] = super_source repeat n times: select unused city v with minimum key record station if parent is source, otherwise record wire update every unused city's key by wire_cost(v, city) output total and recorded construction""", "CodeForces-1095F": """hub = vertex with minimum a[hub] candidates = all special offers for every v != hub: add ordinary edge hub-v with cost a[hub]+a[v] output Kruskal(candidates)""", "CodeForces-609E": """T, total = Kruskal_MST(graph) preprocess binary lifting for maximum edge on every tree path for edge e=(u,v,w): if e belongs to T: answer[e] = total else: answer[e] = total + w - maximum_on_tree_path(u,v)""", "CodeForces-160D": """sort edges into equal-weight groups; DSU contains only lighter edges for each group: edges already inside one DSU component are 'none' contract DSU roots and build a temporary multigraph from remaining edges temporary bridges are 'any'; other remaining edges are 'at least one' union all group edges in the global DSU""", "CodeForces-1706E": """process input edges by index; every successful DSU merge creates a new parent node new node value = current edge index; its children are the two old component roots preprocess LCA on the reconstruction tree need[i] = value(LCA(original_vertex_i, original_vertex_i+1)) answer(l,r) = max(need[l .. r-1]), or 0 when l == r""", "CodeForces-888G": """sort and deduplicate values solve(group, bit): split group by current bit answer = solve(zero_side, bit-1) + solve(one_side, bit-1) if both sides exist: build a lower-bit binary trie for the smaller side answer += 2^bit + minimum lower-bit XOR across the split return answer""", "CodeForces-1144F": """two-color the graph if an edge has equal-colored endpoints: output NO otherwise orient every edge from color 0 to color 1 translate each orientation back to a 0/1 character in input order""", "CodeForces-1354E": """two-color every connected component and store its two sides group-knapsack: from each component choose one side so total chosen size is n2 recover choices; label chosen side 2 among all remaining vertices label any n1 as 1 and the rest as 3""", "CodeForces-741C": """make one vertex for each chair add an inequality edge for every romantic pair add inequality edges (1,2), (3,4), ... two-color every resulting even-cycle component output the two colors at each romantic pair's chair positions""", "POJ-1274": """match_right[stall] = unmatched for each cow u: clear visited stalls DFS through acceptable stalls: take an empty stall, or recursively move its currently matched cow count successful augmentations""", "POJ-3041": """rows are left vertices; columns are right vertices each asteroid adds a row-column edge maximum_matching = Kuhn(graph) output maximum_matching # equals minimum vertex cover by Konig""", "CodeForces-1139E": """potential values are left vertices; clubs are right vertices start with students that never get deleted and maintain a matching advance mex while the current potential can be augmented process deletions in reverse: record current mex for that day add the deleted student's potential-club edge continue augmenting from current mex""", "HDU-2255": """initialize left label lx[x] = max_y weight[x][y], right label ly = 0 for every left vertex root: search an augmenting path using only equality edges lx+ly == weight if search fails: delta = minimum slack of every unvisited right vertex subtract delta from visited lx; add it to visited ly; update slack repeat until root is matched output weight sum of the perfect matching""", "CodeForces-498C": """factor all array values and iterate over each distinct prime p capacity[i] = exponent of p in a[i] build flow network: source->odd indices, even indices->sink for every allowed pair add infinite-capacity odd->even edge answer += maximum_flow(network) output answer""", } BLOCK = re.compile(r"```(?:cpp|c\+\+)\n(.*?)```", flags=re.DOTALL) VJUDGE = re.compile(r"https://vjudge\.net/problem/([A-Za-z0-9_-]+)") def main() -> int: course = Path("课程") attachment_root = Path("参考实现") moved = 0 for document in sorted(course.rglob("*.md")): text = document.read_text(encoding="utf-8") output: list[str] = [] cursor = 0 for match in BLOCK.finditer(text): code = match.group(1) if not re.search(r"\bint\s+main\s*\(", code): continue preceding = text[: match.start()] queries = VJUDGE.findall(preceding) if not queries: raise RuntimeError(f"no preceding VJudge ID for {document}") query = queries[-1] if query not in PSEUDOCODE: raise RuntimeError(f"missing pseudocode for {query} in {document}") topic = document.parent.name attachment = attachment_root / topic / f"{query}.cpp" attachment.parent.mkdir(parents=True, exist_ok=True) attachment.write_text(code.rstrip() + "\n", encoding="utf-8") relative = Path("../..") / attachment replacement = ( "```text\n" + PSEUDOCODE[query].rstrip() + "\n```\n\n" + f"完整 GNU C++17 参考实现见附件：[{query}.cpp]({relative.as_posix()})" ) output.append(text[cursor : match.start()]) output.append(replacement) cursor = match.end() moved += 1 if output: output.append(text[cursor:]) document.write_text("".join(output), encoding="utf-8") print(f"moved={moved}") return 0 if __name__ == "__main__": raise SystemExit(main())