[数学]莫比乌斯函数及其反演

莫比乌斯函数

定义

​ 设\(n = p1 ^ {k_1} p2^{k_2}p3^{k_3}....p_{m}^{k_m}\)

​ 如果n = 1 则 \(\mu(n) = 1\)

​ 如果\(\Pi{k_{i}} = 1\)\(\mu(n) = (-1) ^ {m}\)

​ otherwise \(\mu(n) = 0\)

​ 可知有平方因子的数的莫比乌斯函数值为 0。

USACO Fine Dining

题目解析

因为题目要求经过一个干草堆和不经过干草堆的最短路,所以我们可以先求出每一个点到n的最短路

再来看看经过一个干草堆的最短路,不妨设这个干草堆为k。所以这个最短路可以写成\(dis2_{i} = dis_{i}{k} + dis_{k}{n} - V_{k}\)

题解 P2146 [[NOI2015]软件包管理器]

题目大意

​ 给你一棵树, 求一点到根的路径上有多少个未标记点并全标记, 和询问一个点的子树内有多少已标记点和撤销标记

题解 P3628 [[APIO2010]特别行动队]

题目大意

​ 给你一个序列, 将这个序列分成若干段, 每一段的贡献为 \(ax ^ 2 + bx + c\)(x 为 这一段的权值之和)

具体思路

[算法学习笔记]左偏树的基本操作及其应用

简介

左偏树是一种可以快速支持合并等操作的堆, 是可并堆中代码复杂度最低,也最容易理解的一种(注意左偏树的每一棵子树都为左偏树)

点分治详解

一.概念

​ 是处理树上路径的一个极好的方法。如果你需要大规模的处理一些树上路径的问题时,点分治是一个不错的选择。

NOIP2018滚粗记

Day-1

​ 在机房里刷了刷水题,心情不错~~~

Day0

​ 中午朱老大说要放松一下 ~~~ (耳机飞起来)

​ 下午跟邓大佬在机房里刷模板题, 惊奇的发现邓大佬太强了!Orz. 模板分分钟切,黑题也是秒杀。

题解 P1311 【选择客栈】

思路导引

这道题要用到一点前缀和的思想,设l[i][j]为第i个客栈左边有多少个色调为j的客栈个数。r[i][j]为第i个客栈右边有多少个色调为j的客栈个数。(均包括自己)

此时我们考虑当一个客栈可以作为咖啡馆时,可以有多少种新的住宿方案。很显然有~~l[i][j]*r[i][j]~~ 是的,这当然是错的,因为会有重复的情况

题解 P1215 【[USACO1.4]母亲的牛奶 Mother's Milk】

代码君跑了

题解 P1379 【八数码难题】

啊♂!!这一题算是BFS中的经典了,如果你不懂BFS的话,可以睡觉了~

啊♂!!现在我们来分析一下思路

1.使用3*3的数组存储,操作十分简单,但会超时很多点,有兴趣的读者可以自行尝试一下;

2.程序中用3*3的二维数组表示布局比较直观,但在判断重复,判断是否达到目标方面,却给程序增加了复杂性,也影响了运行速度。可以改用字符串形式来表示布局,第1..3个数表示第一行的三个数,第4..6个数,表示第二行的三个数,第7..9个数表示第三行的三个数。这样,程序的判断和判重可以方便很多。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×