K 件物品的最大和

【模擬】 按照1,0,-1的順序選前k個(gè)。

【分類討論】如果k <= numOnes + numZeros，ans=前k里面1的數(shù)量，剩下情況，只能選numsOnes - (k - numOnes - numZeros)即ans=前k里面1的數(shù)量減-1的數(shù)量。

質(zhì)數(shù)減法運(yùn)算

前置知識(shí)：埃式篩又稱素?cái)?shù)篩，從2開(kāi)始將每個(gè)素?cái)?shù)的倍數(shù)都標(biāo)記成合數(shù)；線性篩是對(duì)埃式篩的優(yōu)化，在篩選每個(gè)合數(shù)時(shí)，用它的最小質(zhì)因子去篩。

【埃式篩 + 二分】因?yàn)橐獓?yán)格遞增，所以前面的數(shù)要盡可能小，首先nums[0]減去小于nums[0]的最大質(zhì)數(shù)，然后對(duì)于每個(gè)num, 因?yàn)閲?yán)格遞增，所以num - prime > pre，移項(xiàng)prime < num - pre。代碼中，primes里初始放一個(gè)0作為哨兵，避免二分越界。

數(shù)據(jù)范圍較大時(shí)可以換成線性篩。

使數(shù)組元素全部相等的最少操作次數(shù)

【排序 + 前綴和 + 二分】由于每次只能加減1，所以就是每個(gè)元素到q的距離，要求的距離和相當(dāng)于矩形面積減掉前綴和。

收集樹(shù)中金幣

【拓?fù)渑判颉渴紫扰芤淮瓮負(fù)渑判騽h掉所有沒(méi)金幣的節(jié)點(diǎn)（”瘦身“）。再跑兩次拓?fù)渑判颍―FS），去掉兩輪葉子節(jié)點(diǎn)（含金幣的葉子節(jié)點(diǎn)距離≤2即可，無(wú)需訪問(wèn)，刪掉），得到了一顆”核心樹(shù)“，其中每個(gè)節(jié)點(diǎn)都必須要訪問(wèn)。從樹(shù)的任意節(jié)點(diǎn)出發(fā)，訪問(wèn)所有節(jié)點(diǎn)然后返回，每條邊恰好訪問(wèn)兩次。（以樹(shù)上任意一點(diǎn)為根的歐拉回路長(zhǎng)度都是邊數(shù)×2，先刪掉葉節(jié)點(diǎn)為0的邊，使得每個(gè)樹(shù)葉都為1，再刪兩層邊，答案就是剩下的邊數(shù)×2。）

代碼中，用一個(gè)數(shù)組time記錄每個(gè)點(diǎn)的入隊(duì)時(shí)間（刪掉葉子的時(shí)間），那么只要走到time[x]=2的節(jié)點(diǎn)x，就能收集到在葉子上的金幣。遍歷所有邊x-y，如果滿足time[x]≥2且time[y]≥2，那么這條邊需要恰好經(jīng)過(guò)2次（因?yàn)樾枰氐匠霭l(fā)點(diǎn)），答案加2；如果不滿足，則無(wú)需經(jīng)過(guò)。