對(duì)角線上的質(zhì)數(shù)

【遍歷】遍歷兩條對(duì)角線，用埃式篩判斷。

等值距離和

【前綴和】將相同元素下標(biāo)分組，對(duì)于每個(gè)組a，設(shè)a[i-1]到其他元素的距離之和為sm，那么a[i]到其他元素的距離之和為sm + (2*i - n) · (a[i] - a[i -1])。

最小化數(shù)對(duì)的最大差值

【貪心 + 二分】排序后，為了讓差值最小，盡量選相鄰的元素，二分?jǐn)?shù)對(duì)中的最大差值mx。

網(wǎng)格圖中最少訪問(wèn)的格子數(shù)

【優(yōu)先隊(duì)列】只向右和向下走，可以不用bfs，直接二重循環(huán)。在位置(i,j)時(shí)，考慮上一步是向下還是向右走，如果上一步是向下走，那上一個(gè)位置應(yīng)該是(i',j)，需要滿(mǎn)足i'<i，(i',i)要能走到(i,j)，到(i',j)的移動(dòng)次數(shù)要最小。可以用優(yōu)先隊(duì)列維護(hù)所有i'，堆頂為移動(dòng)次數(shù)最少的位置，在獲取堆頂時(shí)進(jìn)行判斷，如果堆頂?shù)膇'不滿(mǎn)足要求，就可用將它永久從優(yōu)先隊(duì)列中移除（因?yàn)橹蠊蚕硗涣衘的位置i只會(huì)更大，走不到）。因此可以對(duì)每一列都維護(hù)一個(gè)優(yōu)先隊(duì)列，第j個(gè)優(yōu)先隊(duì)列存儲(chǔ)所有位于第j列的位置，優(yōu)先隊(duì)列中存兩個(gè)值，第一個(gè)是到達(dá)(i',j)最少的移動(dòng)次數(shù)，第二個(gè)值為i'。對(duì)每一行也維護(hù)一個(gè)優(yōu)先隊(duì)列用于處理向右走的情況。