hattricker的日记 · · · · · · · · · · ( 全部 )
这道题教我们怎么使用二维的树状数组。 #include <cstdio> int lowerbit(int a) { return (a ^ (a & (a - 1))); } int n,c[1025][1025]; void add(int x,int y,int delta) { int y_save = y; for (; x <= n; x += lowerbit(x)) { y = y_save; for (; y <= n; y += lowerbit(y)) { c[x][y] ......
编程之美中寻找水王就是xoj 1054寻找黑客。 可以将整个数组排序，第n/2个即是答案。这样时间复杂度为o(nlogn)，还要n的空间。 可以每次去除两个不同id的记录，这样去除的记录中水王的记录总是小于等于1/2,而总的当中水王记录大于1/2,那么剩下的记录中水王的记录也总是超过1/2,到最后剩下的记录就是水王了。 如果显示地删除......
id: 3534910 2009-01-23加入  
| ||
hattricker的朋友(13) · · · · · · ( 全部 )
hattricker的同城活动 · · · · · · ( 1个参加 )
订阅hattricker的收藏:
feed: rss 2.0