题意

螺旋状棋盘(如下)，棋子一开始在格子1，q次询问，每次询问x，表示棋子往前走x步(循环，n*n->1)，且分数加上行号和当前行号距离<x或列号和当前列号距离<x的格子的编号之和，输出每次走完的分数。

题解

关键词

预处理，二维前缀和

做法一

首先处理出编号i与行和列的关系，即求出a[x][y]为x行y列的编号，b[i]为编号i的行，c[i]为编号i的列。
接下来模拟游戏过程，每次暴力把合法的格子的编号加上即可。
复杂度 ，预计通过30%。其中k=6，是骰子的最高点数。

做法二

可以发现每次加上的格子由一些行和一些列组成，那么我们可以预处理出每行和每列的和，然后模拟时加上这些行和列的和。
注意需要减去重复的格子，但每次这些格子最多只有11*11个。
复杂度 ，预计通过100%。

做法三

也可以求一个二维前缀和。令。
sum数组可以dp进行求解：
然后假设矩形为左上角,右下角，那么这个矩形的和为： 。
这样我们可以时间求得一个矩形的和。而每次加上的分数可以分解为不超过3个矩形。
复杂度 ，预计通过100%

代码

做法一

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn = 2020;
const int mod = 1000000007;
ll a[maxn][maxn], b[maxn*maxn], c[maxn*maxn];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};

class Solution {
public:
    /**
     * 求每一步后的总分数
     * @param n int整型 棋盘大小
     * @param query int整型vector 每次掷出的点数的列表
     * @return long长整型vector
     */
    vector<int> getScores(int n, vector<int>& query) {
        for (int i=0;i<=n+1;i++) for (int j=0;j<=n+1;j++) a[i][j]=0;
        for (int i=0;i<=n*n+1;i++) b[i]=c[i]=0;
        int x=1,y=1,dir=0;
        for (int i=1;i<=n*n;i++) {
            a[x][y]=i,b[i]=x,c[i]=y;
            if (i<n*n) for (;;dir=(dir+1)%4) {
                int nx=x+dx[dir],ny=y+dy[dir];
                if (1 > nx || nx > n || 1 > ny || ny > n || a[nx][ny]) continue;
                x=nx,y=ny;
                break;
            }
        }

        vector <int> result;
        int now = 1;
        ll ans = 0;
        int m = query.size();
        for (int i=0;i<m;i++) {
            int x = query[i];
            now = (now + x - 1)%(n*n)+1;
            ll tmp = 0;
            int l=max(1ll,c[now]-x+1), r=min((ll)n,c[now]+x-1);
            for (int i=1;i<=n;i++) for (int j=l;j<=r;j++) tmp += a[i][j];
            int l2=max(1ll,b[now]-x+1), r2=min((ll)n,b[now]+x-1);
            for (int i=l2;i<=r2;i++) {
                for (int j=1;j<l;j++) tmp += a[i][j];
                for (int j=r+1;j<=n;j++) tmp += a[i][j];
            }
            ans += tmp;
            result.push_back(ans%mod);
        }
        return result;
    }
};

做法二

询问前处理行和和列和，具体来说，后一段改成这样：

    static ll d[maxn], e[maxn];
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) d[i]+=a[i][j], e[j]+=a[i][j];
    vector <int> result;
    int now = 1;
    ll ans = 0;
    int m = query.size();
    for (int i=0;i<m;i++) {
        int x = query[i];
        now = (now + x - 1)%(n*n)+1;
        ll tmp = 0;
        int l=max(1ll,c[now]-x+1), r=min((ll)n,c[now]+x-1);
        int l2=max(1ll,b[now]-x+1), r2=min((ll)n,b[now]+x-1);
        for (int i=l;i<=r;i++) tmp += e[i];
        for (int i=l2;i<=r2;i++) tmp += d[i];
        for (int i=l2;i<=r2;i++) {
            for (int j=l;j<=r;j++) tmp -= a[i][j];
        }
        ans += tmp;
        result.push_back(ans%mod);
    }

做法三

预处理二维前缀和，具体如下：

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn = 2020;
const int mod = 1000000007;
ll a[maxn][maxn], b[maxn*maxn], c[maxn*maxn];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};

class Solution {
public:
    ll ask(int l,int r,int l2,int r2,int n) {
        l2=min(l2,n), r2=min(r2,n);
        l=max(l,1), r=max(r,1);
        if (l2 < l || r2 < r) return 0;
        return a[l2][r2]-a[l-1][r2]-a[l2][r-1]+a[l-1][r-1];
    }
    /**
     * 求每一步后的总分数
     * @param n int整型 棋盘大小
     * @param query int整型vector 每次掷出的点数的列表
     * @return long长整型vector
     */
    vector<int> getScores(int n, vector<int>& query) {
        for (int i=0;i<=n+1;i++) for (int j=0;j<=n+1;j++) a[i][j]=0;
        for (int i=0;i<=n*n+1;i++) b[i]=c[i]=0;
        int x=1,y=1,dir=0;
        for (int i=1;i<=n*n;i++) {
            a[x][y]=i,b[i]=x,c[i]=y;
            if (i<n*n) for (;;dir=(dir+1)%4) {
                int nx=x+dx[dir],ny=y+dy[dir];
                if (1 > nx || nx > n || 1 > ny || ny > n || a[nx][ny]) continue;
                x=nx,y=ny;
                break;
            }
        }

        for (int i=1;i<=n;i++) {
            for (int j=1;j<=n;j++) {
                a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
            }
        }

        int now = 1;
        ll ans = 0;
        vector <int> result;
        int m = query.size();
        for (int i=0;i<m;i++) {
            x = query[i];
            now = (now + x - 1)%(n*n)+1;

            ll tmp = ask(1,c[now]-x+1,n,c[now]+x-1,n) +
                ask(b[now]-x+1,1,b[now]+x-1,n,n) -
                ask(b[now]-x+1,c[now]-x+1,b[now]+x-1,c[now]+x-1,n);
            ans += tmp;
            result.push_back(ans%mod);
        }
        return result;
    }
};