ELSE K: = M 1;
END;
a [i]: = a [0]; {Put the root in the right position}
END;
Procedure Heapsort;
Varj: integer;
Begin
For J: = N DIV 2 DOWNTO 1 Do Sift (J, N);
For j: = n Downto 2 do begin
SWAP (A [1], A [J]);
SIFT (1, J-1);
END;
END;
F. Multiplexing
{A is a sequence list, TMP is auxiliary array}
Procedure Merge (VAR A: LISTTYPE; P, Q, R: Integer);
{Mr. A [p..Q] and A [Q 1..r]} of the sorted subsequences and A [Q 1..r]}
Var i, j, t: integer;
TMP: LISTTYPE;
Begin
T: = p; i: = p; j: = q 1; {t is TMP pointer, i, j is a pointer of left and right subsequences, respectively.
While (t <= r) DO Begin
IF (i <= q) {left sequence has the remaining} and ((j> R) OR (a [i] <= a [j])) {Meet the requirements of the current element of the left sequence}
Then Begin
TMP [T]: = a [i]; INC (i);
end
Else Begin
TMP [T]: = a [j]; inc (j);
END;
INC;
END;
For i: = p to r do a [i]: = TMP [i];
End; {merge}
Procedure merge_sort (var A: listType; p, r: integer); {merge sorting a [p..r]}
Var q: integer;
Begin
IF P <> r the begin
Q: = (p r-1) DIV 2;
Merge_sort (A, P, Q);
MERGE_SORT (A, Q 1, R);
MERGE (A, P, Q, R);
END;
END;
{main}
Begin
Merge_sort (a, 1, n);
End.
G. Boundary Sort
Thought: For each element, you can sort each bit from low to high.
8. High precision calculation
A.
B.
C.
D.
9. Tree traversal sequence conversion
A. Requisition in prequlese sequence
Procedure Solve (Pre, Mid: String);
VAR i: integer;
Begin
IF (pre= ') or (MID =' ') THEN EXIT;
I: = POS (Pre [1], MID);
Solve (Copy (Pre, 2, I), COPY (MID, 1, I-1);
Solve (Copy (Pre, I 1, Length (Pre) -i), Copy (MID, I 1, Length (MID) -i));
Post: = post pre [1]; {plus root, post-recursive end traversal traversal}
END;
B. Pre-sequence prequight sequence
Procedure Solve (MID, Post: String);
VAR i: integer;
Begin
IF (MID = '') or (post = '') THEN EXIT;
I: = POS (Post [Length (POST)], MID);
Pre: = pre post [length (post)]; {plus root, after recursive end, pre-sequence traversal}
Solve (Copy (MID, 1, I-1), COPY (POST, 1, I-1);
Solve (Copy (MID, I 1, Length (MID) -i), Copy (POST, I, Length (POST) -i);
END;
C. Prequasing order
Function OK (S1, S2: String): Boolean;
Var i, l: integer; p: boolean; begin
OK: = true;
L: = Length (S1);
For i: = 1 to l do begin
P: = false;
For j: = 1 to l do
IF S1 [I] = S2 [J] THEN P: = TRUE
IF NOT; End;
END;
END;
Procedure Solve (Pre, Post: String);
VAR i: integer;
Begin
IF (pre = '') or (post = '') THEN EXIT;
I: = 0;
Repeat
INC (I);
Until OK (Copy (Pre, 2, I), Copy (POST, 1, I));
Solve (Copy (Pre, 2, I), COPY (POST, 1, I));
Midstr: = Midstr pre [1];
Solve (Copy (Pre, I 2, Length (Pre) -i-1), Copy (POST, I 1, Length (POST) -i-1);
END;
10. Weak connection of the figure (DFS)
Procedure DFS (Now, Color: Integer);
Begin
For i: = 1 to n DO
IF a [now, i] and c [i] = 0 THEN Begin
C [I]: = Color;
DFS (I, Color);
END;
END;
11. Topology Sort
Look for a number, including any of the consecutive P items, and the sum of the sum of any Q items, if there is no existence, the NO is output.
12. Encourage conversion
A. Integer arbitrarily integrated interaction
NOIP1996 digital conversion
The structure of the string A $ is: a $ = 'mp'
Where m is a numeric string (length <= 20), while N, P is 1 or 2 digits (where the content is between 2-10)
Program requirements: After reading a $ A $ (without correctness check), the digital string M (N) in the A $ is output in the form of P-based form.
For example: a $ = '48 <10> 8'
Its significance is: the 10-based number 48 is converted to an 8-based output.
Output results: 48 <10> = 60 <8>
B. Real numbers arbitrarily integrated
C. Negative number of credits:
NOIP2000
Design a program that reads a decimal number of bases and a base of the number of loads, and converts this decimal number to this negative number: -r∈ {-2, -3, -4, .. ..- 20}
13. Range and combination generation
Arranged: (1..n)
Procedure Solve (dep: integer);
VAR
i: integer;
Begin
IF DEP = N 1 THEN Begin WriteLn (S); EXIT; END;
For i: = 1 to n DO
IF NOT USED [I]
S: = S CHR (i ORD ('0')); used [i]: = true;
Solve (dep 1);
S: = COPY (S, 1, Length (s) -1); used [i]: = false;
END;
END;
Combined generation (all options for selecting K numbers in 1..n)
Procedure Solve (dep, pre: integer);
VAR
i: integer;
Begin
IF dep = K 1 THEN Begin Writeln (S); EXIT; END;
For i: = 1 to n DO
IF (not used [i]) and (i> pre) THEN BEGIN
S: = S CHR (i ORD ('0')); used [i]: = true;
Solve (DEP 1, I);
S: = COPY (S, 1, Length (s) -1); used [i]: = false;
END;
END;
14 push relationship
Calculate string serial number model
Usaco1.2.5 stringsobits
The number of 01 strings of the length of N (n <= 31) is less than or equal to the series of skewers of the L, it is found in the first size sort in size.
Digital division model
* NOIP2001 number of divisions
The integer n is divided into K, and each copy cannot be empty, any two kinds of degradation cannot be the same (regardless of the order).
D [0,0]: = 1;
For P: = 1 to n DO
For i: = p to n DO
For J: = K DOWNTO 1 Do INC (D [I, J], D [I-P, J-1]);
Writeln (d [n, k]);
* Deformation 1: Consider the order
D [i, j]: = d [i-k, j-1] (k = 1..i)
* Deformation 2: If each number of decomposition has one upper limit m
D [i, j]: = d [i-k, j-1] (k = 1..m)
15. Accumulate priority method to solve the problem of expression
Const maxn = 50;
VAR
S1: Array [1..maxn] of integer; {S1 is a digital stack}
S2: Array [1..maxn] of char; {s2 is an operator stack}
T1, T2: Integer; {Stack top pointer}
Procedure Calcu;
VAR
X1, x2, x: integer;
P: char;
Begin
P: = S2 [T2]; DEC (T2);
X2: = S1 [T1]; DEC (T1);
X1: = S1 [T1]; DEC (T1);
Case P of
' ': x: = x1 x2;
'-': x: = x1-x2;
'*': x: = x1 * x2;
'/': x: = x1 Div 2;
END;
INC (T1); S1 [T1]: = x;
END;
PROCEDURE WORK;
Var C: char; v: integer;
Begin
T1: = 0; T2: = 0;
Read (c);
While C <> ';' Do
Case C of
' ', '-': Begin
While (t2> 0) and (S2 [T2] <> '(') do Calcu;
INC (T2); S2 [T2]: = C;
Read (c);
END;
'*', '/': begin
IF (t2> 0) AND ((S2 [T2] = '*') or (S2 [T2] = '/')) The Calcu;
INC (T2); S2 [T2]: = C;
Read (c);
END;
'(': Begin Inc (T2); S2 [T2]: = C; READ (C); END;
')': Begin
While S2 [T2] <> '(' Do Calcu;
DEC (t2); read (c);
END;
'0' .. '9': Begin
v: = 0;
Repeat
v: = 10 * V ORD (C) -ORD ('0');
Read (c);
Until (c <'0') or (c> '9'); INC (T1); S1 [T1]: = V;
END;
END;
While T2> 0 do Calcu;
Writeln (S1 [T1]);
END;
