NOIp中很少见的数据结构的题目,可以用堆实现,也可以用两条队列. 用堆实现,调了很久 = =
需要注意down函数的边界问题.
1
#include<stdio.h>
2
#include<string.h>
3
#include<iostream>
4
using namespace std;
5
int n, h[10010];
6![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct heap
{
7![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
void swap(int*i, int*j)
{
8
int k = *i; *i = *j; *j = k;
9
}
10![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
void up(int k)
{
11
while (k > 1)
12![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (h[k/2] > h[k])
{
13
swap(&h[k/2], &h[k]);
14
k /= 2;
15
}else break;
16
}
17![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
void down(int k)
{
18![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while (2*k <= n)
{
19
int l = 2*k, r = l<n ? l+1 : l;
20
if (h[r] < h[l]) l++;
21![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if (h[k] > h[l])
{
22
swap(&h[k], &h[l]);
23
k = l;
24
}else break;
25
}
26
}
27![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
void insert(int x)
{
28
h[++n] = x;
29
up(n);
30
}
31![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
void del(int k)
{
32
swap(&h[k], &h[n--]);
33
34
down(k);
35
}
36![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
int pop()
{
37
del(1);
38
return h[n+1];
39
}
40
};
41
heap hp;
42![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int 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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
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