hsl-beat的blog

感谢@Cute_SilverWolf为这篇题解作出的贡献。 有关最小生成树的问题有很多，像是今年S组T2。每次用kruskal写出一道题，就总是觉得kruskal的题其实都很简单，但是场上我就是写不出来它的简单结论。 ——Hsl_Beat在写这篇文章时对SW说的感叹 题目描述 现有一张 nnn 个点，mmm 条边的无向连通图，边带权。对于每个 i(1≤i≤m)i(1 \le i \le m)i(1≤i≤m)，求出如果一个最小生成树中要求必须包括第 iii 条边，最小生成树的边权总和最小值。 1≤n≤2×1051 \le n \le 2 \times 10^51≤n≤2×105，n−1≤m≤2×105n-1 \le m\le 2 \times 10^5n−1≤m≤2×105，1≤ui,vi≤n1 \le u_i,v_i \le n1≤ui​,vi​≤n，ui≠viu_i \neq v_iui​=vi​，1≤wi≤1091 \le w_i \le 10^91≤wi​≤109。 ...

感谢@Cute_SilverWolf为这篇文章作出的贡献 单调栈部分 求下一个最大数 题目描述 给你nnn个整数a1,a2,…,ana_1, a_2, \dots ,a_na1​,a2​,…,an​,请问从每个数字往后看，第一个比它大的数字下标是多少？如果后面没有比它大的数字，输出0。 1≤n≤2×1051 \leq n \leq 2 \times 10 ^ 51≤n≤2×105 思路 直接暴力显然不可行 下面引入单调栈的思想，我们维护一个栈，然后从后往前遍历数组，每次我们要做这么几件事： 不断把栈顶小于它的元素弹出，直到栈顶元素对应的数大于当前的数或栈为空。我们知道从这个元素之后遍历的元素肯定不会再看到那些被弹出的元素，因为肯定优先看到当前的元素。 此时栈顶就是要求的答案，如果栈为空就表示后面没有比它大的数字。 把当前数字的下标插入栈。 这就是单调栈的思想，时间复杂度为O(N)O \left ( N \right )O(N) ...

题目 A - Permute to Maximize 题目描述 给你介于 111 和 999 之间的三个数字 A,B,CA,B,CA,B,C 。 求将 A,B,CA,B,CA,B,C 按任意顺序排列并连接而成的所有 333 个整数中的最大值。 思路 语法题 代码 12345678910111213141516171819#include<bits/stdc++.h>#define int long longusing namespace std;signed main(){ string s; cin >> s; sort(s.begin(), s.end()); if (s[0] == '0') { for (int i = 1; i < s.length(); i++) { if (s[i] != '0') { swap(s[0], s[i]); break; } } } ...

题目 题目评级 A < B < C < E < D <<< F <<<<<<<<<<<<<< G A.Robot Balance 题目描述 高桥可以将头部部件和身体部件组合成一个机器人。如果头部部件的重量大于身体部件的重量，机器人就会摔倒。 目前，他有一个头部部件和一个身体部件。头部的重量为 HHH 克，身体部分的重量为 BBB 克。 他想让身体部分更重一些，这样机器人就不会摔倒。求为了使机器人不倒下，身体部分需要再加重多少克？ 思路 语法题 代码 1234567891011#include<bits/stdc++.h>#define int long longusing namespace std;signed main(){ int a, b; cin >> a >> b; cout << max(a - b, 0ll); return 0;} B.Robot...

题目 题目评级 A.Too Many Requests 题目描述 给你正整数 NNN 和 MMM 。 打印 NNN 行。 如果是 i≤Mi\leq Mi≤M ，则 iii /th行 (1≤i≤N)(1\leq i\leq N)(1≤i≤N) 应包含 “OK”，否则应包含 “Too Many Requests”。 思路 语法题，所以就做完了 代码 123456789101112#include <bits/stdc++.h>using namespace std;#define int long longsigned main(){ int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { cout << (i <= m ? "OK" : "Too Many Requests") << '\n'; } return 0;} B.N - 1 题目描述 给你一个长度为 NNN ,...

F手写300行主席树 然后样例没过 还剩5min这一块 题目 题目评级 A.Grandma’s Footsteps 题目描述 高桥在学校里玩得很开心。下课铃一响，游戏就开始了。 铃声响起后，他立即重复以下动作： 以每秒 SSS 米的速度跑 AAA 秒。然后，保持静止 BBB 秒。 到下课铃响后 XXX 秒时，他总共跑了多少米？ 思路 小学奥数周期问题 所以就做完了 代码 1234567891011121314151617#include<bits/stdc++.h>using namespace std;#define int long longsigned main(){ int s, a, b, x; cin >> s >> a >> b >> x; int ans = 0; for (int i = 1; i <= x; i++) { int tp = i % (a + b); if (1 <= tp && tp...

题目 题目评级 A = B < C < E < F = D F虽说是折半搜索板子可以 但是卡常卡了707070min 555发才过的我 因为我们忘记把map换成unorderedmap A.ABC -> AC 题目描述 给你一个由大写英文字母组成的字符串 SSS 。这里， SSS 的长度是奇数。 打印删除 SSS 中间字符后得到的字符串。 SSS 的中间字符是 SSS 的 L+12\frac{L+1}{2}2L+1​ -th 字符，其中 LLL 是 SSS 的长度。 思路 语法题 所以就做完了 代码 1234567891011#include<bits/stdc++.h>using namespace std;#define int long longsigned main(){ string s; cin >> s; s.erase((s.length()) / 2, 1); cout << s; return 0;} B.Sum of Digits Sequence 题目描述 对于正整数...

题目让你求： ∑i=1nlcm⁡(i,n)\sum_{i = 1}^n \operatorname{lcm}(i, n) i=1∑n​lcm(i,n) 推式子： =∑i=1ni×ngcd⁡(i,n)= \sum_{i = 1}^n \frac{i \times n}{\gcd(i, n)} =i=1∑n​gcd(i,n)i×n​ =n∑i=1nigcd⁡(i,n)= n \sum_{i = 1}^n \frac{i}{\gcd(i, n)} =ni=1∑n​gcd(i,n)i​ =n∑d∣n∑i=1nid[gcd⁡(i,n)=d]= n \sum_{d | n} \sum_{i = 1}^{n} \frac{i}{d}[\gcd(i, n)=d] =nd∣n∑​i=1∑n​di​[gcd(i,n)=d] =n∑d∣n∑i=1n/di[gcd⁡(id,n)=d]= n \sum_{d | n} \sum_{i = 1}^{n/d} i[\gcd(id,...

不妨设n≤mn \leq mn≤m。 那原式： =∑i=1n(n mod i)×∑j=1m(m mod j)−∑i=1n(n mod i)×(m mod i)= \sum_{i = 1} ^ n (n \bmod i) \times \sum_{j = 1} ^ m (m \bmod j) - \sum_{i = 1} ^ n (n \bmod i) \times (m \bmod i) =i=1∑n​(nmodi)×j=1∑m​(mmodj)−i=1∑n​(nmodi)×(mmodi) =∑i=1n(n−⌊ni⌋×i)×∑j=1m(m−⌊mj⌋×j)−∑i=1n(n−⌊ni⌋×i)(m−⌊mi⌋×i) = \sum_{i = 1} ^ n (n - \left \lfloor \frac{n}{i} \right \rfloor \times i) \times \sum_{j = 1} ^ m (m - \left \lfloor \frac{m}{j} \right \rfloor \times j)-\sum_{i = 1} ^ n (n - \left...

在洛谷过审了：https://www.luogu.com.cn/article/tl32jtl5 首先不难发现： ANS=∑i=0n−1(i+1)×P(i)=∑i=0n−1P(x≥i)ANS = \sum_{i = 0}^{n - 1} (i + 1) \times P(i) = \sum_{i = 0}^{n - 1} P(x \geq i) ANS=i=0∑n−1​(i+1)×P(i)=i=0∑n−1​P(x≥i) 其中： P(x≥k)=B1×B2×⋯×Bk×k!S×(S−1)×…(S−k+1)P(x \geq k) = \frac{B_1 \times B_2 \times \dots \times B_k \times k!}{S \times (S - 1) \times \dots (S - k + 1)} P(x≥k)=S×(S−1)×…(S−k+1)B1​×B2​×⋯×Bk​×k!​ 这里，S=∑AiS=\sum A_iS=∑Ai​。 分母很好理解，就是总共的方案数，然后 BBB...