Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

呵呵,此题数据太弱。你的蒙分算法如下吧~

Posted by fanhqme at 2008-09-29 17:34:08 on Problem 1021
In Reply To:惊讶:蒙分算法0ms过! Posted by:AllwaysDead at 2008-09-29 17:30:46
#include <cstdio>
#include <string.h>
using namespace std;
int father[10000];
int findfather(int a){return father[a]==-1?a:father[a]=findfather(father[a]);}
void together(int a,int b){if (findfather(a)!=findfather(b))father[findfather(a)]=findfather(b);}
int map1[100][100],map2[100][100],map3[100][100],W,H,colors1[10000][6],colors2[10000][6];
int T2(int a){return a*a;}
int Minn(int a,int b){if (a<b)return T2(b);return T2(a);}
int main(){
    int N,s,i,x,y,j;
    scanf("%d",&N);
    while (N--){
          memset(map1,0,sizeof(map1));memset(map2,0,sizeof(map2));
          scanf("%d %d %d",&W,&H,&s);
          for (i=0;i<s;i++){scanf("%d %d",&x,&y);map1[y][x]=-1;}
          for (i=0;i<s;i++){scanf("%d %d",&x,&y);map2[y][x]=-1;}
          memset(father,0xff,sizeof(father));
          for (x=0;x<H;x++)for (y=0;y<W;y++)if (map1[x][y]){
              if (x>0 && map1[x-1][y])together(x*100+y,(x-1)*100+(y));
              if (y>0 && map1[x][y-1])together(x*100+y,(x)*100+(y-1));
              if (x+1<H && map1[x+1][y])together(x*100+y,(x+1)*100+(y));
              if (y+1<W && map1[x][y+1])together(x*100+y,(x)*100+(y+1));
          }
          memset(colors1,0xff,sizeof(colors1));
          for (x=0;x<H;x++)for (y=0;y<W;y++)if (map1[x][y]){i=map1[x][y]=findfather(x*100+y)+1;i--;
              colors1[i][0]++;
              if (colors1[i][1]==-1 || colors1[i][1]>x)colors1[i][1]=x;
              if (colors1[i][2]==-1 || colors1[i][2]<x)colors1[i][2]=x;
              if (colors1[i][3]==-1 || colors1[i][3]>y)colors1[i][3]=y;
              if (colors1[i][4]==-1 || colors1[i][4]<y)colors1[i][4]=y;
          }
          for (x=0;x<H;x++)for (y=0;y<W;y++)if ((i=map1[x][y]-1)>=0)
              colors1[i][5]+=Minn(x-colors1[i][1],colors1[i][2]-x)+Minn(y-colors1[i][3],colors1[i][4]-y);
          memset(father,0xff,sizeof(father));
          for (x=0;x<H;x++)for (y=0;y<W;y++)if (map2[x][y]){
              if (x>0 && map2[x-1][y])together(x*100+y,(x-1)*100+(y));
              if (y>0 && map2[x][y-1])together(x*100+y,(x)*100+(y-1));
              if (x+1<H && map2[x+1][y])together(x*100+y,(x+1)*100+(y));
              if (y+1<W && map2[x][y+1])together(x*100+y,(x)*100+(y+1));
          }
          memset(colors2,0xff,sizeof(colors2));
          for (x=0;x<H;x++)for (y=0;y<W;y++)if (map2[x][y]){i=map2[x][y]=findfather(x*100+y)+1;i--;
              colors2[i][0]++;
              if (colors2[i][1]==-1 || colors2[i][1]>x)colors2[i][1]=x;
              if (colors2[i][2]==-1 || colors2[i][2]<x)colors2[i][2]=x;
              if (colors2[i][3]==-1 || colors2[i][3]>y)colors2[i][3]=y;
              if (colors2[i][4]==-1 || colors2[i][4]<y)colors2[i][4]=y;
          }
          for (x=0;x<H;x++)for (y=0;y<W;y++)if ((i=map2[x][y]-1)>=0)
              colors2[i][5]+=Minn(x-colors2[i][1],colors2[i][2]-x)+Minn(y-colors2[i][3],colors2[i][4]-y);
          for (x=0;x<10000;x++)if (colors1[x][0]!=-1){
              colors1[x][2]-=colors1[x][1];
              colors1[x][4]-=colors1[x][3];
              if (colors1[x][4]<colors1[x][2]){y=colors1[x][4];colors1[x][4]=colors1[x][2];colors1[x][2]=y;}
          }
          for (x=0;x<10000;x++)if (colors2[x][0]!=-1){
              colors2[x][2]-=colors2[x][1];
              colors2[x][4]-=colors2[x][3];
              if (colors2[x][4]<colors2[x][2]){y=colors2[x][4];colors2[x][4]=colors2[x][2];colors2[x][2]=y;}
          }
          for (j=0;j<10000;j++)if (colors1[j][0]!=-1){
              for (i=0;i<10000 && (!(colors1[j][0]==colors2[i][0] && colors1[j][2]==colors2[i][2] &&
                  colors1[j][4]==colors2[i][4] && colors1[j][5]==colors2[i][5]));i++);
              if (i==10000){puts("NO");break;}
              colors2[i][0]=-1;
          }
          if (j==10000)puts("YES");
    }
    getchar();getchar();getchar();
    return 0;
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator