文章目录   $线段树优化建图的作用$    $问题$    $线段树优化建图的实现$ $线段树优化建图的相关代码$    1. $建图$ 2. $叶子节点连边$ 3. $点\rightarrow区间 连边$ 4. $区间\rightarrow点 连边$ 5. $最短路$    $线段树优化建图的应用$            线   段   树   优   化   建   图   的   作   用    线段树优化建图的作用   线段树优化建图的作用       问   题    问题   问题 有      N    N   N 个节点, 执行      M    M   M 次以下连边操...

回   家   路   线    回家路线   回家路线       <mstyle mathcolor="blue">   最   初   想   法   </mstyle>   \color{blue}{最初想法}   最初想法 设      D   i   s   [   i   ,   j   ]    Dis[i,j]   Dis[i,j] 表示使用编号为      j    j   j 的边走到      i    i   i 节点的最小花费, 则      D   i   s   [   t   o   ,   j   ]   =   ...

B   e   a   r  <mtext>   </mtext>  a   n   d  <mtext>   </mtext>  B   o   w   l   i   n   g    Bear\ and\ Bowling   Bear and Bowling 题意与 这道题目 大致相同, 唯一不同的是所选序列可以在原序列中不连续, 即子序列 .      <mstyle mathcolor="blue">   最   初   想   法   </mstyle>   \color{blue}{最初想...

任   务   安   排    任务安排   任务安排 机器上有N个需要处理的任务，它们构成了一个序列。这些任务被标号为1到N，因此序列的排列为1,2,3…N。这N个任务被分成若干批，每批包含相邻的若干任务。从时刻0开始，这些任务被分批加工，第i个任务单独完成所需的时间是Ti。在每批任务开始前，机器需要启动时间S，而完成这批任务所需的时间是各个任务需要时间的总和。注意，同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数Fi。请确定一个分组方案，使得总费用最小。      N   ≤   1    0   5    ,   S   ≤   50   −    2   8 ...

B   e   a   r  <mtext>   </mtext>  a   n   d  <mtext>   </mtext>  B   o   w   l   i   n   g  <mtext>   </mtext>  4    Bear\ and\ Bowling\ 4   Bear and Bowling 4         D   e   s   c   r   i   p   t   i   o   n    \mathcal{Description}   Description  给一个长度为     N ...

文章目录   $斜率优化的作用$ $斜率优化的内容$ $斜率优化的实现$ $斜率优化的变形$ $相关数学推导补充$            斜   率   优   化   的   作   用    斜率优化的作用   斜率优化的作用        F   i    =   min   ⁡   (  <mtext>   </mtext>   F   j    +    s   i   2    +   (    s   j    +   L    )   2    −   2    s   i    (    s   j    +   L   )  <mtext&gt...

单   调   队   列   的   内   容    单调队列的内容   单调队列的内容  顾名思义, 始终 单调递增 或 单调递减 的 双端队列 即为单调队列 . 接下来以 滑动窗口 为例说一下基础的单调队列操作. 设当前枚举到了       A   i     A_i   Ai​, 且维护的是从队首到队尾单调递增的队列, (队首比队尾入队时间早)  若队列为空, 直接将       A   i     A_i   Ai​ 入队. 若队列不为空, 设队尾为      b   k    bk   bk,  若       A    b   k     >    A   i  ...

O   n  <mtext>   </mtext>  I   t   e   r   a   t   i   o   n  <mtext>   </mtext>  o   f  <mtext>   </mtext>  O   n   e  <mtext>   </mtext>  W   e   l   l   −   K   n   o   w   n  <mtext>   </mtext>  F   u   n   c   t   i   o   n    On\ Iter...

完   全   平   方   数    完全平方数   完全平方数         D   e   s   c   r   i   p   t   i   o   n    \mathcal{Description}   Description  小 X 自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。 这天是小X的生日，小 W 想送一个数给他作为生日礼物。当然他不能送一个小X讨厌的数。他列出了所有小X不讨厌的数，然后选取了第 K个数送给了小X。小X很开心地收下了。 然而现在小 W...

P   r   o   b   l   e   m  <mtext>   </mtext>  b    Problem\ b   Problem b         D   e   s   c   r   i   p   t   i   o   n    \mathcal{Description}   Description  对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。        最   初   想   法    最初想法   最初想法       A   n ...

文章目录   $整除分块$ $莫比乌斯函数$   $定义:$ $性质:$  证明:    $莫比乌斯反演$    证明:    $莫比乌斯反演的变形$    $证明:$    $莫比乌斯反演的应用$   $\color{blue}{求解gcd(i,j)=1的对数}$  $解法 :$  $\color{blue}{求解gcd(i,j)=k的对数}$  $解法 1:$ $解法 2:$ $再提整除分块:$  $\color{blue}{求解gcd(i,j)的幂}$  $解法 :$  待填坑..                整   除   分   块    整除分块   整除分块       Q  ...

D   e   r   a   n   g   e   d  <mtext>   </mtext>  E   x   a   m   s    Deranged\ Exams   Deranged Exams         D   e   s   c   r   i   p   t   i   o   n    \mathcal{Description}   Description       N    N   N 个位置, 求至少前      K    K   K 个数字不在自己位置上的方案数 .        正   解   部   分    正解部分   正解部...

F   r   o   g   s    Frogs   Frogs         D   e   s   c   r   i   p   t   i   o   n    \mathcal{Description}   Description       有   m   个   石   子   围   成   一   圈   ,   有   n   只   青   蛙   跳   石   子   ,   都   从   0   号   石   子   开   始   ,   每   次   只   能   越   过    A   i    个   石   子   .   问   所   ...

幸   运   数   字    幸运数字   幸运数字         D   e   s   c   r   i   p   t   i   o   n    \mathcal{Description}   Description  在中国，很多人都把6和8视为是幸运数字！lxhgww也这样认为，于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码，比如68，666，888都是“幸运号码”！但是这种“幸运号码”总是太少了，比如在[1,100]的区间内就只有6个（6，8，66，68，86，88），于是他又定义了一种“近似幸运号码”。lxhgww规定，凡是“幸运号码”的倍数都是...