71 条题解
-
2smzzl LV 8 @ 2017-12-30 21:51:05
我不懂你们在骚什么好吧,二维树状数组?线段树?(黑人问号)
就直接维护前缀和啊
10000*1000又不会t
代码简单多少#include<iostream>
#include<cstdio>
using namespace std;
long long sum[1026][1026];
int main()
{
int n;
cin>>n;
int m;
cin>>m;
while (m!=3)
{
int ans=0;
if (m==1)
{
int x,y,k;
cin>>x>>y>>k;
x++;
y++;
for (int i=y;i<=n;i++) sum[x][i]+=k;
}
if (m==2)
{
int x,y,_x,_y;
cin>>x>>y>>_x>>_y;
x++;
y++;
_x++;
_y++;
for (int i=_x;i>=x;i--) ans+=sum[i][_y];
for (int i=_x;i>=x;i--) ans-=sum[i][y-1];
printf("%d\n",ans);
}
scanf("%d",&m);
}
//for (int i=0;i<=n;i++,cout<<endl)
// for (int j=0;j<=n;j++) cout<<sum[i][j]<<" ";
} -
12018-04-02 11:12:50@
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#include<iostream>
using namespace std;int main()
{
int n;
cin >> n;int **range=new int*[n];
for (int i = 0; i < n; i++)
range[i] = new int[n];for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
range[i][j] = 0;
while (1)
{
int judge;
cin >> judge;
if (judge == 1)
{
//printf("输入1\n");
int x, y, z;
cin >> x >> y >> z;
range[x][y] += z;
//cout << range[x][y];
}
if (judge == 2)
{
//printf("输入2\n");
int a, b, c, d; int sum = 0;
cin >> a >> b >> c >> d;for (int i = a; i <= c; i++)
for (int j = b; j <= d; j++)
sum += range[i][j];
cout << sum << endl;
}
if (judge == 3)
{system("pause");
return 0;
}
}}
-
12017-03-11 11:54:42@
Vijos本题(SuperBrother打鼹鼠)Code
#include <cstdio> #include <cstring> #define rs 1024 using namespace std; int c[rs+2][rs+2]; void add_1(int x,int y,int data,int s) { for (int i=x;i<=s;i+=i&-i) for (int j=y;j<=s;j+=j&-j) c[i][j]+=data; } int sum_1(int x,int y) { int ans=0; for (int i=x;i>0;i-=i&-i) for (int j=y;j>0;j-=j&-j) ans+=c[i][j]; return ans; } int ask_1(int x1,int y1,int x2,int y2) { int sum_c[5]; sum_c[1]=sum_1(x2,y2),sum_c[2]=sum_1(x1-1,y1-1),sum_c[3]=sum_1(x1-1,y2),sum_c[4]=sum_1(x2,y1-1); return sum_c[1]+sum_c[2]-sum_c[3]-sum_c[4]; } int main() { int o,s,x,y,d,l,b,r,t; memset(c,0,sizeof(c)); scanf("%d",&s); while (1) { scanf("%d",&o); if (o==1) { scanf("%d%d%d",&x,&y,&d); x++,y++; add_1(x,y,d,s); } else if (o==2) { scanf("%d%d%d%d",&l,&b,&r,&t); l++,b++,r++,t++; printf("%d\n",ask_1(l,b,r,t)); } else if (o==3) break; } }
Poj原题(Mobile phones)Code
http://poj.org/problem?id=1195#include <cstdio> #include <cstring> #define rs 1024 using namespace std; int c[rs+2][rs+2]; void add_1(int x,int y,int data,int s) { for (int i=x;i<=s;i+=i&-i) for (int j=y;j<=s;j+=j&-j) c[i][j]+=data; } int sum_1(int x,int y) { int ans=0; for (int i=x;i>0;i-=i&-i) for (int j=y;j>0;j-=j&-j) ans+=c[i][j]; return ans; } int ask_1(int x1,int y1,int x2,int y2) { int sum_c[5]; sum_c[1]=sum_1(x2,y2),sum_c[2]=sum_1(x1-1,y1-1),sum_c[3]=sum_1(x1-1,y2),sum_c[4]=sum_1(x2,y1-1); return sum_c[1]+sum_c[2]-sum_c[3]-sum_c[4]; } int main() { int o,s,x,y,d,l,b,r,t; while (1) { scanf("%d",&o); if (o==0) { scanf("%d",&s); memset(c,0,sizeof(c)); } else if (o==1) { scanf("%d%d%d",&x,&y,&d); x++,y++; add_1(x,y,d,s); } else if (o==2) { scanf("%d%d%d%d",&l,&b,&r,&t); l++,b++,r++,t++; printf("%d\n",ask_1(l,b,r,t)); } else if (o==3) break; } }
-
02017-04-18 08:55:22@
求矩形的时候犯了好几个BUG
1.直接用(0,0)-右下角的矩形减去(0,0)-左上角的矩形
2.左上角两个坐标都应该减1(画图就知道了) -
02016-11-17 10:48:10@
二维裸题。。记得要将下标+1,否则当x or y==0时就完了。。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>using namespace std;
#define lb(A) A&(-A)
int a[2000][2000];
int n,m,x1,y1,k,x2,y2;void add(){
for(int i=x1+1;i<=n;i+=lb(i))
for(int j=y1+1;j<=n;j+=lb(j))
a[i][j]+=k;
}int ask(int x,int y){
int ret=0;
for(int i=x+1;i;i-=lb(i))
for(int j=y+1;j;j-=lb(j))
ret+=a[i][j];
return ret;
}int main(){
scanf("%d",&n);
while(scanf("%d",&m)==1&&m!=3){
if(m==1){
scanf("%d%d%d",&x1,&y1,&k);
add();
}else{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
printf("%d\n",ask(x2,y2)-ask(x2,y1-1)-ask(x1-1,y2)+ask(x1-1,y1-1));
}
}
} -
02016-11-06 19:35:53@
#include<iostream> #include<cstdio> using namespace std; int b[1025][1025]; int n = 0; int lowbit(int a) { return a&-a; } void add(int x,int y,int z) { for (;x <= n;x= x + lowbit(x)) for (;y <= n;y= y + lowbit(y)) { b[x][y] = b[x][y] + z; } } int lll(int x, int y) { int ans = 0; for (; x > 0; x=x - lowbit(x)) for (; y > 0; y=y - lowbit(y)) { ans += b[x][y]; } return ans; } int main() { scanf("%d",&n);/////修改为scanf while (1) { int m = 0; scanf("%d",&m); if (m == 3)break; else if(m == 1) { int x, y, z; scanf("%d%d%d", &x, &y, &z); add(x+1, y+1, z); } else if (m == 2) { int x, y, xx,yy; scanf("%d%d%d%d", &x, &y, &xx, &yy); printf("%d\n", lll(xx+1, yy+1) - lll(x, yy+1)-lll(xx+1,y)+lll(x,y)); } } return 0; }
请问哪里错了!QAQ
-
02016-07-16 20:50:24@
随机数据就是水,一维树状数组都能过
n其实没什么卵用
#include<cstdio>
using namespace std;const int maxn=1050;
int c[maxn][maxn],a[maxn],n,ans;inline int lowbit(int x) { return x&(-x); }
void add(int v,int x,int d)
{
while ( x<=n) {
c[v][x]+=d;
x+=lowbit(x);
}
}int sum(int v,int x)
{
int ans=0;
while (x>0) {
ans+=c[v][x];
x-=lowbit(x);
}
return ans;
}int main()
{scanf("%d",&n);
int m;
for (;;) {
scanf("%d",&m);
if (m==1) {
int x,y,k; scanf("%d%d%d",&x,&y,&k);
add(x+1,y+1,k);
}
if (m==2) {
int x1,y1,x2,y2,ans=0;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
for (int i=x1+1;i<=x2+1;++i) {
ans+=sum(i,y2+1)-sum(i,y1);
}
printf("%d\n",ans);
}
if (m==3) break;
}
return 0;
} -
02015-10-25 20:21:39@
二维树状数组 把所有的坐标都+1
然后左下角为(x1,y1),右上角为(x2,y2)的矩阵 即为 (0,0)(x2,y2)-(0,0)(x1,y2-1)-(0,0)(x2,y1-1)+(0,0)(x1-1,y1-1)
注意不要涉及到0 ,求sum的时候不要复制上边的然后忘记改+-和大小等于号23333
接下来是代码#include <cstdio>
#include <algorithm>
using namespace std;
int a[1200][1200],n,m;void add(int x,int y,int d){
for(int i=y;i<=n;i+=i&-i)
for(int j=x;j<=n;j+=j&-j) a[i][j]+=d;
}int sum(int x,int y){
int ret=0;
for(int i=y;i;i-=i&-i)
for(int j=x;j;j-=j&-j) ret+=a[i][j];
return ret;
}int main(){
scanf("%d",&n);
while(scanf("%d",&m)!=EOF){
if(m==1){
int x,y,k;
scanf("%d%d%d",&x,&y,&k);x++,y++;
add(x,y,k);
}
else if(m==2){
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);x1++;y1++,x2++,y2++;
printf("%d\n",sum(x2,y2)-sum(x1-1,y2)-sum(x2,y1-1)+sum(x1-1,y1-1));
}else break;
}
return 0;
} -
02015-08-18 12:12:22@
二维树状数组。坐标全部+1,因为树状数组从1开始存储
//Vijos P1512
#include <stdio.h>
#include <string.h>int tree[1030][1030];
int size = 0;int lowbit(int index);
void clear(void);
void add(int x, int y, int delta);
int Max(int a, int b);
int sumFromOrigin(int x, int y);
int sumRect(int x1, int y1, int x2, int y2);int main(){
int cmd, x1, y1, x2, y2, n;scanf("%d", &size);
clear();
while(scanf("%d", &cmd)!=EOF){
if(cmd==1){
scanf("%d %d %d", &x1, &y1, &n);
x1++, y1++;
add(x1, y1, n);
}else if(cmd==2){
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
x1++, y1++, x2++, y2++;
printf("%d\n", sumRect(x1, y1, x2, y2));
}else if(cmd==3){
return 0;
}
}return 0;
}
int lowbit(int index){
return ((index-1)^index)&index;
}
void clear(){
int x, y;
for(x=0; x<=size; x++){
for(y=0; y<=size; y++)
tree[x][y] = 0;
}
}
void add(int x, int y, int delta){
int i, k;
if(delta==0)
return;
for(i=x; i<=size; i+=lowbit(i)){
for(k=y; k<=size; k+=lowbit(k))
tree[i][k] += delta;
}
}
int sumFromOrigin(int x, int y){
int i, k;
int tmp = 0;
if(x<=0 || y<=0)
return 0;
for(i=x; i>0; i-=lowbit(i)){
for(k=y; k>0; k-=lowbit(k))
tmp += tree[i][k];
}
return tmp;
}
int sumRect(int x1, int y1, int x2, int y2){
return sumFromOrigin(x2, y2) - sumFromOrigin(x1-1, y2) - sumFromOrigin(x2, y1-1) + sumFromOrigin(x1-1, y1-1);
} -
02014-10-23 16:27:07@
逐一树状数组里最好不要牵涉到0,容易出错。。。
#include<cstdio>
#include<cstring>using namespace std;
int N,tree[1025][1025];
inline int lowbit(int x)
{
return ((x)&(-x));
}void update(int x,int y,int delta)
{
for(int i=x;i<=N;i+=lowbit(i))
for(int j=y;j<=N;j+=lowbit(j))
tree[i][j]+=delta;
}int sum(int x,int y)
{
int ans=0;
for(int i=x;i;i-=lowbit(i))
for(int j=y;j;j-=lowbit(j))
ans+=tree[i][j];
return ans;
}int query(int x1,int y1,int x2,int y2)
{
int ans=sum(x2,y2);
if (x1) ans-=sum(x1-1,y2);
if (y1) ans-=sum(x2,y1-1);
if (x1&&y1) ans+=sum(x1-1,y1-1);
return ans;
}int main()
{
freopen("in.txt","r",stdin);
memset(tree,0,sizeof(tree));
scanf("%d",&N);
while (1)
{
int m;
scanf("%d",&m);
if (m==1)
{
int x,y,k;
scanf("%d%d%d",&x,&y,&k);
update(x+1,y+1,k);
}
else if (m==2)
{
int x1,x2,y1,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
printf("%d\n",sum(x2+1,y2+1)+sum(x1,y1)-sum(x1,y2+1)-sum(x2+1,y1));
}
else if (m==3) return 0;
}
return -1;
} -
02014-07-30 15:20:32@
var
i,n,m,x1,x2,y1,y2,x,y,k:longint;
a,c:array[1..1025,1..1025]of longint;
function lowbit(x:integer):longint;
begin
exit(x and-x);
end;
procedure modify(i,j:integer;aa:longint);
begin
inc(a[i,j],aa);
x:=i ;
while x<=n do
begin
y:=j;
while y<=n do
begin
inc(c[x,y],aa);
inc(y,lowbit(y));
end;
inc(x,lowbit(x))
end;
end;
function sum(i,j:longint):longint;
begin
sum:=0;
x:=i;
while x>0 do
begin
y:=j;
while y>0 do
begin
inc(sum,c[x,y]);
dec(y,lowbit(y));
end;
dec(x,lowbit(x));
end;
end;
begin
readln(n);
read(m);
while m<>3 do
begin
if m=1 then
begin
read(x,y,k);
x:=x+1;
y:=y+1;
modify(x,y,k);
end
else
begin
read(x1,y1,x2,y2);
inc(x2,1);inc(y2,1);
writeln(sum(x2,y2)+sum(x1,y1)-sum(x1,y2)-sum(x2,y1));
end;
read(m);
end;
end. -
02013-07-13 12:15:27@
第一次打树状数组 好不容易A了
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
//#include <fstream>using namespace std;
#define MAXN 1025
//ofstream fout("check.txt");
int t[MAXN][MAXN];
int Exp[31];int Lowbit(int x){
return (x+(((~x)+1)&x));
}int n;
int Add(int x,int y,int k){
int i=x;
while (i<=n){
int j=y;
while (j<=n){
t[i][j]+=k;
j=Lowbit(j);
}
i=Lowbit(i);
}
return 0;
}int Find(int x){
int l=0,r=30;
while (1){
if (r-l==1){
return l;
}
if (Exp[l]==x){
return l;
}
if (Exp[r]==x){
return r;
}
int mid=(l+r)>>1;
if (Exp[mid]==x){
return mid;
}
if (Exp[mid]>x){
r=mid;
}
if (Exp[mid]<x){
l=mid;
}
}
}int sum(int x,int y){
/* cout<<x<<" "<<y<<endl;
if (x==6&&y==8){
cout<<"!"<<endl;
}*/
int rec=0;
int i=0;
while (i<x){
i+=Exp[Find(x-i)];
int j=0;
while (j<y){
j+=Exp[Find(y-j)];
rec+=t[i][j];
}
}
return rec;
}
/*
void out(){
for (int i=0;i++<n;){
for (int j=0;j++<n;){
fout<<t[i][j]<<" ";
}
fout<<endl;
}
}
*/
int main(){
Exp[0]=1;
for (int i=0;i++<30;){
Exp[i]=Exp[i-1]*2;
}
memset(t,0,sizeof(t));
scanf("%d",&n);
while (1){
int m,x,y,k,h;
scanf("%d",&m);
if (m==3){
break;
}
if (m==1){
scanf("%d%d%d",&x,&y,&k);
Add(x+1,y+1,k);
}
if (m==2){
scanf("%d%d%d%d",&x,&y,&k,&h);
// out();
printf("%d\n",sum(k+1,h+1)-sum(x,h+1)-sum(k+1,y)+sum(x,y));
// fout<<sum(k+1,h+1)<<"-"<<sum(x,h+1)<<"-"<<sum(k+1,y)<<"-"<<sum(x,y)<<endl;
}
}
return 0;
} -
02012-11-17 21:40:07@
坑呐……左下角(0,0),我竟然在没看完题的情况下debug了半小时,泪奔……
-
02010-04-13 22:22:26@
ZYM好强大!……SuperBrother好强大!
{---|---|---|---|---|---|以上为不和谐内容可以省略---|---|---|---|---|---|---|-}
这题让我想到了二维的树状数组……
{---|---|---|---|---|---|---|---|--}
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms搞定……
-
02009-11-07 10:39:46@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms2次AC的
-
02009-10-27 22:29:24@
苦恼,本来准备做到睡觉的,结果一遍AC没事干了
-
02009-10-26 17:15:44@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0msconst filename='p1512';
var
c:array[1..1025,1..1025]of longint;
i,j,n,m,k,x,y,x1,y1,ans:longint;
function lowbit(x:longint):longint;
begin exit(x and(x xor (x-1)));end;
procedure add(x,y,k:longint);
var z:longint;
begin
while x0do
begin
inc(q,c[x,z]);
dec(z,lowbit(z));
end;
dec(x,lowbit(x));
end;
exit(q);
end;
begin
assign(input,filename+'.in');reset(input);
assign(output,filename+'.out');rewrite(output);
readln(n);
while true do
begin
read(m);if m=3 then break;
if m=1 then
begin
read(x,y,k);
add(x+1,y+1,k);
end
else begin
ans:=0;read(x,y,x1,y1);
ans:=getsum(x1+1,y1+1)-getsum(x1+1,y)-getsum(x,y1+1)+getsum(x,y);
writeln(ans);
end;
end;
close(input);close(output);
end.#include
#include
#define lowbit(x) (x&(x^(x-1)))
using namespace std;
long i,j,k,n,m,x,y,x1,y1,ans,c[1025][1025]={0};
void add(long x,long y,long k)
{
long i,j;
for(i=x;i0;j-=lowbit(j))
s+=c[i][j];
return(s);
}
int main(){
// freopen("p1512.in","r",stdin);
// freopen("p1512.out","w",stdout);scanf("%ld",&n);
for (;;)
{
scanf("%ld",&m);
if (m==3) break;
if (m==1)
{
scanf("%ld%ld%ld",&x,&y,&k);
add(x+1,y+1,k);
}
if (m==2)
{
scanf("%ld%ld%ld%ld",&x,&y,&x1,&y1);
ans=getsum(x1+1,y1+1)-getsum(x1+1,y)-getsum(x,y1+1)+getsum(x,y);
printf("%ld\n",ans);
}
}
return 0;
}第一道C++,在super brother神牛的帮助下,终于过了,强烈Orz
1、发现了C++和fp的一点点区别,如果用fp写,add过程和getsum函数要写超多行,但是用C++写只用几行,暂时理解中……
2、cin/cout比scanf/printf慢很多(我用cin/cout提交357ms),很多数据结构题最好不要用cin/cout。 ——lql_accept & gnoggnoyil -
02009-10-07 13:44:58@
左下角(0,0)
(0,0)...
-
02009-10-07 11:36:37@
一遍AC,爽啊。
-
02009-10-02 18:11:42@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms一次AC 感觉真好! 蛤蛤