zhangxyhp

摘要： 考慮對(duì)于單次詢(xún)問(wèn)，顯然可以二分，每次將美味度大于等于 \(mid\) 的果汁放在一起按價(jià)格排序，貪心地計(jì)算能否在 \(g_j\) 的限制內(nèi)買(mǎi)夠 \(L_j\) 的果汁。 多次詢(xún)問(wèn)可二分的問(wèn)題，這提醒我們?nèi)プ稣w二分。但是有一個(gè)問(wèn)題，我們無(wú)法在整體二分搜索樹(shù)上的每個(gè)節(jié)點(diǎn)都對(duì)大于等于 \(mid\) 的 閱讀全文

摘要： 一、簡(jiǎn)述 叫簡(jiǎn)述是因?yàn)椴恢涝摻猩丁?整體二分是一種基于值域的分治算法，一般面對(duì)多次可二分的詢(xún)問(wèn)時(shí)就可以整體二分。有時(shí)帶修改的問(wèn)題也可以整體二分，但顯然它難以強(qiáng)制在線。 整體二分的精髓在于對(duì)于一堆問(wèn)題只 check 一次，從而節(jié)省相當(dāng)多的時(shí)間。 二、例題 1.Luogu P3834 【模板】可持久化 閱讀全文

摘要： A. 皮胚 (match) 可行性 dp。設(shè) \(f_{i,j}\) 表示 \(s\) 的第 \(i\) 位能否匹配到 \(t\) 的第 \(j\) 位。分討轉(zhuǎn)移即可。 Code #include<bits/stdc++.h> #define ll long long #define il inli 閱讀全文

摘要： 虛樹(shù)用來(lái)處理一些樹(shù)上的多次詢(xún)問(wèn)，對(duì)于每個(gè)詢(xún)問(wèn)，只考慮那些和詢(xún)問(wèn)有關(guān)的點(diǎn)，將無(wú)關(guān)的點(diǎn)都縮成邊或直接剪掉。對(duì)于 \(Q\) 個(gè)詢(xún)問(wèn)，如果每次詢(xún)問(wèn)涉及的點(diǎn)數(shù)為 \(k_i\)，那么總的時(shí)間復(fù)雜度就是 \((O\sum k_i)\) 的。 一、建樹(shù) 在建樹(shù)過(guò)程中，我們維護(hù)一個(gè)棧 \(stk\)，表示當(dāng)前在樹(shù) 閱讀全文

摘要： 教練并沒(méi)有更改比賽的名字，導(dǎo)致有兩場(chǎng)比賽都叫“2025CSP-S模擬賽7” 閱讀全文

摘要： Made by Zxy and Zsk 閱讀全文

摘要： wylwyl 閱讀全文

摘要： A. Lesson5！ 首先預(yù)處理出以每個(gè)點(diǎn)為起點(diǎn)和終點(diǎn)的最長(zhǎng)路 \(g_u\) 和 \(f_u\)。然后按照拓?fù)湫虮闅v每個(gè)點(diǎn)，刪掉與這個(gè)點(diǎn)相關(guān)的邊后更新答案，再加上相關(guān)的邊（要將所有從這個(gè)點(diǎn)連出的邊都加上，方便后面刪邊）。需要可刪堆。注意 \(n=1\) 的情況，維護(hù)的邊集中將沒(méi)有元素，所以要特判 閱讀全文

摘要： 一、簡(jiǎn)介 折半搜索，即對(duì)于那些數(shù)據(jù)范圍較小卻又不能直接暴搜的題目，采取分兩半暴搜后再想辦法合并兩部分的答案的辦法。一般的方式是二分或者狀壓、map。 二、例題 1.世界冰球錦標(biāo)賽 對(duì)前一半和后一半分別進(jìn)行暴搜，將前半部分的答案存起來(lái)并排序，對(duì)于每個(gè)后面的答案在這個(gè)序列中二分即可。時(shí)間復(fù)雜度 \(O( 閱讀全文

摘要： 一、定義 cdq 分治是一種離線分治算法，一般有三種用途： 處理點(diǎn)對(duì)之間的問(wèn)題 優(yōu)化 1D/1D 動(dòng)態(tài)規(guī)劃 將動(dòng)態(tài)問(wèn)題轉(zhuǎn)為靜態(tài)問(wèn)題 對(duì)于分治區(qū)間 \([l,r]\)，確定一個(gè)中點(diǎn) \(mid\)，對(duì)于左右區(qū)間分別遞歸分治，然后再處理左右區(qū)間之間的貢獻(xiàn)。啊顯然歸并排序就是 cdq 分治。 二、例題 1 閱讀全文