AtCoder ABC206D KAIBUNsyo 题解
AtCoder ABC206D KAIBUNsyo 题解 思路 观察到替换数字的过程，实际上就是将两个数字归为一类。借此不难联想到并查集的工作过程，因此我们可以考虑使用并查集解决这个问题。 我们使用并查集维护当前数字所属的集合，初始时对于数字 \(x\)，它位于集合 \(x\) 中。当我们发现本应相同但是并不在同一个集合内的数字时，我们不得不将其合并，并记录下一次操作。在操作的过程中，你不需要去判
CodingCow's Blog - Code solves everything
OiClass PUJI P3827 函数 题解
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 题解
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 题解
UVA929 Number Maze 题解 思路 简单看一下题目，可以理解为在网格上寻找从点 \((1,\,1)\) 到点 \((n,\,m)\) 的最短路，其中权值为点权。 我们可以考虑直接使用 Dijkstra 算法在网格上跑一遍最短路算法，求得答案。下面简述一下 Dijkstra 算法的过程： 创建一个大小与顶点数量相等的数组 \(f\)，用于存储起始点到各个顶点的当前最短距离估计值。 将
AT_arc132_b Shift and Reverse 题解
AT_arc132_b Shift and Reverse 题解 题意 有一个序列，你可以将它翻转或者将第一个数挪到最后面，求最小的操作使得序列升序的次数。数据保证有解。 思路 首先我们可以看到题目中说保证一定有解，因此我们可以发现挪动的方式一定是将前面的数整体挪到到后面或者翻转后将前面的数移到后面再翻转回来。看一个例子： 13 4 5 6 7 8 9 10 1 2 答案显然是将序列整体翻转后将
Luogu P2568 GCD 题解
Luogu P2568 GCD 题解 思路 首先我们可以根据题意列出式子： \[ \sum_{p \in {\mathbb P}}\sum_{i = 1}^{n} \sum_{j=1}^n [\gcd(i, j)=p] \] 根据一些神秘的直觉，可以将式子化简成下面的样子： \[ \sum_{p \in {\mathbb P}} \sum_{i = 1}^{\left\lfloor\frac n
TYCPC 游记
TYCPC 游记 感受 感觉出题人就是 ___ ，出的全是人类智慧题，罚时吃饱了！ T1 不会。 T2 分解质因数秒了，就是有点担心 unordered_map 常数太大，不过卡过去了，不慌。 T3 排序建图后然后直接分联通块就可以了。但是不知道关掉同步流以后 puts 不可以和 cout 一起用，多吃了一发罚时，大悲。 T4 可以发现，一棵树上的任何一个节点（除根节点）一定入度是 \(1\)，于
Luogu P1495 题解
Luogu P1495 题解 思路 首先看一下题目，可以理解为求解下面的方程： \[ \left\{ \begin{array}{c} x \equiv b_1 \pmod {a_1} \\ x \equiv b_2 \pmod {a_2} \\ \cdots \\ x \equiv b_n \pmod {a_n} \\ \end{array} \right. \] 很显然可以用中国剩余定理求解，