博文
Zoj 2546 Walk Though the Forest(2008-03-02 15:36:00)
摘要：
2767343
2008-03-02 15:15:48
Accepted
2546
C++
00:00.45
4364K
C.D.=.=
写了个最简单的单源路径算法。完全是O(V^2)。比起2281的最小堆+链表差了不止一个档次……
后续还有一个记忆化搜索的处理，当value[u]>value[v]的时候可以把u的路径可能数加到v上。Waterloo的那一次LC还比较简单，加上网站提供标程与数据，已经轻松Clear。
1#include <cstdio>
2#include <string>
3
4#define MAXN 200000000
5
6int N, M, value[1001], visited[1001], a[1001][1001], num[1001];
7
8int init ();
9void dijk ();
10void dp ();
11int func ( int );
12
13int main ()
14{
15 //freopen ( "in.txt", "r", stdin );
16 while ( init () )
17 {
18 dijk ();
19 dp ();
20 &......
Zoj 2704 Breckets(2008-02-26 19:32:00)
摘要：
2761956
2008-02-26 19:16:05
Accepted
2704
C++
00:00.14
924K
C.D.=.=
犯了一个极其低级的错误，把l = strlen(str); for ( i = 0; i < l; i ++ )写成了for ( i = 0; i < strlen ( str ); i ++ )，结果超时无数次。当for循环足够大时，不起眼的地方积累起来，错误也会变得很显著。起初想到可能是使用STL导致的超时，于是把栈简单模拟，结果仍然。看来对这种地方还是不够敏感啊。
1#include <cstdio>
2#include <string>
3
4char str[100001];
5int s[100001], top;
6
7void pt ();
8void print ( int, int );
9
10int main ()
11{
12 // '(' -1 ')' -2 '[' -3 ']' -4
13 //freopen ( "in.txt", "r", stdin );
14 while ( scanf ( "%s", str ) != EOF )
15 &nb......
Zoj 1013 Great Equipment(2008-02-21 19:09:00)
摘要：
2756964
2008-02-21 18:12:06
Accepted
1013
C++
00:03.02
2404K
C.D.=.=
有点意思的DP题，同样也有不小的难度。
模型大致如下：一组背包，除了体积以外，还有重量的限制。有3种不同的item：比如说一把剑，一件盔甲，一双鞋。他们各自有体积，重量，Def值，而组合到一起——也许叫做不死斗篷，出题者明显是英雄无敌的爱好者——又有新的Def加成。如何得到最大的Def？
对于每一辆车（背包），在装满的情形下，可以得到几组不同的xyz，代表三种装备的数量。假如能够得到所有车子总的xyz组合，这题就迎刃而解了。但是我们不能对100辆车子，对每种xyz之和进行搜索，这样数据量太大。
考虑到题目给出xyz<500，故而建立m[i][x][y]的数组，对前i辆车中的xy进行DP。因为在当前i车中，对于每组ix iy，都有唯一对应的iz（最大）。而只要把这辆车中的ixiy去掉就是前一辆车i-1下的xyz值，所以m[i][x][y] =MAX（m[i - 1][x - ix][y - iy]+iz），ix iy 遍历，表示在前i辆车中z能达到的最大值。从而所有的xyz组合都被记录下来了。这种用N-1维数组记录一个N维组合，然后对其DP求得最后一个数的方法就很棒。
为了节省空间，采用滚动数组。具体代码中把i-1提前，对于i-1下每一组xy，加上这辆车里的ixiy就是当前i组下的xy。
#include <cstdio>
#include <string>
#define min(x, y) ( x < y ? x : y )
#define rg(x, y) ( x = ( y > x ? y : x ) ) //replace if greater
int N, c1,&n......
GPU==CPU？(2008-02-19 19:57:00)
摘要：
看到这个熟悉而陌生的画面，我彻底囧了。我知道现在的GPU两个频率都有向CPU靠拢的趋势，但我就料不到N打算把它移植到手机上去呀。
据说可以放高清视频的手机芯片：APX 2500，和微软合作开发，频率高达750MHZ。高中网吧里战Quake的时候，用的也只不过是赛扬667……
http://www.pcpop.com/doc/0/269/269867.shtml......
Zoj 2527 Series(2008-02-19 19:30:00)
摘要：
2755219
2008-02-19 18:56:56
Accepted
2527
C++
00:00.07
4364K
C.D.
做了两天题后有点头昏脑胀，上星期连着熬夜看联盟杯的后遗症不失时机地蹦出来张牙舞爪。也罢，这个礼拜要好好休息，不看冠军杯了。 （其实上个赛季也都是看Bt录播，人懒没药医 =.= ）
一道简单的DP。难点在于原来的算法时间复杂度O(N^3)，N=1000。
题目描述相当简单，给定一个数组，求其中最长的等差数列的长度。
首先考虑一维规划。显然不行，一个等差数列不能用一个数字进行定义。转而考虑二维。当数列的差不大时，可以考虑用F(i,d)表示当前一个数a[i]下等差为d的数列长度。可是这个数列给出了1e10的范围……
继续转进。F(i,j)表示数列的最后一个数是a[i],倒数第二个是a[j]。这样就保存了等差，也可以求得倒数第三个数，前提是找得到。只要在数组里找到它的位置k，就可以继续方程式：F(i,j) = F(j,k) + 1。
但是这样一来无疑要遍历整个数组，使O上升到N^3，这太慢了。为此先对整个数组排序，去除重复的数字，然后在有序的数组里可以用二分搜索k。O(N^2*log(N))，完全满足时间要求。
#include <cstdio>
#include <string>
#include <cstdlib>
int b[1001][1001], a[1001], N, ans;
int cmp ( const void *a, const void *b )
{
return *( int * ) a > *( int * ) b;
}
int init ();
int b_search ( int, i......
Zoj 2740 Message System(2008-02-17 16:50:00)
摘要：
2753473
2008-02-17 16:25:45
Accepted
2740
C++
00:00.00
436K
C.D.
世界上最郁闷的事情，不是连续五个WA，而是连续莫名其妙的WA，却不知道错在哪里；比这更郁闷的事情，是改动之后的连续五个AC，却发现再也找不到刚才究竟错在哪里……
遥想当年，浙大初赛时，雄姿英发；谈笑间，代码灰飞烟灭。故题重做，多情应笑我，迟来三年。卡了近三年的题目，回过头来再看也是一道简单题。
求图是否为连通生成树。预处理边数M，然后用并查集检查一下是否有回路，马上就可以解决。
因为满足生成树的情况下，M恒等于点数N-1，所以在预处理后就不需要考虑是否所有点都能够被访问。开始的时候写了一个BFS算法，遍历，结果失败。（我果然还是比较菜……= =）
#include <cstdio>
#include <string>
int N, M, p[1001], num[1001];
int init ();
void init_set ();
int find_set ( int );
int union_set ( int, int );
int main ()
{
//freopen ( "in.txt", "r", stdin );
while ( init () )
{
}
return 0;
}
void init_set ()
{
in......
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 ......
Zoj 2281 Way to Freedom(2008-02-11 15:23:00)
摘要：无向图中给定单源，求到某点路径中最小权边的最大值。
可以将其看成求单源最短路径的变种，使用dijkstra算法+最大堆。
单源最短路径的算法是：记录从源点出发访问每一点i的最短路为value[i]，对于当前所有value中的最小值点u，进行BFS式的操作，对于每条Edge(u,v)，如果edge(u,v)+value[u] < value[v] 则更新v。这是一个贪心的算法，可以证明每次出队列的u最优。
本题求的是最大单边，对此稍做修改。记录每条边目前能承受的最大重量为value[i]（即从源点所遍历路径的最小权中的最大值）。设u是当前结点，对于每条Edge(u,v)，当路径扩展到v时的最小value（min(edge, value[u])）——即路径的最短边——大于value[v] 时更新。在联通图内，每一次要求的路径都是最大，因此在BFS的过程中，边是从大到小排列，对于当前所有value中的最大值点u进行操作。因为点的数目巨大，遍历需要N<100000，可以用堆存放value。实际程序里堆存放的是点的index，使用一个辅助数组来存放index在heap中的位置，如heap[1] = 6, idx[6] = 1。为了编程方便，heap以1开始。
由于边数目巨大(M<1000000)，因此使用链表储存。使用num数组保存起点为i的起始位置，next数组保存链表。num[i]=a,next[a]=b,next[b]=c,next[c]=d,next[d]=0，这里abcd都为边数组中的位置，表示以i为起点的边终点为abcd。
1#include <cstdio>
2#include <string>
3
4#define min(x, y) ( x < y ? x : y )
5#define INF 2000000001
......
Zoj 2278 Fight for Food(2008-02-11 14:50:00)
摘要：
2745991
2008-02-07 15:05:00
Accepted
2278
C++
00:00.68
1708K
C.D.
感谢W111（WCY）同学的解题报告。
相当出色的DP优化题。
类似于最大不下降子序列，一般有O(N2)的简单算法。但N>30000，故需要优化。原先的算法中，设F(i)= 到第i只老鼠时捕捉到的最大数目，F(i)= max(F(j)+1)，j从1到i-1，假如在时限内能从第i到第j只老鼠出现的方格。这里可以预先使用BFS，用time[rati.i][rati.j][ratj.i][ratj.j]来记录从i到j的最小时间，并加以判断。
为了优化时间，首先进行预处理，把不可能捕捉到的老鼠删除，把从每一点访问所有点至少需要的时间maxtime[rati.i][rati.j]记录下来。
然后把老鼠出现的时间排序。当j从1到i-1访问的时候，可以看到有一些老鼠和当前i的时间相差太多，必然可以访问。这样只要把这些老鼠的最大值+1即可。这些老鼠是：
设老鼠j到老鼠i的时间大于i访问所有点的最大时间maxtime。那么，对于k<j，也必然大于maxtime。
这样就成功剪去大部分时间。
WA了无数遍，终于发现漏了一种不可能捕捉到老鼠的状况。
另外试验一下代码格式
/**//*
作者： Crux.D
日期： 2008-2-11
描述： 动态规划的优化
*/
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
#d......