博文
Poj 3264 Balanced Lineup (2008-02-01 14:31:00)
摘要：最小白的RMQ，求第i到第j的最大值和最小值差值。采用SparseTable算法，其实就是一种相当高效的打表，空间范围nlogn，每次查询的时间只需要常数。
假如是一般的打表，对每组i和j，记录下第i到第j的最大值和最小值，需要的空间为N2，N增大时显然无法满足要求。因此考虑改进算法，适当扩大时间，缩小空间，使之平衡。
ST采用的方法相当高效，二分划分，把每个i的所辖范围划分成1，2，4，8，16的小块，和操作系统中伙伴系统的划分倒有几分类似。
以最大值为例。F(i,j)表示以i位元素开始，连续2i个元素中的最大值。初值设所有的F(i,0)即为i的值。
那么，F[i,j]=max（F[i，j-1],F[i+2^(j-1)，j-1]）。这个等式不难推出。
然后计算l和r区间最大值时，只要划分成两块小且互相覆盖的区间就可以了。
第一次做的时候计算最后区间出了点差错，百思不得其解。为什么是(ln(r-l+1)/ln(2))；r-l计算莫非会出精度错误？
#include <cstdio>
#include <cmath>
#include <string>
int N, Q, a[50000], s[16][50000], t[16][50000], A, B, L;
#define max( x, y ) ( (x) > (y) ? (x) : (y) )
#define min( x, y ) ( (x) < (y) ? (x) : (y) )
void pt ()
{
int i, j;
for ( i = 0; i <= L; i ++ )
{
for ( j = 0; j < N; j ++ )
{
printf......
Zoj 1542 Network(2008-01-23 13:28:00)
摘要：
2730750
2008-01-23 13:12:47
Accepted
1542
C++
00:00.24
728K
C.D.
求最大边最短的生成树。
我怀疑即为最小生成树【？】。因为假如按照Prim算法，每次求得的都为一个集合到另一个集合的最短边，也就是不可能生成两棵树，一颗三条边为2，2，2，一颗为1，1，3；这样的情况应该会产生1，1，2 的生成树。【未严格证明】
但是在求最大边的时候，显然是用排序+并查集更易得到结果。
值得注意的是几点。
1.在unionset操作里使用了不同的返回值分辨不同的处理情况。
2.qsort的处理。
/*
zoj 1542
author: Crux.D
date: 2008.1.23
description: mst, kruscal, n-1 edge
*/
#include <cstdio>
#include <string>
#include <cstdlib>
typedef struct
{
int t1, t2, l;
} Con;
Con hub[15000], ans[1001];
int N, M, ans_num, max_len; // hub个数，connection数量，生成树边数（N-1），最大边长度
int cmp ( const void *a, const void *b )
{
Con *A = ( Con* ) a;
Con *B = ( Con* ) b;
if ( A->l == B->l )
{
if ( A->t1 == B->t1 )
return A->t2 > B->t2;
return A->t1 > B->t1;
......
Zoj 2833 Friendship(2008-01-22 18:40:00)
摘要：
2730205
2008-01-22 18:15:30
Accepted
2833
C++
00:00.95
1180K
C.D.
这大概就是所谓的RPWT，拿出来炫耀一下。【灰溜溜爬开】
其实这题的时限是3000ms，还宽裕的很。但前十名都能把时间压到500ms以内，说明普通的并查集还有值得优化的地方。顺便讲一句，这题通过的人数好X多。第一次写的时候根本就忘了什么是压缩路径，可耻地TLE鸟。【= =】 发现上一次写并查集是一年前的事情，结果又忘记怎么做了……【为什么是又】
所谓的并查集，也只不过是一枚特殊的树罢了。这棵树在完成findset操作之后，高度至多为2，而且形式为根节点下面N个叶子——这就是压缩；在完成两棵树的合并之后高度至多为3.为了方便编写，采用的是数组而不是链表；这一点我倒是牢牢记住了。
/* zoj 2833
author : Crux.D
date : 2008.1.21
description : unionset
*/
#include <cstdio>
#include <string>
int parent[100001], num[100001], N, M, cs = 0;
void init ()
{
int i;
for ( i = 0; i <= N; i ++ )
{
parent[i] = -1;
num[i] = 1;
}
if ( cs ++ )
printf ( "\n" );
printf ( "Case %d:\n", cs );
}
int find_set ( int n )
{
//寻找树的根节点
int pre = n;
while ( parent[pre] != -1 )
{
pre = parent[pre];
&nbs......
终于考完了(2008-01-20 21:59:00)
摘要：借用史达林的一句话，考一次研（失败）是场悲剧，多考几次就是统计。
几天不上zoj的主页，惊奇地发现主页改版了，改的就和我们学校一摸一样。Ranklist上一群牛人，实在是望尘莫及。这样下去，早晚有一天zoj的题目会被他们做完。......
南哥的房子(2007-05-28 22:20:00)
摘要： 注：仅以此文纪念我的大学四年，和有趣的室友们，特别是LC，此文来源于他的idea。本文风格受到了王小波《红拂夜奔》的影响，这是一本有趣的小说，我很喜欢。
—————————————正文的分割线—————————————————
很多年以前，杭州城的天是黑蒙蒙的，云是黑压压的，空气是黑黝黝的，整个城市是黑漆漆的。西域来的黑人在路上行走，谁也看不见，被车轧死的事情时有发生——这是官方说辞，事实上，衙门里的失踪人口册被记得密密麻麻。后来黑人在出门之前先把自己染白，这就是杭州城最早的一批白人。很多年以前，南哥就住在这座城市里。很多年以前，南哥在这座城市里租着一间房子。
在这座城市，房价很高，很多人都住不起。但就像你所知的，世界上有穷人，自然也有富人。有些富人雇了马车，把成堆成堆的钱运进城来，成批成批的马因此而累死。但是他们惊异地发现，即便用上再好的神驹，马车的速度永远比不上房价飞涨的速度。有人曾经用钱堆满了一座别墅，却发现这点钱只买的起一间茅房。孔子曰，逝者如斯夫，不舍昼夜。他老人家掐着钟点周游列国，还不是为了买房！
只可惜有钱人少，没钱人多，所以很多人选择了租房。南哥是未来的中行行长，未来的联合国秘书长，未来的银河系领导，但是此时他没有钱。和所有的没钱人一样，他在离工作的地方不远处租了一间房子。
一般而言，租房有合租的，有单租的，有两室一厅的，有一室一厅的，有20平米的，有40平米的。南哥找的是2平米，二楼，一个房间的。也有3平米的，南哥说，根本没必要，床够放了。其实我看原因还是为了省钱。一个平方月租50两银子，一年就要多交600两银子。不管房价是涨是跌，银子总是重要的，哪朝哪代都一样。
搬家的那一天，为了把床挪进门，南哥费了很大的心思。这里不得不提一下南哥的床，因为这是人类工程学上的奇迹。南哥的床两米长一米宽，和房间的几何特性刚好吻合；上面睡人，掀开床板以后，下面是暗道直通衣柜。暗道里有梯子，方便爬上爬下。床尾有翻板，翻起来是电脑桌，放下去可以做硬木枕，健脑醒目——但是南哥翻起来以后就再也没放下去过：众所周知，南哥是官府银行（那时叫钱......
Zju 1800 Decorations(2007-04-30 22:53:00)
摘要： 最近经常性地在关键时刻掉链子。古希腊先哲说，人不会两次跌进同一个坑——确实，我跌进了两个坑，摔的鼻青脸肿。先是在杭电邀请赛上看错范围，把辅助数组开小，幸好同伴火眼金睛；这道题犯的错误几乎一摸一样，一个a[601][101]的数组开成了a[101][601]。最可恨的是这样的错误假如没有意识到，一辈子都找不出来！ZOJ上wrong answer映的我发绿，莫名其妙，怎么也该打出一个RunTimeError吧……结果我的程序几乎被改成BusyCai同学的程序了……
这类词典型的dp题目倒也差不多，a[i][k]代表了第k个词语在填入第i个位置时的可能总数。只要扫描上一个位置的所有M词语a[i- 1][j]，满足情况者加入a[i][k]即可。BusyCai的写法比较好，用每个位置a[i][k]去加到下一个位置a[i + 1][j]。a[i][k]可能为0，节省了很多时间。
#include <cstdio>
#include <string>
int N, L, M, len, a[110][610];
char str[610][11];
void init ()
{
int i;
for ( i = 0; i < M; i ++ )
{
scanf ( "%s", str[i] );
}
memset ( a, 0, sizeof ( a ) );
len = strlen ( str[0] );
}
int check ( int a, int b )
{
int i;
for ( i = 1; i < len; i ++ )
{
if ( str[a][i] != str[b][i - 1] )
return 0;
}
return 1;
}
void dp ()
{
int i, k, ......
USACO Section 1.4 The Clocks(2007-04-10 21:58:00)
摘要：老实的说，这该称之为穷举——但搜索不也是把所有可能的情况列出来么？无非用的方法巧妙一点……额，是巧妙的多罢了。传说中有位俊朗的数学家王子，为了得到邻国数学家公主的一片芳心，发动全国之力，每个人验证一个数是否为质数，从而得到了一个相当大的质数，为古巴比伦数学的蓬勃发展作出了不可磨灭的贡献。——这就是穷举。BTW，他的想法和并行计算机如出一辙，也不知道谁从谁哪里得到的灵感。
但是我听说，两个数学家走到一起，下场都是很悲惨的，不是女孩把拖鞋下到锅里就是男孩饿死。但似乎王子和公主们不用担心这些……
扯远了。这道题本来想写华丽的bfs……但是写的太华丽了，调试到最后连自己都不知道在写什么。题意是这样的，有9个时钟（A到I），每个时钟只有4档可以拨，12点，3点，6点，9点。有9种操作，每种操作把其中的某几个时钟顺时针拨一档。
Move
Affected clocks
1
ABDE
2
ABC
3
BCEF
4
ADG
5
BDEFH
6
CFI
7
DEGH
8
GHI
9
EFHI
那么，给出一个时钟的排列法，如
9 9 12
6 6 6
6 3 6
求，最小需要几步，把所有时钟都挑到12点？
这是一个非常好的bfs和dfs练习题，但是也相当的难写。在看了某牛人的dfs代码之后，我发现自己比看过之前懂的更少。胡Core也教导我们，要以艰苦朴素为荣。综上所述，我采用了穷举的方法。
但是这也是有前提的。第一，每一个时钟都只有四种状态。换句话说，每种操作也是四种状态，进行0，1，2，3次。第二，4的9次方不大……
/*
ID: Crux.D
PROG: clocks
LANG: C++
*/
#include <cstdio>
#include <string>
#include <cstdlib>
const int L = 10000;
FILE * fin = fopen ( "clocks.in", "r" );
FILE * fout = fopen ( "clocks.out", "w" );
int x[9];
int c[......
Zju 1586 QS Network(2007-03-27 14:53:00)
摘要：这题显然还是用prim，经过优化后的prim效率可以达到O(n2)。
离省赛越来越近，我也越来越没有状态，这种小白题从昨天晚上开始做，做到断网；今天爬起来继续做，才发现是把a[i][k]赋值 无限大的条件写错了——无良的出题者居然加入了两个端点间距离可能为0的情况......
#include <cstdio>
#include <string>
int a[1010][1010], s[1010], dis[1010], t, n;
void pd ()
{
int i;
for ( i = 0; i < n; i ++ )
{
printf ( "%d ", dis[i] );
}
printf ( "\n" );
}
void init ()
{
int i, k;
scanf ( "%d", &n );
for ( i = 0; i < n; i ++ )
{
scanf ( "%d", &s[i] );
}
for ( i = 0; i < n; i ++ )
{
for ( k = 0; k < n; k ++ )
{
&nb......
搜索和动态规划的一些简单分析(2007-03-14 19:12:00)
摘要： tieren同学提问，“深搜和动态规划有什么区别与联系呢”，留言板上写不下，把题目扩充一下，写到这里来。
在我看来，广搜和动态规划更像些：两者都是从上往下计算，在程序中都可以从前到后分出很明显的层次。广搜采用的是队列，后进前出，队列中每一个元素需要记录下他的层次；而动归中一个状态就是一个层次。而深搜是先按第一种算法（如，搜索第一个元素）从第一层计算到最后一层，（一般而言是算那些是否有解的问题），如果发现无解倒退一层，换第二种算法（搜第二个）……依次类推。
比如在棋盘上跳马，每一步就是一个层次。在广搜中可以记录下每一步的行号列号和步数，然后推出这个记录，把它的下一步（n种情况）推入队列中。在动态规划里，扫描所有格子，跳马，在每个跳到的格子里记录下跳到该格需要的步数，这样就算一步（一个层次）。所以从记录的时间效率来看，如果棋盘足够大，显然是广度搜索合算。因为在动归里，每一步都有很多无用的格子，不记录任何东西。但是动归在棋盘足够大，步数足够多时也节约了很多空间，因为它的空间恒定为棋盘大小，而广搜则把同一个格子记录了好多遍，还附带记录了它的行号列号——前提是不做任何优化。
至于另外一种搜索——深搜，可以这样说，在那些求“是否有解”的问题中，深搜和动态规划都很有用。比如求用面值为A元，B元，C元的三种纸币能否凑出SUM元钱之类的问题。深搜处理是写一个递归，然后按某种顺序一直累加到底，若无解则回溯。动归的话可以开一个SUM的数组，初始时凑到0元。然后每一次扫描整个数组，在凑到的钱数上分别加上三种纸币，直到结束。当然也可以用广搜来做，同样是以0元为第一步，然后开始累加，这简直就是动态规划的变种了，但是同样可能会有重复记录。
那么还有一个问题，深搜和动归的效率谁优谁劣？这不是一个简单的问题。因为深搜实际上是一个二进制的问题，对于每个元素有两种选择：搜与不搜。所以如果给定N种纸币，为了简便起见，在每种纸币只许用一次的情况下，要想把所有情况遍历一遍，O(N)=2N。（因为深搜事实上得到的是一个组合，总共有2N个组合）我们也知道，二进制是一种很奇妙的东西，当N=20时只有1M，N=30时就是1......
【ZZ】关于typedef struct(2007-03-13 22:34:00)
摘要：1. 基本解释
typedef为C语言的关键字，作用是为一种数据类型定义一个新名字。这里的数据类型包括内部数据类型（int,char等）和自定义的数据类型（struct等）。
在编程中使用typedef目的一般有两个，一个是给变量一个易记且意义明确的新名字，另一个是简化一些比较复杂的类型声明。
至于typedef有什么微妙之处，请你接着看下面对几个问题的具体阐述。
2. typedef & 结构的问题
当用下面的代码定义一个结构时，编译器报了一个错误，为什么呢？莫非C语言不允许在结构中包含指向它自己的指针吗？请你先猜想一下，然后看下文说明：
typedef struct tagNode
{
char *pItem;
pNode pNext;
} *pNode;
答案与分析：
1、typedef的最简单使用
typedef long byte_4;
给已知数据类型long起个新名字，叫byte_4。
2、 typedef与结构结合使用
typedef struct tagMyStruct
{
int iNum;
long lLength;
} MyStruct;
这语句实际上完成两个操作：
1) 定义一个新的结构类型
struct tagMyStruct
{
int iNum;
long lLength;
};
分析：tagMyStruct称为“tag”，即“标签”，实际上是一个临时名字，struct 关键字和tagMyStruct一起，构成了这个结构类型，不论是否有typedef，这个结构都存在。
我们可以用struct tagMyStruct varName来定义变量，但要注意，使用tagMyStruct varNam......