(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行每行输入两个数字表示nk1 ≤ T ≤ 1001 ≤ n ≤ 640 ≤ k 2^(n-1)输出描述输出T行表示答案输出 blue 表示字符是B输出 red 表示字符是R。备注输出字符串区分大小写请注意输出小写字符串不带双引号。用例输入51 02 13 24 65 8输出redredblueblueblue说明第 1 个字符串R - 第 0 个字符为R第 2 个字符串BR - 第 1 个字符为R第 3 个字符串RBBR - 第 2 个字符为B第 4 个字符串BRRBRBBR - 第 6 个字符为B第 5 个字符串RBBRBRRBBRRBRBBR - 第 8 个字符为B输入164 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到64k的取值范围为0到2^(n-1)-1最大值可达2^63-1即9223372036854775807这个最大值已经超出了JavaScript Number类型的安全整数范围-2^531到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) { // 题目没说异常如何处理因此我默认输入无异常比如n1的话则k只能取0 if (n 1n) { return red; } // n2的话则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算法源码需要注意的是本题中取值范围n1 ≤ n ≤ 64k0 ≤ 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 ≤ 640 ≤ 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): # 题目没说异常如何处理因此我默认输入无异常比如n1的话则k只能取0 if n 1: return red # n2的话则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)