2019CCPC哈爾濱E:數(shù)學(xué)辽聊，思維

2019CCPC哈爾濱E:數(shù)學(xué)绞佩，思維

題目提交網(wǎng)址(含題解):

www.CodeFun2000.com（http://101.43.147.120/）

最近我們一直在將收集到的機(jī)試真題制作數(shù)據(jù)并搬運(yùn)到自己的OJ上寺鸥，供大家免費(fèi)練習(xí),體會(huì)真題難度。現(xiàn)在OJ已錄入50+道2023年最新大廠真題品山，同時(shí)在不斷的更新。同時(shí)谆奥，可以關(guān)注"塔子哥學(xué)算法"公眾號獲得每道題的題解眼坏。

前言:本周比賽的時(shí)候做出來的銀牌題．賽后補(bǔ)題的時(shí)候發(fā)現(xiàn)好像正解和我的還是有點(diǎn)差別．而且正解也挺巧妙的．涉及到了一些我之前沒掌握的結(jié)論．故特此記錄一波.

題意：略

傳送門:https://vjudge.net/contest/398773#problem/E

思路:

首先逆序O(n)標(biāo)記下推可求得基向量．這個(gè)沒問題．

先說我的定理：對序列正序排序，逆序排序．沖突一定連續(xù)．

根據(jù)以上定理．hash桶裝值域．枚舉值域．維護(hù)前綴和后綴和判一下沖突情況即可．復(fù)雜度: $O(nlogn)$

正解思路:

前置題目１:ＨＤＵ1205: 給你一個(gè)序列．問你是否可能將其排列成任意兩個(gè)相鄰的位置值不相同．

鴿巢定理:若出現(xiàn)次數(shù)最多的數(shù)的次數(shù)? $x \leq \lceil \frac{n}{2 } \rceil$ ,則一定有解.

簡單證明: 將出現(xiàn)次數(shù)最多的數(shù)排成一排．　若其他的數(shù)的個(gè)數(shù) n - x >= x - 1. 那么他們可以將出現(xiàn)最多的數(shù)完全分隔開．之后將出現(xiàn)次數(shù)次多的按同樣的方式填．遞歸下去一定能夠填完且合法.

前置題目2:O(n)求序列中出現(xiàn)次數(shù) > 一半　的數(shù)．

方法一:位運(yùn)算

如果Ａ出現(xiàn)次數(shù)最多酸些，那么他在二進(jìn)制上每一位出現(xiàn)的次數(shù)也最多．所以統(tǒng)計(jì)二進(jìn)制每一位上的眾數(shù)(只有0/1).然后做位運(yùn)算合并即可．復(fù)雜度:O(64n).

方法二:摩爾投票法(我們要的)

思想:假設(shè)眾數(shù)貢獻(xiàn)為1宰译，非眾數(shù)貢獻(xiàn)為0.則最后總貢獻(xiàn) > 0.

任意選擇一個(gè)數(shù)y,將其當(dāng)做眾數(shù)，模擬貢獻(xiàn)．當(dāng)貢獻(xiàn)抵消為０時(shí),剩余的數(shù)中眾數(shù)不變

1.若y是眾數(shù).那么抵消的數(shù)中有一半是ｙ.剩下的數(shù)中仍有一半以上是ｙ.

2.否則魄懂，抵消的數(shù)中小于等于一半的數(shù)是y.剩下的數(shù)中仍有一半以上是ｙ.

不管怎樣, $y > \frac{n}{2}$ 的關(guān)系在情況1/2后不會(huì)發(fā)生改變.

? ? 所以根據(jù)上述兩個(gè)特性沿侈，進(jìn)行模擬．逐漸縮小數(shù)組范圍．最后得到的一定是眾數(shù).

plus:如何判斷是否存在超過一半的數(shù)?

? ? 得到答案后，掃一遍序列確認(rèn)一下答案出現(xiàn)的次數(shù):若<= n/2則答案不存在.

有了前面兩個(gè)前置結(jié)論之后：

給一個(gè)序列市栗，重新排列使得位置映射到原序列上數(shù)兩兩不同的充分必要條件:

出現(xiàn)次數(shù)最多的數(shù)的次數(shù)? $x \leq \lfloor \frac{n}{2 } \rfloor$

否則沖突的個(gè)數(shù)為: 2x - n

重點(diǎn):我們可以將這個(gè)問題轉(zhuǎn)化成　HDU１２０５：將序列長度 *= 2. 然后把位置相對看成位置相鄰．得到一樣的結(jié)論.

所以掃一遍[基序列]缀拭，利用摩爾投票法O(n)求次數(shù)出現(xiàn)次數(shù)最多的數(shù)即可．

最后編輯于：2023.03.04 21:28:48

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者