專門在?？蜕嫌涗涀屪约浩品赖墓P試題跪求路過大佬教教第三題做法## 編程題### 第一題輸入n，然后輸入一個長度為n的字符串s，接下來對于s的每一個前綴，將其依次反轉(zhuǎn)然后拼接在一起，得到新的字符串s'輸入m，接下來m次查詢，要求輸出s'的第m個字符（保證1 <= m <= (n + 1) * n / 2）**數(shù)據(jù)范圍** n,m在1e5 對于所在的塊寫了一個二分，花了10min過的debug過程：第一次寫的時候注意到了(n + 1)*n溢出風險，所以用的long long，但是x一開始用int存的將x從int換為long long之后，20%->100%### 第二題輸入T，接下來T組數(shù)據(jù)每組數(shù)據(jù)：輸入n,然后輸入n個數(shù)，組成數(shù)組a。定義：對于一個長度至少為3的子序列，稱其為V圖，當x_1>x2>x3>...>xj且xj<xj+1<xj+2<...<xk 輸出當前數(shù)組所有V圖中，極差最大的那個的極差。**數(shù)據(jù)范圍** T在1e3, n在1e5考慮每一個小標為j時對于答案的貢獻，統(tǒng)計其左邊和右邊最大的數(shù)字，如果都大于a[j]，則統(tǒng)計當前對答案的貢獻左邊右邊最大的數(shù)字用dp，兩邊線性掃描。花了15分鐘過的### 第三題輸入n以及正整數(shù)集合S = {s1, s2, ..., sn} 輸入m，之后m次詢問，每次一個x。判斷S中有無這樣的一個子集T，s.t.對于任意在[1, x]范圍的正整數(shù)y，都存在T的一個子集T'，使得T'的元素之和等于y。如果存在，則輸出所有滿足上述條件的T中，元素個數(shù)最少的那一個；如果不存在，則輸出-1。**數(shù)據(jù)范圍** n,m小于1e5，x小于1e9。**樣例** S = {1, 2, 4, 8, 16} 查詢 7 8 32的期望結(jié)果分別為3 4 -1**當時做出的解題嘗試以及思路回憶**：拿到題目覺得莫名像是最小線性篩，但是玩了一下樣例之后發(fā)現(xiàn)不是這樣的。沒思路，先考慮簡單一點的問題，“對于給定的子集T，驗證其是否能覆蓋1到x的所有數(shù)字”想法：對于T排序之后直接dp即可，不過x的范圍是1e9，dp存不下，所以自頂向下記憶化搜索。好，思維沒閑著，不過對于上面這個，子集T有2^2種可能，無法枚舉，那如何做呢？基于上面做法，我們試試看貪心。對于查詢x，每次選擇S中≤x且最接近(x+1)/2的數(shù)num，將問題遞歸轉(zhuǎn)化為解決1...max(num-1, x-num)。實現(xiàn)的話使用multiset和lower_bound進行二分查找，如果兩邊差值一樣，優(yōu)先使用較大的數(shù)字，否則選更靠近的那個#?？虯I配圖神器#想了半天想到這個之后開始實現(xiàn)，實現(xiàn)完之后發(fā)現(xiàn)過不了樣例，即 反例：S={1,2,4,8,32}, x=8時：我的貪心則會x=8第一次貪心選4，此時x=4；第二次貪2，此時x=2；第三次貪1，此時x=1。x大于0就會繼續(xù)進while循環(huán)體，此時multiset找lowerbound的時候，較大的那一端選到的數(shù)字是8，大于x不予考慮，較小那一段沒得數(shù)字了。即較大較小兩端都沒有可以選的數(shù)字了，break出while并輸出-1無法繼續(xù)選擇導(dǎo)致失敗，但正確解應(yīng)為8,4,2,1**賽后反思**首先，其實可以寫一個枚舉然后驗證的，這樣如果有n < 30的數(shù)據(jù)點，至少可以拿一些部分分然后反思了我的貪心，應(yīng)該自底向上貪心，初始cur=0，然后把S的所有元素全部插入到某一個數(shù)據(jù)結(jié)構(gòu)中，由于選一個≤ cur+1的num可以讓cur = cur + num，所以我們就貪心選數(shù)據(jù)結(jié)構(gòu)中所有≤ cur+1元素中最大的那一個，更新cur,cnt,并從數(shù)據(jù)結(jié)構(gòu)中刪除被選擇的數(shù)。如果cur大于等于查詢x，返回cnr。如果數(shù)據(jù)結(jié)構(gòu)中已經(jīng)沒有≤ cur+1的數(shù)可以選就break輸出-1數(shù)據(jù)結(jié)構(gòu)選擇multiset的時候，時間復(fù)雜度為mnlogn，還是超時，不過正確性來說，應(yīng)該是對的，可以大概想象到貪心正確性證明長啥樣。TODO 正確性證明；考慮使用什么算法可以不超時。

構(gòu)造題有點難度，花了好多時間，導(dǎo)致最后一題沒來得及寫，還是要好好安排時間，太菜了

牛友們我有些慌了，整亞信安全的筆試忘了開手機的攝像頭，有沒有影響啊

我們的薪資待遇——薪資高??，福利好??（我們從不浮夸），全額五險一金[牛逼] 我們需要的人才——你?。?！具有扎實的技術(shù)能力，渴望自我提升的你?。?！測評記得按時做啊，投起來！內(nèi)推鏈接https://app.mokahr.com/m/campus_apply/shein/2932?recommendCode=DSQm9Bgz&hash=%23%2Fjobs#/jobs內(nèi)推碼 DSQm9Bgz面經(jīng)一面八股居多對spark有啥了解Docker屏蔽了哪些操作系統(tǒng)的資源并發(fā)與并行的區(qū)別集群與分布式的區(qū)別與理解Redis主從復(fù)制, 哨兵，集群的區(qū)別怎么部署 都自己部署過嗎？集群比其他好的點在哪s...