NOIp中很少見的數據結構的題目，可以用堆實現，也可以用兩條隊列. 用堆實現，調了很久 = =
需要注意down函數的邊界問題.
1
#include<stdio.h>
2#include<string.h>
3#include<iostream>
4using namespace std;
5int n, h[10010];
6
struct heap
{
7
void swap(int*i, int*j){
8
int k = *i; *i = *j; *j = k;
9
}
10 void up(int k){
11 while (k > 1)
12 if (h[k/2] > h[k]) {
13 swap(&h[k/2], &h[k]);
14 k /= 2;
15 }else break;
16 }
17 void down(int k){
18 while (2*k <= n){
19 int l = 2*k, r = l<n ? l+1 : l;
20 if (h[r] < h[l]) l++;
21 if (h[k] > h[l]){
22 swap(&h[k], &h[l]);
23 k = l;
24 }else break;
25 }
26 }
27 void insert(int x){
28 h[++n] = x;
29 up(n);
30 }
31 void del(int k){
32 swap(&h[k], &h[n--]);
33
34 down(k);
35 }
36 int pop(){
37 del(1);
38 return h[n+1];
39 }
40
};
41heap hp;
42int main(){
43 int i, sum = 0;
44 scanf("%d", &n);
45 for (i = 1; i <= n; i++)
46 scanf("%d", &h[i]);
47 for (i = n/2; i > 0; i--) hp.down(i);
48 while (n > 1){
49 int x = hp.pop(), y = hp.pop();
50 sum += x+y;
51 hp.insert(x+y);
52 }
53 printf("%d\n", sum);
54}
55
78 = 12+15+5+32+14，上80還是很困難.
1.二分查找
設內
部結點的總數為n=2^h-1，則判定樹是深度為h=log(n+1)的滿二叉樹(深度h不計外部結點)。樹中第k層上的結點個數為2k-1，查找它們所需的比較次數是k。因此在等概率假設下，二分查找成功時的平均查找長度為：ASLbn ≈ log(n+1)-1
二分查找在查找失敗時所需比較的關鍵字個數不超過判定樹的深度，在最壞情況下查找成功的比較次數也不超過判定樹的深度。
2.問題求解第二題
21本書中選4本，任意兩本編號不相鄰.
去掉3個間隔，C(18,4)=3060.
排列組合題總是簡單的出乎意料. = =
3.快速排序算法不熟
今天突然發現很多O(nlogn)級別的算法都和樹有很深的關系，遍歷的過程通常都是生成某種樹，然后查找長度和比較次數通常和樹的深度相關.
1.直接插入排序 O(n^2) 穩定
2.希爾排序 O(n^1.3) 不穩定
3.直接選擇排序 O(n^2) 不穩定
4.堆排序 O(nlogn) 不穩定
5.冒泡排序 O(n^2) 穩定
6.快速排序 O(nlogn) 不穩定 =>可以看做構造二叉排序樹
7.歸并排序 O(nlogn) 穩定
整理自《奧賽經典·信息學》 第5章，原理略.
[原文]http://blog.csdn.net/guocai_yao/archive/2009/04/11/4065718.aspx
1.樹的遍歷法
通過中綴表達式，構造表達式樹，然后利用前序或者后序遍歷.
2.括號轉移法
這里我給出一個中綴表達式
a+b*c-(d+e)
第一步：按照運算符的優先級對所有的運算單位加括號
式子變成拉：((a+(b*c))-(d+e))
第二步：轉換前綴與后綴表達式
前綴：把運算符號移動到對應的括號前面
則變成拉：-( +(a *(bc)) +(de))
把括號去掉：-+a*bc+de 前綴式子出現
后綴：把運算符號移動到對應的括號后面
則變成拉：((a(bc)* )- (de)+ )-
把括號去掉：abc*-de+- 后綴式子出現
發現沒有，前綴式，后綴式是不需要用括號來進行優先級的確定的。
樹
形DP，需要記錄方案，并注意空樹的情況.[狀態]f[i][j]從結點i到j的最大加分值[方程]f[i][j] = max{f[i][k-1]*f[k+1][j]+a[k]} (i<=k<=j)實現方程的時候循環順序非常關鍵:結點數由小到大循環.否則會出現需要的值未計算的情況.記錄方案可以用一個數組d[i][j]記錄k，然后遞歸尋找方案并記錄.
1 #include<stdio.h>
2 #include<iostream>
3 using namespace std;
4 int f[35][35] = {0}, d[35][35] = {0}, ans[35] = {0}, t = 0;
5 void print(int start, int end){
6 if (start > end) return;
7 if (start == end) {ans[++t] = start; return;}
8 ans[++t] = d[start][end];
9 print(start, d[start][end]-1);
10 print(d[start][end]+1, end);
11 }
12 int main(){
13 int n, a[35] = {0}, i, j, k, l;
14 scanf("%d", &n);
15 for (i = 1; i <= n; i++){
16 scanf("%d", &a[i]);
17 f[i][i-1] = 1;
18 f[i][i] = a[i];
19 }
20 for (l = 2; l <= n; l++)
21 for (i = 1; i <= n; i++)
22 for (k = i; k <= i+l-1; k++){
23 j = i+l-1;
24 if (f[i][j] < f[i][k-1]*f[k+1][j] + a[k]){
25 f[i][j] = f[i][k-1]*f[k+1][j] + a[k];
26 d[i][j] = k;
27 }
28 }
29 printf("%d\n", f[1][n]);
30 print(1, n);
31 for (i = 1; i < t; i++) printf("%d ", ans[i]);
32 printf("%d\n", ans[t]);
33 }
34
題目中附件不超過2個，因而主附件存在4種不同的存取情況，可以轉化為分組背包問題.[狀態]f[k][v]表示添加前k組物品，剩余空間為v時的最大值[方程]f[k][v] = max{f[k-1][v], f[k-1][v-c[i]]+w[i]}注意循環順序.(參見《背包九講》)需要注意的問題(2次WA):1.仔細讀題，確定編號對應的物品.2.注意到方程中的參數非負(背包類問題需注意).
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 using namespace std;
5 int c[65][4], w[65][4], f[32000], set[70] = {0};
6 int max(int a, int b){return a > b ? a : b;}
7 int main(){
8 int n, m, v, p, q, i, j, t = 0;
9 FILE *fout = fopen("budget.out", "w");
10 memset(c, -1, sizeof(c));
11 memset(w, -1, sizeof(w));
12 memset(f, 0, sizeof(f));
13 scanf("%d%d", &n, &m);
14 for (i = 0; i < m; i++){
15 scanf("%d%d%d", &v, &p, &q);
16 j = 0;
17 if (!q) {
18 c[++t][0] = v;
19 w[t][0] = v*p;
20 set[i+1] = t;
21 }
22 else{
23 q = set[q];
24 if (w[q][1] == -1){
25 //printf("dgfdgds\n");
26 c[q][1] = c[q][0] + v;
27 w[q][1] = w[q][0] + v*p;
28 }
29 else if (w[q][2] == -1){
30 c[q][2] = c[q][0] + v;
31 w[q][2] = w[q][0] + v*p;
32 c[q][3] = c[q][1] + v;
33 w[q][3] = w[q][1] + v*p;
34 }
35 }
36 }
37 for (i = 1; i <= t; i++)
38 for (v = n; v >= 0; v--)
39 for (j = 0; j < 4; j++)
40 if (c[i][j] != -1 && v-c[i][j] >= 0){
41 f[v] = max(f[v], f[v-c[i][j]]+w[i][j]);
42 }
43 printf("%d\n", f[n]);
44 }
45