Welcome to my space!

big-endian 和 little-endian 是内存中存储数据的两种不同方法。

所谓大端和小端指的是多字节值的哪一端存储该值的起始地址。

如一个32位整数n=0x01020304，01这一端称为大端，04称为

小端，如果该4字节数据在内存中的地址从左到右递增，即大端

存储起始地址，我们称其为大端(big-endian)存储法，否则为

小端(little-endian) 存储法。

 

以下C程序用来判断一台机器使用哪种存储方法

#include <stdio.h>
int main()
{
    union
    {
        short a;
        char b[2];
    }x;
    x.a=0x0102;
    if(sizeof(short)==2){
        if(x.b[0]==0x01&&x.b[1]==0x02) printf("big-endian\n");
        else if(x.b[0]=0x02&&x.b[1]==0x01) printf("little-endian\n");
        else printf("neither\n");
    }else printf("size of short=%d\n",sizeof(short));
    return 0;
}

我们的新书终于出版了，isbn是9787121074356，在搜索引擎上也能搜到了

 

下面是百度结果:

 

这是谷歌的：

 

该书适合那些有一定的程序设计基础，希望在算法方面有所提高的中学生和大学本科生。

尤其适合参加ACM/ICPC或者NOIP的同学，本书可以作为一本入门级的教材。

我们力求以最平实的语言来刻画题目背后的算法，希望读者可以通过例题举一反三，

毕竟我们的目的不是教会你做某一道题。

 

由于该书的作者多为在校学生，受水平和经验所限，书中难免有所差错，欢迎各位读者指正。

mail: is03wlei@163.com (王磊)

qq: 12940076 ^_^

 

 

                                      

　　研究生入学一个月了，现在看来，和本科时的感觉相差不大，主要还是上课。

三门必修：程序设计理论，算法和英语。程序设计理论有点难，不习惯那本英文

教材里描述定义和定理的方式，感觉好多地方并不严谨。英语课遇上个变态的口

语老师，还是个乌克兰人，真不知道英语怎么说得那么好，此君作业留得奇多，

定了若干规矩，动不动就要扣分，比如迟到一次扣５分，三次没成绩，课堂提问

不会扣Ｘ分，每次课要看20页的阅读，还要retell the story....至于算法课，就

比较轻松了，大部分都是比较熟悉的内容，每次去上课都是看其他书。

　　下个月又要出去比赛了，这将是我最后一年参加acm分区赛，11月3号去长

春，９号要赶去越南的砚港。肥东和我两个老人带着张大牛，两个老家伙都已经

参加过world finals了，心情应该比较放松了，只是张大牛作为现役中大acm第

一人其压力应该是有的，两个老家伙就尽全力辅佐他吧，希望不要留给他什么

遗憾，也希望他能够轻松上阵。我们去年在河内能够出线就是因为心境比较好，

赛前没有想关于出线的事情。连续两年都去越南，略感郁闷，去年在首都河内尚

且饿个半死，何况这次是个不知名的小城市，一点兴奋感都没有，好在赛后会

去胡志明玩，领略一下传说中的西贡女人。

　　这学期依然是孤家寡人一个，唉，知己可遇不可求啊，也怪自己的生活圈子

太小了，没机会认识女生。本来想工作以后再考虑这些事情的，可是家里人开始

施加压力了，不得不提前了。想我这样一个不喜欢广东的人想在这里找个女朋友

应该是相当困难的，而且前景也是不容乐观的，周围的人大多毕业后留在广东，

而我在主观上是一百个不愿意，我又是那种把找女朋友当作找老婆的人，不愿意

浪费丝毫精力去经营一个没有结果的爱情。这几天看friends，看到ross，joey

他们都有结婚后备人选，自己也yy了一下，可是我还没有和哪个女生亲密到她

愿意做我的后备，所以也仅限于yy了。

 

             

这篇总结拖了太久了，前段时间以写论文为借口，迟迟没有写。比赛过去将近两个月了，不过这样的比赛是值得永远记住的，不论成绩怎么样。下面简单记一下在东京的见闻吧。

 

3月12日

       上午10点从香港出发，经过4小时的飞行到达东京成田机场。过关时很不顺利，我的箱子被翻了个底朝天，小鬼子把里面的布都扯烂了，估计是怕里面藏着毒品。从机场到驻地很远，地铁票也是非常的昂贵，1000多日元。天黑的时候到达disney resort，一出来立刻感受到浓郁的迪斯尼的气氛。这时自然是例行的拍照了，小bug刚到日本就出洋相了，一个日本女人走过来拿着照相机跟bug示意帮忙照张相，bug吓得屁滚尿流的跑了，我们狂汗。然后打的到hilton tokyo bay，短短几百米花了700块。我在想这样的地方以后自己有没有机会来呢？

       到达酒店后，又是先见到浙大的兄弟们，他们早到一天。然后郭老师跟大傻去注册，我在一边无聊地玩起了乐高。

       晚上去cyber café逛了一下，始终上不了argo，郁闷。然后看到跳舞机那里有几个美女，就站下来看了一会儿。这里还有下棋的和打牌的，看到petr在虐别人，不禁想起咱们的kk大哥。

 

3月13日

       上午是IBM的tech trek，实在是无聊的很，因为听到鬼佬不时的哈哈大笑，我们根本不知道人家在说什么，感觉特困。

       中午组织游览disneysea park，这个地方真是不错。首先布景非常好，感觉像进了童话世界。大型的水上表演加上礼花非常的震撼人心。还有很多刺激的游戏，不过都要排很长的队，我们玩了过山车，还有一个骗人的海底探险，进去以后玻璃外面不断喷水泡，还以为真在水里呢，后来被大傻发现说水泡是在两层玻璃之间的。来这里玩的基本上都是我们这个年纪的，好像mm更多，可让我们饱了眼福了，经过那期间的观察，这儿应该是美女最多的地方了。当时天气还比较冷，她们的典型服饰却是短裙。

       中午在disney这一餐彻底把我吃穷了，组委员赞助了3000块餐费，我一顿就吃了2400，哪里够吃啊，下顿要挨饿了，好在后来在disney外吃的都很便宜。

3月14日

       因为第二天要正式比赛了，所以这天以休息为主。下午进行了短暂的试机，不过却遇到了一件很郁闷的事情。我们三个走的时候忘带密码纸了，结果被组委会叫去质问，说有人试图在我们的计算机上访问其他计算机，我们立刻表示我们不知道，并且道歉。以后参加final的同学不要再犯这个错误了。

3月15日

       最不想提起比赛的部分了，开始的形势非常好，过3题时排在第3，过4题时排第10。交第5题时还剩1小时10分钟，我跟他们说，再过两题应该可以拿牌了，谁知最后一题也过不了。我们总共开了6题，说实话，算法性都不强。我们最后拼命做的那个D题是个阴险题，最后结果是64位整数，中间结果却狂溢出，而且只有直接计算出公式时才会溢出，大概就是这样a*b-c*d，两个大数相减，a*b溢出，有些队是用复杂度较大的累加法来计算的，这样就不会溢出，实在是没意思。不知道当时在想什么，三人都不够冷静，竟然没有使用高精度，总是想着可能改个小地方就能过，然后就有时间做F。其间大傻也在写F，bug和我则在想着改D。时间慢慢过去了，由于F是个代码量较大的广搜题，所以最终放弃了。三人一起改D，希望能再过一题。可是改的太没有目的性了，最后十几分钟的时候，我尝试用java来写，不过没有写完……

       就这样浑浑噩噩地度过了最后一小时，毫无建树，三人无比沮丧。封board时排15名，最后却掉到了26，实在是丢人。

       感觉这样的比赛心理素质太重要了，不要奢求什么超常发挥，能够把平时的水平发挥出来应该就能够取得很好的名次了。会做的题过不了，实在是太遗憾了。

       颁奖之后的演出相当不错，印象最深的是那个偷东西的家伙，上去的时候就从观众席偷了一堆手表，然后又把这些人叫上去，把表还给他们，再偷个钱包，腰带什么的。有个北航的朋友也上去玩了，他很自信的认为那人偷不走他的东西，被人家耍了几分钟后，很自信的走下台，并举起双手向观众致意，意思是没被偷，谁知”小偷”却拿出了他的领带，真是不可思议，我都没看见那家伙怎么偷的。下来问朋友，他说一点感觉都没有，实在太强了。在观众的强烈要求下，”小偷”又偷了一只内裤，不知是真是假，感觉这个应该是魔术，不然难度太大了。其实这家伙是反扒的，发现谁被偷了东西，就再把它偷回来。

3月16日

       搬到市区去住，酒店离皇宫比较近。中午去吃饭的时候可费了不少劲，花了两个小时的时间来找餐馆，不是餐馆少，是不知道该吃什么，看到非常多的中国料理，在咱中国还没听过这个词，在这倒挺流行的。

3月17日

       早上出发准备去游皇宫，发现走过一扇小门可以到楼外面去观景，谁知四个人过来后却被锁在外面了，没办法只能开辟新路，从紧急楼梯下去。

       日本的皇宫实在是没意思，由于有皇室成员居住，所以不能进去参观。只能看到最外面的两个宫殿，两个守卫换班的时候还挺有意思的。

       下午去了银座，就是日本最繁华的地方，toshiba的总部就在这里。还看到了歌舞伎馆。

       晚上去了新宿，这里主要是购物的地方，比如数码产品，都说日本相机便宜，很想买一部，不过看了一下好像比国内的还贵。

3月18日

       去上野公园看樱花，因为天气太冷，樱花还没大规模开放，只看到零星的几朵。然后碰到几个中国朋友，用英文让大傻帮忙照相，发现是中国人后聊了一会，其中还有一个内蒙古的老乡呢。

       去机场回家。坐地铁时误入头等车厢，其实只坐了一站，售票员要求我们补票，贵得吓人，跟她们解释了一下，由于沟通困难，最后不了了之了。

 

       7天的旅行总体来说还不错，充分感受了world finals那种处处都非常正规的赛事安排，领略了世界顶级高手的风采，忘不了hilton美妙的自助早餐和东京湾清爽的空气，忘不了那些有着复杂的控制面版的马桶，喜欢那种车停下来让你过马路的感觉。还有，日本的地铁检票系统非常不完善，我一直认为可以轻易的逃票，去机场的时候把地铁票丢在了车上，却轻易的逃了出去，可能像我这样逃票的人不多，不然地铁公司要倒闭了。

 

问题:完全图去掉一条边后有多少个生成树?

 

假设去掉的边为1-n，考虑包含1-n这条边的生成树有多少个，

来看这些生成树的prufer code有什么特点，若节点1成为叶子，

则其一定是编号最小的叶子，与其相连的一定是节点n，于是

prufer code的当前输出为n，且1不在之后的输出中出现。

即prufer code为如下形式：

 

n,.....

1,n,......

...,1,n,...

....

...,1

 

这些code的个数为

(n-1)^(n-3)+sigma[n^i*(n-1)^(n-4-i),n-4>=i>=0]+n^(n-3)

=(n-1)^(n-3)+

  (n-1)^(n-4)*[1-(n/(n-1))^(n-3)]/(1-n/(n-1))+

  n^(n-3)

=(n-1)^(n-3)+(n-1)^(n-3)*[(n/(n-1))^(n-3)-1]+n^(n-3)

=(n-1)^(n-3)+n^(n-3)-(n-1)^(n-3)+n^(n-3)

=2*n^(n-3)

 

所求解为n^(n-2)-2*n^(n-3)=(n-2)*n^(n-3)

 

其实不用prufer code有更简单的解法

考虑每条边在所有生成树中出现的次数之和，

设X为包含某条固定边的生成树的个数，

则：

n^(n-2)*(n-1)=C(n,2)*X

X=2*n^(n-3)

 

最后解为n^(n-2)-X，与前面的结果相同。