静态链表的实现

老姐结婚了,于是国庆只好挤车回家。。在回来的路上一直在构思静态链表的实现。严蔚敏的书上只是简单的提了一下,写了free和malloc函数,但是没有一个完整的静态链表程序,遂决定完成之。。写的挺顺利,难得的是调试过程相当脆。。
具体程序如下,因为调试比较顺利,没有做很多调试,出现错误,请读者留言指正。以后还会加入更多操作。各位中秋快乐!

//注意,基本没有用指针实现,而用数组下标代表指针
#include<stdio.h>
#include<stdlib.h>
#define MAX 10002
#define MAXN 10000
typedef struct Node
{
	int data;
	int next;
}NODE,*PNODE;
NODE space[MAX];
void InitSpace();
int malloc_SL();
void free_SL(int k);
int  InitList();
bool ListEmpty(int s);
void ClearList(int s);
void DestroyList(int s);
int ListLength(int s);
bool ListInsert(int s,int k,int e);
bool ListDelete(int s,int k,int &e);
bool ListBackAppend(int s);
bool ListBackDelete(int s);
void ListTraverse(int s);
void InitSpace()
{
	int i;
	for(i=0;i<MAXN;i++)
	{
		space[i].next=i+1;

	}
	space[MAXN].next=0;
	return;
}
int malloc_SL()
{
	//若备用链表非空,取出第一个元素,返回其索引,否则返回0
	int i=space[0].next;
	if(i)
		space[0].next=space[i].next;
	return i;
}
void free_SL(int k)
{
	space[k].next=space[0].next;
	space[0].next=k;
	return;
}
int  InitList()//从备用链表中申请节点,作为头结点
{
	int s;
	s=malloc_SL();
	space[s].data=0;//头结点的data域用来表示链表长度
	return s;
}
bool ListEmpty(int s)
{
	if(space[s].next==0)
		return true;
	else
		return false;
}
void ClearList(int s)
{
	int i=s;
	if(ListEmpty(s))
		return;
	while(space[i].next)
	{
		i=space[i].next;
	}
	space[i].next=space[0].next;
	space[0].next=space[s].next;
	space[s].next=0;
	space[s].data=0;
	return;
}
void DestroyList(int s)
{
	ClearList(s);
	free_SL(s);
	return;
}
int ListLength(int s)
{
	return space[s].data;	
}
bool ListInsert(int s,int k,int e)//在位置k(从1开始)插入一个元素
{
	int i=s;
	int j=0;
	if(k<=0||k>space[s].data+1)
	{
		printf("参数不合法\n");
		return false;
	}
	while(j<k-1)
	{
		i=space[i].next;
		j++;
	}
	k=malloc_SL();
	if(!k)
	{
		printf("申请失败!\n");
		return false;
	}
	space[k].next=space[i].next;
	space[i].next=k;
	space[k].data=e;
	(space[s].data)++;
	return true;
}
bool ListDelete(int s,int k,int &e)//删除位置k处的元素
{
	int i=s;
	int j=0;
	if(ListEmpty(s))
		return false;
	if(k<=0||k>space[s].data)
	{
		printf("参数不合法\n");
		return false;
	}
	while(j<k-1)
	{
		i=space[i].next;
		j++;
	}
	k=space[i].next;
	space[i].next=space[k].next;
	e=space[k].data;
	free_SL(k);
	(space[s].data)--;
	return true;
}
bool ListBackAppend(int s,int e)
{
	int i=s,k;
	while(space[i].next)
	{
		i=space[i].next;
	}
	k=malloc_SL();
	if(!k)
	{
		printf("申请失败!\n");
		return false;
	}
	space[i].next=k;
	space[k].next=0;
	space[k].data=e;
	(space[s].data)++;
	return true;
}
bool ListBackDelete(int s,int &e)
{
	int i=s,k;
	if(ListEmpty(s))
		return false;
	while(space[space[i].next].next)
	{
		i=space[i].next;
	}
	k=space[i].next;
	e=space[k].data;
	free_SL(k);
	space[i].next=0;
	(space[s].data)--;
	return true;
}
void ListTraverse(int s)
{
	int i=space[s].next;
	if(ListEmpty(s))
		return;
	while(i)
	{
		printf("%d ",space[i].data);
		i=space[i].next;
	}
	printf("\n");
	return;
}
int main()
{
	int s,e;
	InitSpace();
	s=InitList();
	DestroyList(s);
return 0;
}

双向链表的c(++)实现

感觉基本上是重写了以前的单链表,感觉这个还是要常练才能熟练啊。。(没有给出sort算法)

//只有头指针的双链表
//链表索引是从1开始的
#include<stdio.h>
#include<stdlib.h>
typedef struct Node{
	int data;//头结点的num用来保存length
	struct Node*pre;
	struct Node*next;
}NODE,*PNODE;
bool InitList(PNODE &pHead);
bool ListInsert(PNODE &pHead,int i,int e);
bool ListDelete(PNODE &pHead,int i,int &e);
bool ListEmpty(PNODE &pHead);
int ListLength(PNODE &pHead);
void ClearList(PNODE &pHead);
bool InitList(PNODE &pHead);
void ListTraverse(PNODE &pHead);
int LocateElem(PNODE &pHead,int e);
PNODE MergeList(PNODE &pLa,PNODE &pLb);
bool ListBackAppend(PNODE &pHead,int e);
bool ListBackDelete(PNODE &pHead,int &e);
bool InitList(PNODE &pHead)
{
	pHead=(PNODE)malloc(sizeof(NODE));
	if(!pHead)
		return false;
	pHead->data=0;
	pHead->pre=NULL;
	pHead->next=NULL;
return true;
}
bool ListInsert(PNODE &pHead,int i,int e)
{
	int num=0;
	PNODE p=pHead,q;
	while(p&&num<i-1)
	{
		p=p->next;
		num++;
	}
	if(!p||num>i-1)
		return false;
	q=(PNODE)malloc(sizeof(NODE));
	if(!q)
		return false;
	q->next=p->next;
	p->next=q;
	q->pre=p;
	if(q->next!=NULL)
	q->next->pre=q;
	q->data=e;
	q->pre=p;
	(pHead->data)++;
return true;
}
bool ListDelete(PNODE &pHead,int i,int &e)
{
	int num=0;
	PNODE p=pHead,q;
	if(ListEmpty(pHead))
		return false;
	while(p->next&&num<i-1)
	{
		p=p->next;
		num++;
	}
	if(!p->next||num>i-1)
		return false;
	q=p->next;
	e=q->data;
	p->next=q->next;
	if(q->next!=NULL)
	q->next->pre=p;
	free(q);
	(pHead->data)--;
return true;
}
bool ListEmpty(PNODE &pHead)
{
	if(!pHead->next)
		return true;
	else
		return false;
}
int ListLength(PNODE &pHead)
{
	return pHead->data;	
}
void ClearList(PNODE &pHead)
{
	PNODE p=pHead->next,q;
	while(p)
	{
		q=p;
		p=p->next;
		free(q);
	}
	pHead->data=0;
	pHead->next=NULL;
	return;
}
void DestroyList(PNODE pHead)
{
	ClearList(pHead);
	free(pHead);
	return;
}
int LocateElem(PNODE &pHead,int e)//返回第一个数值域等于e的元素的索引
{
	int i=1;
	PNODE p=pHead->next;
	while(p)
	{
		if(p->data==e)
			break;
		p=p->next;
		i++;
	}
	if(!p)
		return 0;
	return i;
}
void ListTraverse(PNODE &pHead)
{
	PNODE p=pHead->next;
	if(ListEmpty(pHead))
	{
		printf("the list is empty---ListTraverse\n");	
		return;
	}
	while(p)
	{
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
return;
}
/*PNODE MergeList(PNODE &pLa,PNODE &pLb)//将两个(非降序)链表合并成一个非降序链表
{
	PNODE pa=pLa->next,pb=pLb->next,pc=pLa,pHead=pc;
	if(!pa&&!pb)
		return pa;
	while(pa&&pb)
	{
		if(pa->data<=pb->data)
		{
			pc->next=pa;
			pc=pa;
			pa=pa->next;
		}
		else
		{
			pc->next=pb;
			pc=pb;
			pb=pb->next;
		}
	}
	pc->next=pa?pa:pb;
	free(pLb);
	pHead->data=ListLength(pLa)+ListLength(pLb);
	return pHead;
}
*/
bool ListBackAppend(PNODE &pHead,int e)//在尾部加入元素
{
	PNODE p=pHead,q;
	while(p->next)
	{
		p=p->next;
	}
	q=(PNODE)malloc(sizeof(NODE));
	if(!q)
		return false;
	p->next=q;
	q->next=NULL;
	q->pre=p;
	q->data=e;
	(pHead->data)++;
	return true;
}
bool ListBackDelete(PNODE &pHead,int &e)
{
	PNODE p=pHead;
	if(!(p->next))
		return false;
	while(p->next)
	{
		p=p->next;
	}
	e=p->data;
	p->pre->next=NULL;
	free(p);
	(pHead->data)--;
	return true;
}
int main()
{
	int e;
	PNODE pHead;
	InitList(pHead);
	DestroyList(pHead);
	system("pause");
	return 0;
}

gcd和lcm 居然忘掉了这个。。

/*==================================================*\ 
| GCD 最大公约数 
\*==================================================*/ 
int gcd(int x, int y)
{ 
    if (!x || !y) return x > y ? x : y; 
    for (int t; t = x % y; x = y, y = t); 
    return y; 
} 
/*==================================================*\ 
| 快速 GCD 
\*==================================================*/ 
int kgcd(int a, int b)
{ 
    if (a == 0) return b; 
    if (b == 0) return a; 
    if (!(a & 1) && !(b & 1)) 
        return kgcd(a>>1, b>>1)<<1;
    else if (!(b & 1))
    return kgcd(a, b>>1); 
    else if (!(a & 1)) return kgcd(a>>1, b); 
    else return kgcd(abs(a - b), min(a, b)); 
} 
/*==================================================*\ 
| 扩展 GCD  
| 求x, y使得gcd(a, b) = a * x + b * y;  
\*==================================================*/ 
int extgcd(int a, int b, int & x, int & y)
{ 
    if (b == 0) { x=1; y=0; return a; } 
    int d = extgcd(b, a % b, x, y); 
    int t = x; x = y; y = t - a / b * y; 
    return d; 
} 

以上代码转自兔子的算法集中营。
lcm只需lcm=a/gcd(a,b)*b即可
至于求一组数的gcd和lcm
可以先求两个数的,在用求出的gcd与第三个数求gcd,以此类推,代码样例:

  for(j=1;j<=m-1;j++)
  {
    s[j+1]=lcm(s[j],s[j+1]);    //将两个数的lcm存放在较大位置那个元素中
  }

欧几里得算法的通俗描述:
两个数a、b ,用较大的数除以较小的数取余,用余数更新较大的数,对新生成的a、b循环执行上述过程直至相除为0。此时较小的数就是两个数的gcd,这样lcm也可得到。

hdoj1712 分组背包

题目链接
分组背包入门题
难得一次性AC。。。

#include<stdio.h>
#include<stdlib.h>
int f[102],v[102][102],c[102][102];
int main()
{
	int n,m;
	while(scanf("%d %d",&n,&m)!=EOF && (n!=0||m!=0))
	{
		int i,j,k;
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
			{
				scanf("%d",&v[i][j]);
				c[i][j]=j;
			}
		for(i=0;i<=m;i++)
			f[i]=0;
		for(i=1;i<=n;i++)
			for(j=m;j>=0;j--)
				for(k=1;k<=m;k++)
				{
					if(c[i][k]<=j)
					{
						if(f[j-c[i][k]]+v[i][k]>f[j])
							f[j]=f[j-c[i][k]]+v[i][k];
						else
							f[j]=f[j];
					}
					else
						f[j]=f[j];
				}
		printf("%d\n",f[m]);
	}
return 0;
}

hdoj1171

题目链接
这道背包题是我粗心的最好证明。。。==!
不过这道题的数据到是挺严格的。。(肯定存在总价值为奇数的情况。。)
先给出错误代码

#include<stdio.h>
int f[200000],c[200000];
int main()
{
	int n;
	scanf("%d",&n);
	while(n>0)
	{
		int i,j,count=1,sum=0;
		
		while(n--)
		{
			int v,m;
			scanf("%d %d",&v,&m);
			sum+=v*m;
			for(int k=1;k<=m;k=k<<1)
				{
					c[count++]=k*v;
					m-=k;
				}
			if(m>0)
				{
					c[count++]=m*v;
				}
		}
			sum=sum/2;
			for(i=0;i<=sum;i++)
				f[i]=0;
			for(i=1;i<=count-1;i++)
				for(j=sum;j>=0;j--)
				{
					if(c[i]<=j)
					{
						if(f[j-c[i]]+c[i]>f[j])
							f[j]=f[j-c[i]]+c[i];
						else
							f[j]=f[j];
					}
					else
						f[j]=f[j];
				}
				printf("%d %d\n",2*sum-f[sum],fsum]);
		scanf("%d",&n);
	}
return 0;
}

检查了大约一个小时,,看不出错在哪。不过最后痛苦中还是突然醒悟。问题在于2*sum-f[sum]。
因为原来的sum可能为奇数,所以sum=sum/2之后再sum*2,可能导致2*sum<原来的sum。。
故纠正之。。菜鸟果然是菜鸟~~

#include<stdio.h>
int f[200000],c[200000];
int main()
{
	int n;
	scanf("%d",&n);
	while(n>0)
	{
		int i,j,count=1,sum=0,size;
		
		while(n–)
		{
			int v,m;
			scanf("%d %d",&v,&m);
			sum+=v*m;
			for(int k=1;k<=m;k=k<<1)
				{
					c[count++]=k*v;
					m-=k;
				}
			if(m>0)
				{
					c[count++]=m*v;
				}
		}
			size=sum/2;
			for(i=0;i<=size;i++)
				f[i]=0;
			for(i=1;i<=count-1;i++)
				for(j=size;j>=0;j–)
				{
					if(c[i]<=j)
					{
						if(f[j-c[i]]+c[i]>f[j])
							f[j]=f[j-c[i]]+c[i];
						else
							f[j]=f[j];
					}
					else
						f[j]=f[j];
				}
				printf("%d %d\n",sum-f[size],f[size]);
		scanf("%d",&n);
	}
return 0;
}

hdoj2159 二维背包

题目链接
练了下二维背包,有了新的收获。这道题求出是否达到经验值不难,用二维背包求出最大经验值即可,但是我不知道如何得到达到经验值时,花掉的最少忍耐度。。看了下discuss,发现其实只要从0到m找一下最小的使之达到过关经验值的忍耐度即可。

#include<stdio.h>
int f[102][102];
int main()
{
	int n,m,k,s;
	while(scanf("%d %d %d %d",&n,&m,&k,&s)!=EOF)
	{
		int i,j,t;
		int v[102],c[102],b[102];
		for(i=1;i<=k;i++)
		{
			scanf("%d %d",&v[i],&c[i]);
			b[i]=1;
		}
		for(j=0;j<=m;j++)
			for(t=0;t<=s;t++)
				f[j][t]=0;
		int sum=0;
		for(i=1;i<=k;i++)
			for(j=0;j<=m;j++)
				for(t=0;t<=s;t++)
				{
					if(c[i]<=j && b[i]<=t)
					{
						if(f[j-c[i]][t-b[i]]+v[i]>f[j][t])
							f[j][t]=f[j-c[i]][t-b[i]]+v[i];
						else
							f[j][t]=f[j][t];
					}
					else
						f[j][t]=f[j][t];
				}
		if(f[m][s]>=n)
		{
			for(i=0;i<=m;i++)		//找到最小的用去忍耐度,使达到过关经验值
				if(f[i][s]>=n)
				{
					printf("%d\n",m-i);
					break;
				}
		}
		else
			printf("-1\n");
	}
return 0;

hdoj2191

题目链接
哈哈,终于把这道多重背包AC了,虽然是水题。。
这几天看背包问题。。01背包和完全背包还是比较好理解,但是看到多重背包就有点不耐心了,今天认真看下,发现还是比较好理解的,当然只看了转化成01背包+一维数组实现+二进制优化的思路(渐进时间复杂度Vlogn),至于用单调队列进行优化,没研究。。。
hdoj2191,这是道典型的多重背包,开始几次都不能AC,但是sample output过了,看了好久。。头痛欲绝。。最后发现居然是k=k<<1写成了k=k<<2(居然过了sample output。。天呐~)。。要细心啊。。
DP真是博大精深,单一个背包问题就分七八种,此外还有树形DP,状态压缩DP,各种优化DP。。哎,学不完啊~
下面贴上AC代码

#include<stdio.h>
int value[2002],size[2002],f[2002];
int main()
{
	int t,x;
	scanf("%d",&t);
	for(x=1;x<=t;x++)
	{
		int n,m;
		scanf("%d %d",&n,&m);
		int s,v,c;
		int count=1;
		while(m–)
		{
			scanf("%d %d %d",&s,&v,&c);
			for(int k=1;k<=c;k=k<<1)
			{
				value[count]=k*v;
				size[count++]=k*s;
				c-=k;
			}
			if(c>0)
			{
				value[count]=c*v;
				size[count++]=c*s;
			}
		}
		int i,j;
		for(j=0;j<=n;j++)
			f[j]=0;
		for(i=1;i<=count-1;i++)
			for(j=n;j>=0;j–)
			{
				if(size[i]<=j)
				{
					if(f[j-size[i]]+value[i]>f[j])
						f[j]=f[j-size[i]]+value[i];
					else
						f[j]=f[j];
				}
				else
					f[j]=f[j];
			
			}
		printf("%d\n",f[n]);
	}
return 0;
}

完善引导程序——未启动分页机制的保护模式3

第二遍写。。刚写完结果电脑重启了。。只好大概重写下要点。。
1.[BITS 32] 明确告诉编译器接下来的段是32位的段
2.用bocsh虚拟机调试操作系统
将run.bat中的..\bochs -q -f bochsrc.bxrc改为..\bochsdbg -q -f bochsrc.bxrc
bocsh常用命令:

3.保护模式下写hello shadow程序
(1)问:如何修改gdt使保护模式下的数据段描述符和代码段描述符的段基址分别与data_32和code_32对应?
答:观察描述符的结构可知,第2、3、4、7位表示段基址(从0开始计数)。修改这几位即可。
相关代码:

			xor eax,eax
			add eax,data_32
			mov word [gdt_data+2],ax
			shr eax,16
			mov byte [gdt_data+4],al
			mov byte [gdt_data+7],ah

(2)问:由实模式跳转到保护模式的代码段时为什么加上dword?(jmp dword gdt_code_addr:0)
答:因为该段是32位的段,偏移应是32位,dword告诉编译器编译时,0为32位。
下面是修改后的程序:

[BITS 16]
org 07c00h
jmp main
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;gdt表
gdt_table_start:
	gdt_null:
		dd 0h
		dd 0h
	gdt_data_addr equ $-gdt_table_start
	gdt_data:
		dw 07ffh
		dw 0h
		db 0h
		db 10010010b
		db 11000000b
		db 0
	gdt_video_addr equ $-gdt_table_start
	gdt_video:
		dw 0ffh
		dw 8000h
		db 0bh
		db 92h
		db 0c0h
		db 0
	gdt_code_addr	equ	$-gdt_table_start
	gdt_code:
		dw 07ffh
		dw 1h
		db 80h
		db 10011010b
		db 11000000b
		db 0
gdt_table_end:
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
	gdtr_addr:
		dw gdt_table_end-gdt_table_start-1;
		dd gdt_table_start
	
main:								;从main开始执行代码	
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;初始化数据段描述符的基地址
	xor eax,eax
	add eax,data_32
	mov word [gdt_data+2],ax
	shr eax,16
	mov byte [gdt_data+4],al
	mov byte [gdt_data+7],ah
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;初始化代码段描述符的基地址
	xor eax,eax
	add eax,code_32
	mov word [gdt_code+2],ax
	shr eax,16
	mov byte [gdt_code+4],al
	mov byte [gdt_code+7],ah
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
	lgdt	[gdtr_addr]				;将gdt的基地址和长度送入gdtr
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
	enable_a20:						;开启A20地址线
		in al,92h
		or al,00000010b
		out 92h,al
	cli								;废弃实模式中断向量表
	
	mov eax,cr0						;修改cr0寄存器的第0位
	or eax,1
	mov cr0,eax
	
	jmp dword gdt_code_addr:0				;真正由实模式跳转到保护模式的代码段,super jump,jump!!。。好耳熟,好像是道acm题的名字。。?
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;	
	[BITS 32]
	data_32:
			db 'hello shadow'
	code_32:
			mov ax,gdt_data_addr
			mov ds,ax
			mov ax,gdt_video_addr
			mov gs,ax
			mov cx,12
			mov edi,(80*10+12)*2
			mov bx,0
			mov ah,0ch
		s:	mov al,[ds:bx]
			mov [gs:edi],al
			mov [gs:edi+1],ah
			inc bx
			add edi,2
			loop s
			jmp $
	times 510-($-$$) db 0
	dw 55aah

这样一个简陋的bootloader基本完成了。。

hdoj1051

题目链接
由题意可知只有长度和重量都非递减时,setup time不增加(下面我把这样的序列称之为严格非递减序列),题目也就转化为求数据对最少有几个严格非递减序列。
解答:
1.首先按长度升序排序。
2.对每个结构成员增加一个flag,标志是否已被访问,并设置变量pre,指向前驱元素的下标。对于每个元素stick[i],,先判断是否已访问,未访问则先置flag=1,置pre=i。从i+1到n寻找符合严格非递减的元素(stick[j].flag==0&&stick[j].w>=stick[i].w),置对应flag=1,更新pre=j.
3.每完成一个i的循环,说明找完了一个严格非递减序列。count++。
悲剧。。。本人没有想到这种方法来实现严格非递减序列的计数,看了别人的解题报告才领会,太菜了。。

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef struct Stick{
	int l;
	int w;
	int flag;
}STICK;
STICK stick[5002];
bool cmp(STICK a,STICK b)
{
	if(a.l!=b.l)
		return a.l<b.l;
	else
		return a.w<b.w;
}
int main()
{
	int t,i;
	scanf("%d",&t);
	for(i=1;i<=t;i++)
	{
		int n,j;
		scanf("%d",&n);
		for(j=1;j<=n;j++)
		{
			scanf("%d %d",&stick[j].l,&stick[j].w);
			stick[j].flag=0;
		}
		sort(stick+1,stick+1+n,cmp);
		int count=0,pre,k,p;
		for(k=1;k<=n;)
		{
			if(stick[k].flag==1)
			{
				k++;
				continue;
			}
			pre=k;
			stick[k].flag=1;
			for(p=k+1;p<=n;p++)
			{
				if((stick[p].flag==0)&&(stick[p].w>=stick[pre].w))
				{
					stick[p].flag=1;
					pre=p;
				}
			}
			k++;
			count++;
		
		}
		printf("%d\n",count);
	}
return 0;
}

hdoj1009

题目链接
又做了几道dp,感觉可以换了,就开始做贪心。
hdoj1009,简单题,贪心之。提交,WA,修改之提交,继续WA。。遂查看discuss,看到如下BT数据:
0 1
1 0
1.000

1 0
0.000

修改之,终于AC,,提醒自己,时刻记得变态测试数据啊~
下面是AC代码:

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
typedef struct Node{
	int j;
	int f;
	double v;
}NODE;
NODE node[1002];
bool cmp(NODE a,NODE b)
{
	return a.v>b.v;
}
int main()
{
	int m,n;
	scanf("%d %d",&m,&n);
	while((m!=-1)&&(n!=-1))
	{
		int i;
		if(n==0)
		{
			printf("%.3lf\n",0);
		}
		else
		{
			for(i=1;i<=n;i++)
			{
				scanf("%d %d",&node[i].j,&node[i].f);
				node[i].v=node[i].j*1.0/node[i].f;
			}
			sort(node+1,node+1+n,cmp);
			i=1;
			double sum=0;
			while(m>=node[i].f)
			{
				sum+=node[i].j;
				m=m-node[i].f;
				i++;
				if(i>n)
					break;
			}
			if(i<=n)
			sum=sum+m*node[i].v;
			printf("%.3lf\n",sum);
		}
		scanf("%d %d",&m,&n);
	}
return 0;
}

未启动分页机制的保护模式(2)

这几天忙着刷题,还发了高烧,居然超过了39度。。还好打了两针,退下来了。终于决定回过来把这部分内容搞定。
开始着手从实模式转入保护模式。
数据段:0——8M;
代码段:8——16M;
1.填写全局描述符表:
注意:gdt的第一项为空。

		gdt_table_start:
			gdt_null:
				dd 0h
				dd 0h
			gdt_data_addr equ $-gdt_table_start
			gdt_data:
				dw 07ffh
				dw 0h
				db 0h
				db 10010010b
				db 11000000b
				db 0
			gdt_code_addr	equ	$-gdt_table_start
			gdt_code:
				dw 07ffh
				dw 1h
				db 80h
				db 10011010b
				db 11000000b
				db 0
		gdt_table_end:

2.gdtr寄存器:
32+16=48位寄存器
cpu如何知道我们创建的gdt表在哪?
答:我们要将gdt表的长度和基地址送入gdtr寄存器。

lgdt指令:
lgdt [描述描述符表的地址]
3.A20地址线(开机加电时默认关闭):
转入保护模式前,A20地址线必须开启。
A20地址线关闭情况下:32位cpu访问1M内存尾部后再往下访问会产生地址回绕现象,不会访问到超过1M的内存。
A20地址线开启情况下:32位cpu访问超过1M内存不会产生回绕,但在此时如何兼容16程序(很多16位程序利用了地址回绕)?
答:将32位地址&00000000000011111111111111111111b
如何得知A20地址线是否开启?
答:用一个标志位表示A20地址线是否开启,1表示开启。
这个位在哪?
答:早期用8042键盘控制器上的一个空闲引脚控制。速度太慢,改为用I/O端口92h来控制。
4.转入保护模式前必须废除原先实模式下16位的中断向量表和中断例程。在32位环境下重建中断向量表和例程。
废除实模式中断向量表:cli ;关中断
5.万事俱备,接下来要明确告诉cpu转入保护模式。
cr0——cr3寄存器:386新增32位寄存器。
cr1:保留
cr2、cr3:和分页机制下的保护模式有关。
下面详解cr0:

PG和PE的组合:

修改cr0的PE位,告诉cpu转入保护模式:

				mov eax,cr0
				or eax,1
				mov cr0,eax

6.jmp到保护模式下的代码段。
保护模式下段地址实际含义为段选择子(也就是段描述符在描述符表中的索引)。
jmp gdt_code_addr:0
下面是具体程序:

org 07c00h
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;gdt表
gdt_table_start:
	gdt_null:
		dd 0h
		dd 0h
	gdt_data_addr equ $-gdt_table_start
	gdt_data:
		dw 07ffh
		dw 0h
		db 0h
		db 10010010b
		db 11000000b
		db 0
	gdt_code_addr	equ	$-gdt_table_start
	gdt_code:
		dw 07ffh
		dw 1h
		db 80h
		db 10011010b
		db 11000000b
		db 0
gdt_table_end:
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
	gdtr_addr:
		dw gdt_table_end-gdt_table_start-1;
		dd gdt_table_start
	lgdt	[gdtr_addr]				;将gdt的基地址和长度送入gdtr?
	enable_a20:						;开启A20地址线
		in al,92h
		or al,00000010b
		out 92h,al
	cli								;废弃实模式中断向量表
	
	mov eax,cr0						;修改cr0寄存器的第0位
	or eax,1
	mov cr0,eax
	
	jmp gdt_code_addr:0				;真正由实模式跳转到保护模式的代码段,不一般的跳跃,super jump,jump!!。。好耳熟,好像是道acm题的名字。。
	
	times 510-($-$$) db 0
	dw 55aah

hdoj1069

DP.隐晦的最长递减子序列。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef struct block{
	int x;
	int y;
	int z;
}Block;
Block a[31*3];
int tall[31*3];
bool cmp(Block a,Block b)
{
	return a.x*a.y>=b.x*b.y;
}
bool is_ok(Block a,Block b)
{
	if((a.x<b.x&&a.y<b.y)||(a.x<b.y&&a.y<b.x))
		return true;
	else
		return false;
}
int main()
{
	int n,cas=0;
	scanf("%d",&n);
	while(n!=0)
	{
		cas++;
		memset(tall,0,sizeof(tall));
		int p,q,r,i,j;
		for(i=1;i<=3*n;)
		{
			scanf("%d %d %d",&p,&q,&r);
			a[i].x=p,a[i].y=q,a[i].z=r;
			i++;
			a[i].x=p,a[i].y=r,a[i].z=q;
			i++;
			a[i].x=q,a[i].y=r,a[i].z=p;
			i++;
		}
		sort(a+1,a+1+3*n,cmp);
		tall[1]=a[1].z;
		for(i=2;i<=3*n;i++)
		{
			int max=0;
			for(j=1;j<=i-1;j++)
				if(is_ok(a[i],a[j]))
					if(tall[j]>max)
						max=tall[j];
			tall[i]=max+a[i].z;
		}
		int maxlen=0;
		for(i=1;i<=3*n;i++)
			if(tall[i]>maxlen)
				maxlen=tall[i];
		printf("Case %d: maximum height = %d\n",cas,maxlen);
		scanf("%d",&n);
	}
return 0;
}

hdoj1160

题目链接
在WA了六七次之后,终于AC了。。
题目不难理解,显然是DP,但是题目要求输出其中一个具体的最长递减子序列。这个我还不会,想了很久,最后还是无耻的上网搜解题报告。看了十几个解题报告,终于看懂了一个。。。(有时候觉得自己是不是真的太笨了~)
多增加一个数组pre[],初始化为-1.(解题报告中貌似都是初始化为本身,但我觉得这样也行。。)pre[i]用来保存以a[i]结尾的最长递增子序列的最后一个元素(即a[i])的前驱元素的下标,通过while(pre[i]!=-1)来遍历。
敲完程序调试,答案wrong。。继续调试,看了半天还是没看出来哪有错,只好去睡觉了,在床上继续想,终于在4点多的时候想到了,,,这道题的一个陷阱在于老鼠体重可以相等,但输出要求体重严格递增的同时,速度严格递减。
所以状态转移时应多加个条件:if(mice[i].w!=mice[j].w)
这回终于最长递减子序列的长度终于对了,不过下面具体的序列对不上。不过应该是正确序列(只要求输出一个正确序列即可),因为AC了。。。
关于STL的sort,下面程序中使用了sort函数,sort的内部是快速排序,并且做了优化,效率为nlogn。如果要对自定义数据类型的数组,按某个数据成员进行排序,需要自定义比较函数或重载<运算符。
以下面程序为例:
需要排序的数组元素是自定义的结构体变量:

    typedef struct node{
	int num;
	int w;
	int s;
}NODE;

自定义cmp函数:

bool comp(NODE x,NODE y)
{
 if(x.w!=y.w)
	 return x.w<y.w;    //按w升序排列
 else
	 return x.s>y.s;    //按y降序排列
}

值得一提的是,sort可以用于元素相等的情况,但并不能保证相同元素在排序后相对位置不变。如果要相对位置不变则需要用相应带stable前缀的sort。
下面是代码:

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
typedef struct node{
	int num;
	int w;
	int s;
}NODE;
NODE mice[1002];
int dp[1002];
int pre[1002];
int b[1002];
bool comp(NODE x,NODE y)
{
 if(x.w!=y.w)
	 return x.w<y.w;
 else
	 return x.s>y.s;
}
int main()
{
	int num=1;
	while(scanf("%d %d",&mice[num].w,&mice[num].s)!=EOF)
	{
		mice[num].num=num;
		num++;
	}
	num=num-1;
	sort(mice+1,mice+1+num,comp);
	dp[1]=1;
	pre[1]=-1;
	int i,j;
	for(i=2;i<=num;i++)
	{
	 pre[i]=-1;
	}
	for(i=2;i<=num;i++)
	{
		int max=1;
		for(j=1;j<=i-1;j++)
			if((mice[i].w!=mice[j].w)&&(mice[i].s<mice[j].s))
				if(max<(dp[j]+1))
				{
					max=dp[j]+1;
					pre[i]=j;
				}
		dp[i]=max;
	}
	int maxlen=0,result=1;
	for(i=1;i<=num;i++)
		if(dp[i]>maxlen)
		{
			maxlen=dp[i];
			result=i;
		}
		printf("%d\n",maxlen);
		int k=result;
		for(i=maxlen;i>=1;i--)
		{
			b[i]=mice[k].num;
			k=pre[k];
		}
		for(i=1;i<=maxlen;i++)
		{
		printf("%d\n",b[i]);
		}
	
return 0;
}

最长递增子序列(LIS)常规方法 hdoj1257

题目链接
最近开始做DP的题目,这题也不例外,经典的LIS问题
直接给出代码:

#include<stdio.h>
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int a[1000],i,j,dp[1000];
       for(i=1;i<=n;i++)
           scanf("%d",&a[i]);        
       dp[1]=1;
       for(i=2;i<=n;i++)
       {
           int max=0;
           for(j=1;j<=i-1;j++)
               if(a[j]<a[i])
                   if(max<dp[j])
                      max=dp[j];
           dp[i]=max+1;                    
       }
       int maxlen=0;
       for(i=1;i<=n;i++)
             if(dp[i]>maxlen)
                maxlen=dp[i];
      printf("%d\n",maxlen);             
    }
return 0;
}

从程序来分析,渐进复杂度O(n^2),这题数据量肯定不大,因为1000×1000直接过了。。