(100分)- 对称美学（Java JS Python）-平芜编程栈

(100分)- 对称美学（Java & JS & Python）

题目描述

对称就是最大的美学，现有一道关于对称字符串的美学。已知：

第1个字符串：R
第2个字符串：BR
第3个字符串：RBBR
第4个字符串：BRRBRBBR
第5个字符串：RBBRBRRBBRRBRBBR

相信你已经发现规律了，没错！就是第 i 个字符串 = 第 i - 1 号字符串取反 + 第 i - 1 号字符串；

取反（R->B, B->R）;

现在告诉你n和k，让你求得第n个字符串的第k个字符是多少。（k的编号从0开始）

输入描述

第一行输入一个T，表示有T组用例；

解析来输入T行，每行输入两个数字，表示n，k

1 ≤ T ≤ 100；
1 ≤ n ≤ 64；
0 ≤ k ＜ 2^(n-1)；

输出描述

输出T行表示答案；

输出 "blue" 表示字符是B；

输出 "red" 表示字符是R。

备注：输出字符串区分大小写，请注意输出小写字符串，不带双引号。

用例

输入	5 1 0 2 1 3 2 4 6 5 8
输出	`red` `red` `blue` `blue` `blue`
说明	第 1 个字符串：R -> 第 0 个字符为R 第 2 个字符串：BR -> 第 1 个字符为R 第 3 个字符串：RBBR -> 第 2 个字符为B 第 4 个字符串：BRRBRBBR -> 第 6 个字符为B 第 5 个字符串：RBBRBRRBBRRBRBBR -> 第 8 个字符为B

输入	1 64 73709551616
输出	red
说明	无

题目解析

如图所示，第1至第6个字符串的长度依次递增，其中第6个已经相当长。题目要求最多计算到第64个字符串，其长度将达到惊人的2^63（即2^(n-1)）。显然，如果采用字符串存储方式，如此庞大的数据量必然会导致内存溢出。因此，任何需要缓存字符串的操作都应严格避免。

我们只能找规律，来通过规律推导出第n个字符串的第k个字符。

那么规律是啥呢？

如图所示（黄框部分），可以观察到：

每个字符串的后半部分都与前一个字符串完全相同。具体来说：

第6个字符串后半部分 = 第5个字符串
第5个字符串后半部分 = 第4个字符串
...
第2个字符串后半部分 = 第1个字符串

因此，当需要查找第n个字符串中位置k的字符时（记为get(n,k)），若k位于后半部分，则可递归转化为get(n-1, k-2^(n-2))。最终递归到基础情况：

第1个字符串为"R"
第2个字符串为"BR"

那么如果我们要找到第k个字符串，位于第n个字符串的前半部分呢？

可以发现，其实get(n,k)，如果k <= 2^(n-2) ，则相当于 get(n-1, k) 的颜色取反。

建议使用JS的同学遇到这题，可以采用偷分策略，即不需要任何算法，直接输入red或者blue，选择分值更高。

JavaScript算法源码

需要注意本题的参数范围：

n的取值范围为1到64
k的取值范围为0到2^(n-1)-1，最大值可达2^63-1（即9223372036854775807）

这个最大值已经超出了JavaScript Number类型的安全整数范围（-2^53+1到2^53-1），超出部分会导致精度丢失，计算结果不准确。例如：

在这种情况下，建议使用BigInt类型替代Number来处理大数值。需要注意的是，BigInt只能与同类型数据进行运算，因此需要将所有数值统一转换为BigInt类型。对于数值字面量，只需在数字后添加"n"后缀即可完成转换，例如1表示Number类型，而1n则表示BigInt类型的数值1。

/* JavaScript Node ACM模式 控制台输入获取 */ const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const lines = []; let t; rl.on("line", (line) => { lines.push(line); if (lines.length === 1) { t = lines[0] - 0; } if (t && lines.length === t + 1) { lines.shift(); const arr = lines.map((line) => line.split(" ").map(BigInt)); getResult(arr); lines.length = 0; } }); function getResult(arr) { for (let [n, k] of arr) { console.log(getNK(n, k)); } } function getNK(n, k) { // 题目没说异常如何处理，因此我默认输入无异常，比如n=1的话，则k只能取0 if (n === 1n) { return "red"; } // n=2的话，则k只能取0或1 if (n === 2n) { if (k === 0n) return "blue"; else return "red"; } // 第n个字符串的一半长度half let half = 1n << (n - 2n); if (k >= half) { return getNK(n - 1n, k - half); } else { return getNK(n - 1n, k) === "red" ? "blue" : "red"; } }

Java算法源码

需要注意的是，本题中

取值范围：
n：1 ≤ n ≤ 64
k：0 ≤ k < 2^(n-1)

注意：

k的最大值为2^63 - 1（即9223372036854775807），恰好是Java long类型的最大值，因此不会出现整型溢出问题所有数值必须使用long类型存储

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); double[][] arr = new double[t][2]; for (int i = 0; i < t; i++) { arr[i][0] = sc.nextDouble(); arr[i][1] = sc.nextDouble(); } getResult(arr); } public static void getResult(double[][] arr) { for (double[] nk : arr) { System.out.println(getNK(nk[0], nk[1])); } } public static String getNK(double n, double k) { if (n == 1) { return "red"; } if (n == 2) { if (k == 0) return "blue"; else return "red"; } double half = Math.pow(2, n - 2); if (k >= half) { return getNK(n - 1, k - half); } else { return "red".equals(getNK(n - 1, k)) ? "blue" : "red"; } } }

Python算法源码

需要注意的是，本题中

1 ≤ n ≤ 64；
0 ≤ k ＜ 2^(n-1)；

也就说 k 最大值可以取到 2^63 - 1，即9223372036854775807

即Python3支持任意大的整数运算。

因为本题中不涉及除法，因此无需额外处理。

# 输入获取 import math t = int(input()) # 注意这里需要转float arr = [list(map(float, input().split())) for i in range(t)] # 算法入口 def getResult(arr): for n, k in arr: print(getNK(n, k)) def getNK(n, k): # 题目没说异常如何处理，因此我默认输入无异常，比如n=1的话，则k只能取0 if n == 1: return "red" # n=2的话，则k只能取0或1 if n == 2: if k == 0: return "blue" else: return "red" # 第n个字符串的一半长度half half = math.pow(2, n - 2) if k >= half: return getNK(n - 1, k - half) else: return "blue" if getNK(n - 1, k) == "red" else "red" # 调用算法 getResult(arr)