menu ZigZagK的博客

正在努力加载中QAQ

[DP]BZOJ1566(NOI2009)【管道取珠】题解
题目概述有两个管道,第一个有 \(n\) 个黑白珠子,第二个有 \(m\) 个黑白珠子,每次可以从一个管道取出最靠管道口的珠子。假设有 \(k\) 中取珠子的方法,第 \(i\) 种方案的方案数...
apps BZOJ
local_offer 查看标签
comment 0 条评论
remove_red_eye 43 次访问
阅读全文
[wqs二分+DP]POJ1160【Post Office】题解
题目概述有 \(n\) 个村庄,现在要建 \(m\) 个邮局,一种方案的代价是每个村庄到最近的邮局的距离之和。
apps POJ
local_offer 查看标签
comment 0 条评论
remove_red_eye 138 次访问
阅读全文
[最大密度子图]POJ3155【Hard Life】题解
题目概述有 \(n\) 个员工 \(m\) 条矛盾,现在要炒若干个员工的鱿鱼,一组方案的权值是矛盾数与员工数的比值。求最大比值的方案。
apps POJ
local_offer 查看标签
comment 0 条评论
remove_red_eye 70 次访问
阅读全文
[最小割+Tarjan]BZOJ1797(Ahoi2009)【Mincut 最小割】题解
题目概述给出一张 \(n\) 个点 \(m\) 条有向边的图,现在要求 \(S,T\) 的最小割,问每一条边: 有没有可能出现在最小割中。 是否一定出现在最小割中。 解题报告先跑出随意一种...
apps BZOJ
local_offer 查看标签
comment 0 条评论
remove_red_eye 57 次访问
阅读全文
[最大权闭合图]BZOJ4873(Shoi2017)【寿司餐厅】题解
题目概述题目太复杂了QAQ,自己去看吧……吃我传送门。解题报告很显然最优解一定是选若干个不相交的区间。我们观察题目里的条件,发现带有很多“强制”操作,比如吃了 \([L,R]\) ,里面的所有子...
apps BZOJ
local_offer 查看标签
comment 0 条评论
remove_red_eye 47 次访问
阅读全文
[最大权闭合图]BZOJ1497(NOI2006)【最大获利】题解
题目概述有 \(n\) 个点 \(m\) 条边,每个点需要花费 \(p_i\) 购买,每条边可以得到 \(c_i\) 的价值。现在要购买一些点,如果一条边两端的点都被购买了,就可以得到这条边的价...
apps BZOJ
local_offer 查看标签
comment 0 条评论
remove_red_eye 77 次访问
阅读全文
最小割模型
对《最小割模型在信息学竞赛中的应用》的一些口胡QAQ。分数规划(01)分数规划为下面一些问题作准备……基本上都是二分答案的套路。分数规划+最小割:ZOJ2676最大权闭合图给出一张带点权的有向图...
apps 图论
local_offer 查看标签
comment 1 条评论
remove_red_eye 105 次访问
阅读全文
[贪心+线性基]BZOJ2460(BeiJing2011)【元素】题解
题目概述有 \(n\) 种无数个的物品,每种物品带有ZZK的蒟蒻值 \(weak_i\) 和JZ的神犇值 \(strong_i\) ,你现在可以选任意个物品,将得到所有物品神犇值之和的JZ神犇值...
apps BZOJ
local_offer 查看标签
comment 0 条评论
remove_red_eye 46 次访问
阅读全文
[分数规划+最小割任意方案]ZOJ2676【Network Wars】题解
题目概述有一个 \(n\) 个点 \(m\) 条双向边的图,每条边的边权是 \(w_i\) 。JZ为了防止神犇之力外泄,想切断 \(1\) 到 \(n\) 的连接(切断一条边的代价是这条边的边权...
apps ZOJ
local_offer 查看标签
comment 0 条评论
remove_red_eye 53 次访问
阅读全文
[Tarjan+树形背包]BZOJ2427(HAOI2010)【软件安装】题解
题目概述有 \(n\) 个软件和 \(m\) 的容量,每个软件需要 \(w_i\) 的容量,有 \(v_i\) 的价值,同时依赖 \(d_i\) 软件( \(d_i=0\) 则没有依赖)。问最大...
apps BZOJ
local_offer 查看标签
comment 0 条评论
remove_red_eye 100 次访问
阅读全文
keyboard_arrow_up