CodingCow's Blog - Code solves everything

OiClass TIGAO P3333 路径难题题解 思路 首先考虑暴力建边的做法，我们使用 \(\mathcal{O}({t_i}^2)\) 的时间建立公交站的边。然后我们考虑如何计算答案。考虑到每次坐公交车的时候都会进行出租车的结算，于是我们直接累计到最后才向上取整的做法是没有正确性的。 于是我们考虑每次到公交节点的时候就进行向上取整，这样就可以保证 Dijkstra 的正确性。 这样就解决了

OiClass PU2TI P3042 拓展的奇拼图题解 思路 首先发现这题是八数码问题的加强版，但是数据量非常大，爆搜+剪枝的方法非常的不可取，于是我们考虑是否可以通过一些神秘的判断方法来判断出是否可以构造出来。 从数据量可以感受出来应该是使用某种接近线性的算法，果断猜测是否是逆序对。把矩阵展开后去掉 \(0\)，然后计算逆序对个数，判断奇偶性即可。 代码 1234567891011121314

OiClass PU2TI P3186 小美的排队次数 题解 思路 以下格式模仿睿智的官方题解。 \(10\,\%\) 做法：呵呵，对于这种神奇的算法还是表示不明觉厉。 \(40\,\%\) 做法：呵呵，依题意模拟计数即可。 \(100\,\%\) 做法：呵呵，随便做即可。考虑以下先做一轮，观察一下有什么性质。手磨样例，一轮以后是 1, 2, 3, 5, 4, 6 发现每一次只可能交换相邻的两个

SPOJ SETSTACK 题解 题意 有一个装着集合的栈，需要你实现以下操作： PUSH. 将把空集 \(\{\}\) 推到堆栈上。 DUP. 将复制最顶层的集合（弹出堆栈，然后将该集合推入堆栈两次）。 UNION. 会弹出堆栈两次，然后将两个集合的联合值推入堆栈。 INTERSECT. 会弹出堆栈两次，然后将两个集合的交集推到堆栈上。 ADD. 会弹出堆栈两次，将第一个集合加入第二个集合，然

SPOJ MARTIAN 题解 思路 首先简单理解一下题目，会发现题目就是在网格上选择若干列（或列的上面一段）以及若干行（或行的左边一段）似的这些被选中的列和行之间的和最大。具体可以看题目的这张图： 很明显这是一个 DP 问题，于是我们着手设计状态转移方程。首先我们先分别预处理出纵向的和横向的两个前缀和分别是 \(y_{i,\,j}\) 和 \(b_{i,\,j}\)，字母对应题目的矿物名称首字

AtCoder ABC206D KAIBUNsyo 题解 思路 观察到替换数字的过程，实际上就是将两个数字归为一类。借此不难联想到并查集的工作过程，因此我们可以考虑使用并查集解决这个问题。 我们使用并查集维护当前数字所属的集合，初始时对于数字 \(x\)，它位于集合 \(x\) 中。当我们发现本应相同但是并不在同一个集合内的数字时，我们不得不将其合并，并记录下一次操作。在操作的过程中，你不需要去判

OiClass PUJI P3827 函数 题解 思路 首先化简一下公式： \[ \begin{align*} f(n,\,r)&={\rm C}^r_n (n - r)!\\ &=\frac{A^r_n(n - r)!}{r!}\\ &=\frac{n!}{r!}\\ &=\prod _{i=r + 1}^n i \end{align*} \] 但是数据范围很大，

CF1612D X-Magic Pair 题解 思路 我们首先假定 \(a < b\) ，那么我们可以通过题目给定的方式将 \((a,\,b)\) 转移到： \((b - a,\,b)\) \((a,\,b- a)\) 这是显然的。但是我们发现如果我们转化为 \((b - a,\, a)\)，那么下一步就会转移到： \(((b - a) - (b - a),\, a) = (0,\,a

UVA929 Number Maze 题解 思路 简单看一下题目，可以理解为在网格上寻找从点 \((1,\,1)\) 到点 \((n,\,m)\) 的最短路，其中权值为点权。 我们可以考虑直接使用 Dijkstra 算法在网格上跑一遍最短路算法，求得答案。下面简述一下 Dijkstra 算法的过程： 创建一个大小与顶点数量相等的数组 \(f\)，用于存储起始点到各个顶点的当前最短距离估计值。 将

AT_arc132_b Shift and Reverse 题解 题意 有一个序列，你可以将它翻转或者将第一个数挪到最后面，求最小的操作使得序列升序的次数。数据保证有解。 思路 首先我们可以看到题目中说保证一定有解，因此我们可以发现挪动的方式一定是将前面的数整体挪到到后面或者翻转后将前面的数移到后面再翻转回来。看一个例子： 13 4 5 6 7 8 9 10 1 2 答案显然是将序列整体翻转后将