Contestant. Rank 2650. Rating +7. A. One and Two 题意 给定一个包含 \(1\) 和 \(2\) 的数组，输出最小的 \(k\)，满足 \(a_1 \cdot a_2 \cdot \ldots \cdot a_k = a_{k+1} \cdot a_{k+2} \cdot \ldots \cdot a_n\)。 思路 维护一个后缀和，统计前面和后面的 \(2\) 的个数，输出第一个 \(k\)，满足 \(2\) 的个数一致。 时间复杂度：\(O(n)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 1010; int a[N], suf[N]; signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t, n; cin >> t; whi ...
Practice. A. Cut the Triangle 题意 给定三个点，判断是否存在水平或数值的切割线，能将三个点所构成的三角形切割成两个三角形。 思路 很显然，我们只需判断是否存在直角三角形即可。 因为我们不知道哪个是直角，所以我们不妨找出所有 \(x\) 轴值相等的点和 \(y\) 轴相等的点。 更具体地说，我们统计一下满足上述条件的点，若为 \(1\) 个及以下，那么就可行，否则不可行。 时间复杂度：\(O(1)\) 对应AC代码 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 110; signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t; cin >> t; while(t --){ int x1, y1, x2, y2, x3, y3; c ...
Rank 1. AC 4/9. 因为11.11为四根棍，所以注定只能写四题 A. 乘方 CSP 2022 T1 题意 比较 \(a ^ b\) 和 \(10 ^ 9\) 的大小关系。 思路1 try-catch 用大数算法直接算，如果算得出来，那就比较；算不出来，也就是溢出了，那么一定是大于 \(1e9\) 的，利用语言特性，捕获这个异常然后输出 \(-1\) 即可。 对应AC代码 import java.math.*; import java.util.*; public class Main{ public static void main(String[] args){ Scanner scanner = new Scanner(System.in); try{ BigInteger a = new BigInteger(scanner.next()); int b = scanner.nextInt(); ...
原题：https://fjnuacm.top/d/contest/p/29?tid=635bad6e691055e12dce5282 题意 带佐在数轴上。\(0\) 时刻，带佐位于 \(0\) 处。在时刻 \(i−1\) 和 \(i\) 之间的时间段中，带佐要么待在当前位置，要么向左或向右跳 \(i\) 个单位长度。输出带佐最早在哪个时刻可以到达 \(X\)。 思路 首先，结论是：首项为 \(1\)，公差为 \(1\) 的等差数列的前 \(n\) 项和满足 \(S_n > x\) 的最小 \(n\) 即为答案。 下面给出证明思路： 上述结论的做法是： 令 \(m = 满足条件的最小 n\)，\(t = Sm - x\)，则只需在 \(t\) 时刻停留即可保证最后一步恰好走到 \(x\)。 上述结论的合理性： ① 我们不可能折回，因为折回后如果直接返回，只能前进 \(1\)，代价大于在 \(t\) 时刻停留的代价（可以根据等差数列理解，列方程来严格证明），而停留后返回代价明显更大（停留需要很长时间，而折回后返回前进的距离远没有这么长）。 ...
原题：https://fjnuacm.top/d/junior/p/P1304C 空调凉凉~ 题意 一个餐馆中有个空调，给定空调的初始温度为 \(m\)，每分钟可以选择上调或下调 \(1\) 个单位的温度，或选择不变。 给定 \(n\) 个食客的到达时间 \(t_i\) 以及所能适应的温度范围 \([l_i, r_i]\)，每个食客只会在 \(t_i\) 时刻逗留。 如果温度不在食客的适应范围内，他就会不舒服。输出空调能否使得所有食客都感到舒服。 思路 当初第一反应是维护一个温度值，根据食客的需求改变温度。但这里存在问题：对于有限的操作，最后能落在温度区间的温度是不唯一的。如果是这样，很多种可能叠加，不难发现会超时。 也许我们可以贪心地认为只要满足最低条件即可，但我们不能保证下一个本因可行的区间可能被判为不可行（如一直递增的温度区间）。 单个值失败了，那就多个值呗。 我们只要维护一个区间，让每次所有的可行解落在该区间。然后，对于每一个区间，将其与后面的区间进行区间重叠运算。 对于重叠的区间，有四种可能： 1.可行区间 \(cur\) 和后一个温度区间没 ...
原题：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); ...