手機站首頁散文詩歌雜文隨筆日記小小說

散文網(wǎng) » 科技 »學(xué)習(xí) » 華泰證券FINTECH編程挑戰(zhàn)賽初賽+決賽個人題解

華泰證券FINTECH編程挑戰(zhàn)賽初賽+決賽個人題解

2022-07-04 12:49 作者:俊杰_Charles 0人讀過 | 我要投稿

比賽鏈接：https://competition.nowcoder.com/3/introduce

受 qcjj 邀請打了個搶錢比賽，結(jié)果只搶了 500，太菜了，哭死

初賽

1 小華拼單詞

題意：分別給出字母 a 到 z 的個數(shù)，求最多能拼出多少個 'huatai'

題解：字母 a 數(shù)量的一半，以及字母 i、u、h、t 的數(shù)量，取最小值

2 股票買賣的最大收益

題意：給定股票每天的價格，初始持有 $x$ 手股票，現(xiàn)金 $0$ 元。每天可以任意次買入或賣出，但最多持有 $k$ 手股票。求最后一天結(jié)束的時候，最終總資產(chǎn)最多為多少。最終總資產(chǎn)=現(xiàn)金數(shù)+持有股票數(shù)×最終股票價格。

題解：貪心，如果下一天股票要跌就在當(dāng)天全部賣出，如果下一天股票要漲就在當(dāng)天全部買入。

3 運貨

題意：給一棵 $n$ 個節(jié)點的樹，一共有 $C_n%5E2$ 條路徑，每條路徑的愉悅值為路徑上的最大結(jié)點編號，求所有路徑愉悅值的和，對 $10%5E9%2B7$ 取模。

題解：從小到大添加結(jié)點，用并查集維護(hù)連通塊大小。當(dāng)添加了一個點時，令它所連接的連通塊個數(shù)為 $k$ ，各個連通塊大小分別為 $s_1%2Cs_2%2C%5Cdots%2Cs_k$ ，那么以該點作為路徑上最大點的路徑個數(shù)為 $%5Csum_%7Bi%3D1%7D%5Eks_i%2B%5Csum_%7Bi%3D2%7D%5Ek%5Csum_%7Bj%3D1%7D%5E%7Bi-1%7Ds_is_j$ ，對序列 $s$ 求前綴和后該式可以? $O(k)$ 求出，總復(fù)雜度 $O(n)$ 。

4 區(qū)間乘積的因子數(shù)之和

題意：給定一個數(shù)組，數(shù)組中每個數(shù)都是不大于 $3$ 的正整數(shù)。已知一個區(qū)間的權(quán)值為該區(qū)間所有數(shù)乘積的因子數(shù)量，求所有區(qū)間的權(quán)值之和。

題解：由題意得一個區(qū)間所有數(shù)的乘積可以表示為 $2%5Ex3%5Ey$ ，它的因子個數(shù)為 $(x%2B1)(y%2B1)$ 。令 $S%5E%7B(2)%7D_i$ 表示前 $i$ 個數(shù)中 $2$ 的個數(shù)， $S%5E%7B(3)%7D_i$ 表示前 $i$ 個數(shù)中 $3$ 的個數(shù)，那么所有區(qū)間的權(quán)值之和可以表示為：

$%5Cbegin%7Balign%7D%0A%26%20%5Csum_%7Br%3D1%7D%5En%5Csum_%7Bl%3D1%7D%5E%7Br%7D(S_r%5E%7B(2)%7D-S_%7Bl-1%7D%5E%7B(2)%7D%2B1)(S_r%5E%7B(3)%7D-S_%7Bl-1%7D%5E%7B(3)%7D%2B1)%20%5C%5C%0A%3D%20%26%20%5Csum_%7Br%3D1%7D%5En%5Csum_%7Bl%3D1%7D%5E%7Br%7D(S_r%5E%7B(2)%7DS_r%5E%7B(3)%7D-S_%7Bl-1%7D%5E%7B(2)%7DS_r%5E%7B(3)%7D%2BS_r%5E%7B(3)%7D-S_r%5E%7B(2)%7DS_%7Bl-1%7D%5E%7B(3)%7D%2BS_%7Bl-1%7D%5E%7B(2)%7DS_%7Bl-1%7D%5E%7B(3)%7D-S_%7Bl-1%7D%5E%7B(3)%7D%2BS_r%5E%7B(2)%7D-S_%7Bl-1%7D%5E%7B(2)%7D%2B1)%5C%5C%0A%3D%20%26%20%5Csum_%7Br%3D1%7D%5En%5Br(S_r%5E%7B(2)%7DS_r%5E%7B(3)%7D%2BS_r%5E%7B(2)%7D%2BS_r%5E%7B(3)%7D%2B1)-(1%2BS_r%5E%7B(3)%7D)%5Csum_%7Bl%3D1%7D%5E%7Br%7DS_%7Bl-1%7D%5E%7B(2)%7D-(1%2BS_r%5E%7B(2)%7D)%5Csum_%7Bl%3D1%7D%5E%7Br%7DS_%7Bl-1%7D%5E%7B(3)%7D%2B%5Csum_%7Bl%3D1%7D%5E%7Br%7DS_%7Bl-1%7D%5E%7B(2)%7DS_%7Bl-1%7D%5E%7B(3)%7D%5D%0A%5Cend%7Balign%7D$

對序列 $S%5E%7B(2)%7D$ 與 $S%5E%7B(3)%7D$ 以及兩者的逐元素乘積求前綴和后，該式可以 $O(n)$ 求出。

決賽

1 股票最小的陡峭值

題意：給定一個序列 $a_1%2Ca_2%2C%5Cdots%2Ca_n$ ，其中某些元素值是未知的，保證第一個和最后一個是已知的，求 $%5Csum_%7Bi%3D2%7D%5En%7Ca_%7Bi-1%7D-a_%7Bi%7D%7C$ 的最小值。

題解：容易想到未知的值只要落在兩側(cè)已知的值之間即可保證結(jié)果最小，為方便代碼，將未知的值直接替換為前一個元素的值即可。

2 小華的字符串后繼

題意：給定一個小寫字母字符串，求與該串長度相同且字典序大于該串的字符串中字典序第 $k$ 小的字符串，若不存在輸出 -1。

題解：把字符串看作 26 進(jìn)制數(shù)，把 $k$ 也轉(zhuǎn)化為 26 進(jìn)制數(shù)，作高精加法即可。

3 小華的排列交換

題意：給定一個排列，每次可以交換一個奇數(shù)和偶數(shù)的位置，求最少多少次交換能使得排列變得有序。

題解：每個位置看作一個結(jié)點，將該結(jié)點和該位置上的數(shù)的對應(yīng)結(jié)點連一條單向邊，可以得到若干環(huán)，稱作置換環(huán)。通過推斷可以得到如下結(jié)論：

如果一個長度為 $k$ 的置換環(huán)上既有奇數(shù)又有偶數(shù)，那么通過 $k-1$ 次交換即可將環(huán)上的所有數(shù)歸位。
對于一個長度為 $k_1$ 的只有奇數(shù)的環(huán)，和一個長度為 $k_2$ 的只有偶數(shù)的環(huán)，可以先通過一次交換將兩環(huán)合并成一個既有奇數(shù)又有偶數(shù)的環(huán)，然后再通過 $k_1%2Bk_2-1$ 次交換將所有數(shù)歸位，總次數(shù)為 $k_1%2Bk_2$ 。
對于一個長度為 $k$ 的只有奇數(shù)/偶數(shù)的環(huán)，且沒有偶數(shù)/奇數(shù)環(huán)與之合并，那么必須先通過一次交換將一個偶數(shù)/奇數(shù)加入該環(huán)，然后通過 $k$ 次交換將所有數(shù)歸位，總次數(shù)為 $k%2B1$ 。

4 區(qū)間權(quán)值和

題意：定義一個數(shù)組的極差為該數(shù)組最大值減去最小值的差，定義一個區(qū)間的權(quán)值為該區(qū)間內(nèi)所有連續(xù)子數(shù)組的極差之和，求給定數(shù)組的所有區(qū)間的權(quán)值和。

題解：最大值與最小值的貢獻(xiàn)分開計算。對于每個數(shù)，可以通過單調(diào)棧分別找到左右兩測比它大/小且距離其最近的位置，借此可以確定該數(shù)作為最大/最小值時的最長區(qū)間。令一個數(shù)的位置為 $i$ ，其左邊比它大的距離最近的位置為 $l$ ，其右邊比它大的距離最近的位置為 $r$ ，計算得該數(shù)作為最大值時的總次數(shù)為：

$(%5Cunderline%7Bl%2B1%7D%2B%5Cunderline%7Bl%2B2%7D%2B%5Cdots%2B%5Cunderline%7Bi-1%7D%2B%5Cunderline%7Bi%7D)(%5Cunderline%7Bn-r%2B2%7D%2B%5Cunderline%7Bn-r%2B3%7D%2B%5Cdots%2B%5Cunderline%7Bn-i%7D%2B%5Cunderline%7Bn-i%2B1%7D)$