夜间模式
字体
阴影
滤镜
主题色

标签:dfs

3 篇文章

bzoj 1052: [HAOI2007]覆盖问题 & Luogu P2218 [HAOI2007]覆盖问题 题解
题意 在平面直角坐标系中有$n$个点,现在给你$3$个$L\times L$的正方形,问要用这$3$个正方形盖住所有点的最小的$L$。 思路 终于开始刷$bzoj$了$QwQ$... 非常明显,这道题肯定要二分,那么怎么写$check$呢? 可以考虑如果用一个非常大的正方形盖住了所有点,那么必定会有点在这个正方形的四条边上。所以有正方形必须在边上。…
CF293B Distinct Paths 题解
题意 给定一个$n\times m$的矩形色板,有kk种不同的颜料,有些格子已经填上了某种颜色,现在需要将其他格子也填上颜色,使得从左上角到右下角的任意路径经过的格子都不会出现两种及以上相同的颜色。路径只能沿着相邻的格子,且只能向下或者向右。 计算所有可能的方案,结果对 $1000000007 (10^9 + 7)$ 输入及输出格式 输入格式 第一…
洛谷P1331 海战 题解
题目传送门 思路 肯定食用dfs啦。。。 但关键是两条船接触了怎么判断呢?? 上图: 可以发现一下规律 当两条船接触时,必有一条直线连续穿过两条船 当一条船不与另一条船接触时,没有一条直线连续穿过两条船 所以只需要在每一次碰见一条船的一部分(一条船内每个点都要拓展一遍)时,将其沿右上、左下分别拓展一遍,边拓展边用sum前缀和check一遍就好啦。。…