2025年4月8號 19：00 - 20：40

題型：

基礎 - 單選 7題 21分

基礎 - 多選 5題 15分

Java基礎 - 單選 2題 6分

Java基礎 - 多選 1題 3分

編程題（工程） 1題 20分

編程題（共用） 2題 35分

編程題（工程）：

整體判斷：

題目描述：

對于給定的k個數(shù)組，第i個數(shù)組由ni個整數(shù)組成。現(xiàn)在想知道，是否存在這樣兩個不同的數(shù)組，使得這兩個數(shù)組各自刪除一個整數(shù)后，這兩個數(shù)組剩下的元素和相等。

輸入：

第一行輸入一個整數(shù)，代表數(shù)據(jù)組數(shù)。

每組測試數(shù)據(jù)：第一行輸入一個整數(shù)k，代表有k個數(shù)組。

第i個數(shù)組：第一行輸入一個整數(shù)n，代表i數(shù)組的元素個數(shù)。

第二行輸入n個整數(shù)，即i數(shù)組。

輸出：

存在兩個數(shù)組使得兩個數(shù)組各刪除一個整數(shù)后，這兩個數(shù)組剩下的元素和相等，則輸出YES，反之輸出NO。

例如：
輸入：
2
2
5
2 3 1 3 2
6
1 1 2 2 2 1
2
2
8 9
9
2 10 20 6 18 6 2 1 8 7
輸出：
YES
NO

編程題（共用）：

1.小苯的字符串構造

題目描述：

小苯給了你一個正整數(shù)n，他希望你構造一個僅包含小寫英文字母'a'到'z'長度為n的字符串s，滿足s的所有本質不同連續(xù)子串中，長度為奇數(shù)的字串恰好出現(xiàn)了奇數(shù)次。

本質不同連續(xù)子串：指的是從一個字符串中提取的所有連續(xù)子串中，按內容相同性去重后得到的集合。在這個集合中，如果有兩個子串在字符序列上完全相同，那么他們被視為“本質相同”，只記作一個。

例如，對字符串“aa”。所有可能的連續(xù)子串為：從位置1：“a”，“aa”；從位置2：“a”，其中“a”出現(xiàn)兩個，但本質不同連續(xù)子串只記作“a”，“aa”兩個。

輸入：

第一行包含一個正整數(shù)T（1≤T≤100），代表T組數(shù)據(jù)

接下來T組數(shù)據(jù)在單獨一行輸入一個正整數(shù)n（1≤n≤2000）

例如：
輸入：
1
4
輸出：
live

2.小紅的子樹操作

題目描述：

在神秘莫測的比特王國中，流傳著這樣一個傳說——在王國深處生長著一棵蘊含天機的神奇大樹。這棵樹由n個節(jié)點構成，1號點是根節(jié)點，每個節(jié)點都記錄著一段古老的符文，初始每個節(jié)點的符文為ai。傳說只有將樹上所有節(jié)點的符文調和為零，才能開啟通往失落寶藏的大門。聰明勇敢的小紅接受了挑戰(zhàn)，她掌握了一套奇特的操作法則，能夠對樹中部分節(jié)點施法改變其符文，但每次施法都需要付出一定代價。

具體來說，小紅可以進行如下操作：

• 選擇樹中的任一節(jié)點 v 及一個非負整數(shù) x 。
• 將 v 以及 v 的子樹中所有與 v 距離為偶數(shù)的節(jié)點的權值進行異或操作，即更新為：a[u] = a[u] ^ x 。
• 每進行一次此操作就產生 x 的代價。

請問小紅至少需要花費多少總代價，才能使得所有節(jié)點的符文權值均變?yōu)?？

名詞解釋：在一棵樹中，對于任一節(jié)點 v ，以 v 為根節(jié)點并包含所有從 v 出發(fā)可以達到的后代節(jié)點（包括 v 自身）的集合構成了 v 的子樹。在樹中，任意兩個節(jié)點之間僅存在一條簡單路徑，該路徑上所經(jīng)過的邊的數(shù)目定義為這兩個節(jié)點之間的距離。

輸入：

第一行包含一個整數(shù) n ，表示節(jié)點的數(shù)量。

第二行輸入 n 個整數(shù) a1，a2，……，an ，表示各個節(jié)點初始權值。

接下來第 n-1 行輸入兩個整數(shù) u，v ，表示樹中的一條邊，所給邊構成一棵以1為根的樹。

1≤ n ≤2×10^5

0≤ ai ≤10^9

輸出：

輸出一個整數(shù)，表示將所有節(jié)點權值變?yōu)?的最小總代價。

例如：
輸入：
5
1 4 3 5 5
1 2
2 3
3 4
3 5
輸出：
9
解析：
先選節(jié)點1，花費1代價，使得節(jié)點變?yōu)閇0,4,2,5,5];
再選節(jié)點2，花費4代價，使得節(jié)點變?yōu)閇0,0,2,1,1];
再選節(jié)點3，花費2代價，使得節(jié)點變?yōu)閇0,0,0,1,1];
再選節(jié)點4，花費1代價，使得節(jié)點變?yōu)閇0,0,0,0,1];
再選節(jié)點5，花費1代價，使得節(jié)點變?yōu)閇0,0,0,0,0];
因此輸出為 1 + 4 + 2 + 1 + 1 = 9