What number should I guess next ？
這篇文章的靈感來源于最近技術部的團建與著名的DP優化《鷹蛋》，記得在一個月前，查到鷹蛋的題解前，我在與同學討論時，一直試圖尋找一種固定的模式來決策，但是，卻總存在更理想的方案，在此，我想以團建的游戲作為背景，系統(sui bian)地描述和分析在這些決策模式，
又或者說，我想試著介紹的是： THE FUN OF DECISION 思維游戲與決策的魅力
本文前半部分的受眾可以是沒接觸過OI但是學過高中數學的、正在或想要接觸計算機編程或是單純覺得有趣的小伙伴，我希望通過這篇文章，能激起你們對決策思路、動態規劃、甚至是分析資料找規律的興趣，我希望，大家在看這篇文章的時候，不要急著往下翻，可以適當地停下來，思考一下，想想自己能想出什么樣的決策，或是找個同學過過招，只有跟著一起思考，才能體現出思維游戲的有趣之處，
后半部分主要是在理解了朱晨光大佬的這篇論文后用自己的話進行了表述，受眾主要是有一定dp基礎的，但是沒能看懂論文或是被論文嚴謹的公式證明嚇住的小伙伴，
一. 萬惡起源——深草革命的開端
溫馨提示：背景純屬虛構，如有雷同，我爬就是了，
季樹部奇奇怪怪的團建開始了，部長jxh為了鞏固獨裁統治，加強思想集中，下令全體部員為ta唱一首歌，
原本，靦腆的小萌新們并不敢反對，但是，不知怎么混進來的，突然出現的一個陌生的ID打破了這片表面的祥和，
ta在群中揭露了部長把發紅包的錢拿去買奶茶的照片，引發了部員的不滿，隨著輿情的發酵，部員們決定發動革命，由于部的吉祥物是深草，史稱深草革命，
眼看情勢不妙，狡猾的部長決定用一個游戲來與部員決戰，
ta說：”我會在紙上寫一個 \(1\) 到 \(1\times 10^{18}\) 間的數，然后你們12個人來通過猜數字來確定它，放心，每次猜數，我都會告訴你們這個數是否比你們猜的數小，但是，如果某個人猜的數大于或等于我寫的數，這個人便出局了，不能再猜下一個數字，如果12個人全部出局，你們必須馬上提交答案，當你們覺得已經確定我手中的數字時，也可以在全部出局前提交答案，但是，作為答案的這個數字必須在你們猜過的數字中，
”如果你們答案錯了，你們就乖乖唱歌，如果你們答案對了，我們就角色互換，你們來寫數我來猜，為了保證公平性，在我猜了12個大于等于答案的數后，我會停止猜數，提交答案，當然，我也和你們一樣，可以在出局前提交答案，然后，我們比拼確定對方答案時猜數的次數，誰少誰贏，跟我一樣少也算你們贏，若你們贏了，我就給你們唱歌，“
憨厚的部員們接受了這個提議，但是部長很狡猾，ta并沒有把答案寫在紙上，而是根據部員們猜的數字決定答案，也就是說，ta隨時在心里計算著，想盡辦法地把部員們猜數的次數提到最高，甚至使他們猜不出來，ta在紙上寫字只是個假動作，事實上，答案并不是事先確定的，而是在部員們猜的程序中不斷調整的，
好在部里的大佬比較多，他們決定，用科學的猜數（決策）方式，擊潰部長的幻想，
由于部長實在太強了，就算部員們不先確定數字，也像部長那樣調整，部長還是能用最優決策使自己的猜數次數最少，
所以，要贏部長，取得革命勝利，部員們必須想出最優的決策，來應對部長絕對聰明的調整，并同樣以絕對聰明的調整，將部長的次數卡到盡可能高，
頭腦風暴就這樣打響了，
但是，由于各位大佬各抒己見，部員內部分裂成了幾派，革命軍陷入混亂之中，部史學家稱之為黎明前最后的混沌，
下面，為了討論的方便，我可能會將部員的人數比如12記為K，部長給出的范圍的右邊界比如 \(1\times 10^{18}\) 記為N，我們將部員猜數的次數用含有N和K的式子表示，
下面轉化為鷹蛋問題做一個簡單的描述：
現在你買了一棟有1e18層的大樓，你想要知道蛋從幾樓起摔下來會摔壞（也有可能從頭扔到尾都沒摔壞），你手頭只有12個蛋，摔壞的蛋就不能用了，問，在最壞情況下，最少需要扔幾次才能確定答案？
在下文中我們討論的內容無非這幾點：怎么扔？效率如何？哪種情形最壞？
如果你被上面的“最壞”和“最少”繞暈了，那請回過頭去看故事背景，相信你能理解這個最壞與最少的含義，
P.S. 上面的這句”也有可能“是我加上去的，你也可以理解為：就算你試了N-1層樓蛋都沒壞，你仍然需要把蛋從第N層樓上扔下去，這與前面部長的”你們的答案必須在猜過的數里面“這條規則都是同一個目的：避免歧義，
二. 起于混沌——保守派的決策
保守派認為，想要戰勝部長，第一步是要保證，一定能確定答案，因此，他們主張選用一種最為穩妥的方式，
毫無疑問，一個一個往上猜絕對能確定最終結果，但這樣的操作容易被狡猾的部長卡到 \(10^{18}\) 次，
他們所想到的第一種方式，是每隔11個數猜一次，
他們的想法是這樣的：從12開始，到 24、36、48、最后到 999,999,999,999,999,996 ，這樣一來，就算部長在某個時候說出“答案不比這小”的話，他們也可以用剩下的11個人掃遍余下的11個數字來確定結果，
最終，他們猜數的最壞次數（也就是狡猾的部長會卡的次數），便是 \(10^{18}\div 12+11=83,333,333,333,333,344\) ，這個數字有17位，顯然大得離譜，
但是，保守派得部員們并沒有灰心，他們觀察到，自己其實完全沒有余下11個人來掃遍11個數的必要，只要留下一個人，從縮小了的范圍的底端往上掃，同樣可以確定部長的數字，
怎樣最大限度得利用余下的11個部員來縮小范圍呢？
他們想到了無敵的二分法，
每次選擇范圍的中點，再根據部長給出的大小提示，在縮小了的范圍中取下一個中點，這樣，每次猜數，都可以使范圍縮小為原來的一半，
經過估算，二分法在任何情況下，只需要猜測 \(\log_2 N\approx 60\) ，這簡直就是史詩級的飛躍，
然而，想要完成這樣完美的策略，需要有60名部員，僅靠12名部員無法完成，
保守派的成員對此心知肚明，于是，他們決定由11名部員進行二分來縮小范圍，剩下的一名部員從最終范圍的底端往上掃，
顯然，部長不會容忍范圍一次次地縮小，ta會盡可能得讓試圖二分的隊員出局，進而將范圍維持得盡可能大，因此，部員們最多只能進行11次二分，
（在上面有涉及到一點部長視角的決策思路，關于這一點，之后會有更詳細的論述）
經過估算，最終他們需要猜測的最壞次數是 \(10^{18}\div 2^{11}+11=488,281,250,000,011\) ，這個數字，只有15位，與第一種方法相比，效率接近其200倍，
正當保守派的成員為了這個結果欣喜不已，疲憊不堪時，有一個聲音從旁邊傳出：“為什么不多留下一個人，進一步縮小范圍呢？”
（草這段寫得我尷尬癥犯了）
long long guess1(long long N,long long K){
long long l=1,r=N,mid,c=K,cnt=0;
while(l<=r&&c>1){
mid=(l+r)>>1;
cnt++;
if(evil_check(l,r,mid,c)){
c--; r=mid-1;
}else l=mid+1;
}
while(l<=r){
cnt++;
if(evil_check(l,r,l,c)) break;
l++;
}
return cnt;
}
上面的代碼只供參考，方便大家理解這種策略的決策程序，我用evil_check來表示部長對大小關系的判斷，下文中出現的類似代碼，都只是作為一種框架，方便大家理解決策的程序和大致的實作，
簡單的說，我寫的這些代碼只是用來看著玩的，不是拿來跑的，
evil_check也就是怎樣讓次數卡到最多的策略會在后面的番外篇討論，不過自己想想也好，其實不難，
看不懂也沒關系，跳過就是了，我自認為文字的表述大概可能還是清楚的，，
三. 黑夜里的燭光——改良派的崛起
發出聲音的，是改良派的部員，
改良派的部員分析了保守派的兩種主張，提出了把兩種方式結合起來的思路，
先由10名部員進行二分來縮小范圍，然后選擇合適的間隔來猜數，最后掃剩下的區間X就行了，
經過粗略的計算，在二分10次后，余下的待定區間大小為 \(SIZE=10^{18}\div2^{10}=976,562,500,000,000\)
此時，如果直接把SIZE分為兩份，就是保守派的第二種方案，那么，如果分為3份呢？
不難發現分為三份后，每段的大小只有325,520,833,333,333，雖然為此，他們比分成兩份多猜了一個數，但是余下的每段大小卻大幅減小，
分為兩份大概還需猜測： \(1+SIZE\div2=488,281,250,000,001\) 次
分為三份大概還需猜測： \(2+SIZE\div3=325,520,833,333,335\) 次
P.S. 為什么我總是在“還需猜測”前面加上“大概”或“估算”，是應為實際操作中可能會出現向下取整、l=mid-1之類的種種變動，這一點在下面對三分乃至k分的介紹中體現尤為顯著，為了方便討論，而且大多情況下這一點小小的變動對于1e18的大數字來說也算不上什么，我選擇了估算忽略的方式，順帶一提，如無特別說明，默認向下取整，
顯然，分成三份要顯著優于分成兩份，
當然，改良派的部員并沒有止步于此，他們繼續探究：在分成幾份時，能取得最優秀的結果？
將分成的份數記為X，我們希望結果最優，就是希望函式 \(f(X)=SIZE\div X+(X-1)\) 取到最小，
季樹部的大佬怎么可能不會對勾函式呢？于是他們很快找到了答案，
當 \(X=31,250,000\) ，取到最優解 62,499,999，
下面我來整理一下我們達成的成就：
- 利用間隔11的演算法： 83,333,333,333,333,344
- 二分11次后完全遍歷：488,281,250,000,011
- 二分10次后分三份：325,520,833,333,345
- 二分10次后分 \(\sqrt {SIZE}\) 份：62,500,009
全體起立！！！從現在開始這里叫盧，，好吧串場了
long long guess2(long long N,long long K){
long long l=1,r=N,mid,c=K,cnt=0;
while(l<=r&&c>2){
mid=(l+r)>>1;
cnt++;
if(evil_check(l,r,mid,c)){
c--; r=mid-1;
}else l=mid+1;
}
long long block=sqrt(r-l+1);
while(l+block<=R){
cnt++;
if(evil_check(l,r,l+block,c)){
r=l+block-1;
break;
}
l+=block+1;
}
while(l<=r){
cnt++;
if(evil_check(l,r,l,c)) break;
l++;
}
return cnt;
}
幕間 愚者的嘗試
（這里懶得編背景了）
在與同學討論時，我曾經想到某種優化區間掃描的策略：倍增掃描策略，
也就是，掃描時，每次間隔由1、2、4、8逐漸遞增，
當時，我的想法是這樣的：既然一個一個掃太費時，那我就多留下一個人，倍增地掃來縮小范圍，
于是，我打了一個先二分K-2次后倍增的策略和先倍增后二分K-2的策略，發現在某些N較大，K較小的數字下能夠取得優于直接二分K-1次后遍歷全區間的結果，
但是，在隨后的思考中，我發現了這種做法在最壞情況下，還是只能將區間縮小為原本的二分之一，而且為此要猜數的次數還高于直接取中點的二分法，
那么，為什么縱使這樣一個看起來毫無好處的策略，卻真的可以使次數減少呢？
在幾個星期前，我對這個問題的思考還只停留在二分答案的最劣情況與倍增的最劣情況答案出現的位置不同所以中和了這種幼稚且錯誤的想法上，
現在，我想我能給出較為科學的解釋，
以先二分K-2次后倍增的策略為例：
因為每次倍增程序我們試圖排除的區間大小是1、2、4、8最后是 \(2^n\)
這些區間大小加起來 總大小有 \(\sum2^i=2^{n+1}-1<SIZE\)
最壞情況下，余下來的區間大小是 \(2^n\)
當 \(2^n+n<SIZE\div2+1\) 時，我的策略便會優于直接二分11次后遍歷的策略，
一樣的道理，n足夠大時，這種差距會體現得尤其明顯，
下面是我當時打的暴力，僅供參考：
（寫得太丑了于是刪掉了）
四. 破空一閃——革命派的創舉
（越來越中二了我的天）
前排宣告，這個策略是同學想出來的，我好菜啊orz
革命派的小伙伴們想得更為深入：說到底，我們為什么要用二分呢？
首先，讓我來介紹一下，什么是三分法，
與二分法不同，我們每次將區間分為三份，并對兩個三等分點由小到大依次做出猜測，
如果小的三等分點比答案大，證明答案在第一份里；
如果大的三等分點比答案大，證明答案在中間那一份里；
如果大的三等分點比答案小，證明答案在第三份里，
之后，對縮小了的區間執行相同的操作，直到人耗盡或是區間縮小到可判斷，
如果我們是從大到小來猜測的話，同樣將區間縮小為三分之一，卻需要消耗兩個猜測大數的機會，
在人數足夠多的情況下，我們可以對二分與三分做如下的比較：
從長度為N的范圍中確定一個數，使用二分法，在任何情況下，都需要 \(\log_2 N\) 次
使用三分法，最壞情況下，需要 \(2\times \log_3N\)
\(2\times \log_3N/\log_2N=2\times\log_32=\log_34>1\)
所以，在人數充足的最壞情況下，三分法并不比二分法優秀，
但是，革命派的部員們并沒有因此局限了思路，他們在改良派對最后區間處理的改進中意識到，增大分的份數的實質，就是在每次劃磁區間時，通過額外的猜數，在仍然只消耗一個人的情形下，達到進一步縮小范圍的目的，或者說，這是一種舍小局辦大事的決策手段，
于是，抱著這樣的思想，革命派人首先嘗試了三分11次后掃描余下區間的策略，
經過估算，最壞情形下需要猜數的次數是： \(11\times2+10^{18}\div3^{11}=5,645,029,269,498\)
相比起二分11次后掃描余下區間的 488,281,250,000,011，效率高了接近100倍，
我們不難發現，三分11次后余下的區間仍高達13位數，有巨大的優化空間，
革命派部員聯想到了二分法達到最優的條件： \(K\geq\log_2N\)
那么為什么我們不試著找到一個合適的底數k，使我們的K滿足上面的式子呢？
于是，k分法應運而生了，
對于這個底數k，應有 \(K\geq\log_kN\) ，換句話說，應有 \(k^K\geq N\) ，
我們不妨取 \(k=\sqrt[K-1]{N}=\sqrt[11]{10^{18}}\approx43\) ，
確定了這個k之后，經過估算，需要猜數的個數變成了： \(11\times42+10^{18}\div43^{11}\approx463\)
求出了這條式子后的革命派部員們回過頭去看了看改良派對最后區間的優化處理，頓時百感交集，
其實，改革派的優化是將改良派的優化變得更普遍化，只是這一步之遙，有時也是那么遙不可及，而只有走出關鍵的一步的人，才會被載入史冊，
到此，讓我們再來整理一遍部員們達到的成就，為自己看到這里的耐心和黎明的臨近鼓掌吧：
-
保守派： 二分11次后完全遍歷：488,281,250,000,011
-
改良派： 二分10次后分 \(\sqrt {SIZE}\) 份：62,500,009
-
改革派： 43分11次后完全遍歷：463
沒錯，你沒有看錯，這只是臨近，黎明仍沒有到來，
long long guess3(long long N,long long K){
long long l=1,r=N,c=K,cnt=0,block,num,mid;
while(l<=r){
num=floor(pow(r-l+1,1.0/(c-1)));
block=(r-l+1)/num+1; mid=l;
while(mid+block<=r){
mid+=block; cnt++;
if(evil_check(l,r,mid,c)){
c--; r=mid-1; break;
}else l=mid+1;
}
if(mid==l) break;
}
while(l<=r){
cnt++;
if(evil_check(l,r,l,c)) break;
l++;
}
return cnt;
}
再次提醒，代碼僅僅作為一種決策模式的參考，（當然你也可以自己寫個evil_check跑跑看，不過我比較菜，可能會出鍋）
事實上，我們不難發現，在上面的代碼中，向下還是向上取整、加block后要不要加減一等玄學問題，都有可能使猜數的次數出現微妙的變化，甚至只是在某次k分時作了調整，也可能會對結果產生玄學的影響，這一點，在1e18這樣的大范圍上體現尤為顯著，但是，我們的最優解卻只有一個，想要從這些許許多多的可能的調整（比如有的加block后減了1，有的卻不減）中分析出最優的結果，從解的唯一性這個角度來看，我認為，這個演算法過于玄學，雖然求出來的答案或許很接近于最優解，但它應該不是正確的解法，
什么，沒看懂上面這段話？那就跳過吧，我也不知道怎么解釋，只是一種單純的感覺罷了，
五. 撥開混沌——神秘的支援者
（打到這里我才發現我根本找不到能算1e18的代碼，雖然我嫖了個題解的截圖，不過看不懂也打不出來，所以具體的最優答案是多少，我也不知道，或許過幾天就知道了，所以我只能通過較小資料的分析，讓大家體會一下其正確性）
在經過了各自的討論后，部員們有了一定的底氣，
但是，強大的部長是一個不可輕敵的對手，
一定要贏才行，一定要確保最終的勝利才行，每個人都在心中這樣默念著，
但是，部長胸有成竹的樣子仍讓部員們感到不安，
還有嗎？難道猜數的次數還能再縮小嗎？
就在部員們苦惱不已之際，Q群中那個神秘的ID，給出了ta的提示，
“為什么要局限于某種規律性的分段呢？”
現在，讓我們代入部員的身份，一起思考吧，（其實是懶得改人稱了）
每次需要決定在范圍 \([l,r]\) 內猜某個數x后，狀況會出現如下的變化：
- 若x大于等于部長的答案，一名部員出局，余下的K-1名部員繼續在 \([l,x\big)\) 內猜數
- 若x小于部長的答案，則由K名部員繼續在 \(\big(x,r]\) 內猜數
由于部長太過強大，他一定會在情況1和情況2中挑出一個猜數次數較多的來繼續，
好在雖然我們無法選擇情況1和情況2，卻有選擇x的自由，
那么，我們只需要計算出每個x對應的情況1和情況2的次數最大值，然后再從這些x中選出一個最大值最小的來猜數，就能夠達到最優的次數，
但是，我們要如何求出這個值呢？
我們將k個人在區間長度為n的范圍里猜數的最優次數記為 \(f(k,n)\)
也就是說，我們需要求解的，是 \(f(K,N)\)
假如在第一次猜數中，我們猜測的數字是區間中的第W個，
則對于情況1，我們余下來的區間為 \([l,l+W-1\big)\) 對應的區間長度為 \(W-1\) ，人數為 \(K-1\)
對于情況2，余下的區間為 \(\big(l+W-1,r]\) 對應的區間長度為 \(N-W\) ，人數為 \(K\)
那么我們有：
\(f(K,N)=max\{f(K-1,W-1),f(K,N-W)\}+1\)
換句話講：我們將在K個人、長度為N的區間情況下求最壞情況的最小猜測次數的問題，轉化為了在K-1個人、長度為W-1的區間情況下和K個人、長度為N-W的區間情況下求解的兩個規模較小的子問題，
或許你會問，這有什么意義，問題不還是沒有得到解決嗎？
這當然是有意義的，因為，隨著子問題規模的不斷縮小，最終，我們將具有能夠將子問題求解的能力，并利用求出的子問題，我們可以將其代入大子問題的式子中，解出大子問題，最終解出我們要求得f(K,N)，
像這樣，自頂向下將問題不斷分解到可以計算答案后，通過迭代回溯，計算大問題的程序，我們稱之為遞回，
那么，什么樣的小問題我們可以直接回答呢？
顯然的，對于任意的區間長度n，我們有 \(f(1,n)=n\) ，因為在我們只剩1個人的時候，我們必須從底向上一個數一個數的猜，假如我們先猜了第1個數，發現它小于答案，后猜了第三個數，如果第三個數大于等于答案，我們就無法再確定第二個數是否是答案了，正是因為如此，最壞情況下，我們需要猜測n次，
顯然的，對于任意人數k，我們有 \(f(k,0)=0\) ，區間長度為0自然沒有猜的必要，
于是，我們在利用遞回求解出問題的解的同時，記錄下為了取到這種解，我們每次取的是區間中的第幾個數，這樣一來，我們只需要照著事先算好的表回答，就能夠實作最優的策略，
long long f(long long K,long long N){
if(N==0) return 0;
if(K==1) return N;
long long ans=INF;
for(int w=1;w<=N;w++){
long long temp=max( f(K-1,w-1),f(K,N-w) );
if(temp+1<ans){
ans=temp+1;
chosen[K][N]=w;
}
}
}
就這樣，除了求出 \(f(K,N)\) 及取到這個最小值每次所需要選擇的數字外，我們還求出了其它各種K和N下需要選擇第幾個數最優，就算部長臨時起意，做出了不符合最壞情況的決策，我們也能通過查表，做出最優的選擇，
順帶一提，如果我們不是利用遞回來計算，而是先預處理出每個小問題的解并存下來，之后再一步一步擴展問題的規模，從下而上得計算，我們將其稱之為動態規劃，簡稱dp，
\[f(K,N)= \begin{cases} max\{f(K-1,W-1),f(K,N-W)\}+1 & K>1,N>0\\ 0 & N=0\\ N & K=1 \end{cases} \]而上面的這條公式，我們稱之為動態規劃的狀態轉移方程，
代碼就不再給出了，dp的寫法隨便搜一下就有了，在這里我只給出 N=1000，K=3 時，k分法與正解的對比：
k分法（代碼）：跑出46 可能存在evil_check判斷不夠合理的問題
理論計算31分法：30*2+1000/(31^2)=61
dp：19
代碼我會放在文章的最末尾，僅供參考，
就這樣，部員們利用自己的聰明才智，想出了擊潰部長的方法，
正當他們打開計算機，準備把理論付諸實踐時，他們突然發現，用剛才的方法，若是直接列舉K、N和W，就需要回圈接近 \(12\times10^{18}\times10^{18}\) 次 ，想要在短時間內描述出1e18中的每一種情況幾乎是不可能的，就算是計算機，也不可能在在決戰開始前算出一條合適的路徑，
怎么辦？只能優化dp了，
就在這時，有人突然發現，群里那個陌生的id，居然是部長的小號！
原來，部長是看到最近部里氣氛沉悶，大家在枯燥的學業中迷失了自己，就把自己掏錢給部員們買奶茶的照片用另一個馬甲發了出來，
部員們終于理解了部長的良苦用心，他們與部長更改了游戲規則，把每次決策的思考時間改成了1秒，并且禁止了計算機的使用，場面于是變得混亂而快樂起來，
六. DP優化——接近神的領域
警告： 本節或許不會再像上面那樣從非常基礎的地方開始解釋，
然而寫完這節我并沒有覺得接近了神的領域，反而覺得自己越來越菜了
下面的內容是對這篇論文的內容作較為感性的解讀，
在這里，我們不再考慮決策程序中究竟發生了什么，我們只希望求出這個最優的猜數次數，
首先，當人數一樣多的情況下，區間越長，猜數的次數只可能更多，不可能更少，按照這樣感性的分析，我們可以得出這樣的結論(下記為結論1)： \(f(K,N)>=f(K,N-1)\)
（當然，你也可以像論文中的那樣用數學歸納法去準確地證明這個結論）
得出這個結論后，我們回過頭看我們列舉W的程序，
列舉后，我們取的是 \(max\{f(K-1,W-1),f(K,N-W)\}\) （下記為式1）
根據結論1，我們不難發現，隨著w的遞增，f(K-1,W-1)逐漸遞增，f(K,N-W)逐漸遞減，我們將f(K-1,W-1)和f(K,N-W)隨著w的變化的曲線大致畫出來后，不難發現：
式1取到最小值的位置，就在兩條曲線的交匯處，
所以，我們就不需要列舉每個w，而是直接利用二分查找找到令 \(f(K-1,w-1)\geq f(K,N-w)\) 的第一個位置mid，然后比較挑選式1在w取mid與mid-1下的最優取值就行了，
此外，不難發現，就單次操作而言，其對縮小區間的最大貢獻是把區間一分為2（因為最壞情況下部長肯定不會允許你取到不等分段后的小區間）
再加上我們前面在k分法的描述中也有提到，在所有的分法中，假如人數足夠多，二分法在最劣情況下擁有最優的表現，所以，當人數足以進行2分法時，我們直接進行二分法便是最優的，此時，直接記為二分法所需的次數就行了，不需要列舉或是二分w來計算，
到這里，我們已經將原本 \(O(KN^2)\) 的樸素演算法優化到了 \(O(KN\log_2N)\)，
但是這樣的復雜度顯然還不能使我們算出1e18這樣的資料，我們還需要進一步的優化，
（很顯然這種神仙思路就不是我這種凡人想得出來的）
可以發現，當人數一定時，若區間長度多了1，猜數次數要么多一，要么不變，
這里可以感性地理解一下：我們可以假裝不知道區間的長度是N+1，仍然按區間長度為N的策略去猜數，然后得到最壞情況下的最優次數后，我們再把這個多冒出來的數再猜一遍，這樣一來猜數次數便只多了1，再怎么搞，也不至于多2或多更多，
這是更為科學詳細的證明：
對于式子 \(f(K,N)=max\{f(K-1,W-1),f(K,N-W)\}+1\)
我們單獨拿出W=1的情況出來，很顯然，f(K-1,W-1)=0 我們有 f(K,N)<=f(K,N-1)+1
另一方面，我們又有結論1： f(K,N)>=f(K,N-1)
綜合起來，我們有 \(f(K,N-1)\leq f(K,N)\leq f(K,N-1)+1\)
換句話說，f(K,N)要么等于f(K,N-1) 要么等于f(K,N-1)+1，
顯然，當存在某種決策w，使得max{f(K-1,W-1),f(K,N-W)}+1等于f(K,N-1)時，我們有f(K,N)=f(K,N-1)，否則，我們有f(K,N)=f(K,N-1)+1
在計算f(K,N)時我們考慮通過某種O(1)的手段，來確認是否存在相應的決策，進而實作O(1)的狀態轉移，
現在，我們思考一下，當我們試圖計算f(K,N)時，在這之前的計算中我們已經或者可以得出了什么？
我想，dp本身就是從已知子問題推匯出新問題的解的程序，所以，在我們試圖優化dp時，弄清我們在dp程序中能夠得出什么值或是規律、可以維護什么值至關重要，我們不應總把目光放在最終的結果或是回圈的層數上，當然，我不是說我們總是去盯著打出來的數表上，至少，我們不應總把dp的中間資料當成一個黑盒子，有時，或許只有善于觀察分析、或是不倦于打表觀察的人，才能發現打開寶盒的鑰匙，
啊這讓我想起了之前在洛谷隨機跳到的這道題，那個打表的題解就是我寫的（
啊說到底上面這段話只是我這個凡人的想法，不喜勿噴，
啊不小心跑題了，我們回到剛才的問題吧，
按照for回圈的順序，在我們試圖計算 f(K,N) 時，我們已經計算出了 f(K,0) 到 f(K,N-1) 的所有值，
對于的某個數p，假如其被用于 f(K,N) 的計算中，式子應該是這樣的：
\(f(K,N)=max\{f(K,p),f(K-1,N-p-1)\}+1\) p的含義為猜數后鷹蛋并沒有摔碎的時余下的范圍大小
我們知道，隨著 p 的增大，f(K,p) 的值會越來越大，而 f(K-1,N-p-1) 的值會越來越小，
當p=N-1時 f(K,N) = max{ f(K,N-1),f(K-1,0) }+1 = f(K,N-1) + 1
換句話說，如果我們試圖找到一個p使 max{ f(K,p),f(K-1,N-p-1) } + 1 = f(K,N-1)，這個p一定在N-1之前，
舉例來說，我們知道，在算 f(K,N-1) 時，假如 f(K,N-1) = f(K,N-2) 我們找的對應的 p 絕對不是 N-2 ，
再進一步講，我們希望 f(K,N) = f(K,N-1) ，我們選的這個 p ，其對應的 f(K,p) 就必須小于 f(K,N-1) （因為取了max后面還有個+1呢）
同時，我們不能忘記，max{ } 里頭還有個 f(K-1,N-p-1)
我們知道 f(K-1,N-p-1) 隨p的遞減而遞增，所以，我們的p既不能離N-1太近，又不能離它太遠，否則f(K-1,N-p-1)變大，這對我們沒有好處，
那么問題就簡單了，
我們取p 使之是滿足 f(K,p) < f(K,N-1) 的最大的數，由于我們知道 f(K,N) 相鄰項的最大差距是1 ，所以必然有 f(K,p) = f(K,N-1)-1
假如這個p不能使 max{ f(K,p),f(K-1,N-p-1) } + 1 = f(K,N-1) ，那么更小的p同樣不行，
這是很顯然的，因為 f(K,p) = f(K,N-1)-1，而 max{ f(K,p),f(K-1,N-p-1) } + 1 卻大于 f(K,N-1)，表明 f(K-1,N-p-1) 比 f(K,p) 要大，就算再往小的p處取，由于 f(K-1,N-p-1) 是隨p的遞減而遞增的，所以不可能取到更優的結果，
所以，我們每次只需要判斷 max{ f(K,p),f(K-1,N-p-1) } + 1 是否等于 f(K,N-1) 就行了，假如 f(K,N) 比 f(K,N-1) 還大，那么只需要把p改成N-1就行了，維護和查詢都是 O(1) 的，
這樣一來，我們就將dp優化到了 O(KN)
雖然這樣還是沒能算出1e18的資料，不過為了把這玩意理解表述得清楚、白話一點，我的腦細胞已經死光了
到這里，對這種dp已經優化得相當徹底了，無法再繼續優化了，
什么？你問1e18到底怎么算的？那是另外一種思路了，
七. 思路翻轉——最后的黎明
首先，讓我們用下面的k分法代碼跑一次 K=12 N=1e18 的資料（當然我們前面也理論分析過了是400多）
我們得到了444的結果，
再來點極端點的，我們跑個 K=3 N=1e18 的資料，
我們得到了1499999999的結果，
我們知道，k分法并不是最優的演算法，實際上我們在小資料的分析中已經發現，正解與K分法存在較大的差距，
比如： 同樣的 K=3 N=1e8 k分法跑出了14999 而用dp跑出的正解是844
這樣的差距，顯然會隨著N的增大而放大，
我想說明什么呢？既然我們知道，K>2時答案會比 1499999999 小得多，我們不妨大膽猜想：這個答案的大小相當有限，既然f(K,N)的狀態多到算不完，那么我們就調整一下思路，不再根據K和N來算猜數的次數F，而根據K和F來推導N的大小
換句話說，我們的dp思路是這樣的：
用 n(K,F) 表示通過 進行了F次猜數（其中摔壞了K個蛋），所能確定答案的最大區間長度，
我們知道，K=1時，我們只能一次一次從小到大猜，所以 n(1,F) 總等于 F
對于狀態轉移方程的推導，論文中描述得非常好懂，我在此處只做簡要介紹，順便解釋一下可能有些同學無法理解的為什么是加起來的問題（如果我講得清楚的話），
我們假設第F次猜的是數字x，若這個數比答案小，則接下來我們需要用余下的K個蛋（沒摔壞）去猜x+1開始的往上的區間，于是，我們將問題轉化為了用K個蛋猜F-1次的子問題，同理，如果這個蛋摔壞了，我們就將問題轉化為了用K個蛋猜F-1次的子問題，
我們有 \(n(K,F)=n(K-1,F-1)+1+n(K,F-1)\)
下面解釋為什么是兩個子問題的解加起來：
若在最壞情形下我們第F次猜的蛋沒摔壞，我們知道，那意味這x往下的區間就不需要我們去理會了，而往上的區間長度是有限的 n(K,F-1) ，所以為了達到最大的區間長度，我們需要把x往下的區間長度盡可能設大，但這并不意味著我們就可以為所欲為地把x往下的區間設到無窮大，我們知道，我們所有的討論的基于這樣一個前提：最壞情況下，而用K-1個蛋嘗試F-1次最終能確定的區間長度是 n(K-1,F-1) ，如果我們把區間長度設得更長，那么下面區間就需要更多的猜數次數，那么蛋摔壞的情況就會比沒摔壞的情況更劣，這就與最壞情形的前提相矛盾，因此，我們有n(K,F)=n(K-1,F-1)+1+n(K,F-1)
摔壞的情況同理，可以分析出相同的結論，
于是乎，我們只需要預先處理出 n(K,F) 之后二分查找 n(K,F)>=N，把最小的F輸出來就行了，
然后問題就來了，這個東西怎么算？要算到多大？
答案是，先算了再說，
（啊啊啊我居然一本正經得加粗了我在干什么）
論文中對這個復雜度有一個清晰嚴謹但我太菜了所以看不懂的證明，在此我們采用直接打表硬算的方式確定我們需要的范圍，
打表時，我們知道，蛋越多，同樣次數下能確定的區間就越大
所以，想知道需要F要開多大，我們其實不需要去試那么大的K
而F開大一點是必要的，但要小心long long可能會溢位的問題，可以在發現N可以取到1e18就停下來，
打表的代碼在后面的代碼庫中，
順帶一提，我有的地方使用了n(F,K) 有的地方用了 n(K,F) 大家不必糾結順序，只需要知道 K指人數 F指次數 就行了，
經過打表，在我們已經把F定到1e7的情況下，仍然求不出K=2下使 n(F,K)>=1e18 對應的F
而K=3的情況則順利得求了出來，F=1817121，這個數字的大小尚且還在我們能接受的范圍內，
但K=2顯然不能了，也就是說，對于K=2和1的情況，我們需要特判，
好在，這兩種情況都相對簡單，
對于K=2的情況：
n(F,2) = n(F-1,2) + n(F-1,1) + 1 = n(F-1,2) + F
換句話說 n(F,2) = 1 + 2 + 3 + ... + F = (1+F)*F/2
F*(F+1)=N*2
到此，問題已經解決（代碼在后面的代碼庫中），
最后，讓我們看看算出來的 K=12 N=1e18 的結果吧： 143
這個數字的大小，是否符合你們的預期呢？
尾聲 小小的宣傳
建議大家可以去看看那篇論文最后對動態規劃的總結，其實，比起學會一道題并把它A掉，總結方法更為重要，
作為一個連noip都沒拿過一等的小萌新，我真誠地希望你們能從我這篇博客中識訓到什么，
最后宣傳一下技術部的博客
里面會陸陸續續的有奇奇怪怪的干貨出來，歡迎大家關注，（雖然大概不會是我寫的）
番外1 Evil Check——部長的如意算盤
在部員們猜數字 x 的時候，部長是怎么認定，是否該讓x小于答案呢？
顯然，如果部長也打出了 f(K,N) 的表，那么他只需要根據表選擇一個更大的就行了，
這也是最科學、最準確的決策方式，
這里，我們試著給部長針對k分法的決策思路，
（其實我有試著給出更普遍的思路，但是最后失敗了）
我們知道，部長的目的是猜數次數最大化或是無法確定區間，
那么當人數只剩一人時，如果部員們犯下了不老老實實一個一個試的錯誤，就讓他們輸掉吧，
下面我們試著討論人數大于1的情形：
假如ta認定x不小于答案，就會有一名部員出局，
在k分法中，區間并不總是能被k整除，
例如，我們在將11分為三份時 每份為11/3=3......2
我們需要判斷的兩個三等分點為1 5 9 11
劃分出的三個區間分別為[1,4] [6,8] [10,11]
不難發現，除了最后一個區間，前面的區間的大小相同，
我們希望k分法的猜數次數盡可能多，自然就希望k分產生的k-1個中間點都被猜一次，
在最后一個k分點判斷時，顯然的，選擇讓x大于等于答案更優一些，這樣一來，一方面我們取到了倒數第二個的區間，這個區間不會小于最后余下來的那一段區間，另一方面，又使部員們失去了一次扔鷹蛋（猜較大數字）的機會，
typedef long long ll;
bool evil_check(ll l,ll r,ll x,ll c){
if(c==1) return x!=l;
return x-l > r-x;
}
番外2 對n(F,K)的感性分析
注意：這一節還沒寫完，有待完善，
科學嚴謹的比較分析和復雜度計算請移步論文，
在看HIT的題解時，我看到這樣一個結論：
\(n(F,K)=\sum^K_{i=1}{F\choose i}\)
\(F\choose i\) 表示 F選i的組合數（應該都看得懂吧）
關于這個結論怎么出來的，題解前面只有一句話："利用數學歸納法有:"
眾所周知數學歸納法是OI中最強大的演算法，不信你去看輾轉相除法
我想在這里用一種比較感性的方式解讀這個公式，
自己畫個楊輝三角出來吧，方便理解，
n=0: 1
n=1: 1 1
n=2: 1 2 1
n=3: 1 3 3 1
首先，n(F,K)與C(n,m)也就是n選m的組合數遞推公式有相似之處，
公式1：n(F,K) = n(F-1,K) + n(F-1,K-1) + 1 (K>1)
公式2：C(n,m) = C(n-1,m) + C(n-1,m-1)
撇開原有的數不看，當n=1這一層往下統計K>1的點時時多加了1，多出來的這個數造成的變化
n=0: 0
n=1: 0 0
n=2: 0 1 1
n=3: 0 1 2 1
好像有什么不對的（
算了，我爬（
代碼庫
需要注意一下，ural那道題的k可以到1000，記得特判k比較大的情況，真的傻逼，
比如下面這樣，
if(k>=log2(n)){ printf("%d\n",log2(n)); continue; }
下面的代碼一般默認為K<=63
N的話可以根據復雜度自行選擇合適的大小，（畢竟我開了vector）
還有，我的log2(n)是自己寫的，因為我覺得直接用函式去算有點太玄學了，還不如自己模擬一遍，反正常數也差不了多少，
下面的代碼僅供理解和研究，可能會因為stl的常數問題被卡爆，但是比較清晰和簡潔，
我把所有的修改過的且ac的代碼扔在另一篇文章里，有需要的可以進行參考，
發現代碼有誤可以在評論區指出，不過我查了挺多遍了，合理沒有問題，
順帶一提，我的輸入格式不一定按著題目來，你們想提交的話要改一下，都能A的，
不會吧應該不會有人看不懂滾動陣列吧不會吧
代碼1：k分法 附帶適用于k分法的evil_check
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
bool evil_check(ll l,ll r,ll x,ll c){
if(c==1) return x!=l;
return x-l > r-x;
}
ll guess3(ll N,ll K){
ll l=1,r=N,c=K,cnt=0,block,num,mid;
while(l<=r){
num=floor(pow(r-l+1,1.0/(c-1)));
block=(r-l+1)/num+1; mid=l;
while(mid+block<=r){
mid+=block; cnt++;
if(evil_check(l,r,mid,c)){
c--; r=mid-1; break;
}else l=mid+1;
}
if(l==mid) break;
}
while(l<=r){
cnt++;
if(evil_check(l,r,l,c)) break;
l++;
}
//上面這個while可以直接改成 cnt+=(r-l+1);
return cnt;
}
int main(){
//注意讀入順序 先人數 后范圍
ll K,N; scanf("%lld%lld",&K,&N);
printf("%lld\n",guess3(N,K));
return 0;
}
代碼2：無優化的n^3 dp 附帶決策程序的打表
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define REG register
#define rep(i,a,b) for(REG int i=a;i<=b;i++)
#define Rep(i,a,b) for(REG int i=a;i>=b;i--)
const int INF=1e9;
int N,K;
int main(){
scanf("%d%d",&K,&N);
vector<int> f[K+1],pre[K+1];
//resize后vector中元素默認為0
rep(i,0,K) f[i].resize(N+1),pre[i].resize(N+1);
rep(i,1,N) f[1][i]=i;
rep(i,2,K){
rep(j,1,N){
f[i][j]=INF;
rep(w,1,j){
int now=max(f[i-1][w-1]+1,f[i][j-w]+1);
if(now<f[i][j]){
f[i][j]=now;
pre[i][j]=w;
}
}
}
}
printf("%d\n",f[K][N]);
//下面是決策路徑的列印
int x=K,y=N,base=max(K,N)+1,l=1;
vector<int> route,L;
route.push_back(x*(N+1)+y); L.push_back(l);
while(pre[x][y]){
REG int w=pre[x][y];
if(f[x-1][w-1]>f[x][y-w]) x--,y=w-1;
else y-=w,l+=w;
L.push_back(l);
route.push_back(x*base+y);
}
rep(i,0,route.size()-1){
x=route[i]/base,y=route[i]%base;
if(y==0) break;
printf("[%d,%d] with %d people f[%d][%d]=%d\n",L[i],L[i]+y-1,x,x,y,f[x][y]);
}
return 0;
}
代碼3：二分優化+部分(i,j)直接取二分結論
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
inline int log2(int x){
//直接模擬二分程序的最壞情況
int l=1,r=x,c=0;
while(l<=r){
int mid=(l+r)>>1; c++;
if(r-mid>mid-l) l=mid+1;
else r=mid-1;
}
return c;
}
int main(){
int k,n; scanf("%d%d",&k,&n);
vector<int> f,p;
f.resize(n+1); p.resize(n+1);
for(int i=1;i<=n;i++) f[i]=i;
for(int i=2;i<=k;i++){
f.swap(p); f.resize(n+1); f[1]=1;
for(int j=2;j<=n;j++){
//當足以二分時 直接二分
if(i>=log2(j)){ f[j]=log2(j); continue; }
//利用二分查找找出交匯點 確定可能的兩個位置并比較
int l=1,r=j,mid,ans=r;
while(l<=r){
mid=(l+r)>>1;
if(p[mid-1]>=f[j-mid]) ans=mid,r=mid-1;
else l=mid+1;
}
f[j]=max(p[ans-1],f[j-ans])+1;
if(--ans>=1) f[j]=min(f[j],max(p[ans-1],f[j-ans])+1);
}
}
printf("%d\n",f[n]);
return 0;
}
代碼4：O(KN) 線性神仙優化
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
int k,n; scanf("%d%d",&k,&n);
vector<int> f,p; f.resize(n+1);
for(int i=1;i<=n;i++) f[i]=i;
for(int i=2;i<=k;i++){
f.swap(p); f.resize(n+1);
int pre=0; f[1]=1;
for(int j=2;j<=n;j++){
//f[pre]<f[j-1]且是滿足這個條件的最大pre
if(max(f[pre],p[j-pre-1])+1==f[j-1]) f[j]=f[j-1];
else f[j]=f[j-1]+1,pre=j-1;
}
}
return printf("%d\n",f[n]),0;
}
代碼5 打表以確定需要預處理的 g(K,F) 的范圍
#include <cstdio>
typedef long long ll;
const ll F=1e7,K=3,N=1e18;
ll f[F+3][K+1];
int main(){
for(int i=1;i<=F;i++) f[i][1]=i;
f[1][1]=f[1][2]=f[1][3]=1;
for(int i=2;i<=F;i++){
for(int k=2;k<=K;k++){
f[i][k]=f[i-1][k]+f[i-1][k-1]+1;
}
}
for(int k=2;k<=K;k++){
printf("K=%d:",k);
bool have=0;
for(int i=1;i<=F;i++){
if(f[i][k]>=N){ have=1; printf("%d",i); break; }
}
if(!have) printf("MAX:%lld",f[F][k]);
printf("\n");
}
return 0;
}
代碼6 另一個的dp思路
其實HIT的原題K<=64 不過K>60的情況會因為log2(1e18)=60而被判掉
然而請同學幫忙測的時候還是re了，或許是oj問題，
這里給出一個HIT的大樣例供參考：
353529145519311753 5
答案是 8426
我跑的也是 8426 那就當它過了吧（霧
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
#define REG register
#define rep(i,a,b) for(REG int i=a;i<=b;i++)
#define Rep(i,a,b) for(REG int i=a;i>=b;i--)
inline char getc(){
static char buf[1<<14],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<14,stdin),p1==p2)?EOF:*p1++;
}
inline ll scan(){
REG ll x=0; REG char ch=0;
while(ch<48) ch=getc();
while(ch>=48) x=x*10+ch-48,ch=getc();
return x;
}
inline ll log2(ll x){
ll l=1,r=x,mid,c=0;
while(l<=r){
mid=(l+r)>>1; c++;
if(mid-l>r-mid) r=mid-1;
else l=mid+1;
}
return c;
}
const ll F=2e6,K=60,N=1e18;
ll f[K+1][F],end[K+1];
inline void prework(){
rep(i,1,F-200) f[1][i]=i;
rep(i,1,F-200){
rep(j,2,K){
if(end[j]) break;
f[j][i]=f[j][i-1]+f[j-1][i-1]+1;
if(f[j][i]>=N) end[j]=i;
}
}
}
int main(){
REG int T=scan();
prework();
while(T--){
REG ll n=scan(),k=scan(),temp;
if(k==1){ printf("%lld\n",n); continue; }
if(k==2){
ll t=floor(sqrt(n<<1));
if(t*(t+1)<n<<1) t++;
printf("%lld\n",t); continue;
}
temp=log2(n);
if(k>=temp){ printf("%lld\n",temp); continue; }
REG int l=1,r=end[k],mid,ans;
while(l<=r){
mid=(l+r)>>1;
if(f[k][mid]>=n) r=mid-1,ans=mid;
else l=mid+1;
}
printf("%d\n",ans);
}
return 0;
}
END
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/161519.html
標籤：其他
下一篇：—用python寫截屏小工具