酷暑一夏1

不忘初心，方得始终

• 于  Vijos  阅读 

Vijos 1512 SuperBrother打鼹鼠 题解

题目

在这个“打鼹鼠”的游戏中，鼹鼠会不时地从洞中钻出来，不过不会从洞口钻进去（鼹鼠真胆大……）。洞口都在一个大小为n(n<=1024)的正方形中。这个正方形在一个平面直角坐标系中，左下角为(0,0)，右上角为(n-1,n-1)。洞口所在的位置都是整点，就是横纵坐标都为整数的点。而SuperBrother也不时地会想知道某一个范围的鼹鼠总数。这就是你的任务。

题解

二维树状数组，注意坐标值不能为0。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cstdio>
const int MAXN=1024+5;
int mat[MAXN][MAXN],n,m,x,y,d,d1;
int lowbit(int x){return x&(-x);}
void Add(int x,int y,int d)
{
	for(int i=y;i<=n;i+=lowbit(i))
		for(int j=x;j<=n;j+=lowbit(j))
			mat[i][j]+=d;
}
int Query(int x,int y)
{
	int ans=0;
	for(int i=y;i>0;i-=lowbit(i))
		for(int j=x;j>0;j-=lowbit(j))
			ans+=mat[i][j];
	return ans;
}
int main()
{
	scanf("%d",&n);
//	n++;
	while(1)
	{
		scanf("%d",&m);
		if(m==3) break;
		if(m==1)
		{
			scanf("%d %d %d",&x,&y,&d);
			x++;y++;
			Add(x,y,d);
		}
		if(m==2)
		{
			scanf("%d %d %d %d",&x,&y,&d,&d1);
			x++;y++;d++;d1++;
			printf("%d\n",Query(d,d1)+Query(x-1,y-1)-Query(x-1,d1)-Query(d,y-1));
		}
	}
	return 0;
}
最近的文章

CodeVS1160 蛇形矩阵 题解

题目小明玩一个数字游戏，取个n行n列数字矩阵（其中n为不超过100的奇数），数字的填补方法为：在矩阵中心从1开始以逆时针方向绕行，逐圈扩大，直到n行n列填满数字，请输出该n行n列正方形矩阵以及其的对角线数字之和. 题解蛇形矩阵生成见GIF，从$(n,n)$开始每一圈按照左-&gt;上-&gt;右-& …

• 于  CodeVS 继续阅读
更早的文章

Vijos1474 雷曼兔(csapc) 题解

题目这次，OI山成为了雷曼兔那无尽的冒险传说的新舞台！传说OI山中埋藏着巨大的宝藏，伴随着这个传说的是一个迷题：最瑰丽的舞者将达至精灵世界的彼岸……经过仔细推敲，雷曼兔发现这是一个提示宝藏埋藏位置的谜语，在该谜语中指出了一个特定的路径，只有经过了该路径宝藏才会出现，具体情况如下：OI山的地势图可以看 …

• 于  Vijos, csapc 继续阅读