1.4924. 矩陣 - AcWing題庫

一開始打表找規律以為是右上角向左下角遞增,但當n很大的時候就不對了,因此我們得去觀察

i * i + 100000 * (i - j) + j * j + i * j
這個式子,我們關心的是這個式子的單調性因此我們可以分別將i和j看作常數來對式子進行求導,可以得到

f'(i) = 2 * i + 100000 + j

f'(j) = 2 * j + i - 100000

2.4926. 中位數 - AcWing題庫

注意,類似該題中的check函數原為每次二分查找,類似性質的情況下雙指針復雜度更優

3.4932. DZY愛劃分 - AcWing題庫

將n拆分成k個不同的正整數,使得這k個數乘積最大,首先可以知道要想n個數相乘盡可能大那就使得,這n個數彼此之間的差盡可能的小,因此我們嘗試構造一個公差為1的等差數列,但是有時候并不能正好湊出x,但缺少的值一定小于k(若大于等于k可以在這k個數身上每個加1),那么為了保證每個數之間差距盡可能小且不會出現重復我們從最大的數開始每個+1直到少的值加完

4.F-雙生雙宿之探_2025牛客寒假算法基礎集訓營1

一種做題技巧,像是上次一場div2的d題與中位數相關的題目都可以使用,那便是若一個數組中的數字只有兩種性質,并且需要我們進行計數,那么不妨將兩個種類的數字映射成1,-1,如此一來求出前綴和之后就可以快速知道一段區間中兩種性質的數字的個數情況

5.4935. 范圍發現 - AcWing題庫

關鍵點在于對前綴和進行排序,如此一來此時的s[i] - s[j - 1]代表的是|a[j] + ....... + a[i]|

6.5086. 第一個 - AcWing題庫

給定一個范圍,求出一個數組中所有滿足和在這個區間內的子數組,可以通過雙指針來實現,實際上也可以理解成三指針,第一個指針是我們枚舉的子數組的起點i,第二個指針l滿足pre[l] - pre[i - 1] >= L,第三個指針r滿足pre[r] - pre[i - 1] <= R,如此一來對于起點i而言所有位于[l , r]區間內的點都可以作為終點滿足與i構成一個合法子數組