博文
Zoj 2107 Quoit Design(2008-02-14 14:03:00)
摘要：
2750801
2008-02-14 13:48:15
Accepted
2107
C++
00:02.95
4068K
C.D.
分治算法的应用。在求左和右之间的最短点对时，先把满足X坐标差值小于CurMin的点对按Y排序，然后可以剪掉Y坐标值差小于CurMin的点对。
/**//* 作者 Crux.D 日期 2008.2.14 描述 分治求最短距离点对*/#include <cstdio>#include <string>#include <cstdlib>#include <cmath>typedef struct{ double x, y;} Point;Point p[100001];int N, q[100000];int init ();double b_search ( int, int );inline double dist ( int i, int j ){ double x = sqrt ( ( p[i].x - p[j].x ) * ( p[i].x - p[j].x ) + &n......
Zoj 2279 In the Mirror(2008-02-13 18:21:00)
摘要：一道很好的搜索题。WA一次，原因是二进制hash开的太小。
一般求最短步数的问题，大多采用BFS，当终点与当前节点的XY值相等时输出，本题也不例外。难点在于，镜子的状态如何处理。
注意到镜子的数目<10，每一镜子仅有两种状态 \ 和/ 。因此将每一面镜子左右视为0与1，得到二进制编码的值hash，存入BFS中的节点。最大节点状态为2^10*10*10=102400 ，时间和空间上完全满足要求。
这里总共有三个102400的数组。一个队列Q，一个step存放某节点的步数，一个sight进行预处理，记录下当镜子出于某种状态hash下，每个点是否能够访问。
代码太长，格式放不上来，辛辛苦苦打了半天没了，只好帖原文。里面有一些相当有用的技巧，比如对于每一面镜子i的开关操作（0置为1，1置为0）是2^i xor hash，又比如对方向的处理数组与处理函数——这就和马路边的城管一样，常见，而且实用。但是方向函数看代码是看不懂的，需要自己分析一下。
#include <cstdio>#include <string>
char a[11][11];int N, M, num_m, num_b, step[10][10][1024], sight[10][10][1024], ans;int dir[4][2] ={ { 0, 1 }, { 1, 0 }, { 0, -1 }, { - 1, 0 }};int p[11] ={ 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024};
typedef struct{ int x, y, dir, step, h;} Bat;Bat sb, eb, Mirror[12], Q[102410], B[100];
int init ();void bfs ();void proc ( int );int redir ( int, int, int ); //计算方向void print ();
int main (){ //freopen ( "in.txt", "r", stdin ); while ( init () ) { bfs (); ......
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 126 6 66 3 6
求，最小需要几步，把所有时钟都挑到12点？
这是一个非常好的bfs和dfs练习题，但是也相当的难写。在看了某牛人的dfs代码之后，我发现自己比看过之前懂的更少。胡Core也教导我们，要以艰苦朴素为荣。综上所述，我采用了穷举的方法。
但是这也是有前提的。第一，每一个时钟都只有四种状态。换句话说，每种操作也是四种状态，进行0，1，2，3次。第二，4的9次方不大……
/*ID: Crux.DPROG: clocksLANG: 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[9][9] = {{ 1, 1, 0, 1, 1, 0, 0, 0, 0......
zoj 2002 Copying Books(2007-03-11 23:58:00)
摘要：经典的判定。对N个正整数的k-划分，要求的是划分中最大数的最小值。如有相同最小值，使前面的划分和最小。
这题的思路是穷举这个最小值，然后计算是否满足k划分。设当前的划分数为x，mx得到的是满足x<=k的最小值。穷举的过程可以用二分。
判定计算采用的是贪婪算法，从后向前，尽量使后面的划分之和在要求判定的值范围内最大。同时把划分处b[i]置1。
另外，有可能出现mx的划分数x<k，而mx-1的划分数x>k的情况。此时为了使前面的划分最小，只消将前面几个空闲的b[i]置1即可。
#include <cstdio>#include <string>
int m, n, t, b[501]; //seperate
double a[501], sum, mx, mn; //book
int check ( double chk_n ){ int i, total = 0; double t_sum = 0; memset ( b, 0, sizeof ( b ) ); for ( i = n - 1; i >= 0; i -- ) { t_sum += a[i]; if ( t_sum > chk_n ) { t_sum = a[i]; b[i] = 1; &nb......
Zju 1004 Anagrams by Stack(2007-01-23 20:57:00)
摘要：挺早的时候写的。那个时候还不知道C的读入效率比C++高，用的还是vector。
/* source: zju 1004 *//* algo: dfs *//* date: 2006/5/17 *//* author: Crux.D */
#include <iostream>#include <fstream>#include <string>#include <stack>#include <vector>#include <algorithm>using namespace std;
string str0, str1;stack<char> cs;vector<char> cv;int l;
void prints(){ for(int i = 0; i < cv.size(); i ++) { cout << cv[i] << " "; } cout << endl;}
void dfs(int ii, int oi){ if(ii == l && oi == l) prints(); if(ii + 1 <= l) { cs.push(str0[ii]); cv.push_back('i'); dfs(ii + 1, oi); cs.pop(); cv.pop_back(); } if(oi + 1 <......
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 38742......
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(){ int i; for(i = 0; i < ans; i ++) { printf("%d ", ......
Zju 2416 Open the Lock(2006-09-14 23:05:00)
摘要：
2067137
2006-09-14 22:42:54
Accepted
2416
C++
00:00.89
956K
St.Crux
看来我要好好练习，bfs也可以编的很复杂。比如......1649的迷宫我已经WrongAnswer了十来遍了，每一遍都能激动地发现新的错误、作出愉快的改正，然后继续陷入郁闷。
这题还算基本的bfs，一遍ac的感觉真好。STL虽然占内存，也有他的好处。用上queue以后，我就不用再模拟队列了。
#include <iostream>#include <cstring>#include <string>#include <queue>using namespace std;
int n, b[10000], pi, si;string s, p;queue <string> sq, tq;
void init();int stoi(string);void bfs();void print();
int main(){ //freopen("in.txt", "r", stdin); cin >> n; int i; for(i = 0; i < n; i ++) { cin >> s >> p; init(); bfs(); print(); } return 0;}
void init(){ pi = stoi(p); si = stoi(s); memset(b, 0, sizeof(b)); b[si] = 1; sq = tq; sq.push(s);}
int stoi(string str){ int sum = 0, i; for(i = 0; i < 4; i ++) { sum *= 10; s......
Zju 1711 Sum It Up(2006-09-13 21:53:00)
摘要：
2065174
2006-09-13 21:04:57
Accepted
1711
C++
00:00.00
436K
St.Crux
背政治背的太阳穴发疼，连啃着苹果都会自觉想到人与自然的对立统一。黑格尔先生、马克思先生、还有很多很多先生，若是在天有知，定会被几百年后的中国大学生精英们感动到流泪口牙。
好吧，做一道1/2弱题换换脑子。题目还是很弱的，普通的搜索，几个数之和凑成M，不允许有重复出现。之所以加个头衔，是因为当初在学校比赛里做的时候用了很白痴的手段：把搜出来的结果换成string放到一个vector里，后来者要和先到的做比较......这有够烂的了。但在当时是我狗急跳墙，哦不，是灵机一动下的大彻大悟。
但是如今就大不同哦。在清华版《数据结构》的理论光环指引下（注：这是广告），我写下了简洁的方法。
举一个例子。
M = 13。有六个数： 6, 5, 5, 2, 2, 2。
13 = 6 + 5 + 2
显然，搜完第一个2之后，下一个2应该被忽略。然而在搜索里总不能写if(a[i] != 2)吧。因为如果M是15，第二个2是必须的。这个处理困惑了我好久——查理曼的后代称之为Hanter，Angle-Sexons（盎格鲁萨克森人，又译棱角分明的性感男人）改进为Haunt，后来流传到中国称作「鬼啊」——这是迷信的象征。总之就是莫明其妙的出错。
后来仔细的研究了几种遍历。发现如果这里采用后序遍历——也就是先记录子节点再记录根节点的话，问题就迎刃而解了。
考虑上面的例子。遍历时顺序是这样的：2，5，6。这很好的解释了为什么第二个2不需要了——当回溯到5时只要看一下子节点记录（2）就知道了。注意，回溯。规律同样适用于6和5。
比如M＝15。M＝6+5+2+2。但是没有回溯。当第二个2做完之后，第三个2加不了，因为17>15。于是回溯。这时5......
Zju 1901 A Star not a Tree?(2006-08-10 21:37:00)
摘要：
2014083
2006-08-10 20:56:11
Accepted
1901
C++
00:00.06
516K
St.Crux
这个题如果用穷举则超时：总共10000*10000个点。因此考虑从中心点出发向四周扩散搜索。这还是上个学期做的题，一直wronganswer。
#include <cstdio>#include <cmath>
int xi[100], yi[100];int dir[8][2] = {{-1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 0}, {0, -1}, {1, -1}, {-1, 1}};double min;int n;
void dfs(int x, int y){ int i, k; double tm = 0; for(i = 0; i < n; i ++) { tm += sqrt((x - xi[i]) * (x - xi[i]) + (y - yi[i]) * (y - yi[i])); } if(tm < min) { min = tm; for(k = 0; k < 8; k ++) { int xx = x + dir[k][0]; int yy = y + dir[k][1]; dfs(xx, yy); } } else return;}
int main(){ int i; //freopen("in.txt", "r", stdin); while(scanf("%d", &n) != EOF) { int x0 = 10000, x1 = 0, y0 = 10000, y1 = 0; for(i = 0; i < n; i ++) { ......