课堂笔记
2026-09-27 15:51:56
发布于:上海
时隔好长时间终于开始系统课程了。
好感动好开心。
祝大家都能找到合适自己的课程。
——————————————————————————————————————————
今天上课的内容是“从问题的过程走向可计算的结构”
这个题目它需要一层一层地去抽丝剥茧。
1.a+0.1 b+0.9
这是一个神秘的数字不是吗?
众所周知,能够使用整数我们就尽量用整数做法去做。
既然肉和签子的坐标都是整数,我们可以将判断一个签子能不能叉到肉从这样
s<=a+0.1<=e && s<=b+0.9<=e
变成
s<=a<e && s<=b<e
2.思路大转换
题目想要去询问最后能够有多少肉能被吃到
如果要去看一根签子能够串到多少肉,是一个很复杂很麻烦的过程(因为你要处理一块肉还有没有存不存在被吃掉了还是掉地上了)
那么,正难则反。
我们不妨直接去计算一块肉会被谁串到。
如何去计算?
可以把左签子和右签子分别放在两个数组里进行排序。
然后在左签子里锁定一个合法区间,右签里锁定一个合法区间。
最后在这两个合法区间里用ST表分别去找一个最小数值。
时间复杂度O(nlogn)
如果这两个合法数值是相同的,那么就相当于这块肉被吃掉了。
如果两个合法数值不同,就说明这块肉掉地上了。
惊喜发现自己已经遗忘了ST表写法。
SOS紧急复习一下。
P10206
在原图中找一对点添加一条长度为l的双向铁路,使得从点s到点ty的通行时间<=k
问有多少对点可以符合要求。
1.暴力
我们不难想到一个比较直接的暴力。
也就是,枚举点对O(n^2)
那么问题在于,在改变了(u,v)之间的距离之后,从点s到点t之间的最短路如何在O(1)求出。
这是一个典型的换边问题,我们需要一点点分类讨论。
1.最短路并没有通过(u,v)
那么就是原来的路径,没有任何的修改
2.最短路从点u到点v
那么就是dis[u]+l+dis1[v]
(dis1[v]用一个反向建边的技巧,从点v到点t的长度)
3.最短路从点v到点u
那么就是dis[v]+l+dis1[u]
如果min{1,2,3}<=k那么就算是成功
2.转换
现在,我们可以从一个小突破口入手。
当dis[v]<=k,符合要求的点对有多少个?
有n*(n-1)/2个。
然后我们将刚刚的公式扒出来做一点处理(这种不等式的处理往往就是突破口)
即:
dis[u]+l+dis1[v]<=k
变成:
dis[u]<=k-dis1[v]-l
也就是说,我们可以把dis[u]排序,然后用upper找出第一个大于的,后面就全是符合条件的。
总体过程就是:遍历一到n,找符合条件的u
这个时候有一个设问:需要再去遍历一遍找第三种情况下符合条件的吗?
不需要。因为是无向图。
噢噢噢噢。等一下,其实不需要反向建边。这似乎是无向图。
只是需要跑两遍dis罢了。
记得看数据范围。
注意注意注意注意!!!
只要开了defiine int long long
用最大值不要用INT_MAX
要用4e18!!!
还有就是要特判,因为如果原最短路就符合条件,那么直接输出n*(n-1)/2即可。
因为根本不需要用(u,v)之间的边。
用二分去计算的板块是默认一定要用到的。
ACGO可以把这只肥嘟嘟的

狗能屏蔽掉吗?挡视野了(bushi)
1.基础贪心想法&&思路转变
一个10a+b的时候就应该意识到:我们会把尽量大的数字放在a,尽量小的数字放在b
如果直接去模拟,有很多种形态很多种可能,非常非常麻烦,所以猜一猜大概就知道要避免模拟这方面的做法。
2.思路框架具体搭建&&具体实现
所以我们现在的想法是:尽量让大的数当十位,小的数字当个位
那么需要考虑:什么样的数字适合当各位?什么样的数字能当个位?
先来看第二个问题:什么样的数字能当各位?
我们可以由此联想到一个东西:括号匹配。
在十位的数量>个位的时候,当前的这个数字才能够成为个位。
从单纯的数字角度来说,
假设A是所有数字之和,B是所有被选中的个位数字之和
那么总答案就是:10(A-B)+B=10A-10B+B=10A-9B
那么希望B尽可能小。
也就是说,如果可以,我希望把一整个串里最小的数字变成个位数。
但是显然这是不可以的。
那我们可以这样做:
先假设当前位是个位,把它塞到优先队列里。
如果个位的数量已经超出定值(比如现在遍历到i,那么个位的数量必须要<=(i/2)向下取整)
那么就删除一个在优先队列里的候选数值。
删除谁呢?
删最大的即可。
这里空空如也















有帮助,赞一个