题解 | #下棋#_牛客博客

题目的主要信息：

一个 $n*n$ 的棋盘编号呈现螺旋状排列，一开始棋子在1号棋盘格上分数为0
一共q次询问，每次都是1-6数字中的一个，记为j，棋子会按照编号移动相应位数j（ $n*n$ 号会回到1号），按照公式来写：当前在序号i，移动j步后，下一次的位置是 $(i+j-1)\%n^2+1$
我们要计算的分数，就是加上所有行号或者列号与当前格子相差小于上述移动位数j的所有格子的编号
得分是与前面累加的，且要对1000000007取模

方法一：暴力解法（超时）

具体做法：
暴力解法分为两部分，一个是构建棋盘，另一个是对每次查询计算分数。
构建棋盘部分：我们参照螺旋矩阵的输出，对其设置上下左右四个边界，每次都从左界到右界，然后降低上界，再从上界到下界，然后减小右界，再从右界到左界，然后增大下界，再从下届到上界，然后扩大左界，再从左到右，如此循环直到录入 $n^2$ 个数字。录入的数字记录在矩阵encode中，同时用一个 $n^2$ 长度的数组记录每个编号数字对应的行号列号，数组中保存的是pair变量。这样我们构建了棋盘有了从编号到行号列号的映射，也有了从行号列号到编号的映射。
计算分数部分：我们先按照公式 $(i+j-1)\%n^2+1$ 计算下一次的位置，然后遍历其上下邻近的共 $2*(j-1)+1$ 行，每行的编号加入答案中，然后遍历其左右邻近的 $2*(j-1)+1$ 列，每列的编号加入答案中。当然，这个过程我们要注意避免重复相加，即记录访问过的位置。还要注意的是检查下标是否使数组越界。
最后每次得分取模后再与上一询问最后的分数相加取模即可。

class Solution {
public:
    int mod = 1000000007;
    //构建棋盘
    void draw_cheseboard(int n, vector<vector<int>>& encode, vector<pair<int,int>>& index){
        int up = 0, down = n - 1, left = 0, right = n - 1; //四个边界
        int num = 1;
        while (num <= n * n) {
            for(int i = left; i <= right; i++){ //从左往右
                encode[up][i] = num;
                index[num] = make_pair(up, i);
                num++;
            }
            up++;
            for(int i = up; i <= down; i++) {//从右上往右下
                encode[i][right] = num;
                index[num] = make_pair(i, right);
                num++;
            }
            right--;
            for(int i = right; i >= left; i--){ //从右下往左下
                encode[down][i] = num;
                index[num] = make_pair(down, i);
                num++;
            }
            down--;
            for(int i = down; i >= up; i--){ //从左下往左上
                encode[i][left] = num;
                index[num] = make_pair(i, left);
                num++;
            }
            left++;
        }
    }
    int cal_socre(int& cur, vector<vector<int>>& encode, vector<pair<int,int>>& index, int num){
        int n = encode.size();
        vector<vector<bool> > vis(n, vector<bool>(n, false)); //记录改点有无被加过
        cur = (cur + num - 1) % (n * n) + 1; //移动后的位置
        int res = 0;
        //遍历与之邻接的这些行
        for(int i = index[cur].first - num + 1; i < index[cur].first + num; i++){
            if(i < 0 || i >= n) //越界的不用管
                continue;
            for(int j = 0; j < n; j++){
                if(!vis[i][j]){
                    res = (res + encode[i][j]) % mod;
                    vis[i][j] = true;
                }
            }
        }
        //遍历与之邻近的这些列
        for(int i = index[cur].second - num + 1; i < index[cur].second + num; i++){
            if(i < 0 || i >= n)  //越界的不用管
                continue;
            for(int j = 0; j < n; j++){
                if(!vis[j][i]){ //没有访问过的才加，避免重复
                    res = (res + encode[j][i]) % mod;
                    vis[j][i] = true;
                }
            }
        }
        return res;
    }
    vector<int> getScores(int n, vector<int>& query) {
        vector<vector<int> > encode(n, vector<int>(n)); //棋盘编号
        vector<pair<int,int> > index(n * n); //由编号到行列号索引
        draw_cheseboard(n, encode, index); //构建棋盘
        vector<int> res(query.size(), 0);
        int cur = 1; //记录当前位置
        for(int i = 0; i < query.size(); i++){//一共q次查询
            res[i] = cal_socre(cur, encode, index, query[i]);
            if(i != 0) //与前面的累加
                res[i] = (res[i] + res[i - 1]) % mod;
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n^2+n \Sigma_{i=0}^{n-1} query[i])$ ，构建棋盘一共循环 $n^2$ 次，一共 $q$ 次查询，每次查询对于行需要遍历 $2*query[i]$ 这么多行，同样的也要遍历这么多列，因此复杂度为 $O(n^2+n*4* \Sigma _{i=0}^{n-1} query[i])$
空间复杂度： $O(n^2)$ ，不管是一维辅助数组还是二维辅助数组，最大空间都是 $O(n^2)$

方法二：整行整列相加

具体做法：
基于方法一我们做出一些改进。
我们发现在计算得分的时候，每次查询对于行需要遍历 $2*query[i]$ 这么多行，同样的也要遍历这么多列，每行每列都是 $n$ 的长度，要完整地遍历，很浪费时间，因此我们可以考虑直接在构建棋盘的时候就记录这些行与列的和，计算分数的时候直接将方法一中需要的行和与列和加入答案中即可。当然会重复计算行与列交叉的部分，但是这部分最多不会超过12*12的区域（因为每次的移动步数最大为6），对于 $n$ 特别大的情况，这就是常数而已，每次计算的时候遍历这部分区域，减去它们中的编号就可以，时间上属于常数级。
图片说明

class Solution {
public:
    int mod = 1000000007;
    //构建棋盘并计算行和与列和
    void draw_cheseboard(int n, vector<vector<int>>& encode, vector<pair<int,int>>& index, vector<int>& col_sum, vector<int>& row_sum){
        int up = 0, down = n - 1, left = 0, right = n - 1; //四个边界
        int num = 1;
        while (num <= n * n) {
            for(int i = left; i <= right; i++){ //从左往右
                encode[up][i] = num;
                col_sum[i] = (num + col_sum[i]) % mod; //列和
                row_sum[up] = (row_sum[up] + num) % mod; //行和
                index[num] = make_pair(up, i);
                num++;
            }
            up++;
            for(int i = up; i <= down; i++) {//从右上往右下
                encode[i][right] = num;
                row_sum[i] = (row_sum[i] + num) % mod;  //行和
                col_sum[right] = (col_sum[right] + num) % mod; //列和
                index[num] = make_pair(i, right);
                num++;
            }
            right--;
            for(int i = right; i >= left; i--){ //从右下往左下
                encode[down][i] = num;
                row_sum[down] = (row_sum[down] + num) % mod; //行和
                col_sum[i] = (col_sum[i] + num) % mod; //列和
                index[num] = make_pair(down, i);
                num++;
            }
            down--;
            for(int i = down; i >= up; i--){ //从左下往左上
                encode[i][left] = num;
                row_sum[i] = (row_sum[i] + num) % mod; //行列
                col_sum[left] = (col_sum[left] + num) % mod;  //列和
                index[num] = make_pair(i, left);
                num++;
            }
            left++;
        }
    }
    int cal_socre(int& cur, vector<vector<int>>& encode, vector<pair<int,int>>& index, int num, vector<int>& col_sum, vector<int>& row_sum){
        int n = encode.size();
        cur = (cur + num - 1) % (n * n) + 1; //移动后的位置
        int res = 0;
        //临近行，行和相加
        for(int i = index[cur].first - num + 1; i < index[cur].first + num; i++){
            if(i < 0 || i >= n) //越界的不用管
                continue;
            res = (res + row_sum[i]) % mod;
        }
        //邻近列，列和相加
        for(int i = index[cur].second - num + 1; i < index[cur].second + num; i++){
            if(i < 0 || i >= n)  //越界的不用管
                continue;
            res = (res + col_sum[i]) % mod;
        }
        //找到重复的部分，减掉
        for(int i = index[cur].first - num + 1; i < index[cur].first + num; i++){
            for(int j = index[cur].second - num + 1; j < index[cur].second + num; j++){
                if(i < 0 || i >= n || j < 0 || j >= n)
                    continue;
                res = (res - encode[i][j] + mod) % mod;
            }
        }
        return res;
    }
    vector<int> getScores(int n, vector<int>& query) {
        vector<vector<int> > encode(n, vector<int>(n)); //棋盘编号
        vector<pair<int,int> > index(n * n); //由编号到行列号索引
        vector<int> col_sum(n, 0); //某一列编号和
        vector<int> row_sum(n, 0); //某一行编号和
        draw_cheseboard(n, encode, index, col_sum, row_sum); //构建棋盘
        vector<int> res(query.size(), 0);
        int cur = 1; //记录当前位置
        for(int i = 0; i < query.size(); i++){//一共q次查询
            res[i] = cal_socre(cur, encode, index, query[i], col_sum, row_sum);
            if(i != 0) //与前面的累加
                res[i] = (res[i] + res[i - 1]) % mod;
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n^2+ \Sigma _{i=0}^{n-1}query[i])$ ，构建棋盘和方法一一样，都是 $O(n^2)$ ，计算得分部分因为行和列和直接相加，其中的 $n$ 次遍历就去掉了，同时遍历重复区域属于常数级时间，故不写入
空间复杂度： $O(n^2)$ ，不管是一维辅助数组还是二维辅助数组，最大空间都是 $O(n^2)$