题解[下棋]
题意
螺旋状棋盘(如下)，棋子一开始在格子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;
}
};
