hsl-beat的blog

题目 A.Balloon Trip 题目描述 给定整数 WWW 和 BBB ，解决以下问题。 Takahashi的权重为 W[kg]W {\rm [kg]}W[kg] 。（注意单位为 kg{\rm kg}kg ） 一个带有 nnn 气球的物体，当且仅当该物体的质量严格小于 nBnBnB [g]{\rm [g]}[g] 时，才会飞向天空。 让高桥飞上天空最少需要多少个气球？ 思路 语法题 代码 12345678910#include<bits/stdc++.h>using namespace std;#define int long longsigned main(){ int x, y; cin >> x >> y; cout << 1000 * x / y + 1; return 0;} B.Bird Watching 题目描述 NNN 有 MMM 类的鸟在天空中飞翔。 鸟类类型编号为 1,2,…,M1,2,\dots,M1,2,…,M 。 NNN 鸟的编号为...

前言 队名：WA on Test 100! 队员：@litjohn @lucius1 @Hsl_beat day -1 中招甲乙流 在床上高烧一整天 脑子烧坏了 day 0 上午迎接了lucius1 但是天江老师还没有来 下午迎接了litjohn，开始打热身赛。 -30min：艰难找到在场上随机刷新ucup委员会的oier领取吧唧（jiangly很好找到，另一个Colin不好找，使用了场外援助） 0min：我开B题，lucius秒掉了A题，litjohn写出E却发现不知道出题人生日 30min：lucius想出B神秘结论却WA一发，我给出正确贪心后他写出了一大坨二分+预处理但是答案输出完全不对，我殚精竭虑帮他修好了，此时CD我们都不会却还不知道出题人生日 1h30min：我们发现大家都在用手机，使用电子设备和场外援助还是没有试出来出题人生日，这个时候学校的队友告诉我们出题人自己跑过去告诉他们生日在4月17日，然后就过了 1h50min：C我贡献了个疑似对的DP思路，但是转移差一步没推出来，D根本不会，导致只有3题 2h：我们学会了如何使用功能强大的Clion day...

感谢@Cute_SilverWolf为这篇题解作出的贡献。 我不管！我就要写DS！ ——第一眼看到这道题之后，Hsl_Beat的发言 这道题的倍增好写多了——至少是比今天凌晨写的代码源OJ-981的好写不少。 题目描述 这一次，Baby Ehab 只会剪纸而不会粘贴。他开始时有一张纸，上面写着一个长度为 nnn 的数组 aaa，然后他会进行如下操作： 他选择一个区间 (l,r)(l, r)(l,r)，将子段 al,al+1,…,ara_l, a_{l + 1}, \ldots, a_ral​,al+1​,…,ar​ 剪下来，移除数组的其他部分。 然后，他将这个区间再切分成若干个子区间。 为了增加一点数论的趣味，他要求每个子区间内所有元素的乘积必须等于它们的最小公倍数（LCM）。 形式化地说，他需要将 al,al+1,…,ara_l, a_{l + 1}, \ldots, a_ral​,al+1​,…,ar​ 划分为若干个连续的子数组，使得每个子数组的所有元素的乘积等于它们的最小公倍数。现在，对于 qqq 个独立的区间 (l,r)(l, r)(l,r)，请你告诉...

感谢@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 题目描述 对于正整数...