中大sicily 1426. Phone List 解题报告

 

1.原题中文大意;
 
给出一组数字,最多一万个,判断这组数字中是否存在一个数字是其它一个数字的前缀。
 
2.算法思想及解题用到的主要数据结构;
 
每读入一个数字字符串,则把该数字串从高位到低位分解成一个个数字字符。然后开始以最高位数字为树的根,第二个数字为根的子孙结点,第三个数字为第二个数字的子孙结点。如果碰到最后一个数字,如果这组数字符合要求的话则最后一个数字字符一定是叶子结点。不断的加入新的数字字符串到树中,如果在加入的过程中使以前的叶子结点变成了非叶子结点,或者新加入的数字字符串的最后一个数字在树中不是一个叶子结点,则报告这组数字字符串不符合要求。反之,则符合要求。
 
3.逐步求精算法描述(含过程及变量说明);
 
每个结点记下关键信息,一个数字字符。再加上一个指向其它信息的指针. 这个指针指向一个node_data_t结构。结构体中放置了一个tag标签,记字是不是一个数字字符串的最后一个数字;以及一个指向STL的set容器,容器中放置了所有子孙结点。如下代码描述。
 
struct node_t
 
{
 
char _ch;
 
node_data_t* _data;
 
};
 
struct node_data_t
 
{
 
set<node_t, node_comp>  _nodes;
 
bool _terminal;
 
};
 
剩下的逻辑便是分析数字字符串,把每个字符拆出加入树中。
 
4.程序注释清单
 
#include <set>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <cstdio>



using namespace std;



struct node_comp;

struct node_data_t;



struct node_t

{

char _ch;

node_data_t* _data;

};



struct node_comp  // 给STL的set容器的排序算子。

{

bool operator()(const node_t& left, const node_t& right)const

{

return left._ch < right._ch;

}

};
http://ykyi.net zausiu's blog
struct node_data_t

{

set<node_t, node_comp>  _nodes;

bool _terminal;  // 标记是不是一个电话号码的终点字符了。

};



typedef set<node_t, node_comp> nodes_set;



nodes_set top_nodes;



// 如果已经可以判断电话号码不满足要求就返回false.

// 递归调用该函数。

bool odyssey(nodes_set& nodes, const char* num)

{

if ( 0 == *num )

{

return true;

}

//

node_t node;

node._ch = *num;

node._data = new node_data_t;

node._data->_terminal = !num[1];



pair<nodes_set::iterator, bool> retval = nodes.insert(node);

if ( retval.second )  // 还没有这个数字的结点.新插入的.

{

bool b;

b = odyssey(retval.first->_data->_nodes, num+1);

return b;

}

else  // 已经存在

{

delete node._data;

// 并且已经是之前一个数字串的最后一个数字字符.或者现在这个字符是最后一个.

if ( retval.first->_data->_terminal || !num[1] )

{

return false;

}

else if ( !num[1] )

{

retval.first->_data->_terminal = true;

return true;

}

else

{

retval.first->_data->_terminal = false;

bool b;

b = odyssey(retval.first->_data->_nodes, num+1); // 递归

return b;

}

}

}

// 释放内存.

void free_mem(nodes_set& nodes)

{

for ( nodes_set::const_iterator ite = nodes.begin();

ite != nodes.end();

++ite )

{

free_mem(ite->_data->_nodes);

delete ite->_data;

}

nodes.clear();

}



int main(int argc, char* argv[])

{

int case_count;   // 有多少个case

int phone_num_count;    // 多少个电话霖巴

char phone_num_str[11];   // 存电话霖巴

bool successed;  // 一组数字字符串是否符合要求



scanf("%d", &case_count);

for ( int i = 0; i < case_count; i++ )

{

scanf("%d", &phone_num_count);



successed = true;

for ( int j = 0; j < phone_num_count; j++ )

{

scanf("%s", phone_num_str);



if ( successed )

{

successed = odyssey(top_nodes, phone_num_str);

}

}

if ( successed )

{

printf("YES\n");

}

else

{

printf("NO\n");

}



free_mem(top_nodes);

}



return 0;

}

 

 
5.测试数据
 
用简单的脚本帮助生成测试数据.
 
#!/bin/bash
 
INDEX=0
 
if [ -e $1 ];then
 
COUNT=200
 
else
 
COUNT=$1
 
fi
 
while [ $INDEX -lt $COUNT ];do
 
let "INDEX=$INDEX+1"
 
echo $RANDOM
 
done
 
6.对时间复杂度,空间复杂度方面的分析.
 
本算法的时间复杂度的空间复杂度一般都介于O(logN)和O(N)之间。
 
//////////////// 原题  //////////////
 
1426. Phone List
 
 
 
 
 
Description
 
 
 
 
 
 
 
Given a list of phone numbers, determine if it is consistent in the sense that no number is the pre?x of another. Let’s say the phone catalogue listed these numbers:
? Emergency 911
? Alice 97 625 999
? Bob 91 12 54 26
In this case, it’s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the ?rst three digits of Bob’s phone number. So this list would not be consistent.
 
 
 
 
 
 
 
Input
 
 
 
 
 
 
 
The ?rst line of input gives a single integer, 1 ≤ t ≤ 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 ≤ n ≤ 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.
 
 
 
 
 
 
 
Output
 
 
 
 
 
 
 
For each test case, output “YES” if the list is consistent, or “NO” otherwise.
 
 
 
 
 
 
 
Sample Input
 
 
 
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346
 
 
Sample Output
 
 
 
NO
YES
 
 

 

Unix网络编程.第五,六章笔记.

# Unix世界里经常看到的 pst  是 pseudo terminal 的意思啊。

# ps -t pts/6 -o pid,ppid,tty,stat,args,wchan

ps 命令的进程状态。 S表示进程在睡眠,I表示进程在等待输入,O表示进程在等待输出。当进程在S状态时,wlan指示了更详细的状态信息。

# SIGSTOP 和 SIGKILL 两个posix信号不可以被caught.

# 缺省情况下,Unix的信号是不排在队列中的。这意味着多个相同signal到达的时候如果没有来得及处理,就只会记下一个signal.如果需要稳定的信号支持,就要使用RealTime Posix接口。

# init 进程的PID是 1.

# 可以用sigprocmask函数block和unblock信号。This let us protect a critical region of code by preventing certain signals from being caught while that region of code is executing.

# 对于 Unix System V 和 Unix98, the child of a process does not become a zombie if the process sets the disposition of SIGCHLD to SIG_IGN. unfortunately, tis works only under System V & Unix98. Posix明确指票这个行为是未定义的。The portable way to handle zombies is to catch SIGCHILD & call wait or waitpid.

# waitpid 有个 WNOHANG 选项可以让waitpid立即返回。

# POSIX定义了asynchronous I/O model .但是 few systems support POSIX asynchronous I/O. The main difference between asynchronous I/O model and signal-driven I/O model is that with signal-driven I/O, the kernel tells us when an I/O operation can be initiated but with asynchronous I/O, the kernel tells us when an I/O operation is completed.

# 想得到本机到某台机的RTT。怎么做呢?kao,不要太容易啊。用 ping 啊!!!

使用Necessitas在Android平台上运行Qt程序失败

什么是 Necessitas?

NecessitasQtAndroid操作系统上的一个移植,同时提供了Qt CreatorAndroid的集成。Necessitas计划为你提供了Android平台下的Qt,以及一个一流的平易近人的IDE,方便你在安卓平台下管理,开发,部署,运行 调试你的Qt应用。

什么是Minstro?

Necessitas也是Ministro的官网。MinistroLGPL Qt共享库提供了一个系统范围的下载器(downloader)和安装器(installer)。你可以在Andorid软体市场获得Ministro

如何安装Necessitas SDK开发包?

相当地easy啊!http://sourceforge.net/projects/necessitas/files/ 下载sdk开发包。有linux, win, mac 三个平台下的。安装过程傻瓜式 next next next 。哥尝试在Linux下安装出错了。安装程序没有加载起来。

zausiu@potassium:/tmp$ ./necessitas-0.3-online-sdk-installer-linux 

./necessitas-0.3-online-sdk-installer-linux: error while loading shared libraries: libgobject-2.0.so.0: cannot open shared object file: No such file or directory

 

我先尝试在deibian安装linux版本。结果安装文件启动时加载libglobject.so失败了!但是明明在/lib目录下啊!解决不了,唔知点解!就只好在win7下安装了windows版本。注意要勾选上装 ant,如果你的系统里之前没有安装ant的话。装好ant后还要把ant的路径添加入环境变量里。

如何安装Android SDK开发包?

去官网下载了然后安装。简单地令人发指!!!哥不能讲怎么安装它,免得说我侮辱你的智慧。

http://developer.android.com/sdk/index.html

开始开发

运行在安卓上的Qt程序被编译成共享对象(shared objects)。一个Java Launcher,已经集成在necessitas sdk里,会加载这个shared objects。当然,对于应用开发者,这个Java Launcher是完全透明的。要注意的是,Qt包含了很多互相引用的库,只有Android V1.6以上才支持这个functionality

 

哈。最最重要的。尝试第一个将被部署到android上的Qt应用。用安装好的 Necessitas Qt Creator创建了一个GUI程序。运行。。。运行。报错了!!!哭啊。

ma-make: *** [install_target] Error 2

The process "D:\necessitas\QtCreator\bin\ma-make.exe" exited with code 2.

Error while building project 4android (target: Android)

When executing build step 'Copy application data'

"When executing build step 'Copy application data'"google了一下。木有得到有价值的信息。不知道如何解决啊。哈~~那就不管了!!!

copyright ykyi.net

 

 

linux的soname,链接库的问题.

第一次看到soname是读<程序员的自我修养.第一册:链接库>看来的。顺便说一下,这本书确实是本好书吖,国内出的难得技术好书。后来在公司的项目中把它从windows平台下移植到linux下,写makefile时用到过。

 

再后来又忘记了。今天再次看到soname的时候就有点记不起来了。又只好搜索了一些资料看。趁热打铁把学会的东西记下来。

linux为尝试解决动态链接库版本冲突的问题(windows平台下称之为DLL HELL),引入了soname进制。linux的动态链接库的扩展名约定为.so 即shared object的缩写。下面的makefile语句来自于哥今年上半年写的makefile文件:

VERSION_NUM := 1.0.0
soname = lib$(dirname).so.$(firstword $(subst ., ,$(VERSION_NUM)))
LINKFLAGS := -shared -Wl,-soname,$(soname) -L. -lpthread -lrt -lpentagon -lcross_platform
其中的变量$(soname)会被替换为eibcomm.so.1。再看看LINKFLAGS变量指定的几个选项. -shared 表示要生成一个shared object,即动态共享库. -pthread -lrt -lpentagon -lcross_platform 是要链接其它几个库,thread和linux的posix线程库,rt是一个和实时系统相关的库它提供了高精度的时间函数。

比较奇怪的是 -Wl,-soname,$(soname) 它们之前用逗号分开,而不是用空格分开。实际上这几个东东会被gcc传给ld(linux下的链接器)作为链接器的参数。gcc规定的写法就是这样的。指定的soname会被链接器写入到最终生成的elf文件中(linux下的可执行文件格式)。要查看elf文件的段布局什么的,可以用readelf工具。

 

最终生成的文件将命名为 libname.so.x.y.z 的形式。soname是libname.so.x的格式(也不尽然,这只是一个convetion,并非在语法或机制上强行要求)。接着把生成的so文件拷贝到/usr/lib 或者 /lib,这两个文件夹是系统用来放置动态链接库的地方。debian下没有把/usr/local/lib作为默认的动态链接库文件夹.可以通过改/etc/ld.so.conf 文件把更多的路径加入。再运行 ldconfig,更新cache中的库文件信息。为什么要用cache呢,有人就问了!因为library实在太多了咯,cache就被引用了。cache是个好东西啊!!!

这个时候依赖 libname.so.x 的文件就可以找到这个library并加载起来了。但是编译程序时还是找不到呢.编译程序时通常会写 -lname 这个时候会先找 libname.so 再找 libname.a 文件,结果找不到。link就会抱怨没有找到这个库文件。为了让编译通过,于是你就用 ln -sf libname.so libname.so.x.y.z (这个是realname,版本号部分可能只有x.y两个部分) 建一个软链接!搞定!

copyright ykyi.net

关于听陈光荣教授《混沌的故事》讲座的心得报告

    在听你陈老师(陈光荣教授,见文章未尾的介绍)的报告之前没有听说过“混沌数学”的概念。阅读了网络上的一些资料以后,有了大致的认识。早在初中生的年代,有在数学科普杂志上看到过“模糊数学”的概念。我想,混沌数学应该就是模糊数学近乎罢。

陈老师的讲座重点在浅显介绍混沌数学,并没有涉及太多混沌理论的学术内容。报告从牛顿时期的三大定律讲起,当时的的科学界普高认为世界是一个确定的机械系统。到科学家彭家莱在研究天体运动的三体问题时提出了定性分析的研究方向,这是混沌的启蒙思想。陈老师讲三维空间有四种状态:发散,收敛,周期振荡,第四种即“混沌”。数学家Stephen Smale提出了“马蹄理论”又是“混沌数学”领域的一重要理论。我粗略地把“马蹄理论”理解成一个马蹄形状被压缩,拉伸,对折变换,不断重复这一过程,就变成了“chaos”。华人数学家李天岩发表了论文“Period Three Implies Chaos”标志着“离散混沌数学理论的诞生”。这个理论被称为“李.约克理论”。它的核心部分是“区间中存在不可数个初始点,函数从这些点出发的迭代点序列既不是周期的,又不趋向于任何周期轨道。序列的这种特殊状态是混沌的(chaotic)”。“混沌理论”这个概念在大陆由北京大学的朱照宣教授引入。

陈老师在讲混沌理论的历史发展的故事中穿插了小故事给听众解释混沌理论。陈老师举了一个足球场的例子。一个四周用铁丝网封闭的足球场,一群小孩子在足球场内踢足球。这个足球飞向什么位置是不可预测的。这就近似一个“混沌系统”。我自己的理解,在每一个时间点如果可以知道小孩踢球的位置和力量大小以及风速等等物理量,就可以预测出皮球的运动方向啊。唔,我想得岂不是跟拉普拉斯的理论一样了啊机械决定论!!!要被自然辩证法老法鄙视的啊!为了不违反自然辩证法的原则。你要想修补我的想法。这应该是一个视角的问题。如果能得到各种影响物理量的精确值固然可以测出皮球的运动方向,但对于一个非常复杂的系统,要得到所以物理量的精确值是不可能的,于是“混沌”就同来了。混沌,真是好高深的理论啊!!!

陈老师在结束部分讲了“混沌理论”在天体物理学中的应用。Princeton University 的 Peter Goldreich 认为认为太阳系行星的共振是混沌的;混沌决定了太阳系行星的形成,导致地球上的某些“生物种类灭绝” 甚至某些天体的“物质消亡” ,让天体的“牛顿时钟” 最终趋于混沌。幻灯片播放的太阳系(Solar System)的图片相当地漂亮啊。最新的混沌理论认为太阳系起始于混沌状态,在两亿年内又将进入混沌。由微小的扰动会引发巨大无比的突变,行星的轨道最终都趋向于混沌。天体物理学是相当的难懂,看着这些美丽神秘的宇宙深处的图片,我觉得我所具备的物理知识不足以理解宇宙中的神秘星体。从哲学的大尺度高度,任务事情都是出生,发展,高潮,最终走向毁灭。大规模有序的运动里会在局部,某些子过程中蕴含无序的过程。看似无序的过程也必有运动的规律。Actually,我不能理解,Chaotic Solar System是个什么样的system

http://ykyi.net zausiu’s blog

提问阶段,有人问到了计算机的问题,陈老师总结为计算机不可能产生理论上真正随机的数据。这跟我的知识是一致的,计算机只能产生伪随机数。与是又想到之前看Linux内核的书,Linux内核里有一个什么什么池的东东,这个东东用来搜集所有随机发生的事件:如电流噪声,键盘中断等等用它来贡献随机数。咦,这不就能产生真正随机的数字了吗?马上又想到,这是一个看问题的尺度的问题。把时间尺度放小到内核能收集到的两次随机事件之间,这个间隔内产生的随机数依然是通过公式计算到的可预测的数字。果然还是伪随机数。又想到之间的PPT中有讲陈老师用电路可以产生真正的“混沌信号”。那么把这路电路引入到计算机体系中,不就可以产生真正的随机数了吗?唔!那就不对了呀。那只可能是:“混沌”和“随机”并不是完全相等的概念。

讲座结束后。我跟同学讨论了未来“生物计算机”的猜想。应用哲学思想的否定之否定规律。信号从过去的“模拟信号”发展到现在占统治地位的“离散信号”,必定在以后又会发展到更高层次的“模拟信号”,近似生物电神经系统的通讯发式,将完全超越现在的二进制的冯诺依曼体系的计算机。生物电的模拟信号能携带更丰富的信息,并且能够描述真正“混沌”的“模糊”状态。而现在的二进制计算机只能用精确的离散数字近似描述模糊的东西。这样的计算机有什么现实意义呢!至少就能产生真正的随机数了。肯定有意义非凡的现实意义啊。科学学术是先不负责现实意义的,那是工程师们的任务。

/////////////////

讲座题目:混沌的故事

 

演讲人:陈关荣教授,香港城市大学

 

演讲时间:125日上午 10:00-11:30

 

演讲地点:中山大学东校区信息学院楼  207

 

演讲摘要:许多人都听说过,南美洲的一只蝴蝶轻轻地扇动一下翅膀可能会在美国德克萨斯州引发一场龙卷风。这一通俗解释作为“混沌”的代名词经历了人们认识和建立科学意义上的混沌理论的漫长历程,理解到“蝴蝶效应”是混沌的一个基本特征。本讲座以故事的形式向理工科师生介绍混沌的基本概念和混沌理论的发展历史。报告力求通俗生动而不失严谨清晰。内容并不要求听众具有混沌知识,因而也欢迎其他有兴趣的非理工科师生参加。

 

演讲人简介

 

陈关荣教授1981年获中山大学计算数学硕士学位,是中大校友。他于1987年获美国Texas A&M 大学应用数学博士学位,其后在莱斯大学和休斯顿大学任教。自2000年起,他接受香港城市大学讲座教授职位工作至今,在该校成立了“混沌与复杂网络”学术研究中心并担任中心主任。他长期从事非线性科学研究,自1981年以来,发表了多篇SCI杂志论文和出版了多部研究专著,他引次数达一万六千多次,SCI h指数为 62,被ISI评定为工程学高引用率研究人员。

 

陈关荣教授现任IEEE《电路与系统》杂志(IEEE Circuits and Systems Magazine)主编和国际《分岔与混沌》杂志(International Journal of Bifurcation and Chaos)主编,曾经担任过许多国际学术会议主席和组织者、曾任IEEE电路与系统学会非线性电路与系统技术委员会主席。他是IEEE Fellow(自1996年),曾获4 SCI最佳杂志论文奖,2008年获国家自然科学二等奖(第一完成人),2010年获何梁何利科学与技术进步奖,2011年获俄罗斯圣彼得堡国立大学授予荣誉博士学位和俄罗斯欧拉基金会颁发欧拉金质奖章。他是中山大学等国内外多所大学的荣誉或客座教授,并曾多次应邀到过30多个国家讲学。

sicily 1022 Poor contestant Prob 解题报告。

 

         解  题  报  告
 
1 1022 Poor contestant Prob原题中文大意;
 
对于大约十万条数据:如果共奇数条数据则找到最中间那条记录。如果有偶数条记录则忽略。
 
2 算法思想及解题用到的主要数据结构;
 
因为数据的规模比较大。如果给十万条记录排序的话显然会超时。考虑到题目只需要找到最中间那条。易想到把数据平分成两部分,第一部分的数据全部大于第二部分的数据。创建两个堆结构。第一部分的较大数据建大小顶堆,第二部分的较小数据建成大顶堆。在插入数据的过程中,动态维护这两个堆,使小顶堆的元素数等于大顶堆的元素数或者小顶堆的元素比大顶堆的元素多一。本题用性线表来存储堆。
 
3 详细解题思路;
 
因为最终需要输出一个字符串。为了节省拷贝字符串的开销,把字符串存到一个字符串池中,而每个堆中的元素只维护这个字符串池的索引号。
 
初始时,小顶堆和大顶堆的大小都是0。
 
1. 当输入第一条数据时,把这条数据放入小顶堆中。
 
2. 当输入更多数据时:
 
2.1 如果小顶堆和大顶堆的元素个数一样多。为保证添加新数据后,我们需要的最中间的数据在小顶堆的上部。又分两种情况处理:
 
2.1.1 如果待加入数据大于或等于大顶堆的堆顶元素。则把这个待加入数据加入小顶堆。调整小顶堆.
 
2.1.2 如果待加入数据小于大顶堆的堆顶元素.则把大顶堆的堆顶元素弹出添加到小顶堆,调整这两个堆。之后,把待加入数据加入大顶堆。
 
2.2 如果小顶堆和大顶堆的元素个数不一样多。因为前面的约定,那么必定是小顶堆的元素个数比大顶堆的元素个数多一个。仍然分两种情况:
 
2.2.1 如果待加入数据大于小顶堆的堆顶元素。则把待加入数据加入小顶堆并调整,调整后把小顶堆的堆顶弹出加入大顶堆并调整。小顶堆在弹出堆顶元素后再调整一次。
 
2.2.1 如果待加入数据不大于小顶堆的堆顶元素。则把该数据加入大顶堆,调整大顶堆。
 
输入结束时直接取小顶堆的堆顶元素即要求的解。根据元素中的字符串索引可以拿到需要打印的字符串,本题中即那位poor contestant。
 
4 逐步求精算法描述(含过程及变量说明);
int g_name_pool_index = 0;   // 名字池的当前索引号.

char g_name_pool[100001][11];  // 用来存名字的字符串池.



下面是堆相关的描述。

struct heap_elem_t

{

// string _name;

int _name_index;  // 名字的索引

int _solved_count;  // 原题意中表示解决了多少个问题.用这个数量比较堆元素的大小。

};

// STL 用的堆算法的比较算子.

struct heap_elem_less_comparator

{

bool operator()(const heap_elem_t& left,  const heap_elem_t& right)

{

return left._solved_count < right._solved_count;

}

};



// STL 用的堆算法的比较算子.

struct heap_elem_larger_comparator

{

bool operator()(const heap_elem_t& left,  const heap_elem_t& right)

{

return left._solved_count > right._solved_count;

}

};

heap_elem_less_comparator less_comp;

heap_elem_larger_comparator larger_comp;

// 从下往而上调整堆。用到了STL的堆调整算法。堆元素存在线性表中,但不用第一个元素。因为之前的版本用自己写的堆调整算法为了计算坐标方便就不用第一个元素。

inline void adjust_heap_up(heap_elem_t heap[], int tail_pos, bool inc)

{

if ( inc )

{

push_heap(heap+1, heap+tail_pos+1, larger_comp);

}

else

{

push_heap(heap+1, heap+tail_pos+1, less_comp);

}

}

// 把堆顶元素弹出.并调整余下的元素仍然是一个堆。也用了STL的算法.

inline void popup_the_top(heap_elem_t heap[], int tail_pos, bool inc)

{

if ( inc )

{

pop_heap(heap+1, heap+tail_pos+1, larger_comp);

}

else

{

pop_heap(heap+1, heap+tail_pos+1, less_comp);

}

}

// 下面是自已写的堆调整算法。有从上而下的调整,也有从下而上的调整。

/** 调整堆.从下往下调整.

* @param heap 堆的首地址.用顺序表存放堆.但不用下标为0的元素.这个元素可用来作临时存储.

* @param summit_pos 堆顶的位置.summit_pos > 0

* @param tail_pos 最后一个元素的位置.tail_pos > 0

* @param inc 是否建小顶堆.如果false则大顶堆.

*/

void adjust_heap_top2bottom(heap_elem_t heap[], int summit_pos, int tail_pos, bool inc)

{

int i;

heap[0] = heap[summit_pos];  // 存下堆顶的元素先.

for ( i = 2 * summit_pos; i <= tail_pos; i *= 2 )

{

if ( inc )  // 调整小顶堆

{

if ( i < tail_pos && heap[i]._solved_count > heap[i+1]._solved_count )

i++;

if ( ! (heap[0]._solved_count > heap[i]._solved_count) )

break;

}

else  // 调整大顶堆

{

if ( i < tail_pos && heap[i]._solved_count < heap[i+1]._solved_count )

i++;

if ( ! (heap[0]._solved_count < heap[i]._solved_count) )

break;

}

heap[summit_pos] = heap[i];

summit_pos = i;

}

heap[summit_pos] = heap[0];

}



/** 调整堆.从下往上调整.

* @param heap 堆的首地址.用顺序表存放堆.但不用下标为0的元素.这个元素可用来作临时存储.

* @param tail_pos 最后一个元素的位置.tail_pos > 0

* @param inc 是否建小顶堆.如果false则大顶堆.

*/

void adjust_heap_bottom2top(heap_elem_t heap[], int tail_pos, bool inc)

{

int i;

heap[0] = heap[tail_pos];

for ( i = tail_pos; i > 1; i /= 2 )

{

int parent_pos = i / 2;

if ( inc )  // 调整小顶堆

{

if ( heap[parent_pos]._solved_count > heap[0]._solved_count )

{

heap[i] = heap[parent_pos];

}

else

{

break;

}

}

else  // 调整大顶堆

{

if ( heap[parent_pos]._solved_count < heap[0]._solved_count )

{

heap[i] = heap[parent_pos];

}

else

{

break;

}

}

}



heap[i] = heap[0];

}

5 程序注释清单(重要过程的说明);

// poor_guy.cpp : Defines the entry point for the console application.
//

#include <algorithm>
#include <string>
#include <vector>
#include <string.h>
#include <stdio.h>

using namespace std;

template<typename T> class my_vector
{
public:
my_vector(T* addr)
{
m_ary = addr;
m_ava_idx = 0;
}
~my_vector()
{
//  delete []m_ary;
}

T& operator[](int index)
{
return m_ary[index];
}

void push_back(const T& v)
{
m_ary[m_ava_idx++] = v;
}

void resize(int size)
{
m_ava_idx = size;
}

void shrink(int dec)
{
m_ava_idx -= dec;
}

int size()
{
return m_ava_idx;
}
private:
T*   m_ary;
int  m_ava_idx;
};

// 堆的结点定义
int g_name_pool_index = 0;
char g_name_pool[100001][11];

struct heap_elem_t
{
// string _name;
int _name_index;
int _solved_count;
};

heap_elem_t g_heap_elems0[50002];
heap_elem_t g_heap_elems1[50002];

struct heap_elem_less_comparator
{
bool operator()(const heap_elem_t& left,  const heap_elem_t& right)
{
return left._solved_count < right._solved_count;
}
};

struct heap_elem_larger_comparator
{
bool operator()(const heap_elem_t& left,  const heap_elem_t& right)
{
return left._solved_count > right._solved_count;
}
};

heap_elem_less_comparator less_comp;
heap_elem_larger_comparator larger_comp;

/************************************************************************/
/* inc 为真时调整为小顶堆,为false时调整为大顶堆。                      */
/************************************************************************/
inline void adjust_heap_up(heap_elem_t heap[], int tail_pos, bool inc)
{
if ( inc )
{
push_heap(heap+1, heap+tail_pos+1, larger_comp);
}
else
{
push_heap(heap+1, heap+tail_pos+1, less_comp);
}
}

inline void popup_the_top(heap_elem_t heap[], int tail_pos, bool inc)
{
if ( inc )
{
pop_heap(heap+1, heap+tail_pos+1, larger_comp);
}
else
{
pop_heap(heap+1, heap+tail_pos+1, less_comp);
}
}

int main(int argc, char* argv[])
{
const int BUFF_LEN = 64;
char buff[BUFF_LEN];
int case_count;  // 记有多少个case;
int contestant_count;
my_vector<heap_elem_t> littletop_heap(g_heap_elems0);
my_vector<heap_elem_t> bigtop_heap(g_heap_elems1);
heap_elem_t contestant;
string name;
// vector<string> output_vec;

scanf("%d", &case_count);
for ( int i = 0; i < case_count; i++ )
{
littletop_heap.resize(1);  // 为了方便计算.下标0的位置不存堆的元素.
bigtop_heap.resize(1);
g_name_pool_index = 0;
contestant_count = 0;

while(true)
{
scanf("%s", buff);

int little_heap_count = littletop_heap.size() - 1;
int big_heap_count = bigtop_heap.size() - 1;

if ( buff[0] == 'Q' )  // 查询. Querry
{
if ( little_heap_count == big_heap_count || 0 == contestant_count )
{
printf("No one!\n");
//output_vec.push_back("No one!\n");
}
else
{
printf("%s\n", g_name_pool[littletop_heap[1]._name_index]);
//output_vec.push_back(g_name_pool[littletop_heap[1]._name_index]);
//output_vec.push_back("\n");
}
}
else if ( buff[0] == 'E' )  // 结束.
{
if ( little_heap_count == big_heap_count || 0 == contestant_count )
{
printf("Happy BG meeting!!\n");
//output_vec.push_back("Happy BG meeting!!\n");
}
else
{
printf("%s%s",g_name_pool[littletop_heap[1]._name_index], " is so poor.\n");
//output_vec.push_back(g_name_pool[littletop_heap[1]._name_index]);
//output_vec.push_back(" is so poor.\n");
}

break;
}
else if( buff[0] == 'A' )// 加入参赛者数据.
{
contestant_count ++;

scanf("%s", g_name_pool[g_name_pool_index]);
contestant._name_index = g_name_pool_index;
g_name_pool_index++;
scanf("%d", &contestant._solved_count);

if ( 1 == contestant_count )  // 第一个参赛者数据.
{
littletop_heap.push_back(contestant);
}
else if ( little_heap_count == big_heap_count )  // 两个堆的元素相等.
{
// 新元素大于大顶堆的堆顶元素,所以插入小顶堆.
if ( contestant._solved_count >= bigtop_heap[1]._solved_count )
{
littletop_heap.push_back(contestant);
adjust_heap_up(&littletop_heap[0], littletop_heap.size()-1, true);
}
else
{
heap_elem_t top = bigtop_heap[1];
popup_the_top(&bigtop_heap[0], bigtop_heap.size()-1, false);
bigtop_heap.shrink(1);

bigtop_heap.push_back(contestant);
adjust_heap_up(&bigtop_heap[0], bigtop_heap.size()-1, false);

littletop_heap.push_back(top);
adjust_heap_up(&littletop_heap[0], littletop_heap.size()-1, true);
}
}
else  // 不等.只可能是小顶堆比大顶堆多1.
{
if ( contestant._solved_count > littletop_heap[1]._solved_count )
{
littletop_heap.push_back(contestant);
adjust_heap_up(&littletop_heap[0], littletop_heap.size()-1, true);

heap_elem_t top = littletop_heap[1];
popup_the_top(&littletop_heap[0], littletop_heap.size()-1, true);
littletop_heap.shrink(1);

bigtop_heap.push_back(top);
adjust_heap_up(&bigtop_heap[0], bigtop_heap.size()-1, false);
}
else
{
bigtop_heap.push_back(contestant);
adjust_heap_up(&bigtop_heap[0], bigtop_heap.size()-1, false);
}
}
}
}

if ( i + 1 < case_count )
{
printf("\n");
//output_vec.push_back("\n");
}
}

//for ( int i = 0; i < output_vec.size(); i++ )
//{
// cout << output_vec[i];
//}

return 0;
}

 

 
//////// 上面的代码在中山大学ACM网站 www.soj.me 上通过.目前的成绩是第14名.
 
Rank  14    2011-12-07 10:00:19    0.18 sec    2160 KB    6971 Bytes     C++   zausiu
 
注意上面的代码绝不能用C++的标准IO cin cout 做输入输出.如果用C++的IO流会造成超时。我为了调这个超时问题调了整整一天!死活想不到是因为C++ IO的问题.童鞋,一定要用 scanf 和 printf 啊。面对十万级的IO,尤其是在做ACM题,cin cout 是魔鬼。
 
原因是:
 
More should be noted about I/O operations in C++. Due to their complex underlying implementation  models, cin and cout are comparatively slower than scanf and printf. The difference in performance is shown by many experiences to be more significant if the program is compiled by G++. Therefore if a problem has huge input, using cin and cout will possibly lead to Time Limit Exceed.
 
6 测试数据;
 
用一个简单的BASH脚本来创建测试用例。
 
#! /bin/bash

INDEX=1

SHRESHOLD=100000   // 建十万条数据.



while [ $INDEX -lt $SHRESHOLD ]

do

echo "ADD name$INDEX $RANDOM"

let "INDEX=$INDEX+1"

done

 

 
 
7 对时间复杂度,空间复杂度方面的分析.
 
时间复杂度是O(log n), 空间复杂度是 O(n).
 
 
 
附原题:
 
 
 
 
 
1022. Poor contestant Prob
 
Description
 
 
 
As everybody known, “BG meeting” is very very popular in the ACM training team of ZSU.
After each online contest, they will go out for “smoking”. Who will be the poor ones that have to BG the others? Of course, the half who solve less problems.
The rule runs well when the number of the contestants is even. But if the number is odd, it is impossible to divide them into two equal parts. It gives a dilemma to the BG meeting committee. After a careful discussion with Mr. Guo, a new rule emerged: if the number of the contestant is odd, the committee will first sort the contestants according to the number of problems they solved, and then they will pick out the middle one. This poor boy or girl will have no chance to attend the BG meeting.
Strange rule, isn`t it?
As the number of the contestants is becoming more and more large, the committee need to write a program which will pick out the poor one efficiently.
Note that: Every contestant solves different number of problems. The total number of the contestants will not exceed 10^5.
 
 
 
Input
 
 
 
There are several cases in the input. The first line of the input will be an integer M, the number of the cases.
Each case is consisted of a list of commands. There are 3 types of commands.
1. Add xxx n : add a record to the data base, where xxx is the name of the contestant, which is only consisted of at most 10 letters or digits, n is the number of problems he/she solved. (Each name will appear in Add commands only once).
2.Query :
3.End :End of the case.
 
 
 
Output
 
 
 
1.For the Query command: If the current number of contestants is odd, the program should output the poor contestant’s name currently even if there is only one contestants, otherwise, just out put “No one!” (without quotes).
2.For the End command:
If the total number of contestants in the data base is even, you should out put “Happy BG meeting!!”(without quotes),otherwise, you should out put the “xxx is so poor. ”(without quotes) where xxx is the name of the poor one.
3.Each case should be separated by a blank line.
 
 
 
Sample Input
 
2
Add Magicpig 100
Add Radium 600
Add Kingfkong 300
Add Dynamic 700
Query
Add Axing 400
Query
Add Inkfish 1000
Add Carp 800
End
 
Add Radium 100
Add Magicpig 200
End
Sample Output
 
No one!
Axing
Radium is so poor.
 
Happy BG meeting!!
Problem Source
 
ZSUACM Team Member
 

 

熬夜完成 sicily1153 马周游解题报告。困死哥了.

唉!!! 上次交作业写错题目了,做了简单的马周游 sicily 1152。补上新的,应该是sicily 1153.为了解决规模太大的问题。加上了优化算法。

 
中大ACM实验题。
 
(1)原题中文大意
 
中国象棋的马按照象棋的规则在8 x 8 的棋盘上跑64步跑完所有的格子。
 
 
 
(2)算法思想及解题用到的主要数据结构
 
 
 
从每一个点往下走第二步,会有几点有效的行走位置。 把当前位置记在栈里面,以深度优先的方式进入下一个有效位置。如果下一个有效位置在之前已经走过,则从栈顶弹出上一位置,恢复到调出的位置后尝试未走过的有效位置。利用函数调用时会压栈的特别,用函数递归调用即可解决问题。
 
软之简单的马周游,8 x 8 棋盘的规模非常大。需要在可选下一步中找到最接近正确路线的点。求该点的办法是把所以的可选点先找出,再给这些可选点按权重排序,从最优的解依次向次优,次次优…..的点试探。重点在权重的算法。这里的权重的计算法则是指一个点的下一次可走的点的个数。
 
主要的数据结构有:
 
// elocution数组在初始化后会记下每个有效位置的下一步有哪些可走位

// 置.elocution[x][0]用下标0记个数。最多8个有效可走位置。

char elocution[ELEM_COUNT][9];

// stamps数组记每个点是否已经走过了。0表示没走过,1表示走过了。

char stamps[ELEM_COUNT];

// track数组记路径的顺序。

char track[ELEM_COUNT];

通过结合stamps数组和elocution数组可以算出下一步的每个点的权重。



(3)详细解题思路

1. 先初始化一张表。这张表记下了棋盘上所有的30个位置的下一步可走的有效位置.

2. 写一个一般的递归调用自己的函数,表示马在走第几步时到了哪个位置,然后求出余下的所有可走位置。

3. 余下的所有位置按照上文提到的权重排序。

4. 对于排序后的可选点数组,按顺序依次用递归函数尝试。

5. 递归函数有三个退出条件。1.下一个要尝试的点已经走过了,2.试完了所有的可选下一步无解。3.走到了最后一步,即得解!



(4)算法描述

初如化上文提到的elocution数组,清空stamps和tracks.从起点开始调用递归函数。

http://ykyi.net  zausiu's blog.



(5)程序注释清单

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <vector>

#include <csetjmp>

//#include <cassert>



using namespace std;



#define  ROW_NUM     8

#define  COLUMN_NUM  8

#define  ELEM_COUNT ROW_NUM * COLUMN_NUM



jmp_buf jmpbuffer;  // 很深的函数递归调用时用longjmp快速退出.



// elocution数组在初始化后会记下每个有效位置的下一步有哪些可走位

// 置.elocution[x][0]用下标0记个数。最多8个有效可走位置。

char elocution[ELEM_COUNT][9];



// stamps数组记每个点是否已经走过了。0表示没走过,1表示走过了。

char stamps[ELEM_COUNT];



struct coordinate  // 二维坐标

{

char _x;  // start from zero.

char _y;

};



// 作标转序号

char coordinate2serial_num(coordinate co)

{

char num = co._x * COLUMN_NUM + co._y + 1;

return num;

}

// 序号转坐标

coordinate serial_num2coordinate(char sn)

{

coordinate co;

co._x = (sn - 1) / COLUMN_NUM;

co._y = sn - co._x * COLUMN_NUM - 1;

return co;

}



// ((x:1;y:-2),(x:2;y:-1),(x:2;y:1),(x:1;y:2) (x:-1;y:2),(x:-2;y:1),(x:-2;y:-1),(x:-1;y:-2));

char increments[8][2] =

{

1, -2, 2, -1, 2, 1, 1, 2,

-1, 2, -2, 1, -2, -1, -1, -2

};

void next_step(char pos, char steps[])  // 把位置在pos序号的点的每一个下一个可选位置记在数组中。

{

char valid_count = 0;

coordinate co = serial_num2coordinate(pos);

coordinate tmp;

char serial_num;

for ( int i = 0; i < 8; i++ )

{

tmp._x = co._x + increments[i][0];

tmp._y = co._y + increments[i][1];

if ( tmp._x < 0 || tmp._x >= ROW_NUM || tmp._y < 0 || tmp._y >= COLUMN_NUM )  // 保证位置有效

{

continue;

}

serial_num = coordinate2serial_num(tmp);

if ( serial_num >= 1 && serial_num <= ELEM_COUNT )

{

valid_count++;

steps[valid_count] = serial_num;

}

else

{

cerr << "Not expected to reach here.\n";

}

}

steps[0] = valid_count;

}



// 下面的逻辑以每个点的下一步可跳点的数目作为权重排序。

struct pos_weight

{

char _pos;

char _weight;

};

// 又是用递归。这里为了实现快速排序

int partition(pos_weight poses[], int low, int high)

{

pos_weight pivot = poses[low];

while (low < high)

{

while (low < high && pivot._weight < poses[high]._weight)

high--;

poses[low] = poses[high];

while (low < high && pivot._weight >= poses[low]._weight)

low++;

poses[high] = poses[low];

}

poses[low] = pivot;

return low;

}

// 快速排序。

void quick_sort_steps(pos_weight poses[], int low, int high)

{

if ( low < high )

{

int pivot_loc = partition(poses, low, high);

quick_sort_steps(poses, low, pivot_loc-1);

quick_sort_steps(poses, pivot_loc+1, high);

}

}

void rearrage_steps(char poses[], int len) // poese里放置了下一个位置数组。Len是数组长度。

{

char weight, pos, next_step_count;

vector<pos_weight> vec(len);

for ( int i = 0; i < len; i++ ) // 计算权重.

{

weight = 0;

pos = poses[i];

next_step_count = elocution[pos-1][0];

for ( int j = 0; j < next_step_count; j++ )

{

char next_step_pos = elocution[pos-1][j+1];

if ( 0 == stamps[next_step_pos-1] )

{

weight++;  // 如果有一下一跳点没走过则权重加1.

}

}

vec[i]._pos = pos;

vec[i]._weight = weight;

}

quick_sort_steps(&vec[0], 0, len-1);  // 根据权重排序.

for ( int i = 0; i < len; i++ ) // 把排序后的位置写回原始数组.

{

poses[i] = vec[i]._pos;

}

}



void init_elocution()

{

memset(stamps, 0, sizeof(stamps));

for ( int i = 1; i <= ELEM_COUNT; i++ )

{

next_step(i, elocution[i-1]);

}

}



char track[ELEM_COUNT];

void run_horse(char start_pos, char step_count) // step_count [0 -- 64)

{

// 如果已经经过这点就立即退出函数。

if ( 1 == stamps[start_pos-1] )

{

return;

}



track[step_count] = start_pos;



if ( step_count == COLUMN_NUM * ROW_NUM - 1 )  // 是不是最后一步。

{

for ( int i = 0; i < sizeof(track); i++ )

{

cout << (int)track[i];

if ( i + 1 != sizeof(track) )

{

cout << " ";

}

}

cout << endl;

longjmp(jmpbuffer, 0x1);

return;

}



// 记下已经走了这一步。

stamps[start_pos-1] = 1;   rearrage_steps(elocution[start_pos-1]+1, elocution[start_pos-1][0]);

for ( int i = 0; i < elocution[start_pos-1][0]; i++ )

{

run_horse(elocution[start_pos-1][i+1], step_count+1);

}

stamps[start_pos-1] = 0;  // 试完了所有可走步.退出这个函数.重置这个位置为没有走过。

}



int main(int argc, char* argv[])

{

int pos;

vector<int> vec;



while(true)

{

cin >> pos;

if (pos==-1)

{

break;

}

vec.push_back(pos);

}



for ( int i = 0; i < vec.size(); i++ )

{

if(setjmp(jmpbuffer) == 0)  // 为了很深的递归函数快速回退到这里。

{

init_elocution();

memset(track, 0, sizeof(track));

memset(stamps, 0, sizeof(stamps));

run_horse(vec[i], 0);

}

}



return 0;

}

 

(6)该算法的时间复杂度是 O(8 ^ (m * n))   m,n分别为棋盘的长和宽。
 
 
 
/////////////////// 原题目如下:
 
 
 
1153. 马的周游问题
 
 
 
Description
 
和题目C同样的任务,这里只是把棋盘扩大到标准的国际象棋。对这样一个8 * 8的棋盘用同样的方法编号如下:
 
1     2     3       4     5     6       7     8
 
9     10       11    12       13    14       15    16
 
17    18       19    20       21    22       23    24
 
25    26       27    28       29    30       31    32
 
33    34       35    36       37    38       39    40
 
41    42       43    44       45    46       47    48
 
49    50       51    52       53    54       55    56
 
57    58       59    60       61    62       63    64
 
Input
 
输入有若干行。每行一个整数N(1<=N<=64),表示马的起点。最后一行用-1表示结束,不用处理。
 
Output
 
对输入的每一个起点,求一条周游线路。对应地输出一行,有64个整数,从起点开始按顺序给出马每次经过的棋盘方格的编号。相邻的数字用一个空格分开。
 
Sample Input
 
4
-1
Sample Output
 
注意:如果起点和输入给定的不同,重复多次经过同一方格或者有的方格没有被经过,都会被认为是错误的。
 
 
 

 

又是数组越界造成的bug.

又一次遇到数组越界造成的奇怪的,难以调试的,诡异的bug.

前几天做ACM题。‘简单的马周游’。

http://ykyi.net/2011/11/acm-%E9%A9%AC%E5%91%A8%E6%B8%B8%E8%A7%A3%E9%A2%98%E6%8A%A5%E5%91%8A/

因为我的解法用了函数递归调用,函数求到最终解的栈的调用层次非常深。第一版用置一个全局变量的方式让这么深调用的函数快速依次退出。但我也知道还有另外一种解法就是用C语言的setjmp 和 longjmp。用这两个函数可以快速退栈。

 

今天晚上就想用setjmplongjmp改写一下。本来以为是非常简单的事情。结果改完以的程序只能正确求解第一个请求,然后程序看起来就像是死了。Debug时发现程序似乎跑飞了。哎(脑子不灵光,发现程序跑飞竟然没有立即想到是数组越界把堆栈写坏了)。因为我改动的代码非常少,只是用setjmplongjmp快速退出递归取代之前的稍微比较慢的做法。而其它的代码改动的非常之少。于是我当时分析错误的出发点就是比较两份代码的异同。比较来比较去,就只有退出方式不同而已。相当相当地困惑。费了很多时间都没有找到原因。

实在搞不定了。冲了个热水澡,又回来看代码。还是没有发现这个改动在哪里引入了错误。不断反复地看代码,突然灵光一现看到写一个全局数组的语句,下标变量越界!越界!越界!!!啊~~惊喜!于是把数组下标的相关的代码纠正了,于是setjmp版本的代码也运行正常啊。

这次的经验是。操作数组的时候一定要一定要一定要非常非常非常之小心~~在调试程序发现程序跑飞的情况下马上要意识到是写坏了堆栈。

 

另外还有一个疑问是第一版的代码也有写坏栈的问题为什么就一切正常呢。这就是C/C++程序数组危险的地方啊~~第一版本的代码退栈的方式和第二版不一样,于是这个bug就在第一版隐藏了起来。于是第二版出问题时我的思路集中在比较代码差异是如何引入问题的。而这个bug并不是新代码引入的,而是在旧代码隐藏起来的,第二代的新代码让触发了这个bug

总结下经验:

一定要一定要非常小心C/C++的数组越界问题啊!!!操作很多数组时,有很多下标要计算时。千万要注意是从0还是从1开始计算下标。要根据约定多下诊断!!!及时发现隐藏的错误。越界写数组的bug有时发生,可能在引入的当时被隐藏,隐藏的很深很深。但越界读数组的bug隐藏得更深更深更深啊。

copyright ykyi.net

 

中大ACM题.商人的宣传解题报告.

Description

Bruce是K国的商人,他在A州成立了自己的公司,这次他的公司生产出了一批性能很好的产品,准备宣传活动开始后的第L天到达B州进行新品拍卖,期间Bruce打算将产品拿到各个州去做推销宣传,以增加其影响力。

K国有很多个州,每个州都与其他一些州相邻,但是K国对商人作宣传却有一些很奇怪的规定:
1、 商人只能从某些州到达另外一些州,即连通路线是单向的,而且有些州可能是到达不了的。
2、 商人不允许在同一个州连续宣传两天或以上,每天宣传完必须离开该州。
3、 商人可以多次来到同一个州进行宣传。

"我必须找出一条影响力最大的路线才行",Bruce想,"但我首先必须知道到底有多少这种符合规定的宣传路线可供我选择。"现在Bruce把任务交给了你。并且出于考虑以后的需要,你还要帮他算出给出的两州之间的路线的总数。

 

Input

输入文件第一行包含三个整数n,m,L(1≤n,L≤100),分别表示K国的州数、连通路线的数量,以及多少天后必须到达B州。接下来有m行,每行一队整数x,y(1≤x,y≤n),表示商人能从x州到达y州。
第m+2行为一个整数q(1≤q≤100),表示Bruce有q个询问。下面q行每行两个整数A,B(1≤A,B≤n),即A、B州的位置。

Output

输出文件包含q行,每行一个整数t,为所求的从A州到B州满足上述规定的路线总数。
输入数据中的询问将保证答案t在长整数范围内,即t<231

Sample Input

4 5 6
1 2
2 3
3 4
4 1
2 4
2
1 4
4 2

Sample Output

2 1

1. 原题中文大意.

商人的宣传即是一个有向图的问题。有一个有向图。该图的每条件权重一样,从图中任意一点a刚好通过L步到达另一点b有多少条路线。

 

 

2. 算法思想及解题思路.

使用了动态规划算法。令 dp[num][dest] 表示从起点通过 num 条边到达终点共有多少种走法。

先由已经知条件易得从起点通过一条它的邻接边到达它的所有邻接点共有一条路线。即 dp[1][邻接点易求得。而 dp[x][y] = sum( dp[x-1][可以一条邻接边到达y的点] )

 

3. 主要数数据结构.

主要数据结构为三个数组。这本个数组都不用下标为0的元素。

char odgree[MAX_VERTICES_NUM+1];

下标为每个顶点的编号.表示每个顶点的出度

int routine[MAX_VERTICES_NUM+1][MAX_VERTICES_NUM+1];

‘路由表’ routine[x][n] = y 表示从顶点x经它的第n条邻接边可以到达顶点y.

int dp[MAX_VERTICES_NUM+1][MAX_VERTICES_NUM+1];

这个数组即第二节提到的dp数组,dp[L][x] = num从起点开始经L条边走到顶点 共有 num 种走法。

 

4. 逐步求精算法描述(含过程及变量说明);

从已知条件初始化 odgree 和 routine 数组.

bzero(odgree, sizeof(odegree));

for(int x,y, i = 0; i < m; i++)

{

scanf("%d %d", &x, &y);

odgree[x]++;

routine[x][ odgree[x] ] = y;

}



下面的cal函数输入起点顶点和终点顶点,返回共有多少种走法。

int cal(char start, char dest)

{

memset(dp, 0, sizeof(dp));



for ( int i = 1; i <= odgree[start]; i++ )  // 遍历起点的每一条邻接边

{

dp[1][ routine[start][i] ]++;  //  初始时经过一邻接边到达别一点的走法有几种.



}



for ( int i = 2; i <= L; i++ )   // 一直走到第L步.

{

for ( int j = 1; j <= n; j++ )  // 遍历每一个顶点.

{

for ( int k = 1; k <= odgree[j]; k++ )  // 该顶点的第一条邻接边

{

// 上文提到的递推公式。

dp[i][ routine[j][k] ] += dp[i-1][j];

}

}

}



return dp[L][dest];  // 返回结果

}

 

5. 程序注释清单

#include <cstdio>

#include <cstdlib>

#include <memory>

#include <cstring>

#include <vector>



using namespace std;



const int MAX_VERTICES_NUM = 100;  // 最多多少个顶点.

int n, m, L, q;  // 实际n个点、m条边,L 为期限.q为有多少个询问.

static char odgree[MAX_VERTICES_NUM+1];  // 记每个点的出度.不用下标为0的元素.

static int routine[MAX_VERTICES_NUM+1][MAX_VERTICES_NUM+1];  // table[x][y] 表示x点经它的第y条边可以去到哪个点.

static int dp[MAX_VERTICES_NUM+1][MAX_VERTICES_NUM+1];  // dp[x][y] 表示经x条边,可以从某点到 y 点.



int cal(char start, char dest)

{

memset(dp, 0, sizeof(dp));



for ( int i = 1; i <= odgree[start]; i++ )  // 遍历起点的每一条邻接边.

{

dp[1][ routine[start][i] ]++;  // 初始时经过一步到达别一点的走法.

}



for ( int i = 2; i <= L; i++ )   // 一直走到第 L 步.

{

for ( int j = 1; j <= n; j++ )  // 遍历每一个点.

{

for ( int k = 1; k <= odgree[j]; k++ )  // 该点的每一个邻接点.

{

dp[i][ routine[j][k] ] += dp[i-1][j];

}

}

}



return dp[L][dest];

}



int main(int argc, char* argv[])

{

while ( EOF != scanf("%d %d %d", &n, &m, &L) )

{

memset(odgree, 0, sizeof(odgree));

for(int x,y, i = 0; i < m; i++)

{

scanf("%d %d", &x, &y);

odgree[x]++;

routine[x][ odgree[x] ] = y;

}



scanf("%d", &q);

vector<int> results;

for ( int start,dest, i = 0; i < q; i++)

{

scanf("%d %d", &start, &dest);

results.push_back(cal(start, dest));

}

for ( int i = 0; i < results.size(); i++ )

{

printf("%d\n", results[i]);

}



}

return 0;

}

 

6. 测试数据

4 5 6

1 2

2 3

3 4

4 1

2 4

5

1 4

4 2

2 1

1 3

3 4

2

1

2

1

0

 

 

7. 对时间复杂度,空间复杂度方面的分析、估算及程序优化的分析和改进.

本解决方法的时间复杂度为O(L*n*n),空间复杂度为O(n*n).

用动态规划解此题的时间复杂度优于用邻接矩阵表示图然后用图的乘法解出。后者的时间复杂志为O(L*n*n*n)

initramfs 和 initrd 的区别

Linux 2.6内核引入了一个新的feature叫做initramfs。与initrd相比,initramfs有几个好处。
initrd模拟一个磁盘(这就是它的名字的由来,initramdisk或initrd)。模拟磁盘也就同时引入了Linux的块IO子系统的开销,比如缓存(caching),而initramfs从根本上把cache也装载(mounted)成filesystem(因此叫做initramfs).

Initramfs建立在page cahce之上,和page cache一样,会动态地自动增长和缩减尺寸来减入内存的使用量,而initrd做不到这点。
另外,不像initrd需要文件系统驱动(filesystem driver)的支持,比如EXT2 driver,如果你的initrd使用ext2。而initramfs则不需要文件系统的支持,initramfs的实现代码很简单,只是基于page cache的简单一层。

copyright ykyi.net