因为是单向边，牛儿来回的路径长度并不相同，所以需要用两次 dijkstra，一次正向从 \(x\) 开始 dijkstra，再将边全部反向存再来一次。 因为是板子题比较良心 \(n\) 比较小，我们就可以用矩阵来存储啦。如果 \(n\) 比较大的话，我的想法是再造一个图，同时反向存边。内存可能占用比较大但是想起来简单。 代码很短。 12345678910111213141516...

POJ3187 Backward Digit Sums 好熟悉的题目……但是忘了是怎么做的……好像是随机排列？ 反正都是暴力，看了下网上的题解，好像也没有更好的正解了。有想法的告诉我一下蟹蟹~ 题意 我们可以用1~n这n个数字用类似杨辉三角的方法加起来，我们就可以把他们拆回去。这样的排列可能有多种，我们要它字典序最小的一种。 思路 \(n\) 比较小，考虑排列所有可能一个个试...

对树状数组的理解加深了！ 转化题意 动态维护一个单调不降和一个单调不增序列，每次修改后输出两序列取最小值后的最大值和其最大位置。 思路 首先，阅读原题，知道最后答案一定是某个战士的温度，所以我们将温度离散化。 再次阅读，发现冰系是一个（以温度为自变量的）单调不降序列，每次修改一个战士就是修改一段后缀。火系相反，修改前缀。 深度阅读，发现题目其实就是求两个序列的交点。于是转化成上述...

Description 墨墨突然对等式很感兴趣，他正在研究 \(a_1x_1+a_2x_2+...+a_nx_n=B\) 存在非负整数解的条件，他要求你编写一个程序，给定 \(N\)、\(\{a_n\}\)、以及 \(B\) 的取值范围，求出有多少 \(B\) 可以使等式存在非负整数解。 Input 输入的第一行包含 3 个正整数，分别表示 \(N\)、\(B_{Min}\)、\(B...

就是把字符串转变成一个树，每个节点连接下一个字符，用空间换时间。 对于区分大小写或不区分的题目，只需要改变 ch[][26] 的值就行了。 ch[u][x] 表示 u 节点（标号决定）下一个 x 字符节点的标号。 如果题目让记录附加值，那就用 val[] 在插入时记录一下就好了。 1234567891011121314151617181920212223242526272829...

矩阵树定理 定义 邻接矩阵：\(A=(a_{ij})\)，其中 \(a_{ij}\) 表示 \(i\) 到 \(j\) 有几条边相连。 度数矩阵：\(C=(c_{ij})\)，为对角矩阵，其中 \(c_{ii}\) 表示 \(i\) 的度数。 基尔霍夫矩阵：\(D=C-A\)。 余子式：\(M_{ij}\) 表示去掉第 \(i\) 行第 \(j\) 列后得到矩阵的行列式。 ...

“有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”——《孙子算经》 中国剩余定理 即求多个同余方程的解。 举个栗子。求一个数x，使得： \[\begin{cases} x≡2\pmod 3\\ x≡3\pmod 5\\ x≡2\pmod {11}\end{cases}\] 设 \(M=3*5*11=165\), \(a1=3\), \(a2=5\),...

二项式反演 \[ \begin{aligned} g_n=\sum_{i=0}^n(-1)^i\binom ni f_i\Leftrightarrow f_n=\sum_{i=0}^n(-1)^i\binom ni g_i\\ g_n=\sum_{i=0}^n\binom ni f_i\Leftrightarrow g_n=\sum_{i=0}^n(-1)^{n-i}\binom...

主定理（Master Theorem）通常是指在算法分析领域中的一个定理，特别是用于分析递归算法的时间复杂度。 时间复杂度相关定义 在计算机科学中，算法的时间复杂度（time complexity）是一个函数，它定性描述该算法的运行时间。其原理在于，将计算机的每种基本运算（如加减乘除）所需的时间视为常数，然后考察一个算法调用了多大量级的基本运算。时间复杂度常用大 \(O\) 符号...

前言 前几天考试了发现这个东西完全不会欸……学了又忘真是讨厌至极 QAQ 所以又在网上找着看了看写一篇博客备忘。 学习笔记真的很有用！ 分层图 这个很容易理解，来源就是在一些最短路的问题上题目又加了比如说主角可以用传送宝石进行折跃之类的问题（针对），即可以选择k条边把这些边的边权变为零。 怎么样解决呢？可以在原图的基础上多复制k个相同的图，并用k条边把图之间的边用0边权边相连。就...