【連結】h在這裡寫連結
【題意】
給你一個長度最多為2萬的序列(由1..88這些數字組成)。
讓你在裡面找一個子串。
這個子串或它的轉置子串(就是每個數字都加上或減去相同的數字)在這個序列中
出現了至少兩次,且沒有重疊部分。讓你求這個子串最長能夠多長。
這個子串的長度最少為5.
沒有的話就輸出0;
【題解】
字尾數組題。
把相鄰兩個數的差存起來,做字尾數組。
即s[i] = a[i+1]-a[i];
(因為互為轉置的兩個子串,它們相鄰數字的差是一樣的。)
然後問題就能轉化成不重疊子串,沒有覆寫,且長度最長了。
這個時候,如果要求原串長度為i,那麼在這個轉化後的,長度就為i-1了。
且這兩個區間的中間需要空最少一個以上才夠.
二分子串的長度
l = 4,r = n-1;
找連續的大于等于mid的height;
然後記錄Sa[i]的最小值L和最大值R(出現過的);
然後看看L+mid是不是<R的,是的話變大
否則變小.
因為長度越大越不可能。
沒有一個符合,就輸出0就行了.
注意答案要+1
【錯的次數】
【反思】
在這了寫反思
【代碼】