博文
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 ( "%d ", t[i][j] ); &n......
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; i ++) { scanf ("%d", &x); scanf ("%c", &c); &nbs......
Zju 2109 FatMouse' Trade(2006-08-10 01:03:00)
摘要：
2012463
2006-08-10 00:50:36
Accepted
2109
C++
00:00.17
408K
St.Crux
菜题。最简单的排序＋贪婪就可以过。但是有一些陷阱。
是贡献了三次wa。我居然把忘了把调试部分注释掉—_—
#include <cstdio>
int n, m, a[1000], b[1000];double r[1000];
void pt(){ for(int i = 0; i < m; i ++) { printf("%d %d %0.3f\n", a[i], b[i], r[i]); }}
int main(){ //freopen("in.txt", "r", stdin); while(scanf("%d %d", &n, &m) && n != -1) { int i, k, j; for(i = 0; i < m; i ++) { scanf("%d %d", &a[i], &b[i]); if(b[i] == 0) r[i] = 99999999; else r[i] = double(a[i]) / double(b[i]); } //select sort for(i = 0; i < m - 1; i ++) { double mx = r[i]; j = i; for(k = i + 1; k < m; k ++) { if(r[k] > mx) { j ......