博文
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......
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;......
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 ++)
&nbs......