menu ZigZagK的博客

正在努力加载中QAQ

[wqs二分套wqs二分]Codeforces739E【Gosha is hunting】题解
题目概述有 $n$ 个物品,可以用两种方式获得(可以一起用,一种获得了即可),两种方式成功的概率分别为 $a_i,b_i$ ,第一种方式可以用 $A$ 次,第二种方式可以用 $B$ 次。问获得物...
apps Codeforces
local_offer 查看标签
comment 0 条评论
remove_red_eye 21 次访问
阅读全文
[二分]Codeforces1064E【Dwarves, Hats and Extrasensory Abilities】题解
题目概述交互题,有 $n$ 个点,你需要指定每个点的坐标 $(x,y)$ ,每次指定之后会告诉你这个点的颜色。你需要确定你的点的坐标使得你给出的点能被直线分成两半,输出这条直线。解题报告我是zz...
apps Codeforces
local_offer 查看标签
comment 0 条评论
remove_red_eye 15 次访问
阅读全文
【坑】[二分+贪心]Codeforces1059E【Split the Tree】题解
题目概述把一棵有权值的树分成若干条儿子到祖先的路径,每条路径节点个数不能超过 $L$ ,节点权值和不能超过 $S$ ,问最少分成多少路径。解题报告如果只有 $S$ 限制好像是斯波贪心题啊?想去掉...
apps Codeforces
local_offer 查看标签
comment 0 条评论
remove_red_eye 51 次访问
阅读全文
[二分]Codeforces1059D【Nature Reserve】题解
题目概述求一个半径最小的圆使得和 $x$ 轴相切,并且包含了所有给定的点。解题报告很明显可以二分 $r$ ,那么圆心就是 $(x,r)$ ,通过每个点就可以确定 $x$ 的范围,如果 $x$ 有...
apps Codeforces
local_offer 查看标签
comment 0 条评论
remove_red_eye 35 次访问
阅读全文
[wqs二分+决策单调性]POJ1160【Post Office】题解
题目概述有 $n$ 个村庄,现在要建 $m$ 个邮局,一种方案的代价是每个村庄到最近的邮局的距离之和。解题报告我再来水一遍这道题……之前已经用了wqs二分去掉了一维状态,这时候DP的状态数,转移...
apps POJ
local_offer 查看标签
comment 0 条评论
remove_red_eye 38 次访问
阅读全文
[二分+树状数组]Codeforces1058F【Putting Boxes Together】题解
题目概述有 $n$ 个物品,第 $i$ 个物品在 $a_i$ ,移动一格需要 $w_i$ 的代价。现在有两种操作:1.把 $w_x$ 变成 $y$ 。2.询问把 $[L,R]$ 的物品移动到 $...
apps Codeforces
local_offer 查看标签
comment 0 条评论
remove_red_eye 49 次访问
阅读全文
[二分+DP]BZOJ1181(CROATIAN2009)【IZBROI选举】题解
题目概述有 $n$ 个组 $V$ 张票,假设 $i$ 组有 $V_i$ 的票。总共有 $m$ 个钦点机会,令 $S_i$ 表示目前 $i$ 组被钦点了几次,每次会钦点 $V_i\over{S_i...
apps BZOJ
local_offer 查看标签
comment 0 条评论
remove_red_eye 69 次访问
阅读全文
[二分+随机]Codeforces1040D【Subway Pursuit】题解
题目概述交互题,现在要猜一个数 $x$ ,可以询问 $x$ 是不是 $l\le x\le r$ ,但是每次询问完成后 $x$ 会移动一个到距离 $\le K$ 的点。如果一次询问 $(l,l)$...
apps Codeforces
local_offer 查看标签
comment 0 条评论
remove_red_eye 156 次访问
阅读全文
[几何+二分]Codeforces1016E【Rest In The Shades】题解
题目概述有一个光源按照 $(a\to b,s_y)$ 移动,还有 $n$ 个板 $(l_i,r_i)$ 。有 $q$ 个询问,问一个点 $(x,y)$ 被板挡住的总长度。解题报告斯波题,但是我不...
apps Codeforces
local_offer 查看标签
comment 0 条评论
remove_red_eye 50 次访问
阅读全文
[二分]Codeforces1020D【The hat】题解
题目概述交互题,$n(n\le 10^5)$ 个人接成环,手上拿着一个数 $a_i$ 。$i$ 和 $i\ mod\ n+1$ 相邻,保证相邻人之间的数之差绝对值不超过 $1$ ,而 $i$ 和...
apps Codeforces
local_offer 查看标签
comment 0 条评论
remove_red_eye 59 次访问
阅读全文
keyboard_arrow_up