menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[wqs二分+贪心+DP]BZOJ5400【y】题解
题目概述有 $n-1$ 座城市,$n$ 个乡村,每个城市有一条公路和一条铁路连进来(乡村没有连进来的路),每个乡村有参数 $a_i,b_i,c_i$ ,如果乡村走到 $1$ 号城市的路径上有 $...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[二分+随机+斯坦纳树+思维]LOJ2977(THUSCH 2017)【巧克力】题解
题目概述给出一个 $n\times m$ 的巧克力,每个位置有形状和美味值,求一个个数最小的连通块满足形状数 $\ge K$ ,且在个数最小的前提下,美味值的中位数也要最小。解题报告人类智慧题Q...
[wqs二分套wqs二分]Codeforces739E【Gosha is hunting】题解
题目概述有 $n$ 个物品,可以用两种方式获得(可以一起用,一种获得了即可),两种方式成功的概率分别为 $a_i,b_i$ ,第一种方式可以用 $A$ 次,第二种方式可以用 $B$ 次。问获得物...
apps Codeforces
local_offer 查看标签
comment 0 条评论
阅读全文
[二分]Codeforces1064E【Dwarves, Hats and Extrasensory Abilities】题解
题目概述交互题,有 $n$ 个点,你需要指定每个点的坐标 $(x,y)$ ,每次指定之后会告诉你这个点的颜色。你需要确定你的点的坐标使得你给出的点能被直线分成两半,输出这条直线。解题报告我是zz...
apps Codeforces
local_offer 查看标签
comment 0 条评论
阅读全文
【坑】[二分+贪心]Codeforces1059E【Split the Tree】题解
题目概述把一棵有权值的树分成若干条儿子到祖先的路径,每条路径节点个数不能超过 $L$ ,节点权值和不能超过 $S$ ,问最少分成多少路径。解题报告如果只有 $S$ 限制好像是斯波贪心题啊?想去掉...
apps Codeforces
local_offer 查看标签
comment 0 条评论
阅读全文
[二分]Codeforces1059D【Nature Reserve】题解
题目概述求一个半径最小的圆使得和 $x$ 轴相切,并且包含了所有给定的点。解题报告很明显可以二分 $r$ ,那么圆心就是 $(x,r)$ ,通过每个点就可以确定 $x$ 的范围,如果 $x$ 有...
apps Codeforces
local_offer 查看标签
comment 0 条评论
阅读全文
[wqs二分+决策单调性]POJ1160【Post Office】题解
题目概述有 $n$ 个村庄,现在要建 $m$ 个邮局,一种方案的代价是每个村庄到最近的邮局的距离之和。解题报告我再来水一遍这道题……之前已经用了wqs二分去掉了一维状态,这时候DP的状态数,转移...
apps POJ
local_offer 查看标签
comment 0 条评论
阅读全文
[二分+树状数组]Codeforces1058F【Putting Boxes Together】题解
题目概述有 $n$ 个物品,第 $i$ 个物品在 $a_i$ ,移动一格需要 $w_i$ 的代价。现在有两种操作:1.把 $w_x$ 变成 $y$ 。2.询问把 $[L,R]$ 的物品移动到 $...
apps Codeforces
local_offer 查看标签
comment 0 条评论
阅读全文
[二分+DP]BZOJ1181(CROATIAN2009)【IZBROI选举】题解
题目概述有 $n$ 个组 $V$ 张票,假设 $i$ 组有 $V_i$ 的票。总共有 $m$ 个钦点机会,令 $S_i$ 表示目前 $i$ 组被钦点了几次,每次会钦点 $V_i\over{S_i...
apps BZOJ
local_offer 查看标签
comment 0 条评论
阅读全文
[二分+随机]Codeforces1040D【Subway Pursuit】题解
题目概述交互题,现在要猜一个数 $x$ ,可以询问 $x$ 是不是 $l\le x\le r$ ,但是每次询问完成后 $x$ 会移动一个到距离 $\le K$ 的点。如果一次询问 $(l,l)$...
apps Codeforces
local_offer 查看标签
comment 0 条评论
阅读全文
keyboard_arrow_up