早些时候我好好阅读了一下嘎嘎在选拔赛写的线段树，终于知道了还要牺牲大量的空间来Build。当我把Vijos那个只有5个人过的要用离散化+线段树的 “强强的战壕”AC了的时候，我突然意识到：成为大牛的第一步就是写一个高级数据结构。到什么时候动不动就来一个堆了，什么时候就可以被称呼为大牛了。
    前几天做Vijos，遇到一个计算几何（P1087），然后把黑书和算导拿出来看，打算看半平面相交；说到半平面相交，又把线性规划扯起出来了；线性规划一出来，高斯消元不可避免的出现了；这个再一解决，解同余方程（P1009）也解决了。于是知道了这又是一堆新东西，需要一个漫长的过程，想暂时先放一放。恍然醒悟，差的东西太多了，高级数据结构算个把儿。
    上个星期有一天上学还看到了Zroge的，打了个招呼。Zlan说Zroge在4月份要来帮我。我感动得痛哭流涕。
    现在又达到了一种新的境界：Vijos做得基本上没有菜了的时候，开始想起给Vijos出题了。之所以说达到了新的境界，是因为“温饱问题都还没解决不可能去出题给别人做”。出题真的需要耗费大量的精力。像NK那种搞理的缺时间，出个题又没有数据又没有标程，出了等于没出。编数据也很烦：你不知道你的数据是否正确。你要再编一两个效率低的暴力程序，整夜开机验证。再附上一个标程，密密麻麻地写成一团，前面不缩进，后面拖很长，等哪个看懂了的来挑毛病。强啊……

    确实好久没更新了……花功夫去做Vijos了，一天2道……
    把去年重庆选拔赛的那个最小公倍数做了，把高精代码贴在这里供大家瞻仰。
    每种运算都开了a、b、c三个数组，a、b是输入的要算的数，c是返回的结果。按惯例，数组倒序存字串，就是说a[1]表示的个位。

加法：
c[i]:=c[i]+a[i]+b[i];
c[i+1]:=c[i] div 10;
c[i]:=c[i] mod 10;

减法（默认了a比b大）：
if a[i]<b[i] then
begin
  dec(a[i+1],1);
  inc(a[i],10);
end;
c[i]:=a[i]-b[i];

乘法：
inc(c[i+j-1],a[i]*b[j]);
inc(c[i+j],c[i+j-1]div 10);
c[i+j-1]:=c[i+j-1]mod 10;

除法有点复杂，需要调用前面的三种运算。算法和人做竖式计算一样，模拟试商。
简单说一下：

    始终保持两个变量直到最后返回，一个当前得数，一个当前余数。初始化得数为0，余数为被除数。然后不断用当前的余数去减除数，同时当前得数不断跟着加1。
    当除数远远小于被除数时，这种方法显然效率很低。为了能一次减很多，可以在每次减之前试商以减去尽可能大的整数倍的除数。试商方法很简单，先搜i再搜j，搜索小于当前余数的最大的“除数*j*10^i”。然后当前余数减去除数*j*10^i，得数加j*10^i。反复这个过程，直到余数小于除数。可以看到，对j的枚举即是试商的过程。

代码写出来不难，十几行搞定。


24的编剧越来越大胆了。

考大家一道题。
这是一个比较著名的数列：

2,
271,
2718281,
2718281828459045235360287471352662497757247093699959574966967627724076630353547594571,
......

能看出这个数列是个什么东西的人高考加20分。
事实上，这个规律是可以用不到一秒的时间一眼看出的（如果你对那个够熟悉）。

    貌似很多书上没讲，很多人也不会，我在这里讲一下。
    调出Breakpoint List（在Debug菜单里面），你可以看到你现在设的所有断点的列表。选一个来Edit或者New一个，你可以看到如图的窗口。

    里面的Name是文件名（XXX.pas），Line是表示断点设在程序代码的第几行。Ignore Count很有用，里面可以填一个数字，表示“忽略此断点”多少次。比如你在Ignore Count一栏填1000，那么该断点将被忽略1000次，直到第1001次程序经过这里时才停下来。设置一个条件断点可以在Conditions一栏填上相应的语句，比如填一个“i=1000”，那么每次程序经过此断点时都会进行判断，只有变量i的值为1000（i=1000为True）时才停下来。右下角的Type可以自己研究，使用效率不高，一般不用。

      

    分形迷宫(Fractal Maze)是一个芯片，要求从芯片上的负极走到正极，其中A、B、C三个小芯片都是这个芯片自己的一个复制。递归，堆栈。
    如果你过了的话，欢迎挑战——

      

    想起写这个是因为小方的爸爸上课的时候提到了这个东西。他的说法有很多错误的地方。早些时候我对这个有过一些考究，想在这里写一下。
    这个问题最初发表在美国的一个杂志上。美国有一个比较著名的杂志叫Parade，它的官方网站是http://www.parade.com。这个杂志里面有一个名字叫做Ask Marylin的栏目，是那种“有问必答”之类的一个Q&A式栏目。96年的时候，一个叫Craig.F.Whitaker的人给这个栏目写了这么一个问题。这个问题被称为Monty Hall Dilemma问题。他这样写到：

    Suppose you're on a game show, and you're given the choice of three doors. Behind one door is a car, behind the others, goats. You pick a door, say number 1, and the host, who knows what's behind the doors, opens another door, say number 3, which has a goat. He says to you, "Do you want to pick door number 2?" Is it to your advantage to switch your choice of doors?

    这个问题翻译过来，就是说，在一个游戏中有三个门，只有一个门后面有车，另外两个门后面是羊。你想要车，但你不知道哪一个门后面有车。主持人让你随便选了一个门。比如说，你选择了1号门。但你还不知道你是否选到了车。然后主持人打开了另一扇门，比如3号。你清楚地看到3号门后面是一只羊。现在主持人给你一个改变主意的机会。请问你是否会换选成2号门？
    对于这个问题，Marylin的回答是：应该换，而且换了后得到车的概率是不换的2倍。
    这个回答引起了争议。大多数人不同意Marylin的回答。一时间，全国上下几乎所有人都在谈论这个问题，因为这个问题是非常吸引人的，它说起来很简单，很好懂，但想起来很麻烦。争执双方都有一套很完整的说法。至少10篇讨论这个的文章刊登出来，有些文章是相当长的。
    事实上，这个争论是毫无意义的。因为概率问题总可以通过多次试验得到近似结果。到底换了好不好做几次试验就知道了。意识到这一点后，搞电脑的开始编程，学校开始组织活动模拟这个游戏。为了让读者有一个满意的答案，Marylin给一位数学老师打了个电话，请求她帮忙做试验。不久，这位数学老师发过去了一个表格，上面记录了试验结果并且列出了所有的可能。这份表格明确地表明，换一扇门可以得到车的概率更大。与此同时，许多人也相继发布了他们的测试结果。这些试验结果使这一看上去荒谬的结论变成了无可争议的事实。最后，这个问题有了科学的解释。人们接受了这一观点。这个问题已经被解决，它已经不再有争议了。
    一个叫S.K.Stein的人写过一本书，名字叫Strength in Numbers。书里面谈到数学家们如何一步步解决问题的时候引用了这个Monty Hall Dilemma问题。他在书中这样说道：

    If, after thinking some more about the question, you still are not sure about the answer and are not ready to explain it, then do the following. (Keep in mind that just citing experimental data is not an explanation. The data may convince you that something is true, but they do not explain it.)
    Get one more canister and perform a similar experiment, using four canisters instead of three. Put a wad of paper in one canister. After your friend chooses a canister, look in the remaining three and show the friend two empty canisters. The friend then faces a choice between the two other canisters. Carry out the same experiments as before. Think over the results you get. What do they suggest? Do you see a way to explain what happens?
    Performing these experiments not only gives you some clues, it also slows you down from the common frenzy of everyday life, so you can focus on just one thing for a period of time.
    If you still do not see how to explain what is going on, then use ten can- isters. Put the wad in one of them. After your friend chooses a canister, look in the other nine. Show your friend eight empty canisters out of those nine and remove all eight. Again that leaves just two canisters. Conduct a similar experiment.
    I am confident that you will solve this problem, so confident that I do not include the answer anywhere in the book, not even in fine print upside down hidden in the back matter. You mill probably, along the way, calculate the fraction of times that switching will pick the car and the fraction of times that not switching will pick the car. Using these fractions, you will be able to explain the brainteaser completely. Then you will have to admit that you can think mathematically. You just needed the opportunity.

    简单地说，Stein想表达这样一个意思。他建议那些还想不到Monty Hall Dilemma问题的答案的人别忙用数学方法去解，先亲自做几次试验来进行一些感性的认识。叫一个朋友当游戏里的主持人，在三个罐子中的其中一个里放一个东西。多玩几次，用心体会。如果做了试验还没有启发，那么他提出了这样一个非常具有启发性的试验的变形：规则不变，只是把三个罐子改成四个罐子。你的朋友会在你选择了一个罐子后打开另外两个空的罐子，再问你是否换一个。如果还没有一点启示，干脆把四个罐子变成十个。如果你真这么做了还没有一点想法那你就彻底地傻了。想想看，假如游戏中三个门变成了十个门，随便选一个选中车的机会将更渺茫。在主持人打开了另外八扇有羊的门后，你不换你肯定傻了。要是是我，我肯定会毫不犹豫要求换成另一个门。是啊，随着羊一只又一只的跑出来，我肯定会越来越激动，心想，那剩下的那个门里肯定是车了。这里有一个很基本的想法：我开先如果选的羊，换了一下就变成车了；如果开先选的是车，换一个门就变成羊了。既然一开始选的多半是羊，我为什么不换呢？
    根据这个思想，我们得到：在Monty Hall Dilemma问题中，第一次选中车的概率是1/3，显然车在另一扇门的概率是2/3。因此，我换门将有2/3的几率拿到车，而不换则只有1/3的概率拿到车。
    这个问题到这里本来应该结束了，但还有一点疑问：为什么主持人打开一扇羊门会改变选择的几率？其实道理很简单，几率本身是没有变的，只是因为主持人在打开门时就有一个选择。这导致了可能的情况减少。
    还想不清楚的话可以看看这样一个问题，这个问题也是由于看似没有影响的条件发生改变而导致概率的变化：说左右各一个人，已知两个人中至少有一个女的，问右边那个是女的的概率是多少？下面给出一个条件：同样两个人中至少有一个女的，现在告诉了你左边那个是女的，那么现在右边那个是女的的概率又是多少？有变化吗？既然至少有一个女的，那么说了左边那个是女的为什么概率也会跟着变呢？
    Monty Hall Dilemma问题传到中国来要稍微晚一些，但也在各大论坛上引起争论。Monty Hall Dilemma这个名字的中文翻译有很多，多数都比较直观，如“羊与车问题”。对这个问题的分析在网上很多地方都有仔细的讲解，到处都找得到。这也是本文着重在介绍这个问题的提出和发展史的原因。

    做人要厚道，转帖请注明出处。