摘要： 前話： 為什么現(xiàn)在才發(fā)？ 答：因為沒打比賽。 為什么要發(fā)？ 答：因為我是小鳥廚子 知更鳥小姐可愛捏~ 兩個人的演唱會： 一道簡單的貪心，它有策略嗎？（霧） 如果只是一個數(shù)列，我們怎么辦。 讓一個數(shù)為起點，一直把后面的合法的數(shù)加到這個段內(nèi)，一直到不能加，重復(fù)操作即可，這是一個很直接的思路，那么我們證明 閱讀全文

摘要： 掃描線學(xué)習(xí)筆記 今天初學(xué)了掃描線，發(fā)一篇學(xué)習(xí)筆記鞏固一下 掃描線能干什么 計算矩形面積的并 計算矩形周長的并 其他 引入 如下圖所示，給定平面直角坐標(biāo)系內(nèi)N個矩形，求矩形的面積并，定義面積的并為矩形并集覆蓋坐標(biāo)系的面積和 正文部分 面積并： 通過觀察，我們發(fā)現(xiàn)，對于矩形面積的并，可以通過以每個矩形左 閱讀全文

摘要： 前置芝士： 最大流 & 二分圖匹配 原題鏈接：P10940 舞動的夜晚 本題題意：給出一張二分圖，求該圖最大匹配的必不經(jīng)邊 定理1：對于原二分圖中任意邊\((x,y)\)，若\((x,y)\)為匹配邊，并且在殘量網(wǎng)絡(luò)中分屬不同強連通分量,則\((x,y)\)為必經(jīng)邊。 定理2：對于原二分圖中任意邊\ 閱讀全文

摘要： 掃描線學(xué)習(xí)筆記 今天初學(xué)了掃描線，發(fā)一篇學(xué)習(xí)筆記鞏固一下 掃描線能干什么 計算矩形面積的并 計算矩形周長的并 其他 引入 如下圖所示，給定平面直角坐標(biāo)系內(nèi)N個矩形，求矩形的面積并，定義面積的并為矩形并集覆蓋坐標(biāo)系的面積和 正文部分 面積并： 通過觀察，我們發(fā)現(xiàn)，對于矩形面積的并，可以通過以每個矩形左 閱讀全文

摘要： 洛谷題目鏈接：[Violet] 蒲公英 一道分塊好題，調(diào)了整整一上午 一句話題意：在線求區(qū)間眾數(shù) 考慮到眾數(shù)沒有可加性，所以一般數(shù)據(jù)結(jié)構(gòu)是不好維護的，這個時候就要用分塊了，分塊可以維護一些數(shù)據(jù)結(jié)構(gòu)無法維護的復(fù)雜神秘數(shù)據(jù)，對于區(qū)間眾數(shù)就可以用分塊維護 考慮暴力做法，對于每一個詢問，暴力掃描，時間復(fù)雜度 閱讀全文

摘要： 洛谷原題鏈接：P10975 Mondriaan's Dream 看數(shù)據(jù)范圍容易發(fā)現(xiàn)是狀壓DP 考慮如何規(guī)定狀態(tài) 設(shè)f(i,s)為第i行，填充格式為s的方案數(shù)，其中s為二進制數(shù)，1表示在這個位置填充一個長方形并使它延伸到i+1（即以i為起點的兩行一列的長方形），0表示由i-1延伸而來或填充一個長方形并 閱讀全文

摘要： 竟然做了一晚上才AC 發(fā)題解警示自己犯糖 一道思維題，推公式即可 首先手玩一下樣例發(fā)現(xiàn) m=1，m=2均無法成功，直接輸出 如果大于2一定存在范圍[L，R]可以勝利 對于最小值，不難想到對于完全圖可以使n最小，且完全圖的合法炸彈數(shù)一定小于一個m條邊的m元環(huán)（在環(huán)內(nèi)連接邊一定不會更劣嘛） 所以根據(jù)公式 閱讀全文

摘要： 洛谷原題鏈接：P3258 [JLOI2014] 松鼠的新家 化簡題意:給定一棵樹，進行Q次對（x,y）整條鏈節(jié)點權(quán)值+1，輸出每個點權(quán)值 LCA+樹上差分板子 注意：對于2~n個修改的點，每個點計算了兩次，所以減一 代碼： #include<bits/stdc++.h> #define int lo 閱讀全文

摘要： 洛谷原題鏈接：P2912 [USACO08OCT] Pasture Walking G 題意簡化：給定一棵樹，求Q個詢問鏈（x,y）的長度 容易想到LCA，然后考慮求長度，可以通過倍增法求（x，LCA（x,y））,(y,LCA(x,y)),然后求和即可 代碼: #include<bits/stdc+ 閱讀全文

摘要： 原題鏈接：貨車運輸 kruskal重構(gòu)樹+LCA做法，樹剖不想寫 很容易發(fā)現(xiàn)原圖跑最短路可以解，但是復(fù)雜度難以承受，所以考慮如何簡化該圖。 發(fā)現(xiàn)原圖邊權(quán)維護的應(yīng)該是（u，v）的最小值，并且最優(yōu)選擇是這個最小值最大，所以如果有多條（u，v),只保留最大的沒有影響，如果我們維護一棵最大生成樹就一定包含（ 閱讀全文