原题：https://fjnuacm.top/d/junior/p/532?tid=6363a9a5691055e12dd288dc 其实如果没有给出是图论题的话，这题就难在想不想得到拓扑了。 题意 定义"要求"：对于任意停靠的车站，存在优先级，需要满足其余大于等于该车站优先级的车站必须停靠的条件。 给出满足"要求"的几条线路，求出需要划分的最少优先级数量。 思路 首先，我们确定一下每条线路需要处理的车站：从起点到终点这一段路上的所有车站。 对于"优先"这个概念，我们可以联系到图论中的父子关系，也就是建立有向边。 对于有向边，当我们将优先级小的车站作为父节点、优先级大的作为子节点时，就可以采用拓扑排序的逻辑。在每次 \(push\) 的时候，我们只需存入当前节点的优先级，依次迭代并记录优先级的最大值即可。 对于建立有向边，我们可以遍历这条线路上所有非停靠站，将所有车站依次连到各个非停靠车站上即可。 对应AC代码 import java.util.*; public class Main{ private stati ...
原题：https://fjnuacm.top/d/junior/p/542?tid=6363ac4a691055e12dd289de 最短路题单，但是可以用拓扑（ 题意 给定 \(A - Z\) 中前 \(n\) 个字母的大小顺序，且都为小于关系，共有 \(m\) 个条件，从前往后判断满足所有条件的序列是否存在且唯一。 对于从前往后的 \(t\) 次遍历中，若能确定最后输出，则略过后面的输入。 有唯一解，输出 \(Sorted \ sequence \ determined \ after \ t \ relations: yyy...y.\) 有多解（冲突），输出 \(Inconsistency \ found \ after \ t \ relations.\) 无解（没有给全所有点的条件），输出 \(Sorted \ sequence \ cannot \ be \ determined.\) 思路 因为题面提到需要整个序列的顺序输出，而联想到拓扑排序，它可以将一个有向图转换成一个有先后顺序的序列，这正是我们 ...
原题：https://fjnuacm.top/d/junior/p/512?tid=633d6550d2fe705a3c4684c7 之所以来写这个题解，是因为思路真的太清晰啦（（ 题意 给定一段由 \(0, 1, 2\) 组成的二叉树序列 \(S\)，序列由下面三种元素构成： \(0\)：表示该树没有节点； \(1 S_1\)：表示该数有一个节点，\(S_1\) 为其子树的二叉树序列； \(2 S_1 S_2\)：表示该树有两个子节点，\(S_1\) 和 \(S_2\) 分别表示其两个子树的二叉树序列。 根据上述序列建树，并标上红蓝绿三种颜色，相邻颜色不能重复，子节点颜色不能重复，求出这棵树中绿色节点的最大和最小数量。 思路 我们考虑下面的两个问题。 如何建树 根据题给条件，在给出根节点后，后面将会有一段数字作为根节点的子树，而其子树又可向右找到他的子树，以此类推。 但我们要如何确定下一个节点从哪里开始呢？显然，在上一个子节点遍历完后，下一个下标即为另一个子节点的开始下标。 于是乎，我们可以记录一下当前的下标在哪个位置，然后..... ...
原题：https://fjnuacm.top/d/junior/p/369?tid=6301e681027d8fe886628d9d 感觉之前写得太蠢了就重新写一下（ 题意 每次把最小的两个拿出来合并并将数量作为本次体力消耗，输出最小体力消耗值。 思路1 显然，我们只需边枚举边排序，考虑到数据范围够小，暴力是完全可行的。 时间复杂度：\(O(n \log n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; int d[20001]; int main() { int n; cin >> n; for(int i=0;i<n;i++) cin >> d[i]; sort(d, d + n); int ans = 0; for(int i=1;i<n;i++){ d[i] += d[i - 1]; ans += d[i]; sort(d + i, d + n); ...
原题：https://fjnuacm.top/d/junior/p/491?tid=633184a5ea0e1b063194593d 杰尼龟刚刚接触了信息学竞赛，有一天它遇到了这样一个题：靶形数独。 “简单！”杰尼龟心想，同时很快就写出了一份程序，可是测试时却出现了错误。 题意 完成一个每格具有分数的数独，使分数和最大。 铺垫 先来看看这题 数独 - 洛谷. 显然，我们只需要用 \(dfs\) 就可以了。 我们传递两个参数，代表当前我们搜索的点。 然后我们判断一下列有没有超出最大值，有的话跳到下一行即可。 不过需要注意的是，我们没有必要嵌套两个 \(for\) (你喜欢的话记得 \(break\) )，只需在传递参数的时候把当前列 \(+1\) 即可。 思路 首先，我们很容易想到直接套数独的模板，然后记录一下最高分即可。 这没有错，但你会喜提 \(2tle\)。 为什么呢？你可以试试用你的思维来解数独。 当拿到一个数独的时候，你的第一反应是什么？ 没错，自然是从空格最少的行填起。 这里就存在一个剪枝：对行排序。 我们可以用桶排序 ...
原题：https://fjnuacm.top/d/junior/p/464?tid=62e26edd3a711450d9b817c5 题意 小渊很懒，给你各个位置的高度，让你画立体图。 思路 首先，根据题单名称，我们可以知道要模拟。 方块之间的前后视觉遮挡问题 首先，我们来考虑这个本题最难的点。 显然，对于斜二测画法的立体图，后面靠左的区域会被前者覆盖。那么我们自然会发现，从前往后画，覆盖问题会变得很复杂（不过也不是不能做）。 所以，我们不妨试试从俯视视角的左上角开始画。 我们以一个方块为一个单位开始画图。这里我们定义一个 \(char\) 二维数组来存储一个方块，并用题给的 \(.\) 符号来表示空区域。 char[][] one = { "..+---+".toCharArray(), "./ /|".toCharArray(), "+---+ |".toCharArray(), "| | +".toCharArray(), "| |/.". ...
Practice. A. Divide and Conquer 题意 给定一个数组 \(a\)，定义操作为选定一个元素并将其除 \(2\) 后向下取整，输出最少操作数，使整个数组的和为奇数。 思路 考虑到数据量比较小，我们不妨直接用“分治”的方法，考虑每个元素需要多少次才能改变奇偶性，然后找出操作数最少的元素，对应的操作数就是我们想要的答案。 当然，本来就是奇数的话就直接输出 \(0\)。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 60, inf = 0x3f3f3f3f; int a[N]; signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t, n; cin >> t; while(t --){ memset(a, 0 ...
Practice. A. Joey Takes Money 题意 给定一个包含 \(n\) 个 \(\geq 1\) 的元素的数组 \(a\)，定义操作为： 选定 \(i, j, i \neq j\)； 选两个 \(\geq 1\) 的正整数 \(x, y\)，满足 \(x \cdot y = a_i \cdot a_j\)； 将 \(a_i, a_j\) 改为 \(x, y\)。 输出任意次操作后数组的和的最大值 x2022。 思路 显然，对于 \(a_i, a_j\)，\(1 + a_i \cdot a_j\) 一定是所有操作中最大的和，那么我们可以依次从左到右将所有数都执行一遍该操作，得到 \(1, 1, 1, \ldots, \prod a_i\)，求和即可。 时间复杂度：\(O(n)\) 对应AC代码 import java.util.*; public class Main{ public static void main(String[] args){ Scanner sca ...
Practice A. Absolute Maximization 题意 给定一个数组 \(a\)，定义操作为选择两个元素 \(a_i, a_j\)，并交换它们二进制下的第 \(b\) 位。输出任意次操作后的 \(\max(a) - \min(a)\) 的最大值。 思路 既然可以无限次交换，那么我们只要找出最高位，从最高位开始往下找，只要有一个元素该位存在 \(1\)，那么我们就拿过来构建新的数字，这样即可得到最大值。反之同理。 时间复杂度：\(O(n)\) 对应AC代码 import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int t = scanner.nextInt(); for(int w=0;w<t;w++){ int n = scanner ...