机房

我终于荣升为机房党，o(∩∩)o…哈哈。原先是在二楼机房的，由于教室不够（学校事业蓬勃发展？？orz），所以二楼机房要改作教室，于2011.07.29提前搬入四楼机房，和众大牛混在一起。我记得在现代的时候，我用的是38号机子，如今我用的是36号（从二楼拿上来的），同时38号机被当作了共享机兼服务器（cena测评、课件程序等文件共享、Tor代理服务器、CS服务器），使用远程桌面控制……我跟38可真有缘啊……

四楼机房其实没有以前老师骗我们的“泡菜味”（隔壁某同学对此深感惊讶），倒是有很多的书以及灰尘……有些书还是已毕业的学长们留下的，Orz。灰尘这种东西没得说了，那天搬机子的时候就感受到了，由于灰尘众多，所以也就把自己的机子和位置擦擦就完事了。四楼某些键盘鼠标过于恶心（有的是沾满灰尘，有的是严重失灵，比方说现在stu38用的那个鼠标），我只得从二楼拿了套上来……

这边确实是拥挤，搬上来的时候想找个位置放机器都难啊，更别说像以前那样一人两台机器那么奢侈了。至于拥挤的原因，倒不是人多，而是书等杂物多，占满了几乎剩下的所有位置……

机器

在现代奢侈惯了（双核+2G+NVIDIA GTS210），来到这里深深感到机器的老旧啊。虽然赛扬2.9G+512M+Intel 865的搭配对于OI来说算是不错了，但是512M内存足实使我们这群新人无语了（其实最早在现代才128M内存呢）。本人RP较好，在来的第一天，就选中了stu36，后来才发现，我的内存比别人多了256M（512M+256M=768M）^_^，据说是某学长去年搜刮到一条512M的内存插上去的。其它同学只能眼馋了，因为他们的机器是256M*2，而主板总共也就2个插槽……娃哈哈，RP高就是有这样的好处。

学习

从福州回来的这个星期没教新课，都在改福州的题目，倒是去福州之前讲了不少，包括了：堆、单调队列、链表、双向广搜、Bellman-Ford、Fleury……现在发现，一到高中就先教了一大堆数据结构！！想想也是，最近这些题目很多要用各种数据结构优化，O(n^2)能降到O(nlgn)甚至O(n)，果然是程序=算法+数据结构~！Orz。现在写堆、链表神马的也都很顺手了，图也更喜欢用邻接表而不是邻接矩阵（对于大部分题目，浪费空间不说还浪费时间）……

玩

是的，高中你得安排好玩和学习的时间。机房Top2游戏：CS1.6、魔兽。由于本人不会魔兽，所以只能玩CS了……可以说全机房的CS技术都是很高的，或者说在每天的练习中都提高不少！至于xun，则是令人蛋疼无比，机房还没有人不会被他虐的……

另外，机房里面怪叫的声音常常出现，“习惯就好了”……- -||原因可能是游戏、AC、WA等等……其实听习惯了还挺好听的……- -!

最近的状况就是这样了，我才新来，好多事情不了解，鉴于好久没更新博客了，就写下此片。

本文使用C++/Pascal两种语言

上次说到了C++的指针，还不算很蛋疼，今天这个是相当蛋疼：函数指针！

1
2
3
4
5
6
7
8

double pow(double a, int b)
{
  double ans = 1;
  for (int i=1; i<=b; ++i) ans*=a;
  return ans;
}
double (*aa)(double, int) = &pow;//定义了一个指针aa，并把它指向了形参列表和返回类型都匹配的函数pow
cout << aa(2, 10);//等同于调用pow(2, 10);

1
2
3
4
5
6
7
8
9
10

var aa:function (a:extended;b:longint):extended;
function pow(a:extended;b:longint):extended;
  var i:longint;
  begin
    pow:=1;
    for i:=1 to b do pow:=pow*a;
  end;
begin
  writeln(aa(2,10));
end.

在OI中，经常要用到递推，有时候递推式可以转换为变量间的转换，比如Fibonacci数列。而当数据量提升时，就常常要用到高精度算法，也就将单个变量转化为数组，因此就用到了数组的复制。对于C/C++用户，可以使用memcpy函数；对于pascal用户，可以直接赋值；另一个通法则是用循环遍历并复制数组。但不管怎样终究是要复制数组，这一步需要额外O(n)的时间（n代表数组元素个数）。说是额外，因为这可以当作一个常量，并不算在算法的时间复杂度上。比方说我们一般认为计算Fibonacci数列的时间复杂度是O(n)。

f2 = 0
f3 = 1
for i=2 to n
  f1 = f2
  f2 = f3
  f3 = f1 + f2

可以看出f1,f2,f3是循环的。那么既然复制数组的时间很长，为什么我们不用指针呢？复制指针只需要O(1)的时间，说不定能大大的缩短程序运行的时间。下面分别是采用直接复制和复制指针的两个程序（pascal语言）： Read on →

新斯诺克( ( ( sheeta.pas/c/cpp sheeta.pas/c/cpp sheeta.pas/c/cpp ) ) )
【问题描述】
斯 诺克又称英式台球，是一种 流行的 台球运动 。在球桌上 ，台面四角以及两长边中心位置各 有一个球洞，使用的球分 别 为 1 个白球， 15 个红球和 6 个彩球（黄、绿、棕、蓝、粉红、黑）共 2 2个球。击球顺序为一个红球、一个彩球直到红球全部落袋，然后以黄、绿、棕、蓝、粉红、黑的 顺序逐个击球，最后以得分高者为胜。 斯诺克的魅力还在于可以打防守球，可以制造一些障碍球使 对方无法击打目标球而被扣分。正是因为这样，斯诺克是一项充满神奇的运动。
现在考虑这样一种新斯诺克，设母球（母球即是白球，用于击打其他球）的标号为 M ，台面 上有 N 个红球排成一排，每一个红球都有一个标号，他们的标号代表了他们的分数。
现在用母球击打这些红球，一杆击打，如果母球接触到红球，就称为 “ K 到红球 ” 。我们假设 ，一次可以击打任意多相邻连续的红球，也可以只击打一个球。
并且红球既不会落袋，也不会相互发生碰撞，而只是停留在原处。每次击打时候，要想 “ K 到红球 ” ，至少要击打一个红球，如果想一次击打多个红球，那么击打的红球必须是依次连续排列的 。如果一次 “ K 到红球 ” 所有红球的标号之和的平均数大于母球的标号 M ，就获得了一个 “ 连 击 ” 。现在请你计算总共能有多少种 “ 连击 ” 方案。
注意：如果当前有标号为 1 、 2 、 3 的三种红球，母球标号为 0 ，有如下 6 种获得 “ 连击 ” 方案：（ 1 ）、（ 2 ）、（ 3 ）、（ 1 ， 2 ）、（ 2 ， 3 ）、（ 1 ， 2 ， 3 ）
【输入文件】
输入文件 sheeta.in 共有两行，第一行是 N ， M (N<=100000 ， M<=10000) ， N 表示台 面上一共有 N 个红球， M 表示母球的标号。
第二行是 N 个正整数，依次表示台面上 N 个红球的标号，所有标号均不超过 10000 。
【输出文件】
输出文件 sheeta.out 只有一个数，为 “ 连击 ” 的方案 总 数 。
【输入样例】
4 3
3 7 2 4
【输出样例】
7

说白了就一句话的事情：在一个长度为N序列中，问能取几个连续的子序列，使得每一个子序列的数之和的平均数>M。

更蛋疼的是它的解法： Read on →

原创内容，转载请保留出处。 我承认C/C++里面的指针、数组相当令人蛋疼。为了不让以后蛋疼，所以最近就研究了一下这个蛋疼的问题。先列一个本文内容的表，也算是为more标签做点贡献：

• 指针的意义、定义及使用方法（水）
• 数组的意义、定义及使用方法（水）
• 使用负数下标访问数组（雷人）
• 数组指针？指针数组？（吓人）

一.指针的意义、定义及使用方法

所谓指针，就是指向一个对象的变量，这个对象可以是内置类型、类类型甚至指针类型。 学习指针的最好方法是coding!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

//定义：
//定义指针也很简单，只要在变量名之前加*就可以声明一个指针。一个指针变量所接受的值即是它指向的类型变量的地址，要得到这个地址可以用&操作符得到。
int ival1 = 123;
int *iptr1; //这样就定义了一个指针
iptr1 = &ival1; //这样就把iptr1指向了ival
//另外一种简洁点的方法：
int ival2 = 123, *iptr2 = &ival2;

//使用：
//指针变量保存的是变量的地址，要使用指针指向的变量，就需要对指针进行解引用。解引用使用操作符*：
std::cout << "the value of ival2   :" << ival2 << std::endl
    << "the address of ival2 :" << iptr2 << std::endl
    << "the value of *iptr2  :" << *iptr2 << std::endl
    << "the address of iptr2 :" << &iptr2 << std::endl
    << "is iptr2 == &ival2   ?" << (iptr2 == &ival2) << std::endl << std::endl;

//我们还可以使用指向指针的指针……
int **pptr = &iptr2, ***ppptr = &pptr;
std::cout << "   ppptr:" << ppptr << std::endl
    << "  *ppptr:" << *ppptr << std::endl
    << " **ppptr:" << **ppptr << std::endl
    << "***ppptr:" << ***ppptr << std::endl;

运行的结果如下：

1
2
3
4
5
6
7
8
9
10

the value of ival2   :123
the address of ival2 :0x7fff405d4ab8
the value of *iptr2  :123
the address of iptr2 :0x7fff405d4aa0
is iptr2 == &ival2   ?1

   ppptr:0x7fff405d4a98
  *ppptr:0x7fff405d4aa0
 **ppptr:0x7fff405d4ab8
***ppptr:123

二.数组的意义、定义及使用方法

对于C++程序员，相比C程序员，可能就比较不喜欢数组了。因为数组的长度固定，需要自己管理，容易溢出……C++ STL提供了vector容器，安全性大大提高，但效率并不比数组差多少，因此C++程序员更喜欢vector。但也不得不说，合格的程序员是能够自己控制好程序的，溢出是可以避免的，长度也可以预设或者动态分配，况且还有那么些情况不能使用vector（比方说NOIP），那么数组就是唯一选择了。

所谓数组，就是一列类型相同的变量，它们在内存的分配上是连续的。定义数组就是在变量名后加[size]，size为数组大小，必须为常量、正整数。 Read on →

Conky is a free, light-weight system monitor for X, that displays any information on your desktop. Conky is licensed under the GPL and runs on Linux and BSD.

——Conky Homepage

Conky不仅仅是一个系统监视器，而且相当酷！前提是你懂的配置它。当然，像所有linux下的软件一样，熟悉它、能自如地写配置也非易事。不过我们可以先用用别人的配置。先上我电脑上的效果图吧：

好了，还是分享一下安装方法吧：

1. 如果还没有安装Conky，那么就先安装吧。对于ubuntu用户，sudo apt-get install conky即可！当然也可以到官方下载源码编译等。
2. 到这儿下载压缩文件：http://gnome-look.org/content/show.php/Conky+lua?content=139024。解压后会有几个针对不同系统的分包，根据需要解压。比方说我解压出了Conky ubuntu-lua，打开发现有三个文件：conkyrc, clock_rings.lua, new-ubuntu-logo.png。
3. 把conkyrc复制到~/，改名为.conkyrc。打开此文件，将caviar dreams全部替换为文泉驿微米黑，当然如果你的系统上有这个字体，那么就不用。
4. 建立文件夹_{/.conky/，将ubuntu-logo.png复制到}/.conky/
5. 建立文件夹_{/.lua/scripts/，将clock_rings.lua复制到}/.lua/scripts/
6. shell: $conky &

看看桌面，有效果吧？

不过可能你会发现，Net中数据，这怎么办呢？ Read on →

1. 新教材编写时希望以流行的硬件、软件为范例。因为旧教材中的很多素材都是上世纪的产物，与现在的时代差距太大，所以我希望起码要以2008年以后的主流软硬件来作为模板编写教材。
2. 普及学生们的计算机知识。现在还是有不少人分不清内存、硬盘、闪存、显存等，既然中小学的信息学教育是为了计算机的普及，那么就要将这些基本功做好。先让大家明白了这些基本的事物，再来教一些其他内容（比方说Office、网页、Flash、编程等）。
3. 推广开源软件。开源软件的优点是巨大的，光是从免费这一点来看就可以为学校节省不少钱。而开源软件背后强大的团队也能使开源软件不断更新升级。开源软件的另一大优势就是跨平台，很多开源软件都同时支持Windows/Linux/Mac，这样无论是在那种系统上面教学，无论是后期换到那一种系统，只要软件不变，同学们都能很容易地适应。对于一些常用的商业软件，我们总能找出与之类似的开源软件，其功能并不比商业软件差。比方说用7-Zip替代WinRAR，用LibreOffice代替Microsoft Office，用GIMP代替Photoshop，用GNU/Linux（还是推荐Ubuntu）替代Windows……
4. 推广免费软件。因为有的商业软件确实是在功能上和易用性上大大高出开源软件，所以为了教学方便不得不使用商业软件。但不少商业软件也有提供“阉割”过的免费版本，使用这些免费版本对于初级教学就已经够了，而且还能剩下不少钱。比方说Microsoft Visual Studio一套是要以千元计价的，但是对于教学并不需要这么多，例如学C++，完全可以使用Visual C++ Express，免费，足够使用！再比方说网页制作，可以使用Microsoft Expression Web（貌似有提供试用版，具体不太清楚），或者Visual Web Developer Express（这个同上，属于Express系列，免费，够用！主攻Asp.Net罢了，当然静态页制作也是可以的）。
5. 不要再教Visual Basic 6.0了，如果实在要教Visual Basic，请选择Visual Basic 2005以上。同样如果要教C++，那也请不要教Visual C++ 6.0了，它的语法不规范，请以ISO规范语法教学。
6. 不要太早教窗体编程，从命令行入手。其实命令行程序也是很有意思的。
7. 编程可以教Python，主流、易学、有深度、扩展性强！
8. 教同学们是非善恶观：要明白使用盗版软件的罪恶，要懂得谦虚请教（特别是学到编程的时候），要懂得提问的智慧。

P.S.点击图片可查看大图，大图中的浮沉比较容易看清楚。

我们知道水的密度是1g/cm^3，不关是神马硬币它的密度都是大于水的密度。由物体的浮沉条件知：把硬币扔进水里面，硬币一定会沉底的！

但是，今天惊现漂浮的硬币！如图所示。至于具体的原因貌似是由于表面张力（表示完全不懂）。

我试了下旧版的1角硬币（这是我知道的、能拿到的最轻的硬币），成功了！但换成1角新币就立马沉底了……具体做法如下：

拿一张面巾纸，把硬币放在纸上。把载有硬币的面巾纸丢到水中（注意要保持平衡），面巾纸不会马上下沉，会托着硬币。等一会儿，面巾纸沉入水底，但硬币还是会留在水面上！

貌似原理是使硬币找到一个平衡，这样有利于表面张力的体现？？

还有另外一个方法：用手指头托着硬币慢慢下沉，多试几次也是会成功的，还是要注意保持平衡！ Read on →

今天上英语课讲评练习时，老师按惯例说：“有问题的举手。”于是最后一排某男说：“11！”估计手上比着“1”的手势。老师没听到，但是看到了手势，说：“第1题是吗？”“……第11题！”这位老兄再说了一遍。于是我就想到了一个问题：会不会是由于手指能够表示的数不够过而导致误解呢？

我们知道，一个正常人的双手共有10个手指头。小时候起，大家就学会了“1……2……3……”地数手指头，并且能很熟练地从1数到10。不错，数手指头确实是很容易搞清楚状况，但问题是：传统的手指表示方式仅能表示[0, 10]的整数。像这位老兄的11就无法表示了。于是，大家就有想到了一个方法：对于两位数ab(a,b均小于5)，可以用一只手表示十位、一只手表示个位。有些懂得用单只手表示0~9的人，利用这种方法就可以表示出[0, 99]的整数。表示范围确实扩大了不少。

还可以再大吗？我在英语课上就走神了。

受到上面想法的启示，我想到了：手势可以屈伸，若把手指弯曲表示成为0、伸直表示为1，那么利用二进制，就可以在手上表示出[0, 2^10-1]即[0, 1023]的整数，比上面又扩大了十倍不止。随后，我又想到手指还是有一些关节的，大拇指最少，但也有一个关节。用全屈、半屈、伸直表示0, 1, 2，利用三进制就可以表示出[0, 3^10-1]的整数……更变态的，如果是去掉两个大拇指，剩余的八指即可用四进制表示出[0, 4^8-1]的整数……

想想，其实如果用三进制、四进制表示，恐怕我们的手指技艺得十分高超，虽然表示范围有所增大，但是不如二进制那么方便。因此，我就把三进制、四进制否决了，觉得二进制表示挺好的！

由于讲语法，有点无聊，所以又开小差了，我又想起一个问题：实数系中的区间[a, b]和[ c, d]，两个区间谁大呢？其实这是一个很显然的问题，即使是[0, 1]和[-100, 100]，它们也是一样大的。虽然在数轴上它们的长短不同，但这两个区间里面都有无穷多个点，所以两个区间大小应该是相等的。这个解释貌似不错，但是为了打发英语课的剩余时间（更是为了等待放学铃敲响的那一刻），我就想了另外一个方法：

如果能够定义一个转换规则f，使得k∈[a, b]能够与f(k)∈[ c, d]一一对应，那么不就说明了这两个区间大小是一样的吗？不过，这个f要怎么弄呢？

！！！盗版！！！

最近我们国家反盗版确实是抓得很严，比方说verycd现在都不敢提供影片下载了。话说回来我们的信息学教育，这就不能够不提到我们信息学教育中的严重的盗版现象了。我们知道，前几年，在一个阳光普照的上午，刹那间，番茄花园、雨林木风、电脑公司、深度……一系列盗版微软系统突然消失，其发行公司（网站）也开始转型。从此，中国人民想要买到盗版的微软系统就难多了。这，大概是反盗版行动中的一次很有力度的行动，从根源上消灭了不少盗版资源（但是是消灭不尽的）。

其实，盗版本无罪，因为根据中国的国情，人民普遍付不起正版软件的高额费用。比方说，现在Windows 7家庭普通版需要￥359，而且这是最简陋的Windows 7。而家庭高级版需要￥599，旗舰版更是高达￥2309（以上数据均来源于微软淘宝官方旗舰店），这对于我们草根阶级是无法接受的。因此，盗版就成了最好的选择，这无可非议。只要你不利用盗版软件从事商业用途，从法律上说，以研究为目的使用盗版软件应该构不上违法。

中国是盗版的重灾区，但这也成全了微软在中国的快速发展。使用盗版的前提是：仅以非商业性研究为目的，但不少人似乎是麻木了，不管是不是公开的商业的目的，盗版照用不误，为什么？因为连教科书都是这么编的！据说某大学教科书《C#和.NET3.0第一步》（作者：周礼，出版社：清华大学出版社）所使用Visual Studio及Windows系统为盗版的，有图为证！