番禺做网站平台,做ppt常用图片网站有哪些,汉中网站开发,网站高级感CSDN编程题-每日一练#xff08;2023-08-27#xff09; 一、题目名称#xff1a;异或和二、题目名称#xff1a;生命进化书三、题目名称#xff1a;熊孩子拜访 一、题目名称#xff1a;异或和 时间限制#xff1a;1000ms内存限制#xff1a;256M 题目描述#xff1a; … 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。而对于任意一个数 aa^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.hint 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 fmtfunc 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 (fmtstrings
)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] 1b : 0 min(dp[v][0], dp[v][1])new_return : min(adp[s][1], dp[s][1]a)new_no_return : min(dp[s][1]b, adp[s][0])dp[s][0] new_no_returndp[s][1] new_return}
}func getch() byte {char : input_str[processed_num]processed_numreturn 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.(1n1000)。 第二行输入n个整数。(1num10000) 输出描述 输出被倒置的数列的左值右值。 如果没有输出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.hvoid 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 )
