ZHLin_Blog

B https://ac.nowcoder.com/acm/contest/120561/B 假设小红手上所有牌中最小的为x，将小笨手上比x大和比x小的牌分为两部分，那么小笨手上所有比x大的牌都会被移除，移除的数量就是最高得分，因此答案就是两部分的全排列结果相乘。 12345678910111213141516171819202122232425262728293031323334353637383940#include <bits/stdc++.h>using namespace std;const int mod = 998244353;const int N = 2e5 + 10;typedef long long LL;int t, n;int a[N], b[N];LL fact[N];void f(){ fact[0] = 1; for (int i = 1; i < N; i++) fact[i] = (fact[i - 1] * i) % mod;}void sol(){ cin >> n; int m...

比赛链接 A 12345678910111213141516171819202122232425262728293031323334#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 >= ...

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

比赛链接 A 12345678910111213141516171819202122232425#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 12345678910111213141516171819202122232425262728293031#include <bits...

原题链接 B. 青蛙的诅咒 每次测试的时间限制：1 秒 每次测试的内存限制：256 兆字节 在一条无限数轴上，点 000 处坐着一只青蛙。经过多年的冥想，青蛙掌握了 nnn 种独特类型的魔法跳跃。第 iii 种跳跃允许它向前跳跃不超过 aia_iai​ 个单位。换句话说，如果它在整数点 kkk，跳跃后它可以落在从 kkk 到 k+aik + a_ik+ai​ 的任意整数点。 但是魔法总是有代价的；它被诅咒了。在第 iii 种跳跃的每第 bib_ibi​ 次尝试之前（即在使用第 iii 种跳跃的第 bib_ibi​ 次、第 2bi2b_i2bi​ 次、第 3bi3b_i3bi​ 次等尝试中），青蛙会向后退 cic_ici​ 个单位！换句话说，如果它在点 kkk，它首先会发现自己在点 k−cik - c_ik−ci​，跳跃之后，它可以落在从 k−cik - c_ik−ci​ 到 k−ci+aik - c_i + a_ik−ci​+ai​ 的任意整数点。 青蛙的目标是到达数字为 xxx 的点，同时使用跳跃并使回滚次数最少。帮助青蛙 —— 找到它在通往目标的路上必须忍受的最小回滚次数，或...

Problem - C - Codeforces CF2200C Specialty String - 洛谷 题目描述 AksLolCoding 正在玩一个关于字符串 sss 的游戏，字符串长度为 nnn。初始时，sss 只包含小写拉丁字母。 每一回合，AksLolCoding 可以选择一对整数 (i,j)(i, j)(i,j)，满足： 1≤i<j≤n1 \leq i < j \leq n1≤i<j≤n； si=sj≠∗s_i = s_j \neq *si​=sj​=∗； 对于所有 i<k<ji < k < ji<k<j，有 sk=∗s_k = *sk​=∗。 如果不存在这样的 i,ji,ji,j，则游戏结束。否则，AksLolCoding 令 si:=∗s_i := *si​:=∗ 且 sj:=∗s_j := *sj​:=∗。当游戏结束后，只有当 sss 的每一个字符都等于 ∗*∗ 时，AksLolCoding 才获胜。请判断是否存在一种操作方式，使得 AksLolCoding 能够获胜。 注意：∗*∗ 表示 ASCI...

L1-111 大幂数 如果一个正整数可以表示为从 111 开始的连续自然数的非 000 幂次和，就称之为“大幂数”。例如 202520252025 就是一个大幂数，因为 2025=13+23+33+43+53+63+73+83+932025 = 1^3 + 2^3 + 3^3 + 4^3 + 5^3 + 6^3 + 7^3 + 8^3 + 9^3 2025=13+23+33+43+53+63+73+83+93 本题请你判断一个给定的数字 nnn 是否是大幂数；如果是，就输出其幂次和。 另一方面，大幂数的幂次和表示可能不是唯一的，例如 919191 可以表示为 91=11+21+31+41+51+61+71+81+91+101+111+121+13191 = 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=11+21+31+41+51+61+71+81+91+101+111+121+131 同时也可以表示为 91=12+22+32+42+52+6291 = 1^2 ...

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[]分别记录一个节点...

原题链接 E小红的完全平方数构造 题面解读 E-小红的完全平方数构造_牛客周赛 Round 126 给定一个整数 nnn，要求你在 nnn 的后面追加至少 1 位数字，使得新的数字 n′n'n′ 成为一个完全平方数。 解题思路 参考题解 显然可以想到遍历后面加了几位。 对于添加了 位的情况，此时数字的范围为 ，不妨取第一个大于等于 的完全平方数，若其小于等于 ，则满足题意。 123456789101112131415161718192021222324252627282930313233343536373839#include <bits/stdc++.h>using namespace std;typedef long long ls;int t, n;ls find(ls x){ ls l = 1, r = 2e9 + 10; while (l < r) { ls mid = l + (r - l) / 2; if (mid * mid >= x) r = mid; else l = mid + 1;...

原题链接 A 题解： 对四则运算依次判断，除法需要多判断一下是否可以整除。 123456789101112131415#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 题解： 对于每一个需要判断的区间，利用函数判断其合法性。模拟题目，考验代码基本功。 123456789101...