31天复习计划

20240312

二分
感觉二分很不扎实,好好复习。

整数二分

# P2249 【深基13.例1】查找
问题:我写的二分答案是搜到小于x的最后一个位置,但是实际含义是大于等于x的第一个位置。

原因:二分答案边界确实是搜到小于x的最后一个位置结束,但是我的ans只记录大于等于x的位置,所以最后一个被记录答案的一定是大于等于x的第一个位置

84 第一个点wa了;

出错的原因:没有认真读题 “非负整数”!表示可能存在 0 。

然而,发现改改边界,可以忽略这个情况

l=1,r=n;

不从 \(0\) 开始,开始使用 \(0\) 的原因是:认为是搜到小于 x 的最后一个位置。如果 1 是答案,那么搜到的位置应该是 \(0\),所以在边界往前靠,但是因为实际操作是错的,所以此时 \(0\) 是没有用的。
code

实数二分

实数二分需要注意的点:精度的问题。

写出以下几点:

  • if(r-l>eps) 中等号写不写都一样
  • 精度问题,使用 long double ,注意输出方式 printf("%.2Lf",x)
  • 关于记录答案的操作,感觉和整数二分是一样的

例题

P1542 包裹快递
看似是一个绿题,实际是到水题,起码水 90不成问题,最后一个点出题人确实卡精度很厉害,这也让我知道对于数据很大的实数二分如何正确最对。

卡精度
在这道题目中卡精度的意思是指:在 check 的时候由于数据范围超过了 double 的最大值,注意是最大值,导致爆掉了
long double 数据范围 :18~19位
1.210-4932~1.210+4932
还有这句话
double tim=1.0*a[i].s/(1.0*x);
将 double 改成 long double 会报错。
关于 long double 的输出:

printf("%.2Lf",x);

因为这一点,确实可以作为一个绿题出现,但是属于绿题里面比较 low 的题目。
code

三分法

三分法笔记

虽然是以前的笔记,但是我依然选择用以前的写法。
简单说一下现在的我的三分出现的问题:

  • 关于三分极值的原理是搞明白的,就是如何缩短区间的原理。
  • 但是以前写法和现在书上写法不同的是,三等分的理解。

原来代码的写法是二分以后再二分,
而现在书上说的是三等分线。

我去搜了搜资料,我竟然没有找到双重二分的博客,都是一些奇怪的东西,无奈,我没办法找出差别。
但是我就是三等分线写不出来,双重二分就能写对。

所以我选的双重二分。
code

离散化

学习书上的离散化,觉得比较好理解

void discrete()
{
	sort(a+1,a+1+n);
	for (int i=1;i<=n;i++)
		if (i==1||a[i]!=a[i-1]) b[++num]=a[i];
}

例题
火烧赤壁
这道题目很显然是一道左右区间排序的问题,处理一下边界问题,就可以做了,但是,这里并没有用到离散化,但是这道题目用离散化。

第一种做法:
存在的问题:在处理边界的时候,会存在相同的区间若干,在统计答案时,也就是下面

if (a[i].l>(r-1))//没有考虑到 0 1 ,0 1 的情况 
{
	sum+=r-l;
	l=a[i].l;
	r=a[i].r;
}

if 的等于不可以加上,否则会重复计算,这是一种 0,1 这一种特殊情况下,因为题目还有一个性质是 左闭右开,所以这种特殊情况卡的死死的,

只有 80pts

code

第二种做法

这才是这道题目的正菜

离散化+差分 天生一对

这道题目可以简化为:黑色刷漆,区间刷,求刷的长度。

有一种想法是看成区间加,这不难想到差分,但是发现统计答案的时候不好搞。

我们将问题反过来想,请问答案一定是一个区间,左右边界的边界都是0,中间不是0,对吧,
那么左右边界是不是给出的左右端点的其中两个,可能两个左端点,可能不是原来一对的端点。
那么这说明,给定的左右端点不是绝对的二元关系。

我只需要找出两个区间端点,之间不为零就可以了,
将区间问题拆成差分看的话,就是两个独立问题,一个是后缀加,一个是后缀减,
通过求前缀和来了解当前边界是否为零,
如果知道前缀和,找到连续不为零区间就简单了,只需要用l,r作为连续区间的左右边界即可。

现在来解决前缀和的问题,这其实就是把两个边界当成两个点,区间加而已,但是我们发现,每个区间端点之间差的很大,不容易遍历,这就想到离散化。
所以离散化每个区间端点,问题就解决了。

哎,说的挺啰嗦的。

为什么说天生一对:
因为离散化,使得区间端点可以按顺序遍历,从而可以找到连续有值区间,这样就把重叠区间相当于缩小求解。
也就是说,因为离散化,将区间重叠问题转化为单点问题,这里面其实还有差分的原因,
对于区间,我们利用差分思想,可以将区间问题转化成一个后缀加,一个后缀减,然后就变成两个独立的子问题了。
这么看,二者都是联系在一起,有点优美。算是一种模型吧

说完原理,值得注意的是边界问题,因为差分作用,即后缀的影响,前边界0到第一个边界中间的值是0 ,但是最后一个边界到右边界 0 的值不是0,而是最后一个右边界的值,这在求边界长度的时候,最右边界是右边界0,但是不包括。

哎我咋说的这么麻烦,服了!

code

总结

自己的做题效率很低,阐述问题的能力不强,说的有点啰嗦,累了,明天再干!

声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。