2023-08-16 19:40 已編輯河南理工大學(xué) Unity3D客戶端發(fā)布于河南

關(guān)注

題解 | 2023河南萌新聯(lián)賽第（六）場：河南理工大學(xué) 題解

簡單的異或

https://ac.nowcoder.com/acm/contest/63602/A

A-簡單的異或

? 題意就是求一個 $x$ ,使得區(qū)間內(nèi)每一個元素與 $x$ 異或后的總和最大

? 先考慮單個元素與 $x$ 異或后最大，根據(jù)異或的性質(zhì)，容易得到 $x$ 應(yīng)該和 $a$ 的每一位都相反，才能使得異或值最大。

? 考慮區(qū)間大小大于等于 $2$ ，假如區(qū)間內(nèi)每個元素的二進(jìn)制第 $i$ 位相同(從右往左數(shù))，比如全為 $1$ ，那么當(dāng) $x$ 的第 $i$ 位取相反值 $0$ 時，該位對于最后的總和貢獻(xiàn)就是 $n*2^{i-1}$ ( $n$ 表示元素的個數(shù))，每有一個元素的二進(jìn)制第 $i$ 位為 $0$ ，該位的貢獻(xiàn)就會減少 $2^{i-1}$ ，當(dāng)有超過 $n/2$ 的元素該位上為 $0$ 時， $x$ 的該位上取1貢獻(xiàn)更大

? 所以貪心考慮 $x$ 上每一位取值 $0/1$ 的貢獻(xiàn)的多少，選擇貢獻(xiàn)大的即可

? 區(qū)間內(nèi)第 $i$ 位上 $1$ 的個數(shù)與 $0$ 的個數(shù)，當(dāng) $1$ 多時 $x$ 的第 $i$ 位上取 $0$ ， $0$ 多則取 $1$ 。

? 特別的當(dāng) $1$ 和 $0$ 的數(shù)量相同時，因?yàn)轭}目要求輸出較小值，取 $0$ 即可

? 暴力計(jì)算區(qū)間內(nèi)第i位上的1個數(shù)求解復(fù)雜度 $O(n^2)$

? 利用前綴和優(yōu)化求解復(fù)雜度 $O(n)$

B-這是dp題嗎

題目思路：

先假設(shè)最后一層的中間點(diǎn)是 $mid$ ，那么根據(jù)題意往左或往右走次數(shù)之差不超過 $k$ 次，那么走到最后一層，他的落腳點(diǎn)一定在 $[mid-k,mid k]$ 之間，那么問的就是走到最后一層在區(qū)間 $[mid-k,mid k]$ 之間最大值是多少。假設(shè)狀態(tài)方程是 $f[i][j]$ ，第 $i$ 層在 $j$ 這個位置所取得的最大值，根據(jù)題意可以往下走，往右下和左下走，那么狀態(tài)方程轉(zhuǎn)移為 $f[i 1][j 1]=max(f[i 1][j 1],f[i][j] a[i 1][j 1])$

$f[i 1][j]=max(f[i 1][j],f[i][j] a[i 1][j])$

$f[i 1][j-1]=max(f[i 1][j-1],f[i][j] a[i 1][j-1])$

? 最后的答案就是在取最大值 $f[n][x], mid-k\leq x \leq mid k$

C-旅游

題目思路：

? 很明顯題中給的是一棵樹，題目中要求的是把每一個節(jié)點(diǎn)作為出發(fā)點(diǎn)得到的期望值中的最大值，所以可以使用換根DP。

? 我們首先先求一個節(jié)點(diǎn)作為出發(fā)點(diǎn)的期望值，定義 $f(x)$ 為以 $x$ 為根節(jié)點(diǎn)的子樹所能得到的期望值，容易想到狀態(tài)轉(zhuǎn)移方程 $f(x)=\sum_{i=1}^{son[x]}\frac{f(son_i) 1}{son[x]}$ ，其中 $son[x]，son_i$ 分別是節(jié)點(diǎn) $x$ 的孩子數(shù)量，和第 $i$ 個孩子節(jié)點(diǎn)。這樣我們就可以求得以某一節(jié)點(diǎn)為出發(fā)點(diǎn)的期望值。

然后使用換根DP求每個節(jié)點(diǎn)作為出發(fā)點(diǎn)的期望值。定義 $dp[x]$ 為以 $x$ 為出發(fā)點(diǎn)所得期望值， $son[x]$ 為點(diǎn) $x$ 的孩子數(shù)量， $siz[x]$ 為以 $x$ 為根節(jié)點(diǎn)的子樹走各個分支所得路程之和，即 $\sum_{i=1}^{son[x]}f(son_i) 1$ 。

狀態(tài)轉(zhuǎn)移方程可以這樣考慮 $dp[j]=\frac{各個分支路程之和}{孩子個數(shù)}$ 。把根節(jié)點(diǎn)從 $u$ 換到 $j$ ，然后 $u$ 就變成了 $j$ 的一個分***么這個分支的路程就是 $\frac {siz[u]-f[j]-1}{son[u]-1} 1$ ，分支總路程就是 $(siz[j] \frac{siz[u]-f[j]-1}{son[u]-1} 1)$ ，然后孩子個數(shù)要 $1$ ，就是 $son[j] 1$ 。

? 所以狀態(tài)轉(zhuǎn)移方程即為

? $dp[j]=\frac{(siz[j] \frac{siz[u]-f[j]-1}{son[u]-1} 1)}{son[j] 1}$ 。

? 狀態(tài)轉(zhuǎn)移完成后， $j$ 成為了根節(jié)點(diǎn)，此時 $siz[j]與son[j]$ 均發(fā)生變化，所以要更新 $siz[j]和son[j]$ ，即:

siz[j] =\frac {siz[u]-f[j]-1}{son[u]-1} 1，son[j]

? 當(dāng)然由于 $son[u]-1$ 可能為0，所以我們還需要特判一下，如果 $son[u]-1==0$ 時， $dp[j]=\frac{siz[j] 1}{son[j] 1}$ ，此時 $siz[j],son[j]$ 分別更新為 $siz[j] 1,son[j] 1$ 。

D-買餅干的小Y

題目思路：

? 先暴力依次讓力氣不為1的人去拿餅干，能拿完則答案就是去拿餅干的人數(shù)，若沒拿完，則剩下的每一個餅干都需要一個人拿，總答案就是體力不為1的人數(shù)加上剩余餅干的數(shù)量。

E-不愛吃早飯的小Y

題目思路:

? 本題僅考查簡單的 $SG$ 函數(shù)的套用。對于單堆餅干暴力或者遞歸求出該堆的 $SG$ 函數(shù)值，如果為0，先手必?cái)?，反之先手必勝。對于n堆游戲，總游戲的合就是每個單堆的 $SG$ 函數(shù)的異或和。

$ans=SG_1 \bigoplus SG_2 \bigoplus...\bigoplus SG_n$

F-愛睡大覺的小C

題目思路：

? $期望=(全部第k大數(shù)的和)/(區(qū)間個數(shù))$

? 顯然區(qū)間個數(shù)是 $(n-k 2)*(n-k 1)/2$ ，所以只需計(jì)算所有長度大于 $k$ 的區(qū)間的第 $k$ 大的數(shù)的和即可。

? 反過來想考慮每個數(shù)作為第 $k$ 個大數(shù)的區(qū)間，只需要計(jì)算出每個數(shù)作為第k大的數(shù)的區(qū)間個數(shù)就能算出答案

? 區(qū)間個數(shù)需要不重復(fù)，不遺漏的計(jì)算，我們考慮從最小的數(shù)開始計(jì)算，只需要包含這個最小的數(shù)，長度為k的區(qū)間就行，換句話說就是找這個數(shù)位置上的左邊和右邊，一共找到k-1個數(shù)。那這些長度為k的區(qū)間的第k個大數(shù)一定是當(dāng)前的最小值。那剩下的區(qū)間一定不是以當(dāng)前的最小值作為第k大的數(shù)了，然計(jì)算次小值，但當(dāng)次小值遇到了前面的最小值就需要再多往左/右取一位，為了減少跳過的時間，我們可以考慮算完一個最小值就刪除一個最小值，然后仍然找長度為k的區(qū)間。

? 那有沒有可以實(shí)現(xiàn)連續(xù)位置的刪除操作的數(shù)據(jù)結(jié)構(gòu)那，當(dāng)然有了！就是我們的鏈表，由于數(shù)據(jù)范圍很大，我們可以先排序所有數(shù)字，再從最小值開始，在鏈表上找左右的區(qū)間，每次算完直接把最小值刪除即可，這樣一來時間復(fù)雜度就變成了 $O（n*q)$

G-小Hの人脈

題目思路：

首先可以用 $LCA$ 求出每個人從出發(fā)點(diǎn)到目的地花費(fèi)的總金錢數(shù)，記錄下來。

? 因?yàn)轭}目要求的是花費(fèi)錢數(shù)最多的人最少花費(fèi)了多少元，所以可以二分找到該答案。

? 在二分的 $check$ 函數(shù)中枚舉所有人的總金錢數(shù)，找出比二分的錢數(shù)多的路徑，對該路徑進(jìn)行樹上差分標(biāo)記出來，并記錄這樣的路徑個數(shù)為 $cnt$ 。

? 進(jìn)行 $dfs$ 統(tǒng)計(jì)每條邊被標(biāo)記了幾次，如果某條邊被標(biāo)記的次數(shù)等于 $cnt$ ，那就說明這條邊被所有大于二分的錢數(shù)的路徑都經(jīng)過了。因?yàn)橐獙⒁粭l邊免費(fèi)，所以我們肯定要免費(fèi)一條被所有大于二分的錢數(shù)的路徑都經(jīng)過的邊，且這條邊的邊權(quán)被減去后，可以使所有人的路徑的總金錢數(shù)都小于等于二分值，那么本次 $check$ 函數(shù)才可以返回1。否則，返回0。

? 在check的同時，我們可以用一個變量 $num$ 表示被免費(fèi)的那條邊的邊權(quán)值。那么最終答案就是二分值和 $num$ 。

H-左右橫跳

題目思路：

? 簡單的動態(tài)規(guī)劃，題目可以理解為一個 n*m 大小的點(diǎn)陣，每個點(diǎn)上有不同的分?jǐn)?shù)，而一個點(diǎn)上能得到的分?jǐn)?shù)或積累的分?jǐn)?shù)需要通過操作一直接繼承正下方的點(diǎn)的分值，或者通過操作二繼承下方任意一列的間隔 k 行的點(diǎn)的分?jǐn)?shù)并加上所在位置上點(diǎn)的分?jǐn)?shù)，那么即可推出如下狀態(tài)轉(zhuǎn)移方程：

f_{i,j} = max(f_{i-1,j}, max(f_{i-k, 1},f_{i-k,2},...,f_{i-k,m}) w_{i,j})

? 另外，因?yàn)橥ㄟ^操作二轉(zhuǎn)移得到的分?jǐn)?shù)需要比較 m 列所有的分?jǐn)?shù)，所以每操作一行就記錄當(dāng)前一行所能獲得的分?jǐn)?shù)的最大值 $maxv$ ，即：

maxv_i = max(f_{i,1},f_{i,2},...,f_{i,m})

f_{i,j} = max(f_{i-1,j},maxv_{i-k} w_{i,j})

? 最后注意邊界情況和初始化即可。

I-簡單的組合

題目思路：

? 將一個小于 $2^{32}$ 的32位二進(jìn)制無符號數(shù)每8位分成一部分，則每一部分都可以表示成一個小于256的數(shù)，將這4個數(shù)從小到大排序，從小到大依次乘于 $2^{0},2^{8},2^{16},2^{24}$ 然后相加即是答案。

J-線代高手

題目思路

? 數(shù)據(jù)范圍較小，直接暴力枚舉左上角和右下角，如果該子矩陣合法，更新答案即可。

? 要注意的是如果暴力的遍歷子矩陣的每一個元素來求其元素和的時間復(fù)雜度為 $O(nm)$ , 這樣總的時間復(fù)雜度為 $O(n^3m^3)$ ，無法通過此題。因此需要用前綴和來快速求一個子矩陣的元素和，總時間復(fù)雜度為 $O(n^2m^2)$ 。

K-神運(yùn)水晶

題目思路：

? 先不考慮選擇 $0$ 的情況：

? 考慮 $dp$ ，令 $dp[i][j]$ 表示選出和為 $i$ ，且最后一次選擇了的 $j$ 序列的概率，轉(zhuǎn)移為： $dp[i][j]=\sum_{l=1}^{j}{dp[i-j][l]}\times\frac{1}{k}$ alt

L-陰晴不定的大橘學(xué)長

題目思路：

? 對于區(qū)間和 $\sum_{i=l}^{r}a[i]\geq x$ 我們可以使用前綴和來將公式轉(zhuǎn)化為 $sum[r]-sum[l-1]\geq x$ ,如果我們想要快速查找以 $r$ 結(jié)尾的區(qū)間有多少滿足條件的區(qū)間，那么公式可進(jìn)一步轉(zhuǎn)化為 $sum[r]-x\geq sum[l-1]$ ,這時只要找出在 $r$ 的左邊小于等于 $sum[r]-x$ 的區(qū)間前綴和數(shù)量即可，由于會有負(fù)數(shù)的出現(xiàn)，前綴和不是遞增的，所以我們可以使用樹狀數(shù)組來維護(hù) $r$ 的左邊小于等于 $sum[r]-x$ 的前綴和數(shù)量，統(tǒng)計(jì) $r$ 左邊小于等于 $sum[r]-x$ 的前綴和出現(xiàn)的次數(shù)，同時，前綴和的值可能很大，所以我們要使用離散化，將數(shù)值范圍降至數(shù)組可以容納的范圍，查詢的復(fù)雜度是 $O(log^2n)$ ，總的時間復(fù)雜度是 $O(nlog^2n)$ 。