xnaja 0.0.0.5
忙活了好几天，终于xnaja 0.0.0.5终于要面世了！！！
xnaja是一款火狐插件，提供了yupoo，flickr等国内外主流相册的批量下载。你可以通过几次按键，就将校内，yupoo，flickr或百度上的大量图片下载下来，节省了不少体力劳动。。。
期待傍晚0.0.0.5的正式发布，也希望旧版本的100+个用户能对我们这几天的劳动满意~~~~
Archive for October, 2008
xnaja 0.0.0.5
忙活了几天，xnaja 0.0.0.5 终于要面世了。。。
这是一款提供校内相册，yupoo相册，百度图片搜索结果，flickr标签，相册下载的工具。其他的主流网站也还在添加之中。
期待着他傍晚的正式发布，也希望，原先的100+个用户能对这个新的版本满意~~
Incoming search terms for the article:
test
first time using ScibeFire,just want a try
netbeans 6.1
这几天为了配置ACM地区赛的IDE，研究起了netbeans来。很无奈，在安装时，总是有些莫名其妙的错误。
一开始，装上netbeans时，要求编译器，于是，我选用了codeblocks的MingW的gcc,g++编译器。想用它的make，但是显示不支持MingW的make。于是，我试了一下别的make.exe（似乎不能在有空格的路径下，能否放在中文路径名下倒未曾考证），这时make倒是能用，不过总提示些问题。提示如下：
AllocationBase 0×0, BaseAddress 0x765B0000, RegionSize 0x3E0000, State 0×10000
D:\msys\1.0\bin\make.exe: *** Couldn’t reserve space for cygwin’s heap, Win32 error 487
这时，便上网查了一下，主要思想是需要将一个文件ReBase为0x765B0000（上文中的数）。
于是，上网下个Rebase.exe，然后再在cmd窗口运行，rebase.exe -b 0x765B0000 …(dll文件所在路径)。例如，我用的是msys，这时，便输入 rebase.exe -b 0x765B0000 d:\msys\1.0\bin\msys-1.0.dll
现在，一切便搞定了。
哈工程之旅
这次哈尔滨之行，虽是比赛而去，但感觉确是趟旅途。
哈工程很特别，里边的建筑尽是鲁班奖的作品，很有特色。看着倒也是种享受。不过，这里还得提一点，就是哈工程的住宿条件，实在是有些不敢恭维了！
在哈工程，我们遇到一个挺漂亮的志愿者，一个相当敬业的志愿者，拎着我们环校旅游。
最后说说比赛，当是总结。比赛失误主要有两点。一是I题看题失误，默认性的将输入默认为不升序列，导致了5次的错误提交，这点责任完全在我。二是C题，我们采取了Dijkstra+二分图最佳匹配算法。据与复旦的队员的讨论，复杂度上是完全过得去的。具体TLE的原因尚未查明，不过估计应该是敲代码时的失误。
相比起来，第一个失误是致命的，他导致我们在结束的前30分钟时直接落到了3道题的倒数第2名。第二个则有些无奈。我们刚开始是用Floyed，超时，这时方想起用Dijkstra，用的是二项堆实现的Dijkstra，敲完代码时，已经只剩下5分钟了。我们只有了一次提交的机会。这样便有些无奈了。。。
写累了，不写了。。。
POJ1062【单源最短路】
原题描述：
[url=http://acm.pku.edu.cn/JudgeOnline/problem?id=1062]见原题[/url]
题目大意：
探险家想获得某样物品，可以直接买，花费P；也可以获得另外一种物品（递归调用。。。），再加上V金币来换取。
另外，与探险家交换的人都有个级别。他只能在一个长度为M + 1的下界不定的范围的级别的人内交换。举个例子，M为1，他要是与级别为3的人交换了，就不能与级别为1的人交换了，反之亦然。
求出，探险家想获取物品0所需花费的最少金币数。
解题思路：
我的想法是，在可以互换的物品间建立一条边，度为其需要的额外金币V。这样便建起了一个图。以0为起始点，用dijkstra算法求出它到每个点的最短 路。这个最短路便是，用该物品经过多次换算，得到物品0所需的最少的金币数。再加上买这个物品的费用，便是获得物品0所需的最小金币数了。
另外，这里还有一个问题，就是每个人都级别的问题了。我是通过两个数组，分别保存换取到物品i时的最大的级别和最小的级别。于是，在dijkstra比较时，加入级别的判定。这样，便能轻松的解决这个问题。
代码:
#include <stdio.h>
#define MAXN 101
#define inf 1000000000
typedef int elem_t;
int Lev[101];
int Lev_lowest[101],Lev_max[101];
int M,N;
void dijkstra(int n,elem_t mat[][MAXN],int s,elem_t* min,int* pre){
int v[MAXN],i,j,k;
for (i=0;i<n;i++)
min=inf,v=0,pre=-1;
for (min[s]=0,j=0;j<n;j++){
for (k=-1,i=0;i<n;i++){
if (!v&&(k==-1||min<min[k])){
k=i;
}
}
for (v[k]=1,i=0;i<n;i++){
if (!v&&min[k]+mat[k]<min && (Lev <= M + Lev_lowest[k]) && Lev >= Lev_max[k] - M){
min=min[k]+mat[pre=k];
Lev_lowest = Lev_lowest < Lev_lowest[k]?Lev_lowestev_lowest[k];
Lev_max = Lev_max > Lev_max[k]?Lev_maxev_max[k];
}
}
}
}
int map_wedding[101][101];
int _abs(int x){
if(x >= 0){
return x;
}
return -x;
}
int main(){
while(scanf("%d %d",&M,&N) != EOF){
int i,k,z;
for(i = 0; i <= N; ++i){
for(k = 0; k <= N; ++k){
map_wedding[k] = inf;
}
}
int P[101],X;
int max_l = -1;
for(i = 0; i < N; ++i){
scanf("%d %d %d",&,&Lev,&X);
Lev_lowest = Lev_max = Lev;
for(k = 0; k < X; ++k){
int T,V;
scanf("%d %d",&T,&V);
T--;
map_wedding[T] = V;
}
}
for(i = 0; i < N; ++i){
for(k = i; k < N; ++k){
if(map_wedding[k] != inf){
if(_abs(Lev - Lev[k]) > M){
map_wedding[k] = map_wedding[k] = inf;
}
}
}
}
//for(i = 0; i < N; ++i){
// for(k = 0; k < N; ++k){
// printf("%d\t",map_wedding[k]);
// }
// printf("\n");
//}
int min[101],pre[101];
dijkstra(N,map_wedding,0,min,pre);
int min_cost = P[0];
for(i = 1; i < N; ++i){
// printf("%d %d\t",min,pre);
min_cost = min_cost > min + P?min + P:min_cost;
}
//printf("\n");
printf("%d\n",min_cost);
}
return 0;
}
测试数据
1 4
10000 3 2
2 8000
3 5000
1000 2 1
4 200
3000 2 1
4 200
50 2 0
1 4
10000 2 1
2 4000
6000 3 1
3 2000
3000 2 1
4 1000
1000 1 0
结果
5250
9000
以上代码未经过优化。