ZHLin_Blog

牛客2025秋季算法编程训练联赛5-基础组_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ C 牛牛战队的秀场 1.首先需要知道pai的精确表示方法：$acos(-1.0)$ 2.解三角形c^2 = a^2+b^2-2ab cosC 用二倍角公式化简完成后得：c = 2r sin(pai / n) 求得边长 3.左右两边都可以走相当于一个环，没必要用循环移位，可以用$O(1)$写出来。 #include <bits/stdc++.h>using namespace std;const double pai = 3.1415926;int r, n, i, j;int main(){ cin >> n >> r >> i >> j; double len = 2 * r * sin(acos(-1.0) / n); int diff = abs(i - j); int min_steps = min(diff, n - diff); // 输出最短距离 cout << fixed <<...

比赛链接 A 题目链接 首先以ABC顺序排，看最后剩下的至多两个类型的比赛的数量，如果有至少一个比赛数量>=2，那么为NO，否则为YES。 #include <bits/stdc++.h>using namespace std;int t;void sol(){ int a, b, c, t; cin >> a >> b >> c; t = min(min(a, b), c); a -= t, b -= t, c -= t; if (a >= 2 || b >= 2 || c >= 2){ cout << "NO" << endl; } else{ cout << "YES" << endl; }}int main(){ cin >> t; while (...

比赛链接 A #include <bits/stdc++.h>using namespace std;#define IO ios::sync_with_stdio(0);cin.tie(0);#define endl '\n'typedef long long ls;const int N = 4e5+10;void sol(){ int x; cin >> x; int p = sqrt(x); if (p * (p + 1) == x) cout << "YES" <<endl; else cout << "NO" << endl;}int main(){ IO sol();} B #include <bits/stdc++.h>using namespace std;#define IO ios::sync_with_stdio(0);cin.tie(0);#define endl &#...

比赛链接 A #include <bits/stdc++.h>using namespace std;#define IO ios::sync_with_stdio(0);cin.tie(0);#define endl '\n'typedef long long ls;const int N = 1e5 + 10;int n;void sol(){ cin >> n; int a[N]; for (int i = 1; i <= n; i++) cin >> a[i]; ls sum = 0; for (int i = 1; i <= n; i++){ int cnt = 0; for (int j = 1; j <= n; j++) if (a[j] <= a[i] && i != j) cnt++; if (cnt >= 1.0 * (n - 1) * 0.8){ //cout << i << end...

比赛链接 D 刚看到这个题目就来了思路，想着用优先队列来做，每次合并最小的两个数，然后把合并好的再添加进优先队列里，不断重复直到只剩一个元素为止，每次合并的重量之和就是答案。问题是只对了65%的数据，仔细想想看，如果总果子的堆数$c_i$特别大，最坏能到 $10^{11}$ 级别，那就会导致内存直接爆炸。果断换一种思路，使用map来做，记录每个重量有多少堆，每次处理最小的重量，因为map天生就是按key来排序的。 注意一个问题：不用mp.size()来做循环变量，这样不好判断是否只剩1个，用tot来记录还剩余几个数，tot等于1时候结束循环。 正确代码如下： #include <bits/stdc++.h>using namespace std;typedef long long ls;const ls MOD = 1e9 + 7;void sol(){ map<ls, ls> mp; int n; cin >> n; ls tot = 0; for (int i = 1; i <= n; i++){ ls c, w; cin >&g...

原题链接 B. 青蛙的诅咒 每次测试的时间限制：1 秒 每次测试的内存限制：256 兆字节 在一条无限数轴上，点 $0$ 处坐着一只青蛙。经过多年的冥想，青蛙掌握了 $n$ 种独特类型的魔法跳跃。第 $i$ 种跳跃允许它向前跳跃不超过 $a_i$ 个单位。换句话说，如果它在整数点 $k$，跳跃后它可以落在从 $k$ 到 $k + a_i$ 的任意整数点。 但是魔法总是有代价的；它被诅咒了。在第 $i$ 种跳跃的每第 $b_i$ 次尝试之前（即在使用第 $i$ 种跳跃的第 $b_i$ 次、第 $2b_i$ 次、第 $3b_i$ 次等尝试中），青蛙会向后退 $c_i$ 个单位！换句话说，如果它在点 $k$，它首先会发现自己在点 $k - c_i$，跳跃之后，它可以落在从 $k - c_i$ 到 $k - c_i + a_i$ 的任意整数点。 青蛙的目标是到达数字为 $x$ 的点，同时使用跳跃并使回滚次数最少。帮助青蛙 —— 找到它在通往目标的路上必须忍受的最小回滚次数，或者确定它无法到达点 $x$。 输入 每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。测试用例的描述如下。 每个测试用例的第一行包含 2 个整数 $n$ 和 $x$ ($1 \le n \le 10^5, 1 \le x \le 10^{18}$) —— 青蛙可以进行的跳跃类型的数量及其最终目标。 接下来的 $n$ 行提供了跳跃类型的描述；第 $i$ 行包含...

Problem - C - Codeforces CF2200C Specialty String - 洛谷 题目描述 AksLolCoding 正在玩一个关于字符串 $s$ 的游戏，字符串长度为 $n$。初始时，$s$ 只包含小写拉丁字母。 每一回合，AksLolCoding 可以选择一对整数 $(i, j)$，满足： $1 \leq i < j \leq n$； $s_i = s_j \neq *$； 对于所有 $i < k < j$，有 $s_k = *$。 如果不存在这样的 $i,j$，则游戏结束。否则，AksLolCoding 令 $s_i := *$ 且 $s_j := *$。当游戏结束后，只有当 $s$ 的每一个字符都等于 $*$ 时，AksLolCoding 才获胜。请判断是否存在一种操作方式，使得 AksLolCoding 能够获胜。 注意：$*$ 表示 ASCII 字符 42。 输入格式 第一行为一个整数 $t$（$1 \leq t \leq 100$），表示测试用例的数量。 每个测试用例的第一行为一个整数 $n$（$1 \leq n \leq 5000$），表示字符串的长度。 每个测试用例的第二行为一个仅由小写拉丁字母组成的字符串 $s$。 所有测试用例中 $n$ 的总和不超过 $5000$。 输出格式 对于每个测试用例，输出一行答案。如果 AksLolCoding 能够获胜，输出 “YES”（不带引号）；否则，输出 “NO”。 输出不区分...

L1-111 大幂数 如果一个正整数可以表示为从 $1$ 开始的连续自然数的非 $0$ 幂次和，就称之为“大幂数”。例如 $2025$ 就是一个大幂数，因为 $$2025 = 1^3 + 2^3 + 3^3 + 4^3 + 5^3 + 6^3 + 7^3 + 8^3 + 9^3$$ 本题请你判断一个给定的数字 $n$ 是否是大幂数；如果是，就输出其幂次和。 另一方面，大幂数的幂次和表示可能不是唯一的，例如 $91$ 可以表示为 $$91 = 1^1 + 2^1 + 3^1 + 4^1 + 5^1 + 6^1 + 7^1 + 8^1 + 9^1 + 10^1 + 11^1 + 12^1 + 13^1$$ 同时也可以表示为 $$91 = 1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 6^2$$ 这时你只需要输出幂次最大的那个和即可。 输入格式 输入在一行中给出一个正整数 $n$，满足： $$2 < n < 2^{31}$$ 输出格式 如果 $n$ 是大幂数，则在一行中输出幂次最大的那个和，格式为： 1^k+2^k+...+m^k 其中 $k$ 是所有幂次和中最大的幂次。 如果解不存在，则在一行中输出： Impossible for n. 其中 n 是输入的 $n$ 的值。 题面解读 一个正整数，分解成从1开始连续数字的幂次方之和，要求幂最大。 解题思路 先看最大长度，如果幂全部都是1的情况，n=1+2+…+m，等差数列求和m最大不超过$\sqrt(n)$也就是$2^{16}$。再看幂最大是多少，如果只有一个数的话，也就是n=$2^p$幂最大也就是31，保守点可以枚举到32。这样就可以通过暴力枚举来A这道题，最高次复杂度大约是32*$2^{16}$就可以做出来。 题解代码...

L2-002 链表去重（分数 25） 给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉，即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21->-15->-15->-7->15，你需要输出去重后的链表 21->-15->-7，还有被删除的链表 -15->15。 输入格式： 输入在第一行给出 L 的第一个结点的地址和一个正整数 N（<= 10^5，为结点总数）。一个结点的地址是非负的 5 位整数，空地址 NULL 用 -1 表示。 随后 N 行，每行按以下格式描述一个结点： 地址 键值 下一个结点 其中 地址 是该结点的地址，键值 是绝对值不超过 10^4 的整数，下一个结点 是下个结点的地址。 输出格式： 首先输出去重后的链表，然后输出被删除的链表。每个结点占一行，按输入的格式输出。 题面解读 不按顺序给出一个链表，第一行输出删除重复元素后的链表，第二行输出删除的元素组成的新链表 解题思路 维护两个数组，nxt[]和val[]分别记录一个节点...

原题链接 A 题解： 对四则运算依次判断，除法需要多判断一下是否可以整除。 #include <bits/stdc++.h>using namespace std;int a, b, c;bool f = false;int main(){ cin >> a >> b >> c; if (a + b == c) f = true; else if (a - b == c) f = true; else if (a * b == c) f = true; else if (a % b == 0 && a / b == c) f = true; if (f) cout << "YES" << endl; else cout << "NO" << endl;} B 题解： 对于每一个需要判断的区间，利用函数判断其合法性。模拟题目，考验代码基本功。 #include <bits/stdc++.h>usi...