35 条题解

  • 2
    @ 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
    @ 2017-11-06 17:13:44

    状态 耗时 内存占用

    #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 KiB

    c++ 暴力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
    @ 2016-11-06 10:21:10

    一定要记得边界是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
    @ 2017-11-11 20:22:32

    直接枚举每个点,搜索总数就行
    取到一样的就使个数+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
    @ 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
    @ 2017-10-13 16:28:15

    简单的模拟ヾ(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
    @ 2017-07-16 15:11:18

    枚举
    #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
    @ 2017-04-05 23:27:22

    #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
    @ 2016-11-19 19:01:30
    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
    @ 2016-11-18 13:15:48

    #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
    @ 2016-11-17 18:12:46

    写这种题 总是 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
    @ 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
    @ 2016-11-10 14:27:00

    顶楼下。。。

  • 0
    @ 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
    @ 2016-08-31 19:53:40

    有必要那么水吗?
    #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
    @ 2016-08-24 14:52:19

    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
    @ 2016-08-24 14:51:36

    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
    @ 2016-08-23 15:21:36

    本蒟蒻以O(n×d^2)**强势鄙视**O(d^2×128^2)!
    c++
    #include <iostream>
    using namespace std;
    int g[129][129],d,n,ans1=0,ans2=0;
    int main()
    {
    ios::sync_with_stdio(0);
    cin>>d>>n;
    for(int i=1;i<=n;i++)
    {
    int x,y,k;
    cin>>x>>y>>k;
    for(int j=x-d;j<=x+d;j++)
    for(int j2=y-d;j2<=y+d;j2++)
    if(0<=j&&j<=128&&0<=j2&&j2<=128)
    {
    g[j][j2]+=k;
    if(g[j][j2]>ans2)ans1=1,ans2=g[j][j2];
    else
    if(g[j][j2]==ans2)ans1++;
    }
    }
    cout<<ans1<<" "<<ans2;
    return 0;
    }

  • 0
    @ 2016-07-12 15:36:24

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    using namespace std;
    int map[200][200];
    int main(){
    int x,y,k,d,n;
    int a=1,b=0;
    int u,v;
    cin>>d>>n;
    for(int i=1;i<=n;i++){
    cin>>x>>y>>k;
    map[x][y]=k;
    }
    int c=0;
    for(int i=0;i<=128;i++){
    for(int j=0;j<=128;j++){
    for(u=i-d;u<=i+d;u++){
    for(v=j-d;v<=j+d;v++){
    if(u>=0 && u<=128 && v>=0 && v<=128)
    c=map[u][v];
    }
    if(b<c){
    a=1;
    b=c;}
    else
    if(b=c)
    a++;
    }

    }

    }
    printf("%d %d",a,b);
    return 0;
    }

  • 0
    @ 2016-02-13 22:15:32

    水啊,直接暴搜,一次AC了
    Pascal AC
    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;
    write(f,' ',s);
    end.

信息

ID
1908
难度
5
分类
模拟 点击显示
标签
递交数
3162
已通过
1160
通过率
37%
上传者