A. 齐全平方数的尾巴

题目形容

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

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

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

示例1

输出

24

输入

true

阐明

1024 = 32 ∗ 3224 = 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]; }

写在最初

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