http://219.244.176.199/JudgeOnline/problem.php?id=1239
这是这次陕西省赛的G题，题目大意是一个n*n的点阵，点坐标从(1, 1)到(n, n)，每个点都有权值，然后从(x, y)引x轴的垂线，然后构成一个三角形，三个顶点分别是(0, 0)，(x, 0)和(x, y)。求三角形内点的权值和，包括边界，n的范围是1000，m的范围是100000，说起来也比较坑。。学弟n*m的复杂度竟然水过去了，目测比赛数据比较水。。不过我挂到我们OJ上给了一组随机数据，一组极限数据，然后学弟就T掉了。。（坑学弟系列。。）
不水了，这个题目感觉本身是个很好的题。
刚拿到题，我的第一反应肯定是求出所有的p(x, y)，然后往dp的转移方程去考虑。但是发现单纯的递推感觉问题更复杂了。。
但是发现一个重要点就是，斜率小的点，必定被它后面斜率大的点包括。然后，我就想到按x轴枚举每一列，维护每个斜率出现的权值和。那么每一个大的斜率必然是前面枚举过的小的斜率的和，于是便可以树状数组维护了。关键是解决斜率的离散化，我的第一想法是map来进行Hash。当时有了这个思路，本来想着应该可以抢个一血什么的。。结果打到一个小时左右的时候，发现这题已经被好几个人A掉了。。。（什么鬼。。）。我的第一发T了。。通过本地测试，map那个Hash实在太慢了。。于是我开始考虑怎么优化这个Hash，想了好几个办法，要满足y1/x1 < y2/x2，并且Hash(x1, y1) < Hash(x2, y2)的函数实在是没办法。。中间还交了两次错误的Hash方法。。最后队友提醒下，发现那个离散化的过程完全可以一开始预处理，不需要每组数据在线完成，因为数据只有1000*1000，那么所有斜率必然在这个范围内。然后终于A掉了。。
预处理复杂度:O(n*n*log(n*n))
打表:O(n*n*log(n*n))
在线查询:O(m)
最后总的复杂度是O(n*n*log(n*n)+T*(m+n*n*log(n*n)))
如果m大一点的话，这个复杂度还是比较优秀的。。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <string>
#define LL long long using namespace std; const int maxM = ;
const int maxN = ;
LL d[maxN]; int lowbit(int x)
{
return x&(-x);
} void add(int id, int pls)
{
while(id <= maxN)//id最大是maxN
{
d[id] += pls;
id += lowbit(id);
}
} LL sum(int to)
{
LL s = ;
while(to > )
{
s = s + d[to];
to -= lowbit(to);
}
return s;
} int gcd(int a, int b)
{
int r;
while (b != )
{
r = b;
b = a%b;
a = r;
}
return a;
} struct node
{
int x, y; void create(int xx, int yy)
{
int t = gcd(xx, yy);
x = xx/t;
y = yy/t;
} bool operator<(node k) const
{
return k.x*y < k.y*x;
}
}; int n, a[maxM][maxM];
LL p[maxM][maxM];
map<node, int> Hash; void init()
{
node t;
for (int i = ; i < maxM; ++i)
for (int j = ; j < maxM; ++j)
{
t.create(i, j);
Hash[t] = ;
}
map<node, int>::iterator it;
int cnt = ;
for (it = Hash.begin(); it != Hash.end(); ++it)
it->second = cnt++;
} void input()
{
memset(d, , sizeof(d));
node t;
int to;
scanf("%d", &n);
for (int i = n; i >= ; --i)
for (int j = ; j <= n; ++j)
scanf("%d", &a[i][j]);
for (int j = ; j <= n; ++j)
{
for (int i = ; i <= n; ++i)
{
t.create(j, i);
to = Hash[t];
add(to, a[i][j]);
p[j][i] = sum(to);
}
}
} void work()
{
int m, u, v;
scanf("%d", &m);
for (int i = ; i <= m; ++i)
{
scanf("%d%d", &u, &v);
printf("%lld\n", p[u][v]);
}
} int main()
{
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
init();
int T;
scanf("%d", &T);
for (int times = ; times <= T; ++times)
{
printf("Case #%d:\n", times);
input();
work();
}
return ;
}
更新一点东西。
虽然还没想到很好的Hash方式。不过队友给了一个很好的Hash生成方式。不管是用map，还是排序，预处理Hash的复杂度是n*n*long(n*n)的。
但是考虑到每一行的点斜率是单调的，于是类似于多路归并。我先选取每一行斜率最小的点，也就是每一行最后一个点，一共n个点。然后进行n路归并，用优先队列，也就是堆维护这n个斜率。然后每次选取队列首的斜率，那么这个斜率必然是当前最小的。然后赋值Hash值，后将刚斜率所在行的前一个点加入优先队列，如此循环，实现了n路归并，也就是一个排序离散化的过程。这样就可以在复杂度n*n*logn的时间内实现Hash了。复杂度降低了一个常数级。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <vector>
#include <string>
#define LL long long using namespace std; const int maxM = ;
const int maxN = ;
LL d[maxN]; int lowbit(int x)
{
return x&(-x);
} void add(int id, int pls)
{
while(id <= maxN)//id×î´óÊÇmaxN
{
d[id] += pls;
id += lowbit(id);
}
} LL sum(int to)
{
LL s = ;
while(to > )
{
s = s + d[to];
to -= lowbit(to);
}
return s;
} int gcd(int a, int b)
{
int r;
while (b != )
{
r = b;
b = a%b;
a = r;
}
return a;
} struct node
{
int x, y; void create(int xx, int yy)
{
int t = gcd(xx, yy);
x = xx/t;
y = yy/t;
} bool operator<(node k) const
{
return k.x*y > k.y*x;
}
}; int n, a[maxM][maxM];
LL p[maxM][maxM];
int Hash[maxM][maxM];
bool vis[maxM][maxM]; void init()
{
memset(vis, false, sizeof(vis));
memset(Hash, , sizeof(Hash));
node t, k;
priority_queue<node> q;
int cnt = ;
for (int i = ; i < maxM; ++i)
{
t.x = maxM-;
t.y = i;
q.push(t);
vis[t.x][t.y] = true;
}
while (!q.empty())
{
t = q.top();
q.pop();
vis[t.x][t.y] = false;
k.create(t.x, t.y);
if (!Hash[k.x][k.y]) Hash[k.x][k.y] = cnt++;
if (t.x > && !vis[t.x-][t.y])
{
t.x--;
q.push(t);
vis[t.x][t.y] = true;
}
}
} void input()
{
memset(d, , sizeof(d));
node t;
int to;
scanf("%d", &n);
for (int i = n; i >= ; --i)
for (int j = ; j <= n; ++j)
scanf("%d", &a[i][j]);
for (int j = ; j <= n; ++j)
{
for (int i = ; i <= n; ++i)
{
t.create(j, i);
to = Hash[t.x][t.y];
add(to, a[i][j]);
p[j][i] = sum(to);
}
}
} void work()
{
int m, u, v;
scanf("%d", &m);
for (int i = ; i <= m; ++i)
{
scanf("%d%d", &u, &v);
printf("%lld\n", p[u][v]);
}
} int main()
{
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
init();
int T;
scanf("%d", &T);
for (int times = ; times <= T; ++times)
{
printf("Case #%d:\n", times);
input();
work();
}
return ;
}