博文
Zju 1184 Counterfeit Dollar(2006-09-15 17:49:00)
摘要：
2068160
2006-09-15 17:18:10
Accepted
1184
C++
00:00.00
844K
St.Crux
这是一个古老的题目，12枚硬币称3次，求出其中那枚轻或重的硬币。
当然，这道题比求解法简单多了，只需求证明。而我们知道，证明一样物体的存在，只需要把与其对立面的物体从物理层面乃至精神层面完全地、不留遗迹地消灭，这点在人类文明史中得到了最有力的支持......因此，最简单的办法是枚举24种情况，然后一一搜索，不满足者剔除即可。但显然这比较笨拙。
有没有简单一点的办法——假如不是12枚，而是12亿枚？好吧，同样是剔除，我们可以从判断语句入手。
比如 ABCD EFGH even 我们知道了这八枚都是even的。
又比如 ABCI EFJK up 我们知道了ABCI里必然有一枚是heavy的，而EFJK必然有一枚light。因此ABCI就是heavy的嫌疑对象，反之亦然。这是可能性。
从上面的语句中，我们还能得到隐含的条件：DGHL必然是even的。这是必然性。
所以，只要把不满足必然性的可能性剔除就OK了。
至于这个问题的解法，大致是用到二分，具体怎么写还有待研究。
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
using namespace std;
int n, b[12], l0, l1, c[12];
string s0, s1, s2;
void proc();
void print();
int main()
{
//freopen("in.txt", "r", stdin);
cin >> n;
int i, k;
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);
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 1119 SPF(2006-09-11 23:24:00)
摘要：
2062175
2006-09-11 23:10:31
Accepted
1119
C++
00:00.08
4368K
St.Crux
若干年以前，这个题就应该被AC了——对弱题的冲动、严蔚敏老师的数据结构、标程——AC的三大要素我都有了，但是我一直停留在第一阶段——被邓公称作是一百年不变的初级阶段。三十年前，光明日报的编辑写过，实践是检验真理的唯一标准。然而在特定的时间，特定的地点，特定的人物身上，实践只会成为怀疑真理的唯一标准。幸好我还有第三样法宝。
修改过的标程
#include <cstdio>
#include <string>
int x, y, vx, idx, a[1001][1001], dfn[1001], low[1001], sub[1001], root, c = 0, mx, mn;
// low[] means the lowest point one root and its subtree point to
int min(int a, int b)
{
return a > b ? b : a;
}
void init()
{
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(sub, 0, sizeof(sub));
idx = 1, low[vx] = dfn[vx] = idx, root = 0;
}
void dfs(int i)
{
int k;
for(k = mn; k <= mx; k ++)
{
if(a[i][k]) // k adjacent to i
{
if(!dfn[k]) // k not visited -- k is in subtre......
Zju 1268 Is It A Tree?(2006-08-31 22:55:00)
摘要：
2049913
2006-08-31 22:34:46
Accepted
1268
C++
00:00.00
448K
St.Crux
题如其名。如何判断一幅图为树？
设x, y是一对父子节点。对每个x, y，都必须满足如下条件。
1.每个节点没有两个父亲。反例p[y] != y，即y已有父节点。
2.没有回路。反例find_set(x) == y，父节点的祖先是子节点。
以上在输入时即可判断。
3.没有森林。遍历p[i]，没有两个以上的祖先节点。
在这里，采用了并查集作为数据结构，可以用路径压缩，求得根节点。
#include <cstdio>
#include <string>
int p[1001], x, y, b[1001], ac, c[1001], k = 1;
int find_set(int i)
{
if(p[i] != i)
{
p[i] = find_set(p[i]);
}
return p[i];
}
void proc()
{
int i, t = 0;
for(i = 0; i < 1001; i ++)
{
if(b[i])
{
c[find_set(i)] ++;
}
}
for(i = 0; i < 1001; i ++)
{
if(c[i] > 1)
t ++;
}
if(t > 1) ac = 0;
}
void init()
{
int i;
for(i = 0; i <= 1000; i ++)
p[i] = i;
......
Zju 1234 Chopsticks(2006-08-31 00:38:00)
摘要：
2049042
2006-08-31 00:00:06
Accepted
1234
C++
00:00.39
448K
St.Crux
题意：3个数一套，(a1≤a2≤a3)，并定义c =(a1 - a2)^2 。在M个已排序数里找出N套这样的数，使得∑c最小。
典型的组合式dp题。这题的关卡在于：数是一套的，而不是一个，而第三个数又是无用的。但是有一点：a1和a2必然是临近的数，(不然必大于这种最优选择)即取到第k个数时，对于ak和ak-1只有两种选择：
1.不取。2.取。(........) 捆绑考虑。
和所有的组合dp一样，可以列出方程：
opt[i, k] = opt[i - 1, k - 2] + (ak - ak-1)^2 (1≤i≤n, 1≤k≤m)
且opt[i, k] = opt[i, k - 1]
其中opt表示前k个数里取i个能取到的最小值。其中k对于每个i都有取值范围，两边都有，这个和组合dp一样，只不过稍显复杂一些。
而这显然要优化，数组开这么大，1000×5000，还好现在内存便宜。但是还得优化，n值一大照样破产。
那么，只需要两个数组便可。这个也是老规矩了，上一步的先存在b[0]里，每个做完了放b[1]里，等k循环完一遍就可把b[1]赋值给b[0]。这是一种经常用的手法，也是所有不写注释的程序最让人百思不得其解的地方。
#include <cstdio>
#include <string>
#define MX 99999999
int a[5001], b[2][5001], c, n, m;
void init()
{
memset(b, 0, sizeof(b));
}
void dp()
{
int i, k;
for(i = 1; i <= m; i ++)
{
for(k = 2 * i; k <= n; k ++)
{
b[1][k] = MX;
if(k > 2 * i......
Zju 1084 Channel Allocation(2006-08-29 20:12:00)
摘要：顶点着色的贪婪算法证明是存在的，即当前的算法得到只是给出最少颜色的一个上界。
算法描述：设G是一个图，它的顶点按某一顺序记为x1，x2,......xn.
(1) 对顶点x1指定颜色1。
(2)对每个i=2，3，....n,令p是在顶点x1,x2,...xi-1与xi相邻接的顶点中没有任何一个顶点着色p的最小的颜色，并且xi指定颜色p。
数学书上的定理为：设G是一个图，对于该图顶点的最大度为△，那么贪婪算法X产生G的顶点的一个（△+1）着色，因此 X（G）<=△+1
#include <cstdio>
#include <string>
int a[26][26], n, m, ans, c[26], b[26];
char s[26];
void greedy()
{
int i, k;
for(i = 0; i < n; i ++)
{
memset(b, 0, sizeof(b));
for(k = 0; k < n; k ++)
{
if(a[i][k] && c[k] != -1)
{
b[c[k]] = 1;
}
}
for(k = 0; k <= i; k ++)
{
if(!b[k]) break;
}
c[i] = k;
}
for(i = 0; i < n; i ++)
{
if(ans < c[i])
ans = c[i];
}
ans ++......
Zju 1789 The Suspects(2006-08-27 22:53:00)
摘要：
2045607
2006-08-27 22:32:59
Accepted
1789
C++
00:00.02
668K
St.Crux
2045606
2006-08-27 22:32:16
Accepted
1789
C++
00:00.02
556K
St.Crux
上面那个是优化过的，没看错.......可能数据碰巧不喜欢这样被优化。
这是标准解法。
#include <cstdio>
#include <string>
int p[30001], r[30001], n, m, t, x, y, ans;
int findset(int i)
{
if(i == -1 || i >= n)
return -1;
if(p[i] != -1 && p[i] != i)
p[i] = findset(p[i]);
return p[i];
}
int ufs(int a, int b)
{
a = findset(a);
b = findset(b);
if(a == b) return a;
if(a == -1) return b;
if(b == -1) return a;
if(r[a] < r[b])
{
p[a] = b;
return b;
}
else
{
if(r[a] == r[b]) r[a] ++;
p[b] = a;
return a;
}
}
void init()
{
memset(r, 0, sizeof(r));
int i;
for(i = 0; i < n......
Zju 1062 Trees Made to Order(2006-08-26 15:17:00)
摘要：
2043646
2006-08-26 14:29:40
Accepted
1062
C++
00:00.00
432K
St.Crux
给出一个N，求中序树形。
Sample Input
1
20
31117532
0
Sample Output
X
((X)X(X))X
(X(X(((X(X))X(X))X(X))))X(((X((X)X((X)X)))X)X)
这个题的思想是不断逼近。要构造一颗树，（最好）要知道他的左子树序列号和右子树序列号。这个一下子求不出来，但是我们可以先看一下能求出的东西。
N个节点数这儿有几棵树。An= C(2n, n) / (n + 1)，这个可以求，打一个表就可。且可求得N<20。
N这整棵树是几个节点。这个就好求了。用An一个一个的依次减，马上就求出来。减出来的数还得存着，待会儿还得减。
左子树几个节点。这个有点技巧了。这要明白一规律，当左子树有l个节点，右子树r个节点时，这样的树有几棵。答案是Al * Ar。这是全题的关键。而且这树是按左子树的节点树依次排下来的。这就好办了，和上面一样，一个一个挨个减下来。算出来以后右子树也出来了。这就是左子树的节点数和右子树的结点数。
最后就是这个序列号了。就拿这4,5,6,7,8来说吧。减到现在，就成了0,1,0,0,1。这有什么规律呢？没错，0,1分别是2号和3号在他们那一组（2棵树的）里的序列号。现在要用数学公式来说的话，就是：
设Sl为左边的序列号（在他们那一组里的，以下同）Sr为右边的，Al是左边节点数树的总个数，Ar同，t是N减到现在还剩的那个数。则可得：Sl = t / Ar, Sr = t % Ar。因为每棵树是从右开始排，填满了Ar * Al种排法就结束，换到下一种Ar －1的排法里去了，也不归这个排法的管了。左边呢？就Al种排法，一个一个来，比作齿轮的话，就先得让右边的Ar轮一遍，才轮到他动一格。于是这个题就变成简单的排列组合了。
具体的算法边界处还得考虑，这个也是挺麻烦的一个地方。
#include <cstdio>
int a[20] = { 1, 1, 2, 5, 14, 42, 132,
429, 143......
Zju 1141 Closest Common Ancestors(2006-08-25 18:39:00)
摘要：
2042868
2006-08-25 18:19:49
Accepted
1141
C++
00:00.40
408K
St.Crux
2042840
2006-08-25 17:48:34
Accepted
1141
C++
00:03.04
848K
St.Crux
一个是c，一个是c++，一样的算法。这数据读取的效率差的真多。
这题还算个简单的题。用c写时，读取的时候比较麻烦。p[n][0]表示的是该点的父节点。p[n][1]表示的是该点的层次。
#include <cstdio>
#include <string>
int n, m, p[1001][2], ans[1001];
int cca(int a, int b)
{
while(p[a][1] > p[b][1])
{
a = p[a][0];
}
while(p[b][1] > p[a][1])
{
b = p[b][0];
}
while(p[a][1])
{
if(a == b)
break;
a = p[a][0], b = p[b][0];
}
return a;
}
int main()
{
//freopen("in.txt", "r", stdin);
int i, j, x, y;
char c;
while(scanf ("%d", &n) == 1)
{
memset(ans, 0, sizeof(ans));
memset(p, 0, sizeof(p));
for (i = 0; i < n;......