前言

至少半年沒寫算法題了，手生了不少，由于python寫太多導致行末老是忘記打分號，printf老是忘記寫f，for和if的括號也老是忘寫，差點連&&和||都忘記了。

題目都是回憶版本，可能有不準確的地方。

代碼如果有機會能拿到的話，會補充的。

A

統計1~202504之間每個數字各數位上的數之和被5整除的個數。

直接循環統計就完事了。

B

統計所有IPv6地址的最短形式的長度之和。

縮寫規則為，每個四位十六進制數的前導零可以省略，除此之外可以省掉一串連續的0000。

注意，當省略的0000序列在序列兩端時，會變成::

例如0234:0000:0000:0000:000f:1f1f:00ab:0000,可以縮寫為

234::f:1f1f:ab:0，長度就是3+2+1+1+4+1+2+1+1=16

但0000:0000:0000:000f:1f1f:00ab:0234:0000，應該縮寫為

::f:1f1f:ab:234:0，長度就是2+1+1+4+1+2+1+3+1+1=17

題解

這題很有意思，陷阱很多。（復盤的時候發現自己錯了）

首先顯然一個非0的四位十六進制數去除前導零的長度總和為sumlen=(15*1+15*16*2+15*16*16*3+15*16*16*16*4)

一個非0的四位十六進制數有sumcnt=(15+15*16+15*16*16+15*16*16*16)種

兩個四位十六進制數長度總和需要求卷積，而不是直接相加或者相乘。

當然也可以一個一個數計算貢獻，也就是sumlen*[sumcnt^(n-1)]*n種（可證明和卷積是等價的）

然后就是最短形式，如果有多串長度相同的連續的0地址，應該優先省去中間的0串。

枚舉最長的0串區間求解的話，會有很多問題，例如去重、合法串的限制。

所以枚舉八個四位十六進制數分別為0的所有組合，時間復雜度為2^8

然后根據枚舉的情況來求應該省去的0串的位置，計算所有0地址提供冒號和0的長度。

最后計算非0地址貢獻的長度總和sum，然后用sumcnt^(非0地址個數)*（所有0地址提供的冒號和0的長度）計算所有0地址的貢獻，最后加起來就可以了。

寫完之后就9：40多了。

C

一個序列ai長度為n，m次操作，一次操作把序列中每個數變成ai*bitcount(ai)，求m次操作后的序列。

n<=1000,m<=5，ai<=1000。

直接模擬即可。

D

最大數字

輸入n，將1~n的每個數字轉換為二進制，拼接成一個長二進制串，再轉換回十進制，要求最終的十進制數最大。

n<=10000

題解

把每個數字的二進制放入結構體，重載小于符號為

a拼接b > b拼接a

（可惡，我連這個都忘記了，直接按字典序排了，太久不做題導致的）

然后排完序之后用原數據值進行高精度計算（用二進制串直接計算會超時），最后用longlong壓8位，勉強能在1秒內出結果。

（我這個SB題還寫了一個小時，我真是服了）

E

冷熱數據隊列

q1隊列長度為n1，q2隊列長度為n2，訪問一個數據x

四條規則

若x不在q1、q2中，則將x加入q2頭部

若x在q2或q2中，則將x提到q1頭部

若q1或q2超過各自的長度限制時，剔除尾端的數據

若q1超過限制但q2還有空位時，則將q1尾部數據放到q2頭部。

題解（非正解）

考場上直接用deque模擬了，兩個隊列各自維護一個vis數組，快速判斷哪些數據在隊列中

但第二條規則需要把deque里面的倒出來在壓回去

不過根據數據范圍來看，應該直接暴力就有80分。

正解？我也不知道

F

01串（又是01串）

把0、1、2、3、……所有數的二進制表示排成一排，求前x個數有多少個1

序列的大致形式就是0；1；1、0；1、1；1、0、0；1、0、1；……

x<=10^18

題解

倍增查詢恰好超過x時，一個數的二進制有多少位，記n為該值減一

設f[i]表示二進制位數小于等于i的所有數的累積，f[i]=f[i-1]*2+2^(i-1)，

可以先將f[n]添加入答案，減掉x用掉的位數。

接下來就確定了x所在的數的二進制位數。

用x的剩余位數除以n，對得到的二進制進行分治：（類似二分查找）

只需要在選擇右子樹的時候統計答案，并只需要添加左子樹的累和即可。

最后算完之后，我們已經確定了x最終位于的十進制數，如果x還有剩余，則可以從高位到低位以此枚舉最終的十進制數的二進制，加入答案即可。

G

甘蔗

給出n個甘蔗高度ai，m個限制bj。

當每個甘蔗與相鄰甘蔗高度差都在集合b中，則序列合法。

求最少砍多少個甘蔗才能讓序列合法。

題解（非正解）

考場上直接暴力dp了

f[i][j]表示第i棵甘蔗高度為j時，前i棵甘蔗的序列合法的最少代價。

當j==a[i]時，則f[i][j]=min(f[i-1][j±b[k]])（1<=k<=m，0<=j±b[k]<=a[i-1]）

當j!=a[i]時，在上式子后+1即可。

O(n^2*m)的復雜度，沒法過完所有數據，可能有優化之類的吧。

H

n個廠房，所有廠房都在x正方向，坐標為ci，原料單價為ai，庫存為bi，原料需求為m個單位，每走一個單位的代價為o。

求滿足原料需求的最少代價。

n<=100000，保證ci遞增

題解（個人猜測）

前面耽誤時間太多了，再加上手比較生了，寫到最后一題只剩20分鐘了，最后直接沒交。

模擬費用流貪心。

維護兩個集合S（空流邊）、T（已流邊），按照原料單價排序

依次加入工廠，加入到S集合中，按照費用排序。

若當前m個單位有剩余，則在S集合中選擇費用最低的工廠<cost,cap>，流過min(m,cap)，總代價ans+=cost*min(m,cap)

在T集合中添加工廠<-cost,min(m,cap)>，或者在已有的-cost元素上添加min(m,cap)的容量

若cap已空，則在S集合中刪除該工廠。

完成上述更新之后，還需要維護S、T的流量平衡。

若當前S集合首元素cost與T集合首元素cost之和為負數，則說明代價還可以減少（也就是更換工廠后會更優），則需要將min(cap_S_begin,cap_T_begin)的貨物從T換到S集合中，與此同時還需要更新S和T集合。

完成所有更新之后，取所有（總代價+ci）的最小值就是最終的代價。

后記

感覺考得好差，太多失誤了，而且最近趕畢設鴨梨山大，生活狀態也不好，希望一切能好起來吧。

這次CDF三道二進制，ABCDF都是數位相關問題，題目比重真的很奇怪。