博客传不上去，只能写这里了

$T1$ 激光炸弹

思路：先用前缀和，然后直接暴力即可（数据水）。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=5e3+5;
int a[N][N];
int main(){
	int n,r;
	cin >> n >> r;
	if(r>5001) r=5001;//题目中的下标从 0 开 始，所以最大坐标为 5001 
	for(int i=1;i<=n;i++){
		int x,y,w;
		cin >> x >> y >> w;
		a[++x][++y]+=w;
	}
	int mxx=5001;
	for(int i=1;i<=mxx;i++){
		for(int j=1;j<=mxx;j++){
			a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
		}
	}
	int mx=0;
	for(int i=r;i<=mxx;i++){
		for(int j=r;j<=mxx;j++){
			mx=max(mx,a[i][j]-a[i-r][j]-a[i][j-r]+a[i-r][j-r]);
		}
	}
	cout << mx;
}

$T2$ 增减序列

思路：差分题变型（带有亿丢丢的数学）

看完应该都知道要用差分吧。

首先，我们要明白，当数组数字一样时，差分数组是怎样的，应该是除了第一个数，其余的数都为0。于是，我们的题目就变成了：给定n个数，每次选两个数一加一减，最后让除了第一个数以外，其他数都变为0。

那我们怎么做呢？首先，我们额外创造一个b[n+1]，模拟从i加到n的情况。（加下来思路忽略b[1]）首先，如果有一正一负，那么肯定要正加负减，最后肯定只剩下min(z,f)个数字(z表示正数和，f表示负数和的绝对值)，他们再单独与b[1]或b[n+1]加减，就产生了abs(p-q)+1种可能(从全与b[n+1]匹配到全与b[1]匹配)，总共需要min(p,q)+abs(p-q)=max(p,q)次，有abs(p-q)+1种可能。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+50;
int a[N],b[N];
signed main(){
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        b[i]=a[i]-a[i-1];
    }
    int z=0,f=0;
    for(int i=2;i<=n;i++){
        if(b[i]<0) f-=b[i];
        else z+=b[i];
    }
    cout << max(z,f) << endl << abs(z-f)+1;
}

$T3$ 最高的牛

思路：一开始所有牛身高都为h，每给一条信息就将A,B中间牛身高都减一即可（用差分）。注意去重

代码：

#include<bits/stdc++.h>
using namespace std;
map<pair<int,int>,bool> mp;
const int N=1e4+50;
int q[N],q2[N];
int main()
{
    int n,p,h,m;
    cin >> n >> p >> h >> m;
    for(int i=1;i<=m;i++){
        int a,b;
        cin >> a >> b;
        if(a>b) swap(a,b);
        if(mp[make_pair(a,b)]) continue;
        q2[a+1]--;
        q2[b]++;
        mp[make_pair(a,b)]=1;
    }
    for(int i=1;i<=n;i++)
    {
        q[i]=q[i-1]+q2[i];
        cout << h+q[i] << endl;
    }
    return 0;
}