技术归档

cf682A题目链接 题意：两个数组，分别为1..n和1..m。。。从两个数组中各取一个，问和能被5整除的方案数。。。

hdu 4123 题目链接 题意：一棵树，定义d[i]为点i到树上某点的最大距离。。。给出若干查询，每个查询一个x,问最多能有多少点满足这些点中，最大的d与最小的d的差小于等于x.要求这些点的编号必须是连续的。

题目链接 题意:一棵树。。然后初始两个推雪机在点s,问如何选择路径使得处理完所有边上的积雪所耗费的汽油最少（走过一条有雪的边和一条没雪的边耗费的汽油一样）

hdu3873题目链接 题意：n个点的图。。。每个点可能被若干其他点保护。。。被保护的意思是。。。如果想访问某个点。。那么必须先访问保护该点的所有点。。。问从点1到点n的最小代价。。

poj 2031 题意：三维空间中n个球要相连。。。通路的代价是距离。。。如果球相交（切）或者包含那么不用建通路就能联系。。。问联系所有球的最小代价。。。

poj1789题目链接 题意：其实题目不难理解。。。直接按照定义去搞就行了。。。 思路：由于距离在分母上。。所以要quality最大。。。就是要分母最小。。。

Poj2349题目链接 题意：给出n个点坐标。。。然后可以建s个卫星基站。。。有卫星基站的地方之间可以互相免费通信。。现在要建一些无线电通讯线路（不同于卫星基站，是另一种通信方式），两个点之间线路的代价是他们的距离。。。问最小距离是多少。。。使得任意两个点之间都可以直接或者间接联系。。。

poj1751题目链接 题意：一开始有一些边，然后添加一些边，使得代价之和最小。 思路：先把给定的边merge掉。。然后计算其余可以添加的边。。。接下来就是最小生成树。。。

hdu4607题目链接 题意：给出一棵树。。。边权都为1. m个查询。。每个查询给一个k,表示只访问k个点。。。问每次的最小路径和是多少。。。 思路：我们发现。。会使路径和变大的一个不利因素是折返。。也就是访问某景点后。。必须要回去才能继续前进。。这样的距离是2倍。。那为了使得路径和尽可能小。。我们就尽量不要访问这样的点。。。而不是这样的点一定在直径上。。。以及我们还发现。。。不在直径上的点。。 。。不管深度如何（深度的意思是说，与和该点最近的直径上的点的距离），距离的贡献是一样的。。都是2倍。。所以我们可以推出一个公式。。。如果树的直径是d,那么k<=d+1的时候，答案为k-1,否则答案为d+(k-d-1)*2。。。

poj3310 题目链接 题意：给出一个无向图。。。问是否满足。。联通，并且无环，并且能找到一条路径，图中所有的顶点要么在这条路径上，要么与这条路径上的顶点相邻。

poj1679 题意：问最小生成树是否唯一。。 思路：求一下次小生成树。。。如果无解，或者次小生成树的权值之和和最小生成树的权值之和不同，那么唯一，否则不唯一。1A

hdu4514 题意：给出一个无向图。。问是否有环。。。有的话输出YES。。如果没有环的话。。输出最长路径。。

hdu2196 题意：给出一棵树。。。求距离每个点的最远距离是多少。。。 思路：最远距离什么的。。能想到树的直径。。。但是有什么关系呢？ 我们在求树的直径的时候。。。直径的两个端点是可以知道的。。。如果再从两个端点分别做两次bfs。。。每个点取两个距离的较大值就是答案。。。。？

poj2631 题意：一棵树中求两个点的最远距离。。。 思路：就是求树的直径。。。裸体。。。。1A

poj1985 题意：求树上两点的最长距离。。。也就是传说中的树的直径。。。

URAL1416 题意：次小生成树模板题 思路：用Kruskal求最小生成树，标记用过的边。求次小生成树时，依次枚举用过的边，将其去除后再求最小生成树，得出所有情况下的最小的生成树就是次小的生成树。复杂度o(m2)。。。貌似有其他优化。。。

1681: [Usaco2005 Mar]Checking an Alibi 不在场的证明 # Time Limit: 5 Sec Memory Limit: 64 MB Submit: 250 Solved: 178 [Submit][Status][Discuss]

题目链接 题意：n个人的上下级关系形成一棵树..每一个人有一个val（可正可负），要选若干个人参加一个party,要求是一个人和他的直接上级不能同时在场。问参加party的人最大的val之和。

一、目的 熟悉ELF文件格式，了解GeekOS系统如何将ELF格式的可执行程序装入到内存，建立内核进程并运行的实现技术。 二、流程 1、修改/geekos/elf.c文件：在函数Parse_ELF_Executable( )中添加代码，分析ELF格式的可执行文件（包括分析得出ELF文件头、程序头，获取可执行文件长度，代码段、数据段等信息），并填充Exe_Format数据结构中的域值。 2、在Linux环境下编译系统得到GeekOS镜像文件。 3、编写一个相应的bochs配置文件。 4、在bochs中运行GeekOS系统显示结果。

现在我们环境已经搭好了，参考 geekos实验环境的搭建