二分答案 – Tgotp-Blog

Life Forms

思路不难想,求出sa以后二分随便搞搞,和上一题比较像。细节卡死人。。。

注意是大于一半。。。一开始以为是至少一半疯狂wa。。。

然后现在还把用来对拍的程序卡掉了。。。

c++代码如下:

数据生成代码:
[cra[......]

Read more

PHRASES - Relevant Phrases of Annihilation

有点难度的sa,把所有的字符串串在一起,然后分段保证段上有长为x的两个子串

首先求出sa,然后再求出height 数组,然后二分答案,对于每段就枚举height差值不超过二分值得段。

然后记录在每一段出现最早与最晚得值(判断有无两个串),然后判断。

搞定。

c++代码如下:[......]

Read more

P3939 数颜色

因为交换只会交换相邻两数,所以交换很好写。

用vector存一下每个颜色出现的位置,然后对于查找的颜色在vector上二分。

c++代码如下:

 

3110: [Zjoi2013]K大数查询

整体二分,用线段树维护区间大于mid 的值

c++代码如下:

 

P2538 [SCOI2008]城堡

爆搜 + 贪心 + 二分 + floyd;

记住:大胆假设,不用证明

先存图,观察数据范围n <= 50 ,直接用floyd求出最短路。

继续二分最大长度 c ,对于每个已有城堡的城市,直接去标记其能到达的城市,然后对于不能到达的,

我们将其距离不超过枚举的c的点期望[......]

Read more

1014: [JSOI2008]火星人prefix

一脸萎靡。。。

这题做的疯。

数据真心有毒。

数字和字母之前不等距 exm?

二分 + hash + splay

我只能说是个p的神题。

bz的常数卡的我疯狂。。。

就是一般的splay入门题,看看代码就好了。

c++代码如下:
[crayon-5b[......]

Read more

P1024 一元三次方程求解

回归刷水题,二分的水题,直接见代码,可以当成二分答案的入门题了。

c++代码如下:

 

BZOJ1067: [SCOI2007]降雨量

时隔半个月写的第一题,还是改的原来的。。。

这道题算法很显而易见,重点在于细节处理。

建代码的处理咯

c++代码如下:

 

疫情控制 NOIP2012 T6

二分答案 + 贪心;

你会发现,其实对于每个点,我们只要能往上(不是根节点)一定是更优的,如果是根节点,我们先看看这个点通不通,不通的话这个点判通,返回,不然的话进入根节点找最小不通的点。

最后一个点恶心的菊花图,所以对于这道题的极限数据,你倍增不倍增都没卵用,我也懒得帖我倍增+桶排的代[......]

Read more

聪明的质监员 NOIP2011

二分答案,sum[i]表示前i个中符合>=x的个数,num[i]表示前i个中这些符合的v之和;剩下的直接二分搞搞就好了。原谅sum与num的英语意义乱用2333.