Posts

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

题目链接 题意：一棵树。。然后初始两个推雪机在点s，问如何选择路径使得处理完所有边上的积雪所耗费的汽油最少（走过一条有雪的边和一条没雪的边耗费的汽油一样） 思路：很容易想到，我们应该尽可能不走已经被清理过雪了的边，因为这样很浪费。。。这样不难想到应该是和树的直径有关。但是初始的位置是给定的。。。怎么办？突然发现由于是给了两个推雪机。。所以其实相当于。。。只有一个推雪机&我们可以从任意位置开始推雪。。。第二个问题是。。。对于不在直径上的边。。我们怎么算cost？解决办法是读边的时候进行记录。。。然后求直径的时候记录路径。。。对于一条边。。。只要有一个点不在直径上。。。那么这条边的代价就是2倍。。。

hdu3873题目链接 题意：n个点的图。。。每个点可能被若干其他点保护。。。被保护的意思是。。。如果想访问某个点。。那么必须先访问保护该点的所有点。。。问从点1到点n的最小代价。。 思路：。。一开始写了spfa。。。然后一脸懵逼。。。因为我第一次访问某个点的时候无法保证距离是最短的。。。所以还是上dij吧。。。

poj 2031 题意：三维空间中n个球要相连。。。通路的代价是距离。。。如果球相交（切）或者包含那么不用建通路就能联系。。。问联系所有球的最小代价。。。 思路：裸的最小生成树。。。。先预处理球和球表面的距离。。。距离是负数的处理成0.。。然后mst搞之。。。不算CE的话是1A….

poj1789题目链接 题意：其实题目不难理解。。。直接按照定义去搞就行了。。。 思路：由于距离在分母上。。所以要quality最大。。。就是要分母最小。。。 然后由于题目中说每一种类型的type只能由其他一种派生出来。。。我们可以把这个派生关系看做一条边。。。把每种类型看成点。。

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

poj1751题目链接 题意：一开始有一些边，然后添加一些边，使得代价之和最小。 思路：先把给定的边merge掉。。然后计算其余可以添加的边。。。接下来就是最小生成树。。。 然而因为多开了一个750*750的数组空间被卡了常。。。毫无人性。。。。

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

poj 3310 题目链接 题意：给出一个无向图，问是否满足：连通，并且无环，并且能找到一条路径，图中所有的顶点要么在这条路径上，要么与这条路径上的顶点相邻。 思路：一个一个来。连通的话任意起点开始跑一遍 dfs？开一个 bool 数组标记走过的点，最后扫一遍，看是否有点没走过。

poj1679 题意：问最小生成树是否唯一。。 思路：求一下次小生成树。。。如果无解，或者次小生成树的权值之和和最小生成树的权值之和不同，那么唯一，否则不唯一。1A 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年07月12日 星期二 16时16分52秒 4File Name :code/poj/1679.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <set> 13#include <map> 14#include <string> 15#include <cmath> 16#include <cstdlib> 17#include <ctime> 18#define fst first 19#define sec second 20#define lson l,m,rt<<1 21#define rson m+1,r,rt<<1|1 22#define ms(a,x) memset(a,x,sizeof(a)) 23typedef long long LL; 24#define pi pair < int ,int > 25#define MP make_pair 26using namespace std; 27const double eps = 1E-8; 28const int dx4[4]={1,0,0,-1}; 29const int dy4[4]={0,-1,1,0}; 30const int inf = 0x3f3f3f3f; 31const int N=105; 32int n,m; 33int ans; 34int f[N]; 35struct Edge 36{ 37 int u,v,w; 38 int in; 39 void input() 40 { 41 scanf("%d%d%d",&u,&v,&w); 42 } 43 bool operator < (Edge b)const 44 { 45 return w<b.w; 46 } 47}edge[N*N]; 48void init() 49{ 50 for ( int i = 1 ; i <= n ; i++) f[i] = i; 51} 52int root ( int x) 53{ 54 if (x!=f[x]) f[x] = root(f[x]); 55 return f[x]; 56} 57void merge( int x,int y) 58{ 59 int rx = root(x); 60 int ry = root(y); 61 if (rx==ry) return ; 62 f[rx] = ry; 63} 64void kruskal( int k) 65{ 66 for ( int i = 1 ; i <= n; i++) f[i] = i; 67 int cnt = 0 ; 68 int cur = 0 ; 69 for ( int i = 1; i <= m ; i++) 70 { 71 int u = edge[i].u; 72 int v = edge[i].v; 73 int w = edge[i].w; 74 if (i==k) continue; 75 if (root(u)==root(v)) continue; 76 merge(u,v); 77 cnt++; 78 cur+=w; 79 if (cnt>=n-1) break; 80 } 81 // cout<<"cnt:"<<cnt<<endl; 82 if (cnt<n-1) return ; 83 ans = min(ans,cur); 84} 85int main() 86{ 87 #ifndef ONLINE_JUDGE 88 freopen("code/in.txt","r",stdin); 89 #endif 90 int T; 91 scanf("%d",&T); 92 while (T--) 93 { 94 scanf("%d%d",&n,&m); 95 init(); 96 for ( int i = 1; i <= m ; i++) edge[i].input(); 97 sort(edge+1,edge+m+1); 98 int cnt = 0 ; 99 int mst = 0 ; 100 for ( int i = 1 ; i <= m ; i++) 101 { 102 int u = edge[i].u; 103 int v = edge[i].v; 104 int w = edge[i].w; 105 if (root(u)==root(v)) continue; 106 edge[i].in = 1; 107 merge(u,v); 108 cnt++; 109 mst+=w; 110 } 111 ans = inf; 112 for ( int i = 1 ; i <= m ; i++) 113 { 114 if (edge[i].in==0) continue; 115 //cout<<"i:"<<i<<endl; 116 kruskal(i); 117 } 118 // cout<<"mst:"<<mst<<endl; 119 // cout<<"ans:"<<ans<<endl; 120 if (ans==inf) 121 { 122 printf("%d\n",mst); 123 }else 124 { 125 if (ans==mst) puts("Not Unique!"); 126 else printf("%d\n",mst); 127 } 128 } 129 #ifndef ONLINE_JUDGE 130 fclose(stdin); 131 #endif 132 return 0; 133}

hdu 4514 题意：给出一个无向图，问是否有环，有的话输出 YES。如果没有环的话，输出最长路径。 思路：无向图判环用并查集就好。关于最长路径这里，一开始以为就是树的直径。 但是需要注意的是，题目并没有保证图一定是联通的，所以 gg 了。

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

poj2631 题意：一棵树中求两个点的最远距离。。。 思路：就是求树的直径。。。裸体。。。。1A 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年07月12日 星期二 13时03分39秒 4File Name :code/poj/2631.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E4+7; 34int n,m; 35vector < pi> edge[N]; 36int lst; 37int ans; 38int d[N]; 39bool vis[N]; 40 41 42void bfs( int s) 43{ 44 ms(d,0x3f); 45 ms(vis,false); 46 queue<int>q; 47 q.push(s); 48 vis[s] = true; 49 d[s] = 0 ; 50 51 while (!q.empty()) 52 { 53 int u = q.front() ; q.pop(); 54 lst = u ; 55// cout<<"u:"<<u<<endl; 56 int siz = edge[u].size(); 57 58 for ( int i = 0 ; i < siz ; i++) 59 { 60 int v = edge[u][i].fst; 61 if (vis[v]) continue; 62 vis[v] = true; 63 d[v] = d[u] + edge[u][i].sec; 64 ans = max(d[v],ans); 65 q.push(v); 66 } 67 } 68 69 int mx = 0; 70 for ( int i = 1 ; i <= n ; i++) 71 { 72// cout<<"i:"<<i<<" d[i]:"<<d[i]<<endl; 73 if (d[i]>mx) 74 { 75 mx = d[i]; 76 lst = i ; 77 } 78 } 79 80} 81int main() 82{ 83 #ifndef ONLINE_JUDGE 84 freopen("code/in.txt","r",stdin); 85 #endif 86 87 int u,v,w; 88 m = 0; 89 n = 0; 90 while (scanf("%d%d%d",&u,&v,&w)!=EOF) 91 { 92 edge[u].push_back(make_pair(v,w)); 93 edge[v].push_back(make_pair(u,w)); 94 m++; 95 n = max(n,u); 96 n = max(n,v); 97 } 98 ans = inf; 99 bfs(1); 100 ans = 0; 101// cout<<"lst:"<<lst<<endl; 102 bfs(lst); 103 cout<<ans<<endl; 104 105 #ifndef ONLINE_JUDGE 106 fclose(stdin); 107 #endif 108 return 0; 109}

poj1985 题意：求树上两点的最长距离。。。也就是传说中的树的直径。。。 思路： 两遍BFS ：先任选一个起点BFS找到最长路的终点，再从终点进行BFS，则第二次BFS找到的最长路即为树的直径； 原理： 设起点为u，第一次BFS找到的终点v一定是树的直径的一个端点 证明： 1) 如果u 是直径上的点，则v显然是直径的终点(因为如果v不是的话，则必定存在另一个点w使得u到w的距离更长，则于BFS找到了v矛盾) 2) 如果u不是直径上的点，则u到v必然于树的直径相交(反证)，那么交点到v 必然就是直径的后半段了 所以v一定是直径的一个端点，所以从v进行BFS得到的一定是直径长度

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] Description # A crime has been comitted: a load of grain has been taken from the barn by one of FJ’s cows. FJ is trying to determine which of his C (1 <= C <= 100) cows is the culprit. Fortunately, a passing satellite took an image of his farm M (1 <= M <= 70000) seconds before the crime took place, giving the location of all of the cows. He wants to know which cows had time to get to the barn to steal the grain. Farmer John’s farm comprises F (1 <= F <= 500) fields numbered 1..F and connected by P (1 <= P <= 1,000) bidirectional paths whose traversal time is in the range 1..70000 seconds (cows walk very slowly). Field 1 contains the barn. It takes no time to travel within a field (switch paths). Given the layout of Farmer John’s farm and the location of each cow when the satellite flew over, determine set of cows who could be guilty. NOTE: Do not declare a variable named exactly ’time’. This will reference the system call and never give you the results you really want.

题目链接 题意：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实验环境的搭建 在main.c中新加个函数，命名为projecto，函数的代码如下： 代码实现 1/* 2 * GeekOS C code entry point 3 * Copyright (c) 2001,2003,2004 David H. Hovemeyer <daveho@cs.umd.edu> 4 * Copyright (c) 2003, Jeffrey K. Hollingsworth <hollings@cs.umd.edu> 5 * Copyright (c) 2004, Iulian Neamtiu <neamtiu@cs.umd.edu> 6 * $Revision: 1.51 $ 7 * 8 * This is free software. You are permitted to use, 9 * redistribute, and modify it as specified in the file "COPYING". 10 */ 11 12#include <geekos/bootinfo.h> 13#include <geekos/string.h> 14#include <geekos/screen.h> 15#include <geekos/mem.h> 16#include <geekos/crc32.h> 17#include <geekos/tss.h> 18#include <geekos/int.h> 19#include <geekos/kthread.h> 20#include <geekos/trap.h> 21#include <geekos/timer.h> 22#include <geekos/keyboard.h> 23 24//added by 111qqz for project 0 25void project0() 26{ 27 Print("To Exit hit Ctrl + d.\n"); 28 Print("Hello from 111qqz !\n"); 29 Print("This is a test of project0 !\n"); 30 31 32 33 Keycode keycode; 34 while(1) 35 { 36 if( Read_Key(&keycode) ) //读取键盘按键状态 37 { 38 if(!( (keycode & KEY_SPECIAL_FLAG) || (keycode & KEY_RELEASE_FLAG)) ) //只处理非特殊按键的按下事件 39 { 40 int asciiCode = keycode & 0xff; //低8位为Ascii码 41 42 if( (keycode & KEY_CTRL_FLAG)==KEY_CTRL_FLAG && asciiCode=='d') //按下Ctrl键 43 { 44 Print("\n---------BYE!--------\n"); 45 Exit(1); 46 }else 47 { 48 Print("%c",(asciiCode=='\r') ? '\n' : asciiCode); 49 } 50 } 51 } 52 } 53} 54 55 56/* 57 * Kernel C code entry point. 58 * Initializes kernel subsystems, mounts filesystems, 59 * and spawns init process. 60 */ 61void Main(struct Boot_Info* bootInfo) 62{ 63 Init_BSS(); 64 Init_Screen(); 65 Init_Mem(bootInfo); 66 Init_CRC32(); 67 Init_TSS(); 68 Init_Interrupts(); 69 Init_Scheduler(); 70 Init_Traps(); 71 Init_Timer(); 72 Init_Keyboard(); 73 74 75 Set_Current_Attr(ATTRIB(BLACK, GREEN|BRIGHT)); 76 Print("Welcome 111qqz to GeekOS!\n"); 77 Set_Current_Attr(ATTRIB(BLACK, GRAY)); 78 79 80 81 // TODO("Start a kernel thread to echo pressed keys and print counts"); 82 //added by 111qqz for project 0 83 struct Kernel_Thread *thread; 84 thread = Start_Kernel_Thread(&project0,0,PRIORITY_NORMAL,false); 85 // added for project 0 end 86 87 88 /* Now this thread is done. */ 89 Exit(0); 90} 再修改Main函数，将TODO(“…..这一行替换为以下代码：

apt-get install build-essential apt-get install bochs bochs-x nasm 此处下载的 bochs 应该是比较新的…如果之后遇到 failed assertion in init_idt :g_handlersizenoterr == g_handlersizeerr 这个错误，建议安装比较老的 nasm 版本，比如 2.08.02链接 下载 geekos-0.3 软件包，地址为： geekOS 下载地址 然后解压到 ~/work 目录。