CSDN每日一练 |『异或和』『生命进化书』『熊孩子拜访』2023-08-27

一、题目名称：异或和

时间限制：1000ms内存限制：256M

题目描述：

小张找到了一个整数 N，他想问问你从 1 到 N 的所有不同整数的异或和是多少， 请你回答他的问题。

输入描述：

第一行包含一个整数 N (1 <= N <= 100000)。

输出描述：

第一行输出一个整数， 代表从 1 到 N 的所有不同整数的异或和。

🚩 示例：

✔️ 示例1:

输入
5

输出
1

🔔 提示：
1 ^ 2 ^ 3 ^ 4 ^ 5 = 3 ^ 3 ^ 4 ^ 5 = 4 ^ 5 = 1。

🔔 解题思路：
根据异或的性质，可以得知一个数与自身异或的结果为0，即 a^a = 0。而对于任意一个数 a，a^0 = a。因此，从 1 到 N 的所有整数的异或和等价于从 1 到 N-1 的所有整数的异或和再与 N 进行异或运算。

代码1如下：

##输入的整数 N
N = int(input())##初始化异或和 xor_sum 为 0
xor_sum = 0##循环遍历从 1 到 N-1 的所有整数 i，并将 xor_sum 与 i 进行异或运算
for i in range(1, N):xor_sum ^= i
##将 xor_sum 与 N 进行异或运算，得到最终的异或和
xor_sum ^= N#输出异或和xor_sum
print(xor_sum)

代码2如下：

##计算从1到N的所有数字的异或和，并将结果输出#include <stdio.h>int main() {int N;##变量xor_sum为0，用于保存异或和int xor_sum = 0;scanf("%d", &N);##使用for循环从1遍历到N-1for (int i = 1; i < N; i++) {## 对变量xor_sum进行异或运算，将当前循环变量i与xor_sum进行异或，## 并将结果赋值给xor_sum，相当于累计计算异或和xor_sum ^= i;}##将变量N与xor_sum进行异或，并将结果赋值给xor_sum，相当于将N也纳入异或和的计算xor_sum ^= N;printf("%d\n", xor_sum);return 0;
}

代码3如下：

#include <iostream>
using namespace std;int main() {int N;cin >> N;int xor_sum = 0;for (int i = 1; i < N; i++) {xor_sum ^= i;}xor_sum ^= N;cout << xor_sum << endl;return 0;
}

代码4如下：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int N = scanner.nextInt();int xor_sum = 0;for (int i = 1; i < N; i++) {xor_sum ^= i;}xor_sum ^= N;System.out.println(xor_sum);}
}

代码5如下：

package mainimport "fmt"func main() {var N intfmt.Scan(&N)xor_sum := 0for i := 1; i < N; i++ {xor_sum ^= i}xor_sum ^= Nfmt.Println(xor_sum)
}

二、题目名称：生命进化书

时间限制：1000ms内存限制：256M

题目描述:

小A有一本生命进化书，以一个树形结构记载了所有生物的演化过程。 为了探索和记录其中的演化规律，小A提出了一种方法，可以以字符串的形式将其复刻下来，规则如下： 初始只有一个根节点，表示演化的起点，依次记录 01 字符串中的字符， 如果记录 0，则在当前节点下添加一个子节点，并将指针指向新添加的子节点； 如果记录 1，则将指针回退到当前节点的父节点处。 现在需要应用上述的记录方法，复刻下它的演化过程。请返回能够复刻演化过程的字符串中， 字典序最小的 01 字符串； 注意：节点指针最终可以停在任何节点上，不一定要回到根节点。

输入描述：

parents[] 数组，其中，parents[i] 表示编号 i 节点的父节点编号(根节点的父节点为 -1)。

输出描述：

返回能够复刻演化过程的字符串中， 字典序最小 的 01 字符串

🚩示例：

✔️示例1

输入
* 输入样例1
[-1,0,0,2]
* 输入样例2
[-1,0,0,1,2,2]

输出
* 输出样例1
00110

解释：共存在 2 种记录方案：
第 1 种方案为：0(记录编号 1 的节点) -> 1(回退至节点 0) -> 0(记录编号 2 的节点) -> 0((记录编号 3 的节点))
第 2 种方案为：0(记录编号 2 的节点) -> 0(记录编号 3 的节点) -> 1(回退至节点 2) -> 1(回退至节点 0) -> 0(记录编号 1 的节点)
返回字典序更小的 ‘00110’

输出样例2
00101100

提示：

1 <= parents.length <= 10^4

-1 <= parents[i] < i (即父节点编号小于子节点)

🔔 解题思路：

利用深度优先搜索（DFS）的方式遍历树，并记录每个节点的演化路径，然后找出字典序最小的01字符串作为结果。

代码1如下：

import sys
##设置递归深度限制为100000，防止递归过深导致堆栈溢出
sys.setrecursionlimit(100000)  ##定义变量N为10000，表示节点数量的上限,可以避免数组或列表溢出的问题，并确保程序可以处理足够大的生物演化树
N = 10000##初始化变量n为0，表示当前已经添加的节点数量
n = 0
##创建一个大小为N的列表parents_node ，用于存储每个节点的父节点编号
parents_node = [0] * N
##创建一个大小为N的二维列表dp，用于存储每个节点的状态信息。dp[i][0]表示以节点i为根节点且不返回该节点的最小字符串，dp[i][1]表示以节点i为根节点且返回该节点的最小字符串
dp = [["", ""] for _ in range(N)]##创建一个大小为N的列表child_node ，用于存储每个节点的子节点列表
child_node = [[] for _ in range(N)]##递归函数dfs，用于遍历树并计算每个节点的最小字符串
def dfs(s):for v in child_node[s]:  ##遍历节点s的子节点列表，对每个子节点调用dfs函数dfs(v)
####计算以节点v为根节点且返回该节点的最小字符串时，加上当前节点s的值（0）和回退符号（1）构成的字符串a = "0" + dp[v][1] + "1"  
##计算以节点v为根节点且不返回该节点的最小字符串时，加上当前节点s的值（0）和子节点v的最小字符串（dp[v][0]和dp[v][1]中较小的一个）构成的字符串b = "0" + min(dp[v][0], dp[v][1])
##计算以节点s为根节点且返回该节点的最小字符串，要么是在a前面添加节点s的值和回退符号，要么是在a后面添加节点u的值和回退符号new_return = min(a + dp[s][1], dp[s][1] + a)
##计算以节点s为根节点且不返回该节点的最小字符串，要么是在b前面添加节点s的值和子节点v的最小字符串，要么是在a后面添加节点s的值和子节点v的最小字符串new_no_return = min(dp[s][1] + b, a + dp[s][0])##更新节点s的不返回的最小字符串dp[s][0] = new_no_return
##更新节点s的返回的最小字符串dp[s][1] = new_return##生物演化树的父节点列表,输入的字符串
input_str = input()##字符串的长度
input_len = len(input_str)###初始化变量processed_number为0，表示已经处理过的字符数量
processed_number = 0##函数getch，用于从输入字符串中获取字符
def getch():
##声明processed_number是全局变量global processed_number
##每次调用getch函数后，processed_number加1processed_number += 1
## 返回输入字符串中第processed_number个字符。return input_str[processed_number - 1]##函数read，从输入字符串中读取一个整数
def read():##初始化变量f为1，表示正数
##  x = 0: 初始化变量x为0，用于存储读取的整数f = 1x = 0
###调用getch函数获取一个字符char = getch()while char > '9' or char < '0':  ##当字符char 不是数字时循环执行以下代码块if char == '-':  ##如果字符char 是负号，则将变量f设为-1f = -1##再次调用getch函数获取一个字符char = getch()
##当字符char 是数字时循环执行以下代码块while char >= '0' and char <= '9':##将字符char转换为对应的数字，并将其加到变量x的末尾x = x * 10 + ord(char) - ord('0')## 再次调用getch函数获取一个字符char = getch()
##返回读取的整数，如果之前设定了f为-1，则返回负数return f * x###初始化变量root_node_number为0，表示树的根节点编号
root_node_number= 0
while processed_number < input_len:  ##当处理过的字符数量小于输入字符串的长度时循环执行以下代码块parents_node[n] = read()  ##将读取的整数作为第n个节点的父节点编号if parents_node[n] == -1:  ##如果第n个节点没有父节点（即是根节点）root_node_number= n  ##将当前节点编号赋值给root_node_number作为根节点的编号else:  ##否则，如果第n个节点有父节点child_node[parents_node[n]].append(n)  ##在父节点的子节点列表中添加当前节点n += 1  ##增加节点数量dfs(root_node_number)  ##调用dfs函数遍历树，并计算每个节点的最小字符串
##打印根节点的不返回和返回的最小字符串中较小的一个
print(min(dp[root_node_number][0], dp[root_node_number][1]))

代码2如下：

package mainimport ("fmt""strings"
)const N = 10000var (n             intparents_node  [N]intdp            [N][2]stringchild_node    [N][]intinput_str     stringprocessed_num int
)func dfs(s int) {for _, v := range child_node[s] {dfs(v)a := "0" + dp[v][1] + "1"b := "0" + min(dp[v][0], dp[v][1])new_return := min(a+dp[s][1], dp[s][1]+a)new_no_return := min(dp[s][1]+b, a+dp[s][0])dp[s][0] = new_no_returndp[s][1] = new_return}
}func getch() byte {char := input_str[processed_num]processed_num++return char
}func read() int {f := 1x := 0char := getch()for char > '9' || char < '0' {if char == '-' {f = -1}char = getch()}for char >= '0' && char <= '9' {x = x*10 + int(char-'0')char = getch()}return f * x
}func min(a, b string) string {if a < b {return a}return b
}func main() {fmt.Scanln(&input_str)input_str = strings.TrimSpace(input_str)input_len := len(input_str)root_node_number := 0for processed_num < input_len {parents_node[n] = read()if parents_node[n] == -1 {root_node_number = n} else {child_node[parents_node[n]] = append(child_node[parents_node[n]], n)}n++}dfs(root_node_number)fmt.Println(min(dp[root_node_number][0], dp[root_node_number][1]))
}

三、题目名称：熊孩子拜访

时间限制：1000ms内存限制：256M

题目描述:

已知存在一个长度为n的整数序列A。 A中所有元素按照从小到达的顺序进行排序。 现在执行操作倒置一段序列。 请找到A序列里的倒置子序列。

输入描述：

第一行输入整数n.(1<=n<=1000)。 第二行输入n个整数。(1<=num<=10000)

输出描述：

输出被倒置的数列的左值，右值。 如果没有输出0 0

🚩示例：

✔️示例1
输入
4
1 3 2 4

输出
2 3

🔔 解题思路：

根据题目描述，我们需要找到整数序列A中的倒置子序列。假设整个A序列是按照从小到大的顺序排列的，那么倒置子序列就是在这个有序序列中出现递减的部分，我们需要找到这个递减的部分的最左值和最右值。找到整数序列中的倒置子序列并输出。如果没有倒置子序列，则输出0 0。

代码1如下：

n = int(input().strip())
##按空格分割成多个子字符串，然后用列表推导式
## [int(item) for item in ...]将每个子字符串转换成整数，最后将这些整数放入列表中并赋值给变量arr
arr = [int(item) for item in input().strip().split()]def solution(n, arr):result = []  ##空列表result，用于存储结果# 初始化right_val为0，用于保存右值right_val = 0# 初始化left_val为0，用于保存左值left_val = 0##初始化next_val为0，表示当前遍历到的元素next_val = 0##遍历列表arr中的每个元素，赋值给变量itemfor item in arr:###如果next_val大于item且item大于right_val，即当前元素比上一个元素小且比右值大if next_val > item and item > right_val:##将next_val赋值给right_val，更新右值为上一个元素right_val = next_val##将item赋值给left_val，更新左值为当前元素left_val = item###如果next_val小于left_val且item大于right_val，即上一个元素比左值大且 当前元素比右值大elif next_val < left_val and item > right_val:## 将next_val赋值给left_val，更新左值为上一个元素left_val = next_val##将item赋值给next_val，更新下一个元素为当前元素next_val = item##将左值转换为字符串，并添加到结果列表result中result.append(str(left_val))##将右值转换为字符串，并添加到结果列表result中result.append(str(right_val))##如果结果列表为空if len(result) == 0:##将结果列表置为["0", "0"]，表示没有倒置子序列result = ["0", "0"]return result  #返回结果列表result = solution(n, arr)
print(" ".join(result))

代码2如下：

#include <stdio.h>void solution(int n, int arr[], int result[]) {int right_val = 0;int left_val = 0;int next_val = 0;
##使用 for 循环从0遍历到 n-1for (int i = 0; i < n; i++) {
##将数组 arr 在索引 i 处的元素赋值给变量 item，即当前遍历到的元素int item = arr[i];##如果 next_val 大于 item 并且 item 大于 right_valif (next_val > item && item > right_val) {##将 next_val 赋值给 right_val，更新右值为上一个数right_val = next_val;##将 item 赋值给 left_val，更新左值为当前数left_val  = item;##否则，如果 next_val 小于 left_val 并且 item 大于 right_val} else if (next_val < left_val && item > right_val) {##将 next_val 赋值给 left_val，更新左值为上一个数left_val = next_val;}##将当前数 item 赋值给 next_val，表示下一个循环的上一个数是当前数next_val = item;}result[0] = left_val; ##将左值 left_val 存储到结果数组 result 的第一个位置result[1] = right_val; ##将右值 right_val 存储到结果数组 result 的第二个位置#如果结果数组的第一个和第二个位置都是0if (result[0] == 0 && result[1] == 0) {result[0] = 0; ##将结果数组的第1个位置设置为0result[1] = 0; ##将结果数组的第2个位置设置为0}
}int main() {int n;scanf("%d", &n);int arr[n];for (int i = 0; i < n; i++) {#读取一个整数n，并将其赋值给数组 arr 在索引 i 处的元素scanf("%d", &arr[i]);     }int result[2]; ##声明一个大小为2的整数数组 result，用于保存结果solution(n, arr, result);printf("%d %d\n", result[0], result[1]);return 0;
}

代码3如下：

n = int(input())
left_val = 0  ##初始化变量left_val为0，用于保存左值
right_val = 0  ##初始化变量right_val为0，用于保存右值
next_val = 0  ##初始化变量next_val为0，表示当前遍历到的元素位置arr = input().split()  # 读取一行输入并拆分为字符串列表##使用for循环迭代1到n之间的每个数，赋值给变量i。范围是左闭右开的，所以不包含n + 1
for i in range(1, n + 1):##如果当前迭代到的是第一个数if i == 1:##将列表arr 的第一个元素转换为整数，并赋值给变量temptemp = int(arr[0])#如果当前迭代到的不是第一个数else:##将变量temp的值赋给临时变量tt = temp##将列表values中索引为i - 1的元素转换为整数，并赋值给变量temptemp = int(arr[i - 1])##如果上一个数t大于当前数temp，即出现了倒置if t > temp:##如果next_val为0，表示当前是第一个倒置if next_val == 0:##将上一个数t赋值给right_val，更新右值为上一个数right_val = t##将当前数temp赋值给left_val，更新左值为当前数left_val = temp##将next_val设为1，表示已经找到了第一个倒置next_val = 1#如果已经找到了第一个倒置else:##将当前数temp赋值给left_val，更新左值为当前数left_val = temp
##打印输出左值和右值
print(left_val , right_val )