摘要：買糖果題目來源京東實習生招聘原題鏈接可在線提交賽碼網問題描述某糖果公司專門生產兒童糖果，它最受兒童歡迎的糖果有兩個序列，均采用盒式包裝。小東希望你能幫她解決這一問題。

最近比較忙，又有一段時間沒寫題目了，終于在前幾天把賽碼網上，JD的2016秋招和2017實習生招聘剩下的4星難度題目做了，至此所有4星難度題目都解決了，5星難度題目還剩下一個應該是計算幾何學的題目，因為這塊我不熟悉，后面找時間再處理。
鑒于賽碼網的難度分類不是特別準確，接下里我把1-3星難度的題目過一次，如果有價值的就和大家一起分享。
這次的解析包含了4個題目，相對比較簡單，但需要考慮全面，否則容易掉坑。

<題目來源: 京東2016實習生招聘 原題鏈接-可在線提交(賽碼網)>

某糖果公司專門生產兒童糖果，它最受兒童歡迎的糖果有A1、A2兩個序列，均采用盒式包裝。包裝好的A1類糖果體積為一個存儲單位，而包裝好的A2類糖果體積正好是A1類的兩倍。
這兩類糖果之所以廣受兒童歡迎，是因為糖果中含有公司獨家研發的魔幻因子。A1或A2序列中的糖果，看起來包裝可能是一樣的，但因為其中的魔幻因子含量不同被細分為不同的產品。
臨近傳統節日，公司的糖果供不應求。作為一個精明的糖果分銷商，小東希望能夠借此大賺一筆，于是帶著現金開著貨車來公司提貨。貨車的容量是確定的，小東希望采購的糖果能夠盡可能裝滿貨車，且糖果的魔幻因子總含量最高。只要不超出貨車容量，糖果總可以裝入貨車中。
小東希望你能幫她解決這一問題。

這個題目的描述似乎不是太準確，其實題目就是說有n個糖果，每個糖果有個體積(1或者2)，此外，有個魔幻因子。最后我們需要解決是在體積不超過v的情況下，選擇若干糖果并且盡可能的獲得最大的魔幻因子總量。

這看起來是個01背包問題*[1]，觀察數據規模后發現，n <= 10^5，v <= 10^9這個用于狀態轉移的枚舉量實在太大，而且單就一個v的上限就足以撐爆空間。看來問題似乎不是直接使用01背包的動態規劃可以解決的，再觀察題目條件，一個比較特別的地方是糖果的體積只有1和2的兩種情況，我們從這個比較特殊的條件來解決問題。

a.考慮一種最簡單的情況：只有體積為1的糖果。
顯然我們只需要對所有的糖果按照魔幻因子從大到小排序，從魔幻因子最大的糖果開始選擇，由于體積都是1，那么給定的v一定可以達到。這些選擇出來的糖果的魔幻因子的和就是我們的求解目標。

b.再考慮另外一種罪簡單的情況，只有體積為2的糖果。
同樣我們需要按魔幻因子的大小進行排序，然后從魔幻因子最大的糖果開始選擇，但是不同于a，由于是每個糖果的體積是2，那么選出來糖果的體積和不一定可以剛好為v，如果剛好為v則問題已經解決。如果超過v，顯然是總體積比v大了1，那么最后選擇的這一種糖果就不要了。這時我們選擇的糖果的總體積為v-1，盡管浪費了1，但是我們沒有任何辦法再放入糖果了。

c.考慮題目既有體積1和2的情況。
基于上述兩種基本情況的分析，我們仍然需要安排魔幻因子大小進行排序，盡可能選擇魔幻因子高的優先選擇，再考慮臨界情況的處理。需要注意到，對于體積為2的糖果，我們不應該直接按照其魔幻因子的總量進行排序，而是按照單位體積的魔幻因子含量進行排序。這是因為，盡管可能體積為2的糖果魔幻因子可能很高，但是他占用2個體積，如果兩個體積為1的糖果魔幻因子沒有其高，但是兩個加起來就超過了，并且最終占用的體積都是2.

排序之后我們按照從大的開始選擇，如果可以剛好取到v，那么問題就得到解決。如果得不到，那么顯然當前取的是體積2的糖果，并且是超過1。這個時候，明顯我們可以有多種選擇，我們既可以在已經選擇的糖果中去掉一個體積為1的且魔幻因子最小的糖果，也可以是在還沒有選擇的糖果中選擇一個體積為1的且魔幻因子最大的一個糖果。至于具體選擇哪種就看哪種方案可以獲得更高的魔幻因子總和了。

那么問題似乎已經解決了，然后我們并沒有考慮到選擇的和沒選擇的中都可能不存在體積為1的糖果。
...已選擇部分...| 體積為2的糖果| ...未選擇部分...

 ^已獲得的魔幻因子pm ^體積限制v

設已選擇的最小的體積為1的糖果的魔幻因子為l
設未選擇的最小的體積為1的糖果的魔幻因子為r
當前體積2的糖果魔幻因子為p，體積不超過v獲得最大的魔幻因子總和為pm
i.l和r都不存在

= v
ii.l存在，r不存在

= max(pm, pm - l + p)

iii.l不存在，r存在

= pm + r
iv.l和r都存在

= max(pm + r, pm - l + p)

最后一個需要解決的問題是輸出選擇糖果的序列問題，這并不難，我們排序后依次記錄選擇了的糖果即可。pm - l + p的情況，刪除記錄中的l即可。但是，由于存在多種方案要得失編號盡可能的小，那么對與ii, iv中存在相等的情況時的處理原則時，選擇編號較小的即可。

排序時間復雜度為O(nlogn)，由于每個糖果只需要處理一次，計算部分時間復雜度為O(n)，非常理想。

import sys

const_n = 0
const_v = 1
const_p = 2


def main():
    while True:
        line = map(int, sys.stdin.readline().strip().split())
        n, vm = line[0], line[1]

        candies = []
        for i in range(n):
            line = map(int, sys.stdin.readline().strip().split())
            if len(line) < 2:
                break
            candies.append((i + 1, line[0], line[1]))

        candies = sorted(candies, key=lambda s: float(s[const_p]) / float(s[const_v]), reverse=True)
        # print candies

        seq = set([])
        v = p = 0
        l = r = -1
        for i, candy in enumerate(candies):
            if v + candy[const_v] >= vm:
                if v + candy[const_v] == vm:
                    seq.add(candy[const_n])
                    p += candy[const_p]
                else:
                    for j in range(i + 1, n):
                        if candies[j][const_v] == 1:
                            r = j
                            break

                    if l == -1 and r == -1:
                        pass
                    elif l == -1 and r != -1:
                        p += candies[r][const_p]
                        seq.append(candies[r][const_n])
                    elif l != -1 and r == -1:
                        if candy[const_p] - candies[l][const_p] > 0:
                            p = p - candies[l][const_p] + candy[const_p]
                            seq.remove(candies[l][const_n])
                            seq.add(candy[const_n])
                    else:
                        if candy[const_p] - candies[l][const_p] > candies[r][const_p]:
                            p = p - candies[l][const_p] + candy[const_p]
                            seq.remove(candies[l][const_n])
                            seq.add(candy[const_n])
                        else:
                            p += candies[r][const_p]
                            seq.add(candies[r][const_n])
                break

            seq.add(candy[const_n])
            v += candy[const_v]
            p += candy[const_p]

            if candy[const_v] == 1:
                l = i

        print p
        if p > 0:
            seq = sorted(seq)
            for s in seq:
                print s,
        else:
            print "No"
        print

if __name__ == "__main__":
    main()

<題目來源: 京東2017實習生招聘 原題鏈接-可在線提交(賽碼網)>

收到情報，有批新造的機器人要運輸到前線。小C將去破壞機器人的運輸。小C將激光炮放置在公路的一旁，等運輸車經過的時候發射（假設激光炮一定可以射穿車輛）。由于能源有限，激光炮只能發射兩次。可以認為激光炮放在坐標軸的原點處，并向y軸正方向發射。每輛運輸車可以看作是一個矩形，起始的x軸坐標為Xi ,所有的車均位于第一象限，長度為Li,速度為1，朝x軸負方向運動。即經過t時間后，該車車頭的x坐標為Xi-t，車尾坐標為Xi-t+Li 。只要打中車的任何一個部分就算擊中。
請你算算，他在哪兩個時刻發射，才能摧毀最多的運輸車。

先簡化下題目的意思，由于每個車輛的前進速度是統一的，那么實際上我們就不用考慮車子移動的情況了，只需要在x軸上選擇兩個點發射激光炮即可。此外，這個題目的數據規模是X、L<= 10^9 而不是109。

需要注意，第2次發射的激光炮不會擊毀被第一次發射的激光炮已經擊毀的車子。也就是1輛車不能被擊毀兩次。我們就不能單純在按某個點上的車輛最多和次多來選擇x軸上發射激光炮的位置了。考慮到只能發射兩枚激光炮，那么我們只需要枚舉這2個位置就可以了。

但是觀察X和L 10^9的限時，直接枚舉x軸上的兩個點顯然不可以。

我們考慮兩個車有重疊的情況，要判斷有沒有辦法一炮機會這兩個車子，實際上我們只需要判斷兩個位置即可，即某個車頭的點是在另外一個車的范圍內即可。這是一種對于極限情況的考慮，如果該情況成立，就還會有若干其他的點可能滿足，但這部分點就不需要再判斷。換句話說，兩個車如果有重疊，那么其中有個車的車頭一定在另外一個車的車身范圍內。

擴展到一般情況，根據上面的討論，對于所有的車，我們激光炮的發射位置只需要選擇每個車車頭的位置即可。枚舉之后再判斷哪些車子被擊毀，做上標記。最后記錄一個最大的擊毀數目即可。由于車輛總數n僅僅200，先兩重循環枚舉2個車頭位置，再用一層循環檢查擊毀數目，算法的時間復雜度為O(n^3)是可以接受的。

import sys


def calc(f, s, c, n):
    destroy = [False for i in range(n)]
    res = 0

    for i, elem in enumerate(c):
        if elem[0] <= f <= elem[1] or elem[0] <= s <= elem[1]:
            if not destroy[i]:
                res += 1
            destroy[i] = True

    return res


def main():
    n = map(int, sys.stdin.readline().strip().split())[0]
    cars = []
    segments = []

    for i in range(0, n):
        line = map(int, sys.stdin.readline().strip().split())
        cars.append((line[0], line[0] + line[1]))
        segments.append(line[0])

    r = 0
    for i in range(len(segments)):
        for j in range(i):
            r = max(r, calc(segments[i], segments[j], cars, n))

    print r


if __name__ == "__main__":
    main()

<題目來源: 京東2017秋招 原題鏈接-可在線提交(賽碼網)>

小明同學學習了不同的進制之后，拿起了一些數字做起了游戲。小明同學知道，在日常生活中我們最常用的是十進制數，而在計算機中，二進制數也很常用。現在對于一個數字x，小明同學定義出了兩個函數f(x)和g(x)。
f(x)表示把x這個數用十進制寫出后各個數位上的數字之和。如f(123)=1+2+3=6。
g(x)表示把x這個數用二進制寫出后各個數位上的數字之和。如123的二進制表示為1111011，那么g(123)=1+1+1+1+0+1+1=6。
小明同學發現對于一些正整數x滿足f(x)=g(x)，他把這種數字稱為幸運數，現在他想知道，小于等于n的幸運數有多少個。

接下來的這兩個題目相對比較簡單，數據范圍也不大，這個題目可以直接按照題目意思模擬即可。
注意以下兩點問題：
1.這類題目都要采用離線的計算方式，一次性先把數據規模內的數據全部計算到出來并保存，然后根據輸出直接輸出結果即可。
2.相對來說這個題目的數據規模較弱，注意到在當次計算時，如果個位沒有發生進位的話，結果就是上次計算的結果+1，如果發生了進位再全部計算一次即可。這樣可以節約非常大的一個計算量。

提交后我大致看了下運行時間，我使用的python耗時369ms，而其他python和java耗時接近或者超過1000ms，其中一個C++的運行時間為623ms。有時候一個很小的優化帶來的性能提升是很顯著的。

import sys

const_max_n = 100000 + 1


def _next(bits, last_sum, base):
    next_add = 0
    bits[0] += 1
    last_sum += 1

    if bits[0] >= base:
        last_sum = 0
        for i in range(len(bits)):
            bits[i] += next_add
            if bits[i] >= base:
                bits[i] = 0
                next_add = 1
            else:
                next_add = 0
            last_sum += bits[i]

        if next_add == 1:
            bits.append(1)
            last_sum += 1

    return last_sum


def main():
    r = [0 for i in range(0, const_max_n)]
    _dec = [0]
    _bin = [0]
    last_bin_sum = last_dec_sum = 0

    for i in range(1, const_max_n):
        last_bin_sum = _next(_dec, last_bin_sum, 2)
        last_dec_sum = _next(_bin, last_dec_sum, 10)

        r[i] = r[i - 1]
        if last_bin_sum == last_dec_sum:
            r[i] += 1

    t_case = map(int, sys.stdin.readline().strip().split())[0]
    for i in range(0, t_case):
        n = map(int, sys.stdin.readline().strip().split())[0]
        print r[n]


if __name__ == "__main__":
    main()

<題目來源: 京東2016實習生招聘 原題鏈接-可在線提交(賽碼網)>

三子棋是一種大家熟知的游戲，幾乎所有人都會玩。游戲規則相當簡單，兩人依次在一個3X3棋盤格上下棋，一個人畫叉，另一個人畫圈。任何一個人畫的三個記號如果形成構成一條水平、垂直或對角的直線則獲勝，游戲結束。畫叉的人先開始游戲，如果所有的棋盤格都畫滿了但兩人都不能獲勝，則游戲平局結束。
游戲在一個3X3的棋盤上進行，每個棋盤格單元處于空白、畫叉或畫圈狀態中的一種，你的任務是確定下一輪由誰下棋: 
1：輪到先手下棋；
2：輪到后手下棋；
或者是判定游戲的狀態： 
x：給定的棋局不是合法的棋局； 
1 won：先手獲勝； 
2 won：后手獲勝； 
Draw：平局；
小東對棋類游戲很有研究，這一次三子棋比賽中，她被邀請作為評判，為了提攜后進，她請你幫忙判定。

本題看似簡單，其實要注意的地方還比較多，包括如何比較優雅的完成代碼的編寫(這我代碼也寫不太好)。

注意到本題的條件具有先后順序。應該是下列順序：
1.給定的棋局是否合法；
2.是否有獲勝方；
3.平局
4.該誰下棋

這類題目建議使用一個方向向量，方向向量可以指示要判斷的方向。比如，要判斷一個從上到下的對角線情況，我們可以設置一個(1,1)的方向向量，當從(0,0)開始后：

= (0, 0)

sx = 0, sy = 0
for i <- 0 to 2:
sx += d[0]
sy += d[1]
即可，對于本題，設置一個判斷8個方向的起始位置后，再對應設置8個方向向量即可。這樣對于我們編寫代碼十分有利。可以最大限度的減少代碼量，便于閱讀。

import sys

start = [(2, 0), (1, 0), (0, 0), (0, 0), (0, 0), (0, 1), (0, 2), (2, 0)]
vector = [(0, 1), (0, 1), (0, 1), (1, 1), (1, 0), (1, 0), (1, 0), (-1, 1)]

def main():

while True:
    x = o = 0
    board = []
    for i in range(3):
        line = map(str, sys.stdin.readline().strip().split())
        if len(line[0]) < 3:
            return
        for l in line[0]:
            if l == "X":
                x += 1
            elif l == "0":
                o += 1
        board.append(list(line[0]))

    legal = True
    w1 = w2 = False

    if 0 <= x - o <= 1:
        for i in range(8):
            d = {"0": 0, "X": 0, ".": 0}
            dx, dy = start[i][0], start[i][1]
            for j in range(3):
                t = d.get(board[dx][dy])
                d[board[dx][dy]] = t + 1
                dx += vector[i][0]
                dy += vector[i][1]

            if d.get("X") == 3:
                w1 = True
            if d.get("0") == 3:
                w2 = True

        if w1 and w2 or x > o and w2 or x == o and w1:
            legal = False

    else:
        legal = False

    if legal:
        if w1:
            print "1 won"
        elif w2:
            print "2 won"
        else:
            if x + o == 9:
                print "draw"
            elif x == o:
                print "1"
            else:
                print "2"
    else:
        print "x"

if name == "__main__":

main()

*[1] 關于01背包問題及其擴展可以參考下列文章:
http://blog.csdn.net/mu399/ar...
http://blog.csdn.net/insistgo...