然后发两道暴力
给定一个三角形数阵，一共 n 行，第 i 行有 i 个数。 此数阵初始全部为 0. 你需要支持以下两个操作： 1.将一个子三角数阵里的数全部加 1。 2.询问一个子三角数阵里的数的和。 我们将以三元组(x,y,a)来描述一个子三角形数阵。 这个数阵中的第一行的元素是(x,y)。 共有 a 行，第 i 行从（x+i-1,y）到（x+i-1，y+i-1）。 注意：(x,y)表示第 x 行的第 y 个数。
输入文件为 delta.in。 第一行，两个整数 N 和 Q，代表三角形的规模和操作数。 以下 Q 行，每行四个整数，第一个数为操作的编号、接下来三个数为子三 角形数阵三元组(xi,yi,ai)。
输出文件为 delta.out。 对于每个 2 类操作，输出一行包含一个整数作为答案。 3 9 2 1 1 2 1 1 1 2 2 1 1 2 1 2 1 2 2 1 1 2 2 2 2 2 1 2 2 2 2 1 1 2 2 1 1 3 【样例输出】 0 3 4 2 5 9
暴力三十分题解，显然我建了一千棵线段树233，不会高级数据结构啊哭泣
#include<cstdio> #include<iostream> #include<cstring> #define MAXN 500000+500 #define MINN 1000+10 #define INF 0x7ffffff struct Tree{ int sum,add,lson,rson; }tree[MAXN*4]; int tail,N,Q; int root[MINN]; void pushup(int rt){ tree[rt].sum=tree[tree[rt].lson].sum+tree[tree[rt].rson].sum; } void pushdown(int rt,int lsum,int rsum){ if(tree[rt].add){ tree[tree[rt].lson].add+=tree[rt].add; tree[tree[rt].rson].add+=tree[rt].add; tree[tree[rt].lson].sum+=lsum*tree[rt].add; tree[tree[rt].rson].sum+=rsum*tree[rt].add; tree[rt].add=0; } } void build(int rt,int l,int r){ tree[rt].lson=++tail; tree[rt].rson=++tail; if(l==r){ tree[rt].sum=tree[rt].add=0; return ; } int m=(l+r)>>1; build(tree[rt].lson,l,m); build(tree[rt].rson,m+1,r); pushup(rt); } void modify(int rt,int l,int r,int L,int R,int delta){ if(L<=l&&R>=r){ tree[rt].sum+=delta*(r-l+1); tree[rt].add+=delta; return; } int m=(l+r)>>1; pushdown(rt,m-l+1,r-m); if(m>=L) modify(tree[rt].lson,l,m,L,R,delta); if(m<R) modify(tree[rt].rson,m+1,r,L,R,delta); pushup(rt); } int query(int rt,int l,int r,int L,int R){ if(L<=l&&R>=r){ return tree[rt].sum; } int m=(l+r)>>1; pushdown(rt,m-l+1,r-m); int ass=0; if(m>=L) ass+=query(tree[rt].lson,l,m,L,R); if(m<R) ass+=query(tree[rt].rson,m+1,r,L,R); return ass; } int main(){ freopen("delta.in","r",stdin); freopen("delta.out","w",stdout); scanf("%d%d",&N,&Q); for(register int i=1;i<=N;i++){ tail++;tree[tail].sum=tree[tail].add=0; }//先给所有根分配节点 for(register int i=1;i<=N;i++){ build(i,1,i);//按照之前分配的节点,i为该树的根,该树的区间为1到i; } for(register int i=1;i<=Q;i++){ int temp,x,y,a; scanf("%d",&temp); if(temp==1){//modify; scanf("%d%d%d",&x,&y,&a); for(register int i=x;i<=x+a-1;i++){ modify(i,1,i,y,y+i-x,1); } }else{ scanf("%d%d%d",&x,&y,&a); int ANS=0; for(register int i=x;i<=x+a-1;i++){ ANS+=query(i,1,i,y,y+i-x); } printf("%d\n",ANS); } } return 0; }下面给上正解
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> using namespace std; const int SZ=1000,N=1005; typedef long long ll; int tag[N][N],x[N],y[N],l[N]; int i,j,n,qnum,t; ll sum[N][N]; int read(){ int x=0;char ch=getchar(); while (!isdigit(ch)) ch=getchar(); while (isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} return x; } void rebuild(){ memset(tag,0,sizeof(tag)); for (;t;t--){ int x0=x[t],y0=y[t],l0=l[t]; int mx=x0+l0; for (i=y0,j=x0;i<y0+l0;i++,j++){ tag[i][j]++;tag[i][mx]--; } } for (i=1;i<=n;i++){ ll now=0,now2=0; for (j=i;j<=n;j++){ now+=(ll)tag[i][j]; now2+=now; sum[i][j]+=now2; } } } int main(){ freopen("delta.in","r",stdin); freopen("delta.out","w",stdout); n=read();qnum=read(); t=0; while (qnum--){ int opt=read(); if (opt==1){ t++; x[t]=read();y[t]=read();l[t]=read(); if (t==SZ) rebuild(); }else{ int x0=read(),y0=read(),l0=read(); int mx=x0+l0-1; ll ans=0; for (i=y0,j=x0-1;i<y0+l0;i++,j++) ans+=sum[i][mx]-sum[i][j]; for (i=1;i<=t;i++){ int xx=min(x0+l0-1,x[i]+l[i]-1),yy=max(y0,y[i]),l1=max(x0-y0,x[i]-y[i]); if (x0>xx||x[i]>xx) continue; if (y0+l0-1<yy||y[i]+l[i]-1<yy) continue; if (x0+l0-1-y0<l1||x[i]+l[i]-1-y[i]<l1) continue; int len=xx-yy-l1+1; ans+=(ll)len*(len+1)/2; } printf("%lld\n",ans); } } return 0; }好不容易在markdown上面调整了一下标程的代码风格，竟然括号要换行？太丑了
给出数字 N（1<=N<=10000）、X（1<=X<=1000）、Y（1<=Y<=1000）代表 有 N 个敌人分布在一个 X 行 Y 列的矩阵上，矩形的行号从 0 到 X-1、列号从 0 到 Y-1。再给出四个数字 x1,y1,x2,y2 分别代表你要从起点(x1,y1)移动到目标点 (x2,y2)。在移动的过程中你当然希望离敌人的距离的最小值最大化，现在请求出 这个值最大可以为多少？以及在这个前提下，你最少要走多少步才可以到目标 点。 注意这里距离的定义为两点的曼哈顿距离，即某两个点的坐标分为(a,b),(c,d), 那么它们的距离为|a-c|+|b-d|。
第一行 3 个整数为 N，X，Y 第二行 4 个整数为 x1,y1,x2,y2 下面将有 N 行，为 N 个敌人所在的坐标。
在一行内输出你离敌人的距离及在这个距离的限制下，你到目标点最少要移 动多少步。
2 5 6 0 0 4 0 2 1 2 3
2 14
暴力思想，每次扩大敌人的影响力（把敌人方圆多少的地方染黑，走的时候判断），每次spfa或者a star 或者直接bfs加vis数组爆搜一次，直到走不通为止 正解的思想比我多了个二分，我只过了40分
暴力：
#include<cstdio> #include<iostream> #include<cstring> #include<queue> #define MAXN 1000+10 using namespace std; int N,X,Y,x1,y1,x2,y2,x,y; int mov[5][2]={0,0,0,1,0,-1,1,0,-1,0}; queue<int>qx,qy; bool vis[MAXN][MAXN],G[MAXN][MAXN]; int bfs(){ vis[x1][y1]=true; queue<int>qxx,qyy,qlen; qxx.push(x1);qyy.push(y1);qlen.push(0); do{ int xx=qxx.front();qxx.pop(); int yy=qyy.front();qyy.pop(); int len=qlen.front();qlen.pop(); for(int i=1;i<=4;i++){ int xxx=xx+mov[i][0]; int yyy=yy+mov[i][1]; if(xxx==x2&&yyy==y2) return len+1; if(xxx>=0&&xxx<X&&yyy>=0&&yyy<Y&&(!vis[xxx][yyy])&&(!G[xxx][yyy])){ qxx.push(xxx); qyy.push(yyy); vis[xxx][yyy]=true; qlen.push(len+1); } } if(qxx.empty())break; }while(true); return 0; } void build(){ memset(vis,false,sizeof(vis)); int size=qx.size(); for(int i=1;i<=size;i++){ int xx=qx.front();qx.pop(); int yy=qy.front();qy.pop(); for(int i=1;i<=4;i++){ int xxx=xx+mov[i][0]; int yyy=yy+mov[i][1]; if(xxx>=0&&xxx<X&&yyy>=0&&yyy<Y&&(!G[xxx][yyy])){ G[xxx][yyy]=true; qx.push(xxx); qy.push(yyy); } } } } int main(){ freopen("escape.txt","r",stdin); //freopen("escape.out","w",stdout); scanf("%d%d%d",&N,&X,&Y); scanf("%d%d%d%d",&x1,&y1,&x2,&y2); for(register int i=1;i<=N;i++){ scanf("%d%d",&x,&y); G[x][y]=true; qx.push(x); qy.push(y); } int prelen=0,cnt=0; while(true){ int len=bfs(); if(len==0) break; prelen=len; cnt++; build(); } printf("%d %d\n",cnt,prelen); }正解：
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> using namespace std; bool mark[1010][1010]; int map[1010][1010]; int x[5000010],y[5000010]; int bs[1010][1010]; int n,m,k,tou,wei,qx,qy,zx,zy; int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; void init() { int i,a,b; scanf("%d%d%d",&k,&n,&m); tou=1;wei=0; scanf("%d%d%d%d",&qx,&qy,&zx,&zy); qx++;qy++;zx++;zy++; for(i=1;i<=k;i++) { scanf("%d%d",&a,&b); a++;b++; wei++;x[wei]=a;y[wei]=b; mark[a][b]=1; } } void bfs() { int i,nx,ny,xx,yy,p; while(tou<=wei) { xx=x[tou];yy=y[tou];tou++; for(p=0;p<4;p++) { nx=xx+dx[p];ny=yy+dy[p]; if(nx<1 || nx>n || ny<1 || ny>m) continue; if(!mark[nx][ny]) { mark[nx][ny]=1;map[nx][ny]=map[xx][yy]+1; wei++;x[wei]=nx;y[wei]=ny; } } } } bool check(int mid) { int i,xx,yy,nx,ny,p; tou=1;wei=1;x[1]=qx;y[1]=qy; memset(mark,0,sizeof(mark)); memset(bs,127,sizeof(bs)); mark[qx][qy]=1;bs[qx][qy]=0; while(tou<=wei) { xx=x[tou];yy=y[tou];tou++; for(p=0;p<4;p++) { nx=xx+dx[p];ny=yy+dy[p]; if(nx<1 || nx>n || ny<1 || ny>m || map[nx][ny]<mid) continue; if(!mark[nx][ny]) { mark[nx][ny]=1;bs[nx][ny]=bs[xx][yy]+1; wei++;x[wei]=nx;y[wei]=ny; } } } if(mark[zx][zy]) return 1; else return 0; } int main() { freopen("escape.in","r",stdin); freopen("escape.out","w",stdout); init(); bfs(); int l=0,r=map[qx][qy],mid; while(l+1<r) { mid=(l+r)>>1; if(check(mid)) l=mid; else r=mid; } if(check(r)) {cout<<r<<" "<<bs[zx][zy]<<endl;} else {check(l);cout<<l<<" "<<bs[zx][zy]<<endl;} // system("pause"); return 0; }