青島網(wǎng)頁制作設(shè)計(jì)營銷寧波如何做seo排名優(yōu)化
CSDN編程題-每日一練(2023-08-27)
- 一、題目名稱:異或和
- 二、題目名稱:生命進(jìn)化書
- 三、題目名稱:熊孩子拜訪
一、題目名稱:異或和
時(shí)間限制:1000ms內(nèi)存限制:256M
題目描述:
小張找到了一個(gè)整數(shù) N,他想問問你從 1 到 N 的所有不同整數(shù)的異或和是多少, 請(qǐng)你回答他的問題。
輸入描述:
第一行包含一個(gè)整數(shù) N (1 <= N <= 100000)。
輸出描述:
第一行輸出一個(gè)整數(shù), 代表從 1 到 N 的所有不同整數(shù)的異或和。
🚩 示例:
?? 示例1:
輸入
5
輸出
1
🔔 提示:
1 ^ 2 ^ 3 ^ 4 ^ 5 = 3 ^ 3 ^ 4 ^ 5 = 4 ^ 5 = 1。
🔔 解題思路:
根據(jù)異或的性質(zhì),可以得知一個(gè)數(shù)與自身異或的結(jié)果為0,即 a^a = 0。而對(duì)于任意一個(gè)數(shù) a,a^0 = a。因此,從 1 到 N 的所有整數(shù)的異或和等價(jià)于從 1 到 N-1 的所有整數(shù)的異或和再與 N 進(jìn)行異或運(yùn)算。
代碼1如下:
##輸入的整數(shù) N
N = int(input())##初始化異或和 xor_sum 為 0
xor_sum = 0##循環(huán)遍歷從 1 到 N-1 的所有整數(shù) i,并將 xor_sum 與 i 進(jìn)行異或運(yùn)算
for i in range(1, N):xor_sum ^= i
##將 xor_sum 與 N 進(jìn)行異或運(yùn)算,得到最終的異或和
xor_sum ^= N#輸出異或和xor_sum
print(xor_sum)
代碼2如下:
##計(jì)算從1到N的所有數(shù)字的異或和,并將結(jié)果輸出#include <stdio.h>int main() {int N;##變量xor_sum為0,用于保存異或和int xor_sum = 0;scanf("%d", &N);##使用for循環(huán)從1遍歷到N-1for (int i = 1; i < N; i++) {## 對(duì)變量xor_sum進(jìn)行異或運(yùn)算,將當(dāng)前循環(huán)變量i與xor_sum進(jìn)行異或,## 并將結(jié)果賦值給xor_sum,相當(dāng)于累計(jì)計(jì)算異或和xor_sum ^= i;}##將變量N與xor_sum進(jìn)行異或,并將結(jié)果賦值給xor_sum,相當(dāng)于將N也納入異或和的計(jì)算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)
}
二、題目名稱:生命進(jìn)化書
時(shí)間限制:1000ms內(nèi)存限制:256M
題目描述:
小A有一本生命進(jìn)化書,以一個(gè)樹形結(jié)構(gòu)記載了所有生物的演化過程。 為了探索和記錄其中的演化規(guī)律,小A提出了一種方法,可以以字符串的形式將其復(fù)刻下來,規(guī)則如下: 初始只有一個(gè)根節(jié)點(diǎn),表示演化的起點(diǎn),依次記錄 01 字符串中的字符, 如果記錄 0,則在當(dāng)前節(jié)點(diǎn)下添加一個(gè)子節(jié)點(diǎn),并將指針指向新添加的子節(jié)點(diǎn); 如果記錄 1,則將指針回退到當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)處。 現(xiàn)在需要應(yīng)用上述的記錄方法,復(fù)刻下它的演化過程。請(qǐng)返回能夠復(fù)刻演化過程的字符串中, 字典序最小的 01 字符串; 注意:節(jié)點(diǎn)指針最終可以停在任何節(jié)點(diǎn)上,不一定要回到根節(jié)點(diǎn)。
輸入描述:
parents[] 數(shù)組,其中,parents[i] 表示編號(hào) i 節(jié)點(diǎn)的父節(jié)點(diǎn)編號(hào)(根節(jié)點(diǎn)的父節(jié)點(diǎn)為 -1)。
輸出描述:
返回能夠復(fù)刻演化過程的字符串中, 字典序最小 的 01 字符串
🚩示例:
??示例1
輸入
* 輸入樣例1
[-1,0,0,2]
* 輸入樣例2
[-1,0,0,1,2,2]
輸出
* 輸出樣例1
00110
解釋:共存在 2 種記錄方案:
第 1 種方案為:0(記錄編號(hào) 1 的節(jié)點(diǎn)) -> 1(回退至節(jié)點(diǎn) 0) -> 0(記錄編號(hào) 2 的節(jié)點(diǎn)) -> 0((記錄編號(hào) 3 的節(jié)點(diǎn)))
第 2 種方案為:0(記錄編號(hào) 2 的節(jié)點(diǎn)) -> 0(記錄編號(hào) 3 的節(jié)點(diǎn)) -> 1(回退至節(jié)點(diǎn) 2) -> 1(回退至節(jié)點(diǎn) 0) -> 0(記錄編號(hào) 1 的節(jié)點(diǎn))
返回字典序更小的 ‘00110’
輸出樣例2
00101100
提示:
1 <= parents.length <= 10^4
-1 <= parents[i] < i (即父節(jié)點(diǎn)編號(hào)小于子節(jié)點(diǎn))
🔔 解題思路:
利用深度優(yōu)先搜索(DFS)的方式遍歷樹,并記錄每個(gè)節(jié)點(diǎn)的演化路徑,然后找出字典序最小的01字符串作為結(jié)果。
代碼1如下:
import sys
##設(shè)置遞歸深度限制為100000,防止遞歸過深導(dǎo)致堆棧溢出
sys.setrecursionlimit(100000) ##定義變量N為10000,表示節(jié)點(diǎn)數(shù)量的上限,可以避免數(shù)組或列表溢出的問題,并確保程序可以處理足夠大的生物演化樹
N = 10000##初始化變量n為0,表示當(dāng)前已經(jīng)添加的節(jié)點(diǎn)數(shù)量
n = 0
##創(chuàng)建一個(gè)大小為N的列表parents_node ,用于存儲(chǔ)每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)編號(hào)
parents_node = [0] * N
##創(chuàng)建一個(gè)大小為N的二維列表dp,用于存儲(chǔ)每個(gè)節(jié)點(diǎn)的狀態(tài)信息。dp[i][0]表示以節(jié)點(diǎn)i為根節(jié)點(diǎn)且不返回該節(jié)點(diǎn)的最小字符串,dp[i][1]表示以節(jié)點(diǎn)i為根節(jié)點(diǎn)且返回該節(jié)點(diǎn)的最小字符串
dp = [["", ""] for _ in range(N)]##創(chuàng)建一個(gè)大小為N的列表child_node ,用于存儲(chǔ)每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)列表
child_node = [[] for _ in range(N)]##遞歸函數(shù)dfs,用于遍歷樹并計(jì)算每個(gè)節(jié)點(diǎn)的最小字符串
def dfs(s):for v in child_node[s]: ##遍歷節(jié)點(diǎn)s的子節(jié)點(diǎn)列表,對(duì)每個(gè)子節(jié)點(diǎn)調(diào)用dfs函數(shù)dfs(v)
####計(jì)算以節(jié)點(diǎn)v為根節(jié)點(diǎn)且返回該節(jié)點(diǎn)的最小字符串時(shí),加上當(dāng)前節(jié)點(diǎn)s的值(0)和回退符號(hào)(1)構(gòu)成的字符串a = "0" + dp[v][1] + "1"
##計(jì)算以節(jié)點(diǎn)v為根節(jié)點(diǎn)且不返回該節(jié)點(diǎn)的最小字符串時(shí),加上當(dāng)前節(jié)點(diǎn)s的值(0)和子節(jié)點(diǎn)v的最小字符串(dp[v][0]和dp[v][1]中較小的一個(gè))構(gòu)成的字符串b = "0" + min(dp[v][0], dp[v][1])
##計(jì)算以節(jié)點(diǎn)s為根節(jié)點(diǎn)且返回該節(jié)點(diǎn)的最小字符串,要么是在a前面添加節(jié)點(diǎn)s的值和回退符號(hào),要么是在a后面添加節(jié)點(diǎn)u的值和回退符號(hào)new_return = min(a + dp[s][1], dp[s][1] + a)
##計(jì)算以節(jié)點(diǎn)s為根節(jié)點(diǎn)且不返回該節(jié)點(diǎn)的最小字符串,要么是在b前面添加節(jié)點(diǎn)s的值和子節(jié)點(diǎn)v的最小字符串,要么是在a后面添加節(jié)點(diǎn)s的值和子節(jié)點(diǎn)v的最小字符串new_no_return = min(dp[s][1] + b, a + dp[s][0])##更新節(jié)點(diǎn)s的不返回的最小字符串dp[s][0] = new_no_return
##更新節(jié)點(diǎn)s的返回的最小字符串dp[s][1] = new_return##生物演化樹的父節(jié)點(diǎn)列表,輸入的字符串
input_str = input()##字符串的長度
input_len = len(input_str)###初始化變量processed_number為0,表示已經(jīng)處理過的字符數(shù)量
processed_number = 0##函數(shù)getch,用于從輸入字符串中獲取字符
def getch():
##聲明processed_number是全局變量global processed_number
##每次調(diào)用getch函數(shù)后,processed_number加1processed_number += 1
## 返回輸入字符串中第processed_number個(gè)字符。return input_str[processed_number - 1]##函數(shù)read,從輸入字符串中讀取一個(gè)整數(shù)
def read():##初始化變量f為1,表示正數(shù)
## x = 0: 初始化變量x為0,用于存儲(chǔ)讀取的整數(shù)f = 1x = 0
###調(diào)用getch函數(shù)獲取一個(gè)字符char = getch()while char > '9' or char < '0': ##當(dāng)字符char 不是數(shù)字時(shí)循環(huán)執(zhí)行以下代碼塊if char == '-': ##如果字符char 是負(fù)號(hào),則將變量f設(shè)為-1f = -1##再次調(diào)用getch函數(shù)獲取一個(gè)字符char = getch()
##當(dāng)字符char 是數(shù)字時(shí)循環(huán)執(zhí)行以下代碼塊while char >= '0' and char <= '9':##將字符char轉(zhuǎn)換為對(duì)應(yīng)的數(shù)字,并將其加到變量x的末尾x = x * 10 + ord(char) - ord('0')## 再次調(diào)用getch函數(shù)獲取一個(gè)字符char = getch()
##返回讀取的整數(shù),如果之前設(shè)定了f為-1,則返回負(fù)數(shù)return f * x###初始化變量root_node_number為0,表示樹的根節(jié)點(diǎn)編號(hào)
root_node_number= 0
while processed_number < input_len: ##當(dāng)處理過的字符數(shù)量小于輸入字符串的長度時(shí)循環(huán)執(zhí)行以下代碼塊parents_node[n] = read() ##將讀取的整數(shù)作為第n個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)編號(hào)if parents_node[n] == -1: ##如果第n個(gè)節(jié)點(diǎn)沒有父節(jié)點(diǎn)(即是根節(jié)點(diǎn))root_node_number= n ##將當(dāng)前節(jié)點(diǎn)編號(hào)賦值給root_node_number作為根節(jié)點(diǎn)的編號(hào)else: ##否則,如果第n個(gè)節(jié)點(diǎn)有父節(jié)點(diǎn)child_node[parents_node[n]].append(n) ##在父節(jié)點(diǎn)的子節(jié)點(diǎn)列表中添加當(dāng)前節(jié)點(diǎn)n += 1 ##增加節(jié)點(diǎn)數(shù)量dfs(root_node_number) ##調(diào)用dfs函數(shù)遍歷樹,并計(jì)算每個(gè)節(jié)點(diǎn)的最小字符串
##打印根節(jié)點(diǎn)的不返回和返回的最小字符串中較小的一個(gè)
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]))
}
三、題目名稱:熊孩子拜訪
時(shí)間限制:1000ms內(nèi)存限制:256M
題目描述:
已知存在一個(gè)長度為n的整數(shù)序列A。 A中所有元素按照從小到達(dá)的順序進(jìn)行排序。 現(xiàn)在執(zhí)行操作倒置一段序列。 請(qǐng)找到A序列里的倒置子序列。
輸入描述:
第一行輸入整數(shù)n.(1<=n<=1000)。 第二行輸入n個(gè)整數(shù)。(1<=num<=10000)
輸出描述:
輸出被倒置的數(shù)列的左值,右值。 如果沒有輸出0 0
🚩示例:
??示例1
輸入
4
1 3 2 4
輸出
2 3
🔔 解題思路:
根據(jù)題目描述,我們需要找到整數(shù)序列A中的倒置子序列。假設(shè)整個(gè)A序列是按照從小到大的順序排列的,那么倒置子序列就是在這個(gè)有序序列中出現(xiàn)遞減的部分,我們需要找到這個(gè)遞減的部分的最左值和最右值。找到整數(shù)序列中的倒置子序列并輸出。如果沒有倒置子序列,則輸出0 0。
代碼1如下:
n = int(input().strip())
##按空格分割成多個(gè)子字符串,然后用列表推導(dǎo)式
## [int(item) for item in ...]將每個(gè)子字符串轉(zhuǎn)換成整數(shù),最后將這些整數(shù)放入列表中并賦值給變量arr
arr = [int(item) for item in input().strip().split()]def solution(n, arr):result = [] ##空列表result,用于存儲(chǔ)結(jié)果# 初始化right_val為0,用于保存右值right_val = 0# 初始化left_val為0,用于保存左值left_val = 0##初始化next_val為0,表示當(dāng)前遍歷到的元素next_val = 0##遍歷列表arr中的每個(gè)元素,賦值給變量itemfor item in arr:###如果next_val大于item且item大于right_val,即當(dāng)前元素比上一個(gè)元素小且比右值大if next_val > item and item > right_val:##將next_val賦值給right_val,更新右值為上一個(gè)元素right_val = next_val##將item賦值給left_val,更新左值為當(dāng)前元素left_val = item###如果next_val小于left_val且item大于right_val,即上一個(gè)元素比左值大且 當(dāng)前元素比右值大elif next_val < left_val and item > right_val:## 將next_val賦值給left_val,更新左值為上一個(gè)元素left_val = next_val##將item賦值給next_val,更新下一個(gè)元素為當(dāng)前元素next_val = item##將左值轉(zhuǎn)換為字符串,并添加到結(jié)果列表result中result.append(str(left_val))##將右值轉(zhuǎn)換為字符串,并添加到結(jié)果列表result中result.append(str(right_val))##如果結(jié)果列表為空if len(result) == 0:##將結(jié)果列表置為["0", "0"],表示沒有倒置子序列result = ["0", "0"]return result #返回結(jié)果列表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 循環(huán)從0遍歷到 n-1for (int i = 0; i < n; i++) {
##將數(shù)組 arr 在索引 i 處的元素賦值給變量 item,即當(dāng)前遍歷到的元素int item = arr[i];##如果 next_val 大于 item 并且 item 大于 right_valif (next_val > item && item > right_val) {##將 next_val 賦值給 right_val,更新右值為上一個(gè)數(shù)right_val = next_val;##將 item 賦值給 left_val,更新左值為當(dāng)前數(shù)left_val = item;##否則,如果 next_val 小于 left_val 并且 item 大于 right_val} else if (next_val < left_val && item > right_val) {##將 next_val 賦值給 left_val,更新左值為上一個(gè)數(shù)left_val = next_val;}##將當(dāng)前數(shù) item 賦值給 next_val,表示下一個(gè)循環(huán)的上一個(gè)數(shù)是當(dāng)前數(shù)next_val = item;}result[0] = left_val; ##將左值 left_val 存儲(chǔ)到結(jié)果數(shù)組 result 的第一個(gè)位置result[1] = right_val; ##將右值 right_val 存儲(chǔ)到結(jié)果數(shù)組 result 的第二個(gè)位置#如果結(jié)果數(shù)組的第一個(gè)和第二個(gè)位置都是0if (result[0] == 0 && result[1] == 0) {result[0] = 0; ##將結(jié)果數(shù)組的第1個(gè)位置設(shè)置為0result[1] = 0; ##將結(jié)果數(shù)組的第2個(gè)位置設(shè)置為0}
}int main() {int n;scanf("%d", &n);int arr[n];for (int i = 0; i < n; i++) {#讀取一個(gè)整數(shù)n,并將其賦值給數(shù)組 arr 在索引 i 處的元素scanf("%d", &arr[i]); }int result[2]; ##聲明一個(gè)大小為2的整數(shù)數(shù)組 result,用于保存結(jié)果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,表示當(dāng)前遍歷到的元素位置arr = input().split() # 讀取一行輸入并拆分為字符串列表##使用for循環(huán)迭代1到n之間的每個(gè)數(shù),賦值給變量i。范圍是左閉右開的,所以不包含n + 1
for i in range(1, n + 1):##如果當(dāng)前迭代到的是第一個(gè)數(shù)if i == 1:##將列表arr 的第一個(gè)元素轉(zhuǎn)換為整數(shù),并賦值給變量temptemp = int(arr[0])#如果當(dāng)前迭代到的不是第一個(gè)數(shù)else:##將變量temp的值賦給臨時(shí)變量tt = temp##將列表values中索引為i - 1的元素轉(zhuǎn)換為整數(shù),并賦值給變量temptemp = int(arr[i - 1])##如果上一個(gè)數(shù)t大于當(dāng)前數(shù)temp,即出現(xiàn)了倒置if t > temp:##如果next_val為0,表示當(dāng)前是第一個(gè)倒置if next_val == 0:##將上一個(gè)數(shù)t賦值給right_val,更新右值為上一個(gè)數(shù)right_val = t##將當(dāng)前數(shù)temp賦值給left_val,更新左值為當(dāng)前數(shù)left_val = temp##將next_val設(shè)為1,表示已經(jīng)找到了第一個(gè)倒置next_val = 1#如果已經(jīng)找到了第一個(gè)倒置else:##將當(dāng)前數(shù)temp賦值給left_val,更新左值為當(dāng)前數(shù)left_val = temp
##打印輸出左值和右值
print(left_val , right_val )