Chinaunix首页 | 论坛 | 博客

熟睡的企鹅finekill.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

zhln

  • 博客访问： 1562244
  • 博文数量： 327
  • 博客积分： 10000
  • 博客等级： 上将
  • 技术积分： 3556
  • 用 户 组： 普通用户
  • 注册时间： 2005-04-05 21:28
个人简介

东黑布衣，流浪幽燕。 真诚善良，值得信赖。

文章分类

全部博文（327）

我的朋友
推荐博文
相关博文
[20180310 PRO] Map Completion V2

分类： BSD

2018-03-27 15:03:37

用hash摘要zone，貌似能加速有点，但是也不是十分确定。

  1. #include "stdafx.h"

  3. #define MAX_MAP_SIZE 64
  4. #define ZONE_SIZE 4
  5. #define HASH_SZ 32

  7. char zone[ZONE_SIZE][ZONE_SIZE];
  8. int hisindex=0;
  9. unsigned short hiszmap[10000][2][2];

  11. unsigned short guess_hash[HASH_SZ][HASH_SZ];

  13. extern void randomscan(char zone[ZONE_SIZE][ZONE_SIZE]);

  15. unsigned short guess_to_hash(char gss[64][64],int x,int y)
  16. {
  17.      //Use bit operation and 16 as base
  18.    return gss[x][y] | gss[x][y+1]<<4 | gss[x+1][y]<<8 | gss[x+1][y+1]<<12;
  19. #if 0//Use 15 as base
  20.    return gss[x][y]+gss[x][y+1]*15+gss[x+1][y]*225+gss[x+1][y+1]*3375;
  21. #endif
  22. }

  24. void zone_to_hash(char zone[4][4], unsigned short zmap[2][2])
  25. {
  26.    //Use bit operation and 16 as base
  27.    zmap[0][0]=zone[0][0] | zone[0][1]<<4 | zone[1][0]<<8 | zone[1][1]<<12;
  28.    zmap[0][1]=zone[0][2] | zone[0][3]<<4 | zone[1][2]<<8 | zone[1][3]<<12;
  29.    zmap[1][0]=zone[2][0] | zone[2][1]<<4 | zone[3][0]<<8 | zone[3][1]<<12;
  30.    zmap[1][1]=zone[2][2] | zone[2][3]<<4 | zone[3][2]<<8 | zone[3][3]<<12;

  32. #if 0 //Use 15 as base
  33.    zmap[0][0]=zone[0][0]+zone[0][1]*15+zone[1][0]*225+zone[1][1]*3375;
  34.    zmap[0][1]=zone[0][2]+zone[0][3]*15+zone[1][2]*225+zone[1][3]*3375;
  35.    zmap[1][0]=zone[2][0]+zone[2][1]*15+zone[3][0]*225+zone[3][1]*3375;
  36.    zmap[1][1]=zone[2][2]+zone[2][3]*15+zone[3][2]*225+zone[3][3]*3375;
  37. #endif
  38. }

  40. void save_guess_info(int N,char gss[64][64])
  41. {
  42.    int k;
  43.    for(k=0;k<=N-2;k+=2){
  44.       guess_hash[k/2][0] = guess_to_hash(gss,k,0);//第0列
  45.       guess_hash[0][k/2] = guess_to_hash(gss,0,k);//第0行
  46.       guess_hash[k/2][(N-2)/2] = guess_to_hash(gss,k,N-2);//第N-2列
  47.       guess_hash[(N-2)/2][k/2] = guess_to_hash(gss,N-2,k);//第N-2行
  48.    }
  49. }

  51. void fill_guess_by_zmap(char gss[64][64],unsigned short zmap[2][2],char x,char y)
  52. {
  53.    char i,j;
  54.    char a=2*x;
  55.    char b=2*y;
  56.    for(i=0;i<2;i++){
  57.       for(j=0;j<2;j++){
  58.          //Use bit operation and 16 as base
  59.             gss[a+i*2][b+j*2]=zmap[i][j]&0xF;
  60.             gss[a+i*2][b+j*2+1]=(zmap[i][j]>>4)&0xF;
  61.          gss[a+i*2+1][b+j*2]=(zmap[i][j]>>8)&0xF;
  62.             gss[a+i*2+1][b+j*2+1]=(zmap[i][j]>>12)&0xF;
  63. #if 0 //Use 15 as base
  64.          gss[a+i*2][b+j*2] = (zmap[i][j] - 1)%15 + 1;//这里要注意的是加1减1操作,这是mod操作的一个技巧
  65.          gss[a+i*2][b+j*2+1] = ((zmap[i][j]-gss[a+i*2][b+j*2])/15 - 1)%15 + 1;
  66.          gss[a+i*2+1][b+j*2] = ((zmap[i][j]-gss[a+i*2][b+j*2]-gss[a+i*2][b+j*2+1]*15)/225 -1 )%15 + 1;
  67.          gss[a+i*2+1][b+j*2+1]=((zmap[i][j]-gss[a+i*2][b+j*2]-gss[a+i*2][b+j*2+1]*15-gss[a+i*2+1][b+j*2]*225)/3375 - 1)%15 + 1;
  68. #endif
  69.         }
  70.     }
  71. }
  72. int calc_and_upmap(int N,char gss[64][64],unsigned short zmap[2][2])
  73. {
  74.    char i,j,x,y;
  75.    int inner=0;
  76.    int meetnum;
  77.    int upnum=0;//初始化为0
  78.    
  79.    for(x=0;x<=N/2-2;x++){
  80.       for(y=0;y<=N/2-2;y++){
  81.          meetnum=0;
  82.          for(i=0;i<2;i++){
  83.             for(j=0;j<2;j++){
  84.                if(zmap[i][j]==guess_hash[x+i][y+j])
  85.                   meetnum++;
  86.             }
  87.          }
  88.          if(meetnum>=2){
  89.             for(i=0;i<2;i++)
  90.             for(j=0;j<2;j++)
  91.                guess_hash[x+i][y+j]=zmap[i][j];

  93.             inner=1;
  94.             upnum=4-meetnum;
  95.             fill_guess_by_zmap(gss,zmap,x,y);
  96.             break;//找到一个匹配就要中断
  97.          }
  98.       }
  99.       if(inner==1)
  100.          break;//中断外层循环
  101.    }
  102.    return upnum;
  103. }

  105. //将random区域摘要为2x2的map
  106. void save_zmap_info(unsigned short zmap[2][2])
  107. {
  108.    int i,j;
  109.    for(i=0;i<2;i++){
  110.       for(j=0;j<2;j++){
  111.          hiszmap[hisindex][i][j]=zmap[i][j];
  112.       }
  113.    }
  114.    hisindex+=1;
  115. }

  117. int update_by_hiszmap(int N, char gss[64][64])
  118. {
  119.    int i,j;
  120.    int index;
  121.    int upnum=0;
  122.    unsigned short hmap[2][2];
  123.    for(index=0;index<hisindex;index++){
  124.       for(i=0;i<2;i++){
  125.          for(j=0;j<2;j++){
  126.             hmap[i][j]=hiszmap[index][i][j];
  127.          }
  128.       }
  129.       upnum=calc_and_upmap(N,gss,hmap);
  130.       if(upnum>0)//首先要记得这里如果upnum大于0,说明已经找到匹配
  131.          break; //因为题目保证了只能匹配一块区域,所以这里要中断
  132.    }
  133.    return upnum;
  134. }

  136. void reconstruct(int N, char gss[MAX_MAP_SIZE][MAX_MAP_SIZE])//map=guess_map
  137. {
  138.    int upnum;
  139.    int leftnum=(N-4)*(N-4)/4;
  140.    char zone[4][4];
  141.    unsigned short zmap[2][2];
  142.    int hisupnum;
  143.    int i,j;
  144.    for(i=0;i<32;i++){
  145.       for(j=0;j<32;j++){
  146.          guess_hash[i][j]=0;
  147.       }
  148.    }
  149.    save_guess_info(N,gss);
  150.    while(leftnum != 0){
  151.       randomscan(zone);
  152.       zone_to_hash(zone,zmap);
  153.       upnum=calc_and_upmap(N,gss,zmap);
  154.       if(upnum!=0)//有更新
  155.       {
  156.          leftnum-=upnum;//更新剩余的2x2map
  157.          hisupnum=0;
  158.          do{
  159.             hisupnum=update_by_hiszmap(N,gss);//用历史zmap更新
  160.             leftnum-=hisupnum;
  161.                 if(leftnum==0)
  162.                     break;
  163.          }while(hisupnum>0);
  164.       }
  165.       save_zmap_info(zmap);
  166.    }
  167.    hisindex=0;//每个case结束后要复位
  168. }

  1. #ifndef _CRT_SECURE_NO_WARNINGS
  2. #define _CRT_SECURE_NO_WARNINGS
  3. #endif
  4. #include "stdafx.h"
  5. #include <stdio.h>
  6. #include <windows.h>//---

  8. #define MAX_MAP_SIZE 64
  9. #define ZONE_SIZE 4

  11. #define MAX_SCAN_COUNT 100000

  13. extern void reconstruct(int N, char map[MAX_MAP_SIZE][MAX_MAP_SIZE]);

  15. static char map[MAX_MAP_SIZE][MAX_MAP_SIZE];
  16. static int N;
  17. static int seed;
  18. static int scancount;

  20. static int pseudo_rand() {
  21.    seed = seed * 214013 + 2531011;
  22.    return (seed >> 16) & 0x7fff;
  23. }

  25. void randomscan(char zone[ZONE_SIZE][ZONE_SIZE]) {
  26.    if (scancount >= MAX_SCAN_COUNT)
  27.       return;

  29.    int x0 = (pseudo_rand() % ((N - ZONE_SIZE)/2 + 1)) * 2; // x0 = 0, 2, 4, ..., N - 4
  30.    int y0 = (pseudo_rand() % ((N - ZONE_SIZE)/2 + 1)) * 2; // y0 = 0, 2, 4, ..., N - 4

  32.    for (int y = 0; y < ZONE_SIZE; ++y)
  33.    for (int x = 0; x < ZONE_SIZE; ++x)
  34.       zone[y][x] = map[y + y0][x + x0];

  36.    ++scancount;
  37. }

  39. static void makemap() {
  40.    for (int y = 0; y < N; ++y)
  41.    for (int x = 0; x < N; ++x)
  42.       map[y][x] = pseudo_rand() % 15 + 1;
  43. }

  45. static bool compare(char map1[MAX_MAP_SIZE][MAX_MAP_SIZE], char map2[MAX_MAP_SIZE][MAX_MAP_SIZE]) {
  46.    for (int y = 0; y < N; ++y)
  47.    for (int x = 0; x < N; ++x)
  48.       if (map1[y][x] != map2[y][x])
  49.          return false;

  51.    return true;
  52. }

  54. int main() {
  55.    int TC, totalscore, totalscan;
  56.    int t;//---
  57.    freopen("20180310i.txt", "r", stdin);

  59.    setbuf(stdout, NULL);
  60.    scanf("%d", &TC);
  61.    t=GetTickCount();
  62.    totalscore = totalscan = 0;
  63.    for (int testcase = 1; testcase <= TC; ++testcase) {
  64.       char guess[MAX_MAP_SIZE][MAX_MAP_SIZE];
  65.       int min_scan_count;

  67.       scanf("%d %d %d", &N, &seed, &min_scan_count);

  69.       makemap();

  71.       scancount = 0;

  73.       for (int y = 0; y < N; ++y)
  74.       for (int x = 0; x < N; ++x)
  75.          guess[y][x] = 0;

  77.       for (int k = 0; k < N; ++k) {
  78.          guess[k][0] = map[k][0];//第0列
  79.          guess[0][k] = map[0][k];//第0行
  80.          guess[k][1] = map[k][1];//
  81.          guess[1][k] = map[1][k];//
  82.          guess[k][N - 1] = map[k][N - 1];//
  83.          guess[N - 1][k] = map[N - 1][k];//
  84.          guess[k][N - 2] = map[k][N - 2];//第N-2列
  85.          guess[N - 2][k] = map[N - 2][k];//第N-2行
  86.       }

  88.       reconstruct(N, guess);

  90.       if (!compare(map, guess))
  91.          scancount = MAX_SCAN_COUNT;
  92.       totalscan += scancount;

  94.       int score;
  95.       if (TC == 5) { // sample testcase
  96.          score = scancount < MAX_SCAN_COUNT ? 100 : 0;
  97.          totalscore += score;
  98.       } else { // eval testcase
  99.          score = scancount <= min_scan_count + (min_scan_count / 2) ? 100 : 0;
  100.          totalscore += score;
  101.       }

  103.       printf("#%d %d\n", testcase, score);
  104.    }
  105.    t = GetTickCount() - t;
  106.    if (totalscan > MAX_SCAN_COUNT) totalscan = MAX_SCAN_COUNT;
  107.    printf("total score = %d, total scan = %d\n", totalscore / TC, totalscan);
  108.    printf("used time is %d\n", t);
  109.    return 0;
  110. }
  111. /*
  112. 5
  113. 8 26585 3
  114. 12 24059 28
  115. 16 26751 50
  116. 20 19164 100
  117. 24 10446 153
  118. */








阅读(1543) | 评论(1) | 转发(0) |
0

上一篇：51nod 1140

下一篇：CF 0798D 二维贪心 随机算法 随机洗牌

给主人留下些什么吧！~~

zhln2018-03-28 09:57:50

#1 100
#2 100
#3 100
#4 100
#5 100
total score = 100, total scan = 334
used time is 0

回复 | 举报
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6