欧美1区2区3区激情无套,两个女人互添下身视频在线观看,久久av无码精品人妻系列,久久精品噜噜噜成人,末发育娇小性色xxxx

第一題 k路字符串 優(yōu)先級隊列第二題 裸的拓撲排序，注意判斷是否有環(huán)第三題 一開始直接寫的最長上升子序列（嚴格），WA，于是推斷山的高度必須是整數(shù)，于是對nums[i]-i求最長上升子序列（不嚴格）AC第四題 樣例過，提交之后過0%樣例，沒看出來哪里錯了，貼一下代碼 #include using namespace std;int main() {    //數(shù)據(jù)范圍來說，至少是需要n方或者更好的算法    //注意讀題，首先不是嚴格大于，其次需要注意交換需要前提條件，即a[i] > x，這意味著交換過程中,x的數(shù)值是原來越大的，和x交換的值的門檻也是越來越大,隱含的條件就是如果小于x的數(shù)字沒有有序，那么久沒辦法完成操作了    //手玩一下：    //81 324 218 413 324 x = 18 如果與i>=1的位置交換，剩下的18沒人可以換走，直接不可行    //18 324 218 413 324 x = 81 同理，如果與i >= 2的位置交換，剩下的81沒有可以換走，直接不可行    //18 81 218 413 324 x = 324 我們選擇將413與324交換    //18 81 218 324 324     //再來領(lǐng)悟一下樣例    //0 2 3 5 4 x = 1 當前發(fā)現(xiàn)后面有一個4在搗亂，我們要想辦法把它調(diào)整下來，但是要調(diào)整，就說明當前x = 1需要換上去到某一個位置，也就只能是和2換，這一步是固定的    //0 1 3 5 4 x = 2 同樣的，搗亂的4還沒有解決，所以繼續(xù)要調(diào)整，當前x = 2只能換在begin，故而    //0 1 2 5 4 x = 3 begin變成了5的下標    //0 1 2 3 4 x = 5 此時發(fā)現(xiàn)已經(jīng)解決//再來領(lǐng)悟一下輸出-1的樣例    //11 9 x = 10 當前begin = 0 end = 1,但是注意到nums[end] < x，最終不可以被移動，所以已經(jīng)寄了    //以上過程說明：對于小于x的內(nèi)容，如果是已經(jīng)有序地位于開頭，那么就已經(jīng)不可行了    //對于大于x的無序的內(nèi)容，如果存在多個，比如10 20 30 40 6 4 x= 3，其中6和4都是亂序的，但似乎此時并不需要決定和其中的誰交換，只能從begin開始交換    //3 20 30 40 6 4 x = 10    //3 10 30 40 6 4 x = 20    //3 10 20 40 6 4 x = 30    //3 10 20 30 6 4 x = 40 爆炸    //至此大膽提出假設(shè)：先處理得到其中單增的區(qū)間    //0 2 3 5 4 x = 1    //其中比x小的部分已經(jīng)確保落在該有的位置上了    //0 [2 3 5] [4] x = 1 那么我們會把{[2, 3, 5] x = 1}變化為{[1 2 3] x = 5}，即相當于原來有序的空間中最大的沒了，最小的變成原有x?；ㄙM是有序空間大小    //然后x變成了原有空間中最大的那個，然后繼續(xù)這樣掃描//再來手玩一下：    //4 5 6 7 8 9 10 3 x = 1     //{[4 5 6 7 8 9 10] x = 1}->{[1 4 5 6 7 8 9] x = 10} 由于次大的9還是大于無序的3，所以沒辦法    //總結(jié)思路：線性掃描，找到從開始到現(xiàn)在最長的有序集（其中小于x的部分不統(tǒng)計長度）int t;    cin>>t;    while(t--)    {        int n, x;        cin>>n>>x;        vector nums(n);        for (int i = 0; i < n; ++i) cin>>nums[i];        int begin = 0, end = 0, costBegin = -1;        int ans = 0;        bool flag = true;        while(begin < n)        {            //end begin costBegin x ans            while(end + 1 < n && nums[end + 1] >= nums[end])//掃描到end，并更新end            {                if (costBegin == -1 && nums[end] > x) costBegin = end;                ++end;            }            // cout<<"begin = "<<<", end = "<<<", costBegin = "<<<'\n';            //從begin 到 end 遞增，且從costBegin開始大于x            if (end == n - 1) break;            if (begin != end)            {                if (nums[end + 1] < nums[end - 1]) {flag = false; break;}//沒辦法調(diào)整                ans += (end - costBegin + 1);                x = nums[end];                end = begin = end + 2;                costBegin = -1;            }            else            {                if (nums[end] > x && x <= nums[end + 1]) {++ans; x = nums[end]; end = begin = end + 2; costBegin = -1;}                else {flag = false; break;}            }        }        if (flag) cout<<<'\n';        else cout<<"-1\n";    }    return 0;}

專門在牛客上記錄讓自己破防的筆試題跪求路過大佬教教第三題做法## 編程題### 第一題輸入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，兩邊線性掃描?；?5分鐘過的### 第三題輸入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 正確性證明；考慮使用什么算法可以不超時。

第一次在?？蜕习l(fā)帖子，直接把寫的筆試復(fù)盤md文件貼過來了。p.s. 暑期實習投遞的太晚，只能說希望能有結(jié)果吧，沒有的話后面找找日常實習也行，現(xiàn)在切忌不要過度焦慮，把戰(zhàn)線拉長，每天好好沉淀總會有好結(jié)果的。# 題目回憶考試時長90分鐘，其中10道選擇題（總分30分），3道編程題（總分70分）## 選擇題前五道題目考的很雜，涉及到數(shù)據(jù)結(jié)構(gòu)（平衡二叉查找樹、棧），磁盤計算等等后面的題目主要是圍繞ML和LLM展開的，lr調(diào)整策略（余弦退火等）一題，ViT一題，微調(diào)好像考了三題## 編程題### 第一題q次查詢，每次查詢：n, m, w2, w3初始數(shù)字是n，每次操作可以（1）將當前乘以二，花費w2代價（2）將其乘以三，花費w3代價對于每次查詢，輸出從n開始，讓其最終大于等于m的最小代價數(shù)據(jù)范圍：- n, m <= 1e9- q <= 1e5### 第二題定義漂亮數(shù)：對于數(shù)字x，如果存在質(zhì)數(shù)p，使得x % p == 0且p * p >= x，則x是一個漂亮數(shù)輸入一個數(shù)字n，需要輸出[1, n]范圍內(nèi)漂亮數(shù)的個數(shù)**數(shù)據(jù)范圍**- n <= 5e5### 第三題輸入n,m接下來n-1行，每行u,v,d表示樹上u和v之間有一條長度為d的邊然后m行詢問，每行x,y，要求輸出樹上經(jīng)過x和y兩個點的簡單路徑的最大長度（其中簡單路徑是指路徑上所有點互不相同）**數(shù)據(jù)范圍**數(shù)據(jù)范圍n和q都是5e5# 考場表現(xiàn)回憶以及反思## 選擇題剛開考的時候明顯沒有進入狀態(tài)，沒有時間的緊迫感。有一道關(guān)于棧的題目描述相當奇怪，自我感覺讀題的時候不專注。用時大約15分鐘## 編程題### 第一題**解題心路過程**1. 一眼看上去是dp2. 但是數(shù)據(jù)范圍是1e9，dp存不下，那看樣子不是dp3. 考慮是不是一個數(shù)學(xué)問題可以直接求，比如是不是最佳策略只會是全乘二或者全乘三或者全乘三但是最后一次乘二4. 發(fā)現(xiàn)完全把握不住，于是還是考慮dp，存不下那我們就記憶化搜索具體時間不記得了，但是我記得這個題目和第二題加起來是花了30分鐘不到### 第二題**解題心路過程**1. 拿到題目首先轉(zhuǎn)化條件，一個數(shù)是漂亮數(shù)當且僅當他的最大質(zhì)因數(shù)的平方大于等于這個數(shù)(n >= 2時)，特別的，1不是漂亮數(shù)2. 這個時候有沖動直接暴力檢驗每一個數(shù)是不是漂亮數(shù)，但是這樣是O(n * sqrt(n))，太慢了，決定再想想，想不出來就先寫暴力3. 印象中這個時候直接跳過去看了一下第三題，題干沒仔細看完，又跳回來做第二題4. 突然靈光一閃，逆向思維一下，對于每一個質(zhì)數(shù)p，找到以其為最大質(zhì)因數(shù)的所有漂亮數(shù)即可。類似于n = 10時。p = 2 -> 2 * 1, 2 * 2; p = 3 -> 3 * 1, 3 * 2, 3 * 3; p = 5 -> 5 * 1, 5 * 2 ... 直到p大于n**代碼實現(xiàn)過程**實現(xiàn)的話就是質(zhì)數(shù)篩，然后對于每一個p，統(tǒng)計其對于答案的貢獻但是一開始寫的是 res += n / p，發(fā)現(xiàn)過不了樣例之后加了幾條調(diào)試信息，于是改成了res += min(n / p, p)，這個調(diào)試過程大概花費了5分鐘### 第三題**解題心路過程**1. 對于題干還不太理解，于是手玩了一下樣例2. 很快意識到這是一個lca + 樹上dp，思考了一下處理查詢所需要的信息：首先對于每一個點，維護它往下的路徑最大值（這個直接一個dfs就行，樹上dp），然后對于查詢的兩個點，以他們?yōu)槎它c的路徑就是一個lca + 樹上前綴和3. 注意這里并沒有去思考上面這個是不是有邏輯bug，直接就開始編碼了**代碼實現(xiàn)過程**整體編碼過程并不利索，我有點分不清是我自己本身編碼熟練度不夠，還是考試的時候太放松沒有緊迫感依稀記得 當時看到時間還有30多分鐘，感覺編碼的時候有點悠哉游哉的，等實現(xiàn)完dfs，得到parent[][0], maxDis[], preSum[], dep[]之后進一步得到parent[][]可以確信的是，關(guān)于lca的部分我寫的很謹慎，都是在腦子里把過程想清楚了再編碼，這一點倒是正確的最后實現(xiàn)完畢之后，只剩下幾分鐘，跑了測試樣例，WA于是加輸出調(diào)試，發(fā)現(xiàn)自己讀進來的x和y在找lca的時候直接修改了x,y。后續(xù)查詢的時候又是直接用的x,y。趕緊修復(fù)了這個，找lca的時候修改的是x,y的副本的值樣例過了，但是提交之后通過樣例0%，這個時候時間好像只有3分鐘了，突然意識到一個邏輯bug，當x是y的祖先關(guān)系的時候，maxDis[x] + maxDis[y] + (preSum[x] + preSum[y] - 2 * preSum[lca])中，兩個maxDis有可能出問題，即y在x往下延申最大路徑上但是我如何知道在不在？在困惑中考試結(jié)束了**賽后正解思考**記一個第二深的葉子再最深和第二深記一下具體是哪個葉子這樣可以判斷v是不是在u最深的葉子那條路上如果是就用第二深的# 一些反思TODO