zxs66的日记

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.2¹⁰-4932~1.2¹⁰+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

总结

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