A. 齐全平方数的尾巴

题目形容

咱们把一个能被示意成某个整数的平方的数称为齐全平方数。

例如 4 = 2 ∗ 2，16 = 4 ∗ 4，所以 4，16 是齐全平方数。

当初输出一个整数为 x (0 ≤ x ≤ 999)，请聪慧的你判断它是不是由某个齐全平方数对 1000 取模失去的呢。

示例 1

输出

24

输入

true

阐明

1024 = 32 ∗ 32
24 = 1024 mod 1000

解法：暴力搜寻

思路剖析

咱们晓得齐全平方数对 k 取模的值，是 k 个一循环的。即对于 f(x) = (x * x) % k，函数值 k 个一循环。

本题对 1000 取模，因而遍历 1 – 999 的齐全平方数模 1000 的值，若都不为 x，则返回 false。

代码实现

public boolean solve (int x) {for(int i = 1; i < 1000; i++) {if(i * i % 1000 == x) return true;
  }
  return false;
}

B. 牛牛的字符串

题目形容

牛牛有一个长度为 N 的由小写字母组成的字符串 S，还有一个整数 K。在每一步中，牛牛都能够抉择一个地位 i，并在 i 和 i + K 处替换字符（i + K < N）并且 $S_i <S_{i+k}$，即替换之后，新造成的字符串应字典序大于旧字符串。牛牛想尽可能替换尽量多的步数。他想晓得最多能够替换多少步呢。

备注:

1 ≤ N ≤ 1e5, 1 ≤ k ≤ N

示例 1

输出

"cbexa",2

输入

2

阐明

cbexa -> cxeba -> excba 步数为 2 

解法：分组求解

思路剖析

咱们看一下交换条件：$S_i <S_{i+k}$。即前一个字符小于后一个字符。

因而对于序列: i, i + k, i + 2k, …。能够替换的次数 = 程序对的个数。

而字符串中总共有 k 个上述序列。故而求解这 k 个序列的 程序对的个数 之和，即可得出答案。

程序对个数的求解办法和逆序对个数的求解办法雷同，经典的办法有归并排序和离散化树状数组。不过本题是求字符数组的程序对，因而能够利用 26 大小的哈希数组来求解。

代码剖析

public int turn (String s, int k) {
  int ans = 0;
  List<Character>[] group = new List[k];
  for (int i = 0; i < k; i++) group[i] = new ArrayList<Character>();
  for (int i = 0; i < s.length(); i++) group[i % k].add(s.charAt(i));
  for (List<Character> list: group) {int[] arr = new int[26];
    for (char c : list) {
      int index = c - 'a';
      for(int i = 0; i < index; i++) ans += arr[i]; // 找到字符 c 之前比字符 c 小的字符的个数
      arr[index]++;
    }
  }
  return ans;
}

C. 下棋

题目形容

牛牛做了一个 $n*n$ 的棋盘，棋盘每个格子有一个编号(从 1 到 $n * n$)，编号是成螺旋形态的，上面给出 $3*3$ 的棋盘编号的例子。

因为隔离在家，牛牛只能本人一个人玩游戏。一开始棋子在 1 号格子上，分数为 0。
每次牛牛会用骰子掷出 1 – 6 中的一个数字 j (1 ≤ j ≤ 6)，而后棋子会沿编号向前挪动 j 步（n 号格子前面到 1 号格子），
且分数加上所有行号或者列号与以后格子相差小于 j 的所有格子的编号。

严格来说，函数 f(x, y) = 第 x 行第 y 列的格子的编号。比方 n = 3 时，f(2, 2) = 9；n = 4 时，f(3, 1) = 11。
假如以后棋子在 i 号格子上，挪动 j 步，那么棋子将挪动到 i’ 号格子上，其中 i’ = (i + j – 1) % (n * n) + 1。且分数加上
$∑_{1≤x,y≤n,\\f(x_0,y_0)=i′,\\min(∣x−x_0∣,∣y−y_0∣)<j}f(x,y)$
牛牛想让你帮他写个程序，计算出每次挪动完累计失去的分数。为了避免输入过大，请返回分数对 1,000,000,007 取模后的值。

备注:

对于 30% 数据，1 ≤ n ≤ 100,1 ≤ q ≤ 1000（q 为询问次数）对于 100% 数据，1 ≤ n ≤ 2000,1 ≤ q ≤ 100000（q 为询问次数）

示例 1

输出

4,[1,2,5,6,2]

输入

[48,138,274,410,510]

解法：前缀和

思路剖析

$∑_{1≤x,y≤n,\\f(x_0,y_0)=i′,\\min(∣x−x_0∣,∣y−y_0∣)<j}f(x,y)$ 在图上来看，其实就是一个以 $f(x, y)$ 为核心的一个十字形框内的编号之和，如图所示。

因为查问的次数很多，所以咱们心愿在常数工夫内求解出答案。

如果咱们能在常数工夫内失去某个矩形内的编号和，那么答案 = 红色矩形 + 绿色矩形 – 蓝色矩形 内编号之和。

如何在常数工夫内失去某个矩形内的编号之和呢？显然咱们能够利用前缀和保留一个大矩形的编号和，大矩形 – 小矩形 = 咱们要求的矩形。

定义前缀和 preSum[i][j] 示意以 (i, j) 为右下角的矩形的编号和。显然前缀和能够通过公式 preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + chessboard[i][j] 来迭代求解。

工夫复杂度：$O(n*n)$。初始化棋盘和前缀和的工夫复杂度为 $O(n * n)$, 每一次查问分数的工夫复杂度为 $O(1)$。

空间复杂度：$O(n * n)$

代码实现

public int[] getScores (int n, int[] query) {int[] ans = new int[query.length];
  int[][] chessboard = new int[n + 1][n + 1]; // 棋盘，chessboard[x][y] 示意第 x 行 第 y 列的编号
  int[][] coordinates = new int[n * n + 1][2]; // 编号对应的下标
  long[][] preSum = new long[n + 1][n + 1]; // 前缀和，preSum[i][j] 示意以 (i,j) 为右下角的矩形内所有编号之和
  init(n, chessboard, coordinates, preSum);
  int now = 1;
  long score = 0;
  for(int i = 0; i < query.length; i++) {int j = query[i];
    now = (now + j - 1) % (n * n) + 1;
    int x = coordinates[now][0], y = coordinates[now][1];
    score += recSum(n, preSum, 1, y - j + 1, n, y + j - 1) + recSum(n, preSum, x - j + 1, 1, x + j - 1, n) - recSum(n, preSum, x - j + 1, y - j + 1, x + j - 1, y + j - 1);
    score %= 1e9 + 7;
    ans[i] = (int)score;
  }
  return ans;
}

// 初始化棋盘，编号对应的坐标，前缀和
void init(int n, int[][] chessboard, int[][] coordinates, long[][] preSum){int[] fx = new int[]{0,1,0,-1};
  int[] fy = new int[]{1,0,-1,0};
  int x = 1, y = 1, opt = 0;
  for(int i = 1; i <= n * n; i++){chessboard[x][y] = i;
    coordinates[i] = new int[]{x, y};
    int x1 = x + fx[opt], y1 = y + fy[opt];
    if(x1 < 1 || x1 > n || y1 < 1 || y1 > n || chessboard[x1][y1] != 0) opt = (opt + 1) % 4;
    x = x + fx[opt]; 
    y = y + fy[opt];
  }
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
      preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + chessboard[i][j];
}

long recSum(int n, long[][] preSum, int x1, int y1, int x2, int y2) {if(x1 < 1) x1 = 1;
  if(y1 < 1) y1 = 1;
  if(x2 > n) x2 = n;
  if(y2 > n) y2 = n;
  return preSum[x2][y2] - preSum[x1 - 1][y2] - preSum[x2][y1 - 1] + preSum[x1 - 1][y1 - 1]; 
}

写在最初

大家好，我是往西汪，一位保持原创的新人博主。
如果本文对你有帮忙，请动动小手指点个赞????。你的反对是我创作路上的最大能源。谢谢大家！
也欢送来微信公众号【往西汪】找我游玩～当前会陆续在公众号里更新学习路线、基础知识和技术文章。