博文
我的26个关键字（上）(2006-12-15 00:55:00)
摘要：开始写文是7月26号，现在是12月15号，已经……好多天了。为了谢谢很多朋友的关注，在这里写些我的八卦。
-------------------------------------------------------------------------
Aquarius
水瓶
继承了良好的水瓶座观察力、思维能力与推理能力，对“桌上的奥莉奥不见了，是谁干的”此类问题洞若观火；拥有水瓶座正常男生的缺点：人格分裂，神经兮兮，忽冷忽热（喂，这是正常麽 ＝＝）
Bayern
拜仁
十年的爱，需要理由麽？
Circumstance
环境
社会性动物的通症。非常在意周围的境况，反应，责备，以及……怒叱。虽然会随机产生一种“随便你怎么看”的强者气场，潜意识里还是非常希望身旁的氛围有利于己。
Delicate
敏感
和C词条结合产生了可怕的化学反应。尤其对自认为很重要的事，自认为很重要的人，有一种“完了，这一定做的很糟”的心态。
Escape
逃避
习惯于逃避。从家里逃到远方念高中；再从远方逃回家里念大学。不断躲着很多人、很多事。看到困难就有“反正会解决的”的条件反射；等到事到临头，又发现自己无能为力的时候……就躲开吧。也不知道是危险神经过于迟钝还是自我能力评价过度了。
Freedom
自由
反感所有压迫，官僚、权力和强者。受王小波影响较大。不喜欢毛派哲学，认为世界和人的思想都是丰富多彩的。同样不喜欢强者哲学，认为世界是平衡的。无奈于现实，于是立志做强者。
German-Fans
德迷
忠实的德迷。对一切带有“德”，“德国”， 以及“德意志”烙印的东西有好感。恩？国家社会德国工人党？风太大，听不清楚—－楚――楚――（回音）。
Hermit
隐居
如果有可能的话，希望做一年的隐居者。在黑森林古道中徜徉，享受史前恐龙呼吸过的、充斥着落叶腐败味道的空气；在破落古堡上看斜阳，余晖勾勒出身旁女友的脸庞；不余此生亚不余此生亚。
Inconsistency
矛盾
这个人简直是矛盾的集合体。光明和黑暗，海水与火焰，学习哲学的时候倒是不错的参照物。
Jumble
混乱
不要试图将“洁”“齐”“净”或是类似的单字和他的生活联系起来，你会感到头疼。事实上，他的电脑桌三个月整理一次，混乱的局面在第二天以出奇顽强的生命力恢复。另外，在他的寝室，......
Zju 2770 Burn the Linked Camp（2）(2006-12-11 21:43:00)
摘要： 正如上文所言，图论的「精髓」就在「转化」了。把一个纯粹的数学问题转换成为可以用图表示的问题，然后通过求解路径（最小值？最大值？），得解。听起来很美。
以本题为例。给出每个军营的最大容量，给出从军营i到军营j最少的人数，求总人数的最小值。
这就是典型的差分约束了。有“分”，有“约束”，至于为什么叫“差”，我想大致是因为首先把Ai + .... + Aj写成S[j] - S[i - 1]（和之差）的形式吧。btw，这种转换似乎是很常见的处理方法。
好吧，看上去和图论八竿子搭不上边。以题目给的第一组数据为例。
3 2
1000 2000 1000
1 2 1100
2 3 1300
我们可以得到如下关系式。（= 省略，下同）
A1 < 1000, A2 < 2000, A3 < 1000;
S2 - S0 > 1100, S3 - S1 > 1300;
第一组不等式又可写作
S1 - S0 < 1000, S2 - S1 < 2000, S3 - S2 < 1000
好吧.....不很明显，再改一下：
S0 - S1 > -1000, S1 - S2 > -2000, S2 - S3 > -1000
全部改成>后，回到上文中最后一个结论Distance(v) < Distance(u) + w(u,v)。即D(u) - D(v) > -w(u,v)。 把D改成S，是不是很像？......很牵强吧。
但毕竟还是有相同的地方。比如离散数学里的传递性：S0 - S1 > -1000, S1 - S2 > -20......
Zju 2770 Burn the Linked Camp（1）(2006-12-11 17:42:00)
摘要：
2168048
2006-12-11 16:57:17
Accepted
2770
C++
00:00.59
676K
Crux.D
图论是一种美妙的东西。虽然不能化粪土为金钱，但是很多看上去不可能的任务可以用简单的转换完成。当然，其中的奥妙就在于「转换」二字。
因此，为了顺利完成从菜鸟成长为大菜鸟的计划，我决定学习进阶图论。
---------------BVB养成计画·第一话 BellmanFord-------------------
BellmanFord是一种计算最短路径的算法。虽然之前学过相当多的最短路径，如Dijkstra算法，Floyd算法，但他们是有适用范围的。即两算法下边的权值不能为负。因为考虑以下情况：
出点 入点 权值
1 2 -3
2 3 -2
3 1 2
这样即构成了一条从1点到3点的负值回路-3 + -2 + 2 = -3，这样永远算不出1到3的最短路径了（因为可以无限循环-3 -6 -9....）。
所以BF算法是专门提出来解决上述问题的－－计算每个点对源点s的最短路径。
算法的伪代码如下
BF(G,w,s)
// 假设一张图G，从源点s出发，每条u至v的边权值为w(u,v)，共有n格点。
Determine Single Source(G,......
Zju 1962 How Many Fibs?(2006-11-24 22:30:00)
摘要： 恩，把以前没做的弱题做了一遍，发现自己对繁琐细节的处理实在差劲。比如这道题不难，就是大数的加法、大数的比较。翻来覆去写了160多行，从饭前的无聊到看完书的愤懑，横跨5个多小时，假如是张白纸，早就被笔迹划成渣了。
惊奇的是，不知不觉，终于做到300题了。
请原谅我把“惊奇”“不知不觉”和“终于”这三个互相矛盾的词放在一起。（迷之音：重点，重点是「不炫耀会死」呀......）>_<
的确做了很久zoj，与此同时，考研就如悬在头顶的达摩克利斯之剑。做题只是爱好，从悲观的角度看，更像是一种逃避——好像一进入编程世界，考研就离自己好遥远了——当然，我还不曾如此悲观，我对于社会主义精神文明的热爱不逊于此。
就比作Relax吧。青罗曼纱，轻烟袅袅，眼明心净，在算法的海洋里享受无穷乐趣，打住，这不是小说。现实是，我的前方是修过三次的17寸平显，我的正下方有一个铁盒，发出持续不断的奇怪噪音，让你想起哥斯拉、大魔王、宿舍楼下的汽车修理厂。我就坐在那里，时而把脸挤成三阶矩阵，时而把手绞作二维曲线，以向入土了两百多年的数学家们致敬；至于大脑内部发生了正弦变换或者傅立叶变换，这和我无关，我也不想知道。重要的是，我做不出来，只好去看帖。
当然这是......恩，多数。少数情况下，我运指如飞，一行行闪烁着人文主义关怀的代码呈现不停。这样的题目有：1001,1001,1001,1001,1001,1001,1001,1001,1001,1001,1001,1001
......其实一直在进步，不是么？希望考研结束的那一天，我也能这样对自己说。
大数加法模版之一：用int来代替数字位真是失败！！！！（呜，我也变成最讨厌的感叹号×4人了）
#include <cstdio>
#include <string>
const int max_int = 102;
typedef struct long_int
{
......
对操作系统进程调度算法的社会学分析（注1） Ⅰ(2006-10-26 23:23:00)
摘要：
无聊的时候写的，搬出来晒晒。
------------------------------------------------------------------------
浙大四门考研科目，有一本大且笨重，唤作《操作系统》。无奈之下苦心研读（注2），读到进程调度，不由拍案叫绝：这点点滴滴，简直就是活生生的社会管理案例。
进程调度有四。一乃FCFS（First Comes First Serves），先来者先服务，后来者不许抢。孔夫子有云，有主的干粮不许碰。又有高卢人一枚，姓卢名梭者，洋洋写道，财产是“公民一切权力中最神圣的权力”。后来蜂拥而至的社会主义者却在他的著作里发现了攻击私有制的痕迹，并把《社会契约论》奉为经典。话说回来，纯粹的FCFS平均等待时间惊人，用流行的话来讲，既不考虑效率，又不兼顾公平。
后来，早期的联邦科学办公署（United States Scientific Bureau，简称US-SB）学乖了。他们提出了用来取代FCFS，具有“划时代性变革”的SJF（Shortest Job First），最短作业优先调度。这一算法将每个进程和下一个CPU区间段相关联。当CPU可用时，它会付给具有最短后续CPU区间的进程——这是原话。简单的讲，谁越有能力，让别人等待时间越短，谁就有资格获得资源。优胜劣汰，适者生存，精彩的丛林法则。
可惜……这永远存在于学者的图纸上。效率优先是最好的，最好的往往不是最适合的，这句话到哪儿都通用。对于这种算法，长时间段进程显然拿不到，起码要等待相当长的时间段才能拿到资源。（注3）而如果这是一个关系到系统运行稳定、关系到必需资源调配的内核进程，那么对于操作系统，这就是一场「灾难」。OK，把系统替换为社会。弱势群体永远是议会两侧争论最激烈的话题，从种族歧视到平权法案（Affirmation Action，又译作A-A），遗憾的是，似乎仅限于此。自由主义要克服“不干涉”和“垄断”之间的矛盾，还有很多路要走。（注4）
------------------------------------------------------------------------
注1：不要被题目吓倒。对题目，作者知道的不比你多。
注2：作者上次OS差点挂科。
注3：事实上，这不是算法的根本缺陷！这种算法根本只存在于图纸上，你永远......
Zju 2402 Lenny's Lucky Lotto Lists(2006-10-22 16:46:00)
摘要：
2113146
2006-10-22 15:53:31
Accepted
2402
C++
00:00.19
1988K
Crux.D
最近偏爱这类题目。当然，这题的Accepted Submit也相当的多。对这类题，我的原则是，宁可错杀一万，不可放过一个。对于弱题天生的嗅觉。
......然而事物的现象和本质永远都是有差距的。这句话在哪里都适用。想算法用了10分钟，修改和提交用了整整1个钟头。题目如下。
给定两个数N和M。比如4和10。求序列An的个数。序列An从某个正整数开始——比如1，每个数都要>=前一个数的2倍，最后一个数<=M，序列长度为N。
但是我还是偷懒了。一般的讲，看到题目以后，尤其是长且欠的题目，我的第一反应一定是打开译题站，然后输入题号，搜索。这除了降低我的英语阅读能力和增强我对于网络的依赖性以外没有任何好处。然后我的第二反应就是看贴，不自觉，或者自觉的。接下来第三步，我看到了标准解法......幸好很多题目我还看的懂。今天我只瞄到了两个字：dp。
......OK，那么dp吧。
其实就像fatboy大人讲过的，dp只是一种思路，并不是一种算法。当我们不把dp当成dp的时候，我们自然就会dp了。
停。我不是杨过。我不会武功。还是讲讲思路吧。
还是拿4，10做例子。
这个例子里，我们能组成4个序列。
1,2,4,8
1,2,4,9
1,2,4,10
1,2,5,10
我的直觉告诉我，一定有递推关系。（......好吧，是帖子告诉我的）首先否决的是搜...搜索。N= 50, M= 2000，C(50,2000) = ∞，四核CPU都不够用。我很快想到了......
Zju 1245 Triangles(2006-10-20 23:17:00)
摘要：
2111683
2006-10-20 22:42:27
Accepted
1245
C++
00:00.12
1004K
Crux.D
1245是一道比较经典的dp。一个大的正三角形，由许多小的三角形组成，他们分为黑白二色。求最大的白色正三角形面积。
思路不难。把每一行白色的累计数存起来作dp。当然这要分尖朝上的和尖朝下的。朝上的公式是r[i][k] = min(r[i - 1][k - 1] + 1, b[i][k]); b存的是白色的累计数，r是最终的边长。朝下的亦同。
似乎很简单。可好久没做题了，犯了些低级失误，比如把b和r写反了。我不知道这和越来越近的考研有什么关系——也许我就是在岩壁上紧抓藤蔓的失足者，寒冷的1月就是悬崖下的毒蛇。
所以......还是要加油了。藤蔓不是这么可靠的，我的数学也一样。
附程序，写的比较烂，仅供参考。
#include <iostream>
#include <cstring>
using namespace std;
int n, b[101][210], r[101][210], ans;
int min(int a, int b)
{
return a < b ? a : b;
}
int main()
{
//freopen("in.txt", "r", stdin);
int i, k, c = 1;
while(cin >> n && n)
{
memset(b, 0, sizeof(b));
memset(r, 0, sizeof(r));
printf("Triangle #%d\n", c ++);
for(i = 1; i <= n; i ++)
......
Zju 2759 Perfect Weighing Skill Ⅱ(2006-10-01 22:31:00)
摘要：
2087262
2006-10-01 22:05:43
Accepted
2759
C++
00:00.10
392K
Sirius.D
这题原来如此简单````根本用不到搜索,更谈不上剪枝..可在那时,却害的我肝肠寸断,为伊消得人憔悴.....可叹一位如花似玉的少年,就这样被zoj的Monthly吓的花容失色,颤抖抖,惊颤颤...
(正色道)此题(参见前文)只需把数改成三进制,不断的「借位」进位即可.
如6,即为2,0 == 1,-1,0;
35,即是1,0,2,2 == 1,1,0,-1;
如此这般,这般如此,1处取加,-1处取减,可爱的ac就在你的眼前.
#include <cstdio>
#include <string>
int b[19], n, l;
void pt()
{
int af = 0, bf = 0, i, x = 1;
for(i = 0; i <= l; i ++)
{
if(b[i] == -1)
{
af = 1;
if(bf)
printf(" ");
printf("%d", x);
bf = 1;
}
x *= 3;
}
if(!af)
printf("-1");
printf("\n");
af = 0, bf = 0, x = 1;
for(i = 0; i <= l; i ++)
{
......
Zju 2759 Perfect Weighing Skill(2006-09-23 22:23:00)
摘要：
2077759
2006-09-23 21:04:50
Accepted
2759
C++
00:00.11
440K
Achilles
这个题花了我一个多钟头，也是今天八道题里唯一会做的（......-_-||||）。还有一题比较简单，物理＋数学，我没做；也许还有几题可以下手，下个月再说。唉，又要开学了。
题目还是很好理解，有很多不同的砝码，都是3的倍数，用他们称重，左码右码。然而数据bt的大，总共有19枚砝码：2^19可以让我的电脑死机好一会儿。
第一次，用普通的dfs，放开手搜，可想而知的挂了，本机都通不过。
第二次，终于考虑到累加之后减不下来的问题，在本机快乐地看到了出解。然而提交依然不行。一拍脑，对称的情况（减后加不上去）没有考虑。
第三次，修正，双手合十，念叨着「小宇宙，AC吧」。绿色的TLE无情地嘲讽着我的虔诚。
第四次，换了一种祈祷方式。
…………
…………
…………
终于绝望了。好吧，继续我的毛概。
在解决了新民主主义革命的基本问题之后，我突然想到了。刚才的解决路线是对的，但第四步错了。累加之后除了减不下来，还有一种情况：加了以后还加不上去。这个才是大头。
而一开始我犯的错误在于，根本加不上去的这种情况本来就包含了减下去加不上来。前者是一般，后者是特殊，后者能剪去的情况自然不如前者。反之亦然。
所以保存当前数之后的数之和为s[19]。sum + a[k] + s[k] < N和sum - a[k] - s[k]时停止。
程序如下
#include <cstdio>
#include <string>
#define MX 3......
Zju 1937 Addition Chains(2006-09-15 23:02:00)
摘要：
2068885
2006-09-15 22:28:27
Accepted
1937
C++
00:00.02
436K
St.Crux
给定队列首数1和尾数N，求一个最短升序队列，之中每一个数都可以用队列中其余两个数（可以相等）之和表示。
这题相当的棒。似乎是枚举构造orz，然而可以用搜索dfs，搜到（加到）N时停止并判断长度。但如果用一个二重循环不断搜索，下场就是死。所以还需要优化。
首先需要计算出，对于队列的最后第二个数M，累计到N最小需要多少步。因为2M到M需要一步，所以s[M] = s[M + M] + 1。这是题目的关键。比如49到98是一步，到100就至少要两步。
然后剪枝：如果s[M] + 目前的长度已经不可能再得到最优解时停止。这种剪枝非常常见。我一开始没有考虑SM的情况，结果很惨。
#include <cstdio>
int n, ans, a[100], r[100], d[202];
void dfs(int);
void print();
void init();
int main()
{
//freopen("in.txt", "r", stdin);
while(scanf("%d", &n) && n)
{
init();
dfs(0);
print();
}
return 0;
}
void init()
{
int i;
ans = n;
a[0] = 1;
for(i = n; i <= n + n; i ++) d[i] = 0;
for(i = n - 1; i > 0; i --) d[i] = d[i + i] + 1;
}
void print()
......