39 条题解
-
2
old_driver_muruan LV 8 @ 2017-11-04 10:16:56
//二维前缀和 坐标整体加1便于取边界 #include<bits/stdc++.h> #define max_n 200 using namespace std; int d,n,x,y,z,maps[max_n][max_n],tot[max_n][max_n],ans,pcs,tmp; int main() { scanf("%d%d",&d,&n); for(register int i=1;i<=n;i++) scanf("%d%d%d",&x,&y,&z),maps[x+1][y+1]=z; for(register int i=1;i<=129;i++) for(register int j=1;j<=129;j++) tot[i][j]+=maps[i][j]+tot[max(0,i-1)][j]+tot[i][max(0,j-1)]-tot[max(0,i-1)][max(0,j-1)]; for(register int i=1;i<=129;i++) for(register int j=1;j<=129;j++) { tmp=tot[min(i+d,129)][min(j+d,129)]-tot[min(i+d,129)][max(0,j-d-1)]-tot[max(0,i-d-1)][min(j+d,129)]+tot[max(0,i-d-1)][max(0,j-d-1)]; if(ans==tmp) pcs++; else if(ans<tmp) pcs=1,ans=tmp; } printf("%d %d",pcs,ans); }//Muruan -
1
aph。 (chenqianrong) LV 10 @ 2021-09-04 15:17:41
#include <bits/stdc++.h> using namespace std; int x,y,d,n,maxm,num,sum=1,cross[170][170]; int main() { cin>>d>>n; for(int i=1; i<=n; i++){ cin>>x>>y; cin>>cross[x+20][y+20]; } for(int i=20; i<=148; i++){ for(int j=20; j<=148; j++){ for(int m=i-d; m<=i+d; m++) for(int k=j-d;k<=j+d;k++) num+=cross[m][k]; if(maxm==num) sum++; else if(maxm<num) sum=1; maxm=max(maxm,num); num=0; } } cout<<sum<<" "<<maxm; return 0; } -
1
孙鹤鸣 (sunheming) LV 10 @ 2020-04-02 16:55:46
一道比较简单的模拟，唯一的难点是对于边界情况的处理
这里本蒟蒻为了避（bú）免（huì）麻（chú）烦（lǐ）的边界情况，在输入时把WIFI的坐标都加了20
所以数组要多开两个20（上下左右分别多20），多开一个20只能A两个点
下面放AC代码
（自认为代码很短）
#include<iostream> using namespace std; int x,y,d,n,maxm,num,sum=1,cross[170][170]; //多开2个20以免越界 int main() { cin>>d>>n; for(int i=1;i<=n;i++) { cin>>x>>y; cin>>cross[x+20][y+20]; } for(int i=20;i<=148;i++) for(int j=20;j<=148;j++) { for(int m=i-d;m<=i+d;m++) for(int k=j-d;k<=j+d;k++) //四重循环。外重两个遍历交叉口的点，内层两个遍历每个点周围d范围内的公共场所数 num+=cross[m][k]; if(maxm==num) //和最大值比较。如果相等则次数+1，如果比最大值小则将次数变为1重计； sum++; else if(maxm<num) sum=1; maxm=max(maxm,num); num=0; } cout<<sum<<" "<<maxm; return 0; } //-萌新瑟瑟发抖=-=-
#1 Accepted 1ms 256.0 KiB
#2 Accepted 1ms 256.0 KiB
#3 Accepted 2ms 256.0 KiB
#4 Accepted 2ms 256.0 KiB
#5 Accepted 3ms 256.0 KiB
#6 Accepted 15ms 376.0 KiB
#7 Accepted 5ms 256.0 KiB
#8 Accepted 4ms 376.0 KiB
#9 Accepted 6ms 360.0 KiB
#10 Accepted 5ms 380.0 KiB
-
1
状态 耗时 内存占用
#1 Accepted 5ms 336.0 KiB
#2 Accepted 5ms 384.0 KiB
#3 Accepted 5ms 256.0 KiB
#4 Accepted 5ms 384.0 KiB
#5 Accepted 6ms 380.0 KiB
#6 Accepted 7ms 384.0 KiB
#7 Accepted 8ms 268.0 KiB
#8 Accepted 7ms 268.0 KiB
#9 Accepted 7ms 372.0 KiB
#10 Accepted 6ms 340.0 KiBc++ 暴力bfs做法
每个点搜索一遍
搜索在2d空间内，能覆盖的公共场所个数（公共场所用结构体存储）
代码如下 （队列）#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <cmath> using namespace std; bool map[129][129]={true}; int a,b,i,j,n,d,nmax=0,ans=0; int dx,dy,tempn; struct DATA{ int x,y,num; } pub[21]; int dir[8][2]={1,0,-1,0,0,1,0,-1,1,1,1,-1,-1,1,-1,-1}; queue <DATA> que; bool check(int x,int y){//合法性判定 if (x < 0 || y < 0 || y > 128 || x >128) return false; if (map[x][y] == 1) return false; return true; } int find(int x,int y){//查找范围内的公共场所 int anum=0; for(i=1;i<=n;i++){ dx=abs(pub[i].x-x); dy=abs(pub[i].y-y); if((dx<=d)&&(dy<=d)){ anum+=pub[i].num; } } return anum; } int main(){ cin>>d; cin>>n; for(i=1;i<=n;i++){ scanf("%d%d%d",&pub[i].y,&pub[i].x,&pub[i].num); } DATA start; DATA next,temp; start.x=0; start.y=0; map[0][0]=1; que.push(start); // 标准广搜模版 while(!que.empty()){ temp=que.front(); tempn=find(temp.x,temp.y); if(tempn==nmax) ans++; if(tempn>nmax){ nmax=tempn; ans=1; } que.pop(); for(i=0;i<=7;i++){ next.x=temp.x+dir[i][0]; next.y=temp.y+dir[i][1]; if(check(next.x,next.y)==true){ que.push(next); map[next.x][next.y]=1; } } } cout<<ans<<" "<<nmax; return 0; } -
1
一定要记得边界是0~128！！！！！！！因为这个WA了若干。。。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>using namespace std;
int d,n,x,y,k,max_=-0x3f3f3f3f,ans;
int m[200][200];int main(){
scanf("%d%d",&d,&n);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&x,&y,&k);
m[y][x]=k;
}
for(int i=0;i<=128;i++){
for(int j=0;j<=128;j++){
int tot=0;
for(int a=max(i-d,0);a<=min(i+d,130);a++){
for(int b=max(j-d,0);b<=min(j+d,130);b++){
tot+=m[a][b];
}
}
if(max_<tot){
max_=tot;
ans=1;
}else if(max_==tot)ans++;
}
}
printf("%d %d\n",ans,max_);
} -
0
/* 用一个二维数组，就是简单填表过程 */ #include <iostream> //[2014提高组Day2-A]无线网络发射器选址 #include <algorithm> using namespace std; int B[130][130] = {0}; void AddB(int x, int y, int k, int d) { int x1, y1, x2, y2; x1 = max(x - d, 0); y1 = max(y - d, 0); x2 = min(x + d, 128); y2 = min(y + d, 128); for (int i = x1; i <= x2; i++) for (int j = y1; j <= y2; j++) B[i][j] += k; } int main() { int d, n, x, y, k; int p = 0, q = 0; cin >> d >> n; for (int i = 0; i < n; i++) { cin >> x >> y >> k; AddB(x, y, k, d); } for (int i = 0; i <= 128; i++) { for (int j = 0; j <= 128; j++) if(q < B[i][j]) { q = B[i][j]; p = 1; } else if(q == B[i][j]) p++; } cout << p << " " << q << endl; system("pause"); return 0; } -
0
直接枚举每个点,搜索总数就行
取到一样的就使个数+1,更大的就将个数重置为1#include<stdio.h> #include<string.h> int k[129][129],d,n,num=0,ans=0; int take(int x1,int y1,int x2,int y2){//求从(x1,y1)到(x2,y2)的矩形的公共场所个数(带边界处理) int i,j,s=0; if(x1<0)x1=0; if(y1<0)y1=0; if(x2>128)x2=128; if(y2>128)y2=128; for(i=x1;i<=x2;i++) for(j=y1;j<=y2;j++){ s+=k[i][j]; } return s; } int main(){ memset(k,0,sizeof(d)); scanf("%d",&d); scanf("%d",&n); int i,j,a,b,c; for(i=1;i<=n;i++){ scanf("%d %d %d",&a,&b,&c); k[a][b]=c; } for (i=0;i<=128;i++)//枚举每个点求值 for(j=0;j<=128;j++){ a=take(i-d,j-d,i+d,j+d); if(ans<a){ ans=a;num=1; }else if(ans==a){ num++; } } printf("%d %d",num,ans); return 0; } -
0
2351599120 LV 9 @ 2017-10-27 17:19:42
前缀和优化
O(n^2)
20ms
另外注意边界#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <cctype> #include <vector> #include <queue> using namespace std; int a[180][180]; int main() { int d,n,x,y,z,ans=0,s=0; scanf("%d%d",&d,&n); for(int i=1;i<=n;i++) { scanf("%d%d%d",&x,&y,&z); a[y+20][x+20]=z; } for(int i=0;i<170;i++) { for(int j=1;j<170;j++) { a[i][j]+=a[i][j-1]; } } for(int i=0;i<170;i++) { for(int j=1;j<170;j++) { a[j][i]+=a[j-1][i]; } } for(int i=0;i<129;i++) { for(int j=0;j<129;j++) { if(a[i+20+d][j+20+d]-a[i+d+20][j-d+19]-a[i-d+19][j+d+20]+a[i-d+19][j-d+19]==ans) { s++; } if(a[i+20+d][j+20+d]-a[i+d+20][j-d+19]-a[i-d+19][j+d+20]+a[i-d+19][j-d+19]>ans) { ans=a[i+20+d][j+20+d]-a[i+d+20][j-d+19]-a[i-d+19][j+d+20]+a[i-d+19][j-d+19]; s=1; } } } printf("%d %d",s,ans); return 0; } -
0
简单的模拟ヾ(o◕∀◕)ﾉ
#include<iostream> #include<cmath> #include<cstring> using namespace std; int f[130][130]; int d,n,x,y,k,zj,yj,sj,xj,pg,ans,num; int main() { memset(f,0,sizeof(f)); cin>>d>>n; for(int i=1;i<=n;++i) { cin>>x>>y>>k; f[x][y]=k; } for(int i=0;i<=128;++i) { for(int j=0;j<=128;++j) { zj=max(0,j-d); yj=min(128,j+d); sj=min(128,i+d); xj=max(0,i-d); pg=0; for(int r=zj;r<=yj;++r) { for(int t=xj;t<=sj;++t) { if(f[r][t]!=0) pg+=f[r][t]; } } if(pg>ans) ans=pg; } } for(int i=0;i<=128;++i) { for(int j=0;j<=128;++j) { zj=max(0,j-d); yj=min(128,j+d); sj=min(128,i+d); xj=max(0,i-d); pg=0; for(int r=zj;r<=yj;++r) { for(int t=xj;t<=sj;++t) { if(f[r][t]!=0) pg+=f[r][t]; } } if(pg==ans) num++; } } cout<<num<<" "<<ans<<endl; return 0; } -
0
枚举
#include<iostream>
#include<climits>
#include<cstdio>
#include<cstring>
using namespace std;
inline const void read(int &x)//快速读入
{
x=0;
char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
}
int d,n,place[130][130],cover[130][130],ans=0,ans_num=0;
int main()
{
memset(place,0,sizeof(place));
memset(cover,0,sizeof(cover));
read(d);read(n);
for(int i=1;i<=n;i++)
{
int x,y;
read(x);read(y);read(place[x][y]);
for(int i=-min(x,d);i<=min(d,128-x);i++)
for(int j=-min(y,d);j<=min(d,128-y);j++)
{
cover[x+i][y+j]+=place[x][y];
ans=max(ans,cover[x+i][y+j]);
}
}
for(int i=0;i<=128;i++)
for(int j=0;j<=128;j++)if(cover[i][j]==ans)ans_num++;
printf("%d %d",ans_num,ans);
return 0;
} -
0
#include<cstdio>
using namespace std;const int MAXSIZE=130;
int f[MAXSIZE][MAXSIZE],n,m;void init()
{
int i,x,y,k;
scanf("%d",&m);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d%d",&x,&y,&k);
f[x][y]=k;
}
}int jisuansum(int i,int j)
{
int ii,jj,sum=0;
for(ii=i-m;ii<=i+m&&ii<=128;ii++)
for(jj=j-m;jj<=j+m&&jj<=128;jj++)
{
if(ii<0) ii=0;
if(jj<0) jj=0;
sum+=f[ii][jj];
}
return sum;
}void work()
{
int i,j,sum=0,max=0,ans=0;
for(i=0;i<=128;i++)
for(j=0;j<=128;j++)
{
sum=jisuansum(i,j);
if(sum==ans) max++;
if(sum>ans)
{
ans=sum;
max=1;
}
}
printf("%d %d\n",max,ans);
}int main()
{
init();
work();
return 0;
} -
0
program wireless; uses math; var d, n, x, y, k, i, j, ans, count, temp: longint; w: array [0..128, 0..128] of longint; begin // assign(input, 'wireless.in'); assign(output, 'wireless.out'); // reset(input); rewrite(output); read(d, n); fillchar(w, sizeof(w), 0); for i := 1 to n do begin read(x, y, k); w[x, y] := k; end; ans := 0; count := 0; for i := 0 to 128 do for j := 0 to 128 do begin temp := 0; for x := max((i - d), 0) to min((i + d), 128) do for y := max((j - d), 0) to min((j + d), 128) do inc(temp, w[x, y]); if temp > ans then begin count := 1; ans := temp; continue; end; if temp = ans then inc(count); end; write(count, ' ', ans); // close(input); close(output); end. -
0
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;int map[200][200];
int main()
{
freopen("in", "r", stdin);
int d, n, ans2 = 0, ans = 0;
scanf("%d%d", &d, &n);
for(int i = 1; i <= n; i++){
int x, y, k;
scanf("%d%d%d", &x, &y, &k);
map[x][y] = k;
}
for(int i = 0; i <= 128; i++)
for(int j = 0; j <= 128; j++){
int res = 0;
for(int x = max(0, i-d); x <= min(128, i+d); x++)
for(int y = max(0, j-d); y <= min(128, j+d); y++)
res += map[x][y];
if(res > ans){
ans = res;
ans2 = 1;
}
else if(res == ans)
ans2++;
}
printf("%d %d", ans2, ans);
return 0;
} -
0
写这种题 总是 i j 写错 调半天才调出来
#include <cstdio>
#include <queue>
#include <algorithm>
#define isok(i,j) (0<=i&&i<=128&&0<=j&&j<=128)
using std::max;
using std::min;int main(){
freopen("in.txt","r",stdin);
int d,n,x,y,k,map[129][129]={0};
scanf("%d%d",&d,&n);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&x,&y,&k);
map[x][y]=k;
}
int way=0,ans=0,sum;
for(int i=0;i<129;i++)
for(int j=0;j<129;j++){
sum=0;
for(int p=-d;p<=d;p++)
for(int q=-d;q<=d;q++)
if(isok(i+p,j+q))
sum+=map[i+p][j+q];
if(sum==ans)
way++;
if(sum>ans)
ans=sum,way=1;
}
printf("%d %d",way,ans);
return 0;
} -
0
lyx2001719 LV 8 @ 2016-11-14 21:12:28
#include <iostream> #include <cstring> #include <algorithm> using namespace std; int map[129][129]; int sum,tot; int main() { memset(map,0,sizeof(map)); int d,n,i,j,a,b,k,w,y,smax=129,smay=129,bigx=0,bigy=0; cin>>d>>n; for(i=0;i<n;i++) { cin>>a>>b>>k; map[b][a]=k; } for(i=0;i<129;i++) for(j=0;j<129;j++) { int res=0; for(w=max(i-d,0);w<=min(i+d,128);w++) for(y=max(j-d,0);y<=min(j+d,128);y++) res+=map[w][y]; if(res>sum) { sum=res; tot=0; }if(res==sum) tot++; } cout<<tot<<" "<<sum<<endl; return 0; } -
0
explodingnerk LV 8 @ 2016-10-06 19:56:52
O(128*128)
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define clr(x,c) memset(x,c,sizeof(x))
int read(){
int x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
return x;
}
const int nmax=150;
const int inf=0x7f7f7f7f;
int sm[nmax][nmax];
int main(){
int d=read(),n=read(),u,v;
rep(i,1,n) u=read()+1,v=read()+1,sm[u][v]=read();
rep(i,1,129) rep(j,1,129) sm[i][j]+=sm[i-1][j]-sm[i-1][j-1]+sm[i][j-1];
int ta,tb,tx,ty,tmp,ans=0,cnt=0;
rep(i,1,129){
rep(j,1,129){
ta=max(i-d,1)-1;tb=max(j-d,1)-1;
tx=min(i+d,129);ty=min(j+d,129);
tmp=sm[tx][ty]-sm[ta][ty]+sm[ta][tb]-sm[tx][tb];
if(tmp==ans) ++cnt;
else if(tmp>ans) ans=tmp,cnt=1;
}
}
printf("%d %d\n",cnt,ans);
return 0;
}
-
0
有必要那么水吗？
#include <iostream>
#include <cstring>using namespace std;
int d,n,x,y,k,graph[1000][1000];
int maxnum=0,maxt=0;int main()
{
memset(graph,0,sizeof(graph));
cin >> d;
cin >> n;
for (int i=1;i<=n;i++)
{
cin >> x >> y >> k;
graph[x][y]+=k;
}
for (int i=0;i<=128;i++)
for (int j=0;j<=128;j++)
{
int here=0;
for (int k=i-d;k<=i+d;k++)
for (int l=j-d;l<=j+d;l++)
if (k>=0 && l>=0)
here+=graph[k][l];
if (here==maxnum)
maxt++;
else if (here>maxnum)
{
maxt=1;
maxnum=here;
}
}
cout << maxt << " " << maxnum << endl;
return 0;
} -
0
pascal 极水无比！！！
pascal
var
d,n,i,j,t,s,x,y,k,p,q,f:longint;
a:array[-100..200,-100..200]of longint;
begin
readln(d);
readln(n);
for i:=1 to n do
begin
readln(x,y,k);
a[x,y]:=k;
end;
x:=0;
y:=0;
s:=0;
for i:=0 to 128 do
for j:=0 to 128 do
begin
x:=i-d;
y:=j-d;
t:=0;
for p:=x to x+2*d do
for q:=y to y+2*d do if a[p,q]>0 then t:=t+a[p,q];
if t>s
then
begin
s:=t;
f:=0;
end;
if t=s then inc(f);
end;
writeln(f,' ',s);
readln;
end.
-
0
pascal 极水无比！！！
var
d,n,i,j,t,s,x,y,k,p,q,f:longint;
a:array[-100..200,-100..200]of longint;
begin
readln(d);
readln(n);
for i:=1 to n do
begin
readln(x,y,k);
a[x,y]:=k;
end;
x:=0;
y:=0;
s:=0;
for i:=0 to 128 do
for j:=0 to 128 do
begin
x:=i-d;
y:=j-d;
t:=0;
for p:=x to x+2*d do
for q:=y to y+2*d do if a[p,q]>0 then t:=t+a[p,q];
if t>s
then
begin
s:=t;
f:=0;
end;
if t=s then inc(f);
end;
writeln(f,' ',s);
readln;
end.
old_driver_muruan
LV 8
@ 2017-11-04 10:16:56
