糯米

題目大意：
給出一個(gè)序列，長(zhǎng)度為N，均為正數(shù)。
找出一段連續(xù)的區(qū)間，此區(qū)間的平均值最大，長(zhǎng)度必須大于F。

好像還是有點(diǎn)實(shí)際用途的，這個(gè)問題。
看完題之后，基本上就知道是做不出來的了。只想得到那種最簡(jiǎn)單的O(N^2)的解法，但是N = 100,000。這種解法必然超時(shí)。

在網(wǎng)上搜了兩個(gè)解題報(bào)告，發(fā)現(xiàn)此題的解法相當(dāng)牛逼！
兩種解法是完全不同類型的。

二分法
我們可以比較容易得出答案的最大值和最小值，即為序列中最大元素和最小元素。
二分法的關(guān)鍵在于判斷“一個(gè)可能的解跟正確答案相比是大了還是小了”。網(wǎng)上給的方法是：
如果要判斷val這個(gè)解，那就讓序列里所有元素的值都減去val。
然后試圖尋找一段連續(xù)的區(qū)間，該區(qū)間的長(zhǎng)度大于F，并且區(qū)間大于0。
可見，問題一下轉(zhuǎn)化成統(tǒng)計(jì)數(shù)字的和，而不是數(shù)字的平均值，問題變得明朗了。
尋找這種區(qū)間的算法是一個(gè)很簡(jiǎn)單的動(dòng)態(tài)規(guī)劃，復(fù)雜度為O(N)。
用 f[a, b] 表示在區(qū)間 [a, b] 中，所有子區(qū)間的最大值。
那么
當(dāng) b - a = F 時(shí)，f[a, b] 為序列中對(duì)應(yīng)的和。
當(dāng) b - a > F 時(shí)，f[a, b] = max{ f[a, b - 1] + arr[b], f[b - f + 1, b] }

我們要求的是 f[0, N]。
因此，二分法的復(fù)雜度是 O(NlgN)。代碼跑了接近300ms。




凸包法
這個(gè)方法不是真的求點(diǎn)的凸包，是用了求凸包時(shí)候的技巧。
首先把序列轉(zhuǎn)化成一個(gè)圖，一共有N個(gè)點(diǎn)，第 i 個(gè)點(diǎn)的坐標(biāo)為 (i, S[i])，其中 S[i] 為序列的前 i 項(xiàng)和。
在圖上，能觀察到，點(diǎn)a點(diǎn)b之間的斜率就是區(qū)間[a, b]的平均值。
當(dāng) N = 6, F = 3 的時(shí)候，按照最簡(jiǎn)單的 O(N^2) 的做法，計(jì)算每?jī)蓚€(gè)點(diǎn)之間的斜率，計(jì)算的順序?yàn)椋?br>[1, 3]
[1, 4] [2, 4]
[1, 5] [2, 5] [3, 5]
[1, 6] [2, 6] [3, 6] [4, 6]
在算第6個(gè)點(diǎn)的時(shí)候，依次算了1，2，3，4跟點(diǎn)6的斜率。
為了避免不必要的計(jì)算，我們要沒必要計(jì)算的點(diǎn)剔除。
用類似凸包的計(jì)算更新方法，在點(diǎn)1，2，3。。。中維護(hù)一條“下凸折線”。
這樣，可以保證末尾的點(diǎn)跟折線中的點(diǎn)的斜率是先遞增再遞減的關(guān)系。
就能比較快的找出最大的斜率了。
這個(gè)算法的復(fù)雜度，網(wǎng)上的人說是O(N)，但我覺得好像不是O(N)啊，也不知道是什么。
但是，絕對(duì)不能單單以復(fù)雜度來評(píng)價(jià)算法的啦。
代碼跑了150ms左右。比2分的還是快一點(diǎn)。

思路：
事先計(jì)算出第1500個(gè)數(shù)為859963392，枚舉2，3，5的所有乘積，過濾掉所有大于859963392的數(shù)。
積攢到1500個(gè)的時(shí)候停止計(jì)算。然后快排就行了。速度還挺快呢。0ms。

思路：
每個(gè)節(jié)點(diǎn)記錄兩個(gè)值：
所有子節(jié)點(diǎn)的增量和
該節(jié)點(diǎn)的增量

代碼爛，1500+ms。
為了避免爆棧，實(shí)現(xiàn)計(jì)算好了左右邊界和中間值。

題目大意：
給出一個(gè)01字符串。將其循環(huán)移位，將所有移位后的串列舉出來，并按字典序排序。
比如“abcd”，可以移位成“bcda”，“cdab”，“dabc”。排序以后，為
“abcd”
“bcda”
“cdab”
“dabc”
將最后一列的字母抽取出來，即“dabc”。
然后，讓你還原出第一行的字符。

這是一個(gè)看上去很蛋疼的問題，沒事研究這個(gè)干啥呢。
想了半天，做不出來。看到discuss里面有人給了一個(gè)鏈接：
http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform

發(fā)現(xiàn)居然是一個(gè)壓縮算法！
據(jù)說，將最后一列抽取出來，較原字符串相比，能夠
“easy to compress a string that has runs of repeated characters by techniques such as move-to-front transform and run-length encoding.”
這個(gè)就不理解了。。

這題簡(jiǎn)化了一下條件，字符串只包含01。

看了它的還原方法。如果直接這樣寫：

def ibwt(r):
"""Apply inverse Burrow-Wheeler transform."""
table = [""] * len(r)  # Make empty table
for i in range(len(r)):
table = [r[i] + table[i] for i in range(len(r))]  # Add a column of r
table.sort()
s = [row for row in table if row.endswith("\0")][0]  # Find the correct row (ending in "\0")
return s.strip("\0")  # Get rid of trailing null character

還是復(fù)雜度很高，為 O(N*N*lgN)。

那disscus里面說的O(N)的方法和那么多0ms是咋來的呢？

想了一下。發(fā)現(xiàn)每一次添加列然后再排序的操作，都是做一樣的置換。
因?yàn)槊看翁砑拥牧卸家粯樱判虻慕Y(jié)果當(dāng)然也是一樣（比如是穩(wěn)定排序）。
所以，第i列的結(jié)果就是置換i次的結(jié)果。我們只需要第一行的數(shù)據(jù)。
經(jīng)過一次排序之后，就知道每一個(gè)行置到了哪個(gè)地方，如果第三行到了第一行，第五行到了第三行。
那么：
第一列第一行的就是未排序數(shù)據(jù)的第三行
第二列第一行的就是未排序數(shù)據(jù)的第五行

由于數(shù)據(jù)中只有01，完全可以在O(N)內(nèi)完成排序操作，之后得出第一行的操作也是 O(N) 完成的。
可惜代碼實(shí)現(xiàn)出來，也沒有到 0ms ，好像是 79ms 。代碼寫得爛！高手改改也是0ms了。
代碼里也包括了一個(gè)求普通字符串的BWT操作。

題目大意：
兩個(gè)人玩游戲。輪流取數(shù)字，范圍在1~20之間。
規(guī)定：
1. 取過的數(shù)字不能再取。
2. 取過的數(shù)字的倍數(shù)不能再取。
3. 任意個(gè)(2)的和不能再取。

當(dāng)某個(gè)人發(fā)現(xiàn)沒有數(shù)字可取時(shí)，他就輸了。
給出一個(gè)“殘局”。問，我現(xiàn)在應(yīng)該怎么取，才能保證勝利。

思路：
其實(shí)這個(gè)也不是很難的博弈問題。只是搜索就可以解決了。要用位來表示當(dāng)前剩余數(shù)字的狀態(tài)，
方便保存動(dòng)態(tài)規(guī)劃的結(jié)果。

題目大意：
有個(gè)叫smith的人，閑得蛋疼，做了如下定義：
如果一個(gè)數(shù)分解的質(zhì)因數(shù)的所有位數(shù)的和加在一起等于該數(shù)字的所有位數(shù)的和，則這個(gè)數(shù)是“smith數(shù)”。
比如：
則4937775是“smith數(shù)”。
另外：素?cái)?shù)不是“smith數(shù)”
給出一個(gè)數(shù)字，求出比該數(shù)字大的數(shù)中最小的“smith數(shù)”。


思路：
按照常規(guī)方法，從2一直向上掃描，遇到能除的就除，求出數(shù)字的質(zhì)因數(shù)。
但要注意，如果掃到大于該數(shù)字的平方，就沒必要繼續(xù)掃了，一定是素?cái)?shù)。沒加這個(gè)就是TLE。
另外，如果現(xiàn)有的和已經(jīng)超過了最大的可能和，也沒必要繼續(xù)掃了。

思路：
先快排，然后用公式計(jì)算出總的volume值。

 

     摘要:   #define ICON_SIZE 32static int _HBitmapToBmp32Bits(HBITMAP hBitmap, U8 *out, int out_len){       /**//* &nb...  閱讀全文