2018百度之星程序设计大赛初赛B——1002hex

HDU-6381

题目：

度度熊最喜欢六边形的网格了！！！

上图由左至右依序是边长为 11, 22 以及 33 的六边形网格。

另外，每个六边形网格最左侧的格子称之为这个六边形网格的锚点，上图中每个六边形网格的锚点都以蓝色着色。

定义在六边形网格上的坐标系统：相对一个坐标为 (x,y)(x,y) 的中心格子，其周围格子的坐标定义为下图中所示的值：

给定一个大小为 LL 的六边形主网格，这个六边形主网格的锚点的坐标为 (1,L)(1,L)。这个主网格中每一个格子上都有一个颜色，以 00 至 6161 之间的整数代表。对于这个主网格有 QQ 个询问，每个询问将会询问这个主网格中某一个六边形子网格的范围中，包含有几个不一样的颜色。

一个询问以三个整数 <x,y,l><x,y,l> 来表示其中一个六边形的子网格，依序为其锚点的坐标 (x,y)(x,y) 以及其大小 ll。例如，下图为一个大小 L=3L=3 的主网格，格子内部的数字为其坐标，而非格子的颜色。绿色边框所包围的子网格是一个锚点坐标为 (5,3)(5,3)，大小 l=2l=2 的子网格，以 <5,3,2><5,3,2> 表示，同时，红色边框表示 <3,1,1><3,1,1> 的子网格。

Input

输入的第一行有一个正整数 TT，代表接下来有几笔测试资料。

对于每笔测试资料： 第一行有一个正整数 LL。 接下来的 2L−12L−1 行输入代表一个大小为 LL 的六边形网格。 六边形网格将会透过下列的过程转换至输入的格式：

1. 将每格内代表颜色的数字 00~6161 按照 0-9a-zA-Z 的顺序对照转换为一个字符，例如 1010 转换为 'a'，而 3636 转换为 'A'。
2. 将每行中的字符由左至右串接起来形成一个字符串，注意两个字符之间并不会安插任何的空格符。
3. 输入中的 2L−12L−1 行每行会有一个字符串，依序代表编码后由上至下的这 2L−12L−1 个字符串。

接下来的一行有一个整数 QQ 代表接下来有几组询问。 接下来的 QQ 行每行有三个正整数 xx, yy 及 ll，代表一组询问 <x,y,l><x,y,l>。

下图为范例测试资料中的六边形网格，格子内显示的数字代表颜色，而非坐标：

• 1≤L≤2501≤L≤250
• 代表六边形网格的字符串中只会有 0-9a-zA-Z 这些字符。
• 0≤Q≤3×1050≤Q≤3×10​5​​
• 1≤x≤4L−31≤x≤4L−3
• 1≤y≤2L−11≤y≤2L−1
• 1≤l≤L1≤l≤L
• (x,y)(x,y) 一定是给定的六边形网格中合法的格子点。
• <x,y,l><x,y,l> 询问的子六边形网格一定完整的位于主网格中。
• 1≤T≤151≤T≤15
• 至多 11 笔测试资料中的 L>50L>50
• 至多 11 笔测试资料中的 Q>1000Q>1000

Output

对于每一笔测试资料，对于每一个询问，请依序各自在一行内输出一个整数，代表此询问的答案。 两笔测试资料间请不要输出多余的空白行。

Sample Input

1
3
012
3456
789ab
cdef
ghi
10
1 3 1
1 3 2
1 3 3
9 3 1
7 3 1
3 3 1
3 3 2
5 3 1
5 3 2
2 2 2

Sample Output

1
7
19
1
1
1
7
1
7
7

（题目复制过来后部分文本重复了）

题目看起来很长，加上有那么多六边形好像很麻烦，但其实根本问题还是：

给一组东西，多次询问某个范围，求这个范围内的某个／某种值。

符合rmq的条件，所以可以尝试用rmq解决。

这道题其实可以算是资格赛1002的进阶版，同样使用rmq算法，只不过那道题给的是一个数组，求的是最值，这里给的是一组六边形，求的是颜色的种数。

rmq算法用到了动态规划，那么就要有状态。

题目的63个颜色可以用63个二进制表示，出现哪种颜色，哪一位用“1”表示，有点类似资格赛1001的思路。可以用long long 类型的数来表示每组六边形的状态。

long long dp [2*MAXL-1] [4*MAXL-3] [9]

dp [i] [j] [k] 表示以点（i，j）为锚点，边长为 2的k次方 的六边形的状态（所包含的颜色）。

状态转移：

rmq算法是以2倍增的思想来不断进行处理的，对应这道题也就是：对于边长为2的k次方的六边形，用边长为2的(k-1)次方的六边形来覆盖处理它。

以边长为2的六边形来看，我们可以用6个点对应的6个边长为1的六边形 + 中心六边形来覆盖它；

当边长=2^k >2时，同样的，6个点对应的6个2^(k-1) 个六边形 + 中心六边形可以表示它。（这里的六边形会有重叠的部分，但不会有遗漏的部分）

为了方便放进数组，先将题目中给出的坐标表示换一下位置，比如题目中（1，3）的点我们表示成（3，1）放进六边形数组six[3][1]。

所以接下来就是确定这7个六边形的锚点的问题了。

可以自己动手再画一个边长为4的六边形，对比边长为2，边长为1的六边形，多利用2^k，2^(k-1)，2^(k+1)不难得出七个六边形的锚点坐标：

／**七个六边形位置：

    1        2

 3       7       4

    5        6
    
*／              
            


                int i1 = i-(1<<(k-1));
                int j1 = j + (1<<(k-1));
                int i2 = i - (1<<(k-1));
                int j2 = j + (1<<(k-1)) + (1<<k);
                int i3 = i;
                int j3 = j;
                int i4 = i;
                int j4 = j + (1<<(k+1));
                int i5 = i + (1<<(k-1));
                int j5 = j + (1<<(k-1));
                int i6 = i + (1<<(k-1));
                int j6 = j + (1<<(k-1)) + (1<<k);
                int i7 = i;
                int j7 = j + (1<<(k+1)) - 2;

所以，

状态转移方程：

dp[i][j][k] = dp[i1][j1][k-1] | dp[i2][j2][k-1]  | dp[i3][j3][k-1] | dp[i4][j4][k-1]  | dp[i5][j5][k-1] | dp[i6][j6][k-1]  | dp[i7][j7][k-1];

也就是这7个六边形做 按位或（ | ）操作 —— 有1为1，全0为0，这个运算就可以来表示这七个六边形组合在一起的颜色情况了。

初始状态：

k=0，只有一个六边形，它的状态就是它本身的颜色。

dp[i][j][0] = (long long)1<<six[i][j]

dp数组存储完之后，剩下的就是查询了。

由于rmq用的是2的倍增，在这道题中也就是计算了1，2，4，8 ... 边长的颜色情况，那么对于3，5，6，7这些边长没办法直接在dp数组里面找到，所以查询仍然是分段查询。同样的道理比如资格赛1002。

先打表，求一下0-250这些数的log2是多少，存储在Log2数组中。（这里存储的时候是向下取整，也就是说log2(3) = 1）

然后，在查询时，我们只需要6个顶点对应的六边形就可以覆盖待查询的六边形了，因为中心六边形肯定包括在这个6个中。

设查询的边长为L，Log2[L] = k；

查询区间的确定，实际上是与 （L - 2^k）有关，可以得到六个六边形的锚点坐标，并进而得到这六个六边形组成的颜色情况n：

 long long n;
    
 int temp = l - (1<<k);     // L - 2^k

        int i1 = x - temp;
        int j1 = y + temp;
        int i2 = x - temp;
        int j2 = y + 3 * temp;
        int i3 = x;
        int j3 = y;
        int i4 = x;
        int j4 = y + 4 * temp;
        int i5 = x + temp;
        int j5 = y + temp;
        int i6 = x + temp;
        int j6 = y + 3 * temp;
    
    
        n = (long long)dp[i1][j1][k] | dp[i2][j2][k]
        | dp[i3][j3][k] | dp[i4][j4][k]
        | dp[i5][j5][k] | dp[i6][j6][k];

最后，只要数一下 n 里面有多少个1，那么就有多少种颜色，就是答案了。

代码：

//
//  main.cpp
//  初赛B1002
//
//  Created by jinyu on 2018/8/13.
//  Copyright © 2018年 jinyu. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

/**
 
 L  ,  L 个    :   1
 L-1,  L+1    :   2
 L-2,  L+2    :   3
 ...          :   ...
 1  ,  2L-1   :   ...
 2  ,  2L-2   :
 3  ,  2L-3   :
 ...          :
 L  ,  L      :   2L-1
 
 */

const int MAXL = 250+7;


int six[2*MAXL-1][4*MAXL-3];
int L;
long long dp[2*MAXL-1][4*MAXL-3][9];
int Log2[MAXL];

void rmq(){
    for(int k = 1;(1<<k)<=L;k++){
        for(int i = 1;i+(1<<(k-1))<=2*L-1;i++){
            for(int j = 1;j+(1<<(k-1))+(1<<k)<=4*L-3;j++){
                if(six[i][j]==-1)
                    continue;
                if((i-(1<<(k-1)))<1)
                    continue;
                
                int i1 = i-(1<<(k-1));
                int j1 = j + (1<<(k-1));
                int i2 = i - (1<<(k-1));
                int j2 = j + (1<<(k-1)) + (1<<k);
                int i3 = i;
                int j3 = j;
                int i4 = i;
                int j4 = j + (1<<(k+1));
                int i5 = i + (1<<(k-1));
                int j5 = j + (1<<(k-1));
                int i6 = i + (1<<(k-1));
                int j6 = j + (1<<(k-1)) + (1<<k);
                int i7 = i;
                int j7 = j + (1<<(k+1)) - 2;
                
                dp[i][j][k] = dp[i1][j1][k-1] | dp[i2][j2][k-1]
                | dp[i3][j3][k-1] | dp[i4][j4][k-1]
                | dp[i5][j5][k-1] | dp[i6][j6][k-1]
                | dp[i7][j7][k-1];
                
            }
        }
    }
}

int query(int x,int y,int l){

    int k = Log2[l];
    int temp = l - (1<<k);
    if(k==0)
        return 1;
    long long n;
    
        int i1 = x - temp;
        int j1 = y + temp;
        int i2 = x - temp;
        int j2 = y + 3 * temp;
        int i3 = x;
        int j3 = y;
        int i4 = x;
        int j4 = y + 4 * temp;
        int i5 = x + temp;
        int j5 = y + temp;
        int i6 = x + temp;
        int j6 = y + 3 * temp;
    
    
        n = (long long)dp[i1][j1][k] | dp[i2][j2][k]
        | dp[i3][j3][k] | dp[i4][j4][k]
        | dp[i5][j5][k] | dp[i6][j6][k];

    int ans = 0;
    //判断n中1的个数
    while(n){
        n = n & (n-1);
        ans++;
    }
    return ans;
}

int main(){
    
    for(int i = 0;i<MAXL;i++){
        Log2[i] = i==0?-1:Log2[i>>1]+1;
    }
    
    int T;
    scanf("%d",&T);
    while(T--){
       
        scanf("%d",&L);
        for(int i = 0;i<4*L+7;i++){
            for(int j = 0;j<4*L+7;j++)
                six[i][j] = -1;
        }
        getchar();
        char c;
        int k = 1;
        for(int i = L;i>=1;--i){
            int tempi = i;
            int num = L+(L-i);
            while(num--){
                c = getchar();
                if(c>='0' && c<='9'){
                    six[k][tempi] = c-'0';
                }
                else if(c>='a' && c<='z'){
                    six[k][tempi] = c-'a'+10;
                }
                else if(c>='A' && c<='Z'){
                    six[k][tempi] = c-'A'+36;
                }
                tempi+=2;
            }
            getchar();
            k++;
        }
        for(int i = 2;i<=L;++i){
            int tempi = i;
            int num = L+(L-i);
            while(num--){
                c = getchar();
                if(c>='0' && c<='9'){
                    six[k][tempi] = c-'0';
                }
                else if(c>='a' && c<='z'){
                    six[k][tempi] = c-'a'+10;
                }
                else if(c>='A' && c<='Z'){
                    six[k][tempi] = c-'A'+36;
                }
                tempi+=2;
            }
            getchar();
            k++;
        }
        
//        for(int i = 1;i<=2*L-1;i++){
//            for(int j = 1;j<=4*L-3;j++)
//            {
//                if(six[i][j]==-1)
//                    cout<<" ";
//                else
//                    cout<<six[i][j]<<" ";
//            }
//            cout<<endl;
//        }
        
        for(int i = 1;i<=2*L-1;i++){
            for(int j = 1;j<=4*L-3;j++){
                if(six[i][j]==-1)
                    dp[i][j][0] = (long long)0;
                else
                    dp[i][j][0] = (long long)1<<six[i][j];
            }
        }
        
        rmq();
        
        int Q;
        scanf("%d",&Q);
        while(Q--){
            int x,y,l;
            scanf("%d%d%d",&y,&x,&l);
            printf("%d\n",query(x,y,l));
        }
        
//        printf("3 1 1 : %lld\n",dp[3][1][1]);
        
    }
    return 0;
}