hsl-beat的blog

洛谷全站推荐 坏了，比赛当天上午我网络流的算法笔记刚过审，晚上就用上了。（忽略这一篇文章发布的日期） 这道题当然可以树形 dp，但很难构造边。 我们可以把点按照深度的奇偶性分开，这样就是一个二分图。 对于一个节点，它在三个颜色的情况下连的边会被删多少次是可以算出来的，所以在这个新图中每个点都对应了三个点，分贝是三个颜色，我们记点 iii 的第 jjj 个颜色的次数为 ai,ja_{i,j}ai,j​。 那么就常规网络流操作，我们建立超级源汇点，源点向深度为奇数的点都连这个点对应的 ai,ja_{i,j}ai,j​，汇点同理。然后对于树上的每一条边，我们都把这条边连接的两个点任意两个不一样的颜色连边，也就是说每个树上的边会带来 666 条边。 这个时候跑最大流，那么要是最大流不是 n−1n - 1n−1...

上一场没写因为实在太唐了，但这场挺难的，rating给我 ±0\pm 0±0 就很尴尬，差两分上蓝。 题目 题目评级 A.Feet 题目描述 111 英尺是 121212 英寸。 AAA 英尺 BBB 英寸等于多少英寸？ 思路 语法题 代码 12345678910#include<bits/stdc++.h>using namespace std;#define int long longsigned main(){ int a, b; cin >> a >> b; cout << a * 12 + b; return 0;} B.Tombola 题目描述 有一个行数为 HHH 列数为 WWW 的网格。每个方格上都写有一个整数，这些整数是不同的。从上面起第 iii 行，从左边起第 jjj 列的方格上写着整数 Ai,jA_{i,j}Ai,j​ 。 现在，主持人喊出了 NNN 个不同的整数 B1,…,BNB_1, \dots, B_NB1​,…,BN​...

又是一个水蓝题 好像不难 为什么我不会 首先要注意到aaa想要有答案必须满足这样的条件： 0≤ai+1−ai≤20 \leq a_{i + 1} - a_i \leq 2 0≤ai+1​−ai​≤2 0≤ai+1−ai0 \leq a_{i + 1} - a_i0≤ai+1​−ai​ 是因为每一个小于等于 iii 的数肯定小于等于 i+1i + 1i+1 。 ai+1−ai≤2a_{i + 1} - a_i \leq 2ai+1​−ai​≤2 是因为在 111 到 iii 中大于 iii 且小于等于 i+1i + 1i+1 的数只可能有一个（也就是 i+1i + 1i+1 ）然后你再把一个小于 i+1i + 1i+1 的数放在 i+1i + 1i+1 这个位置，差值就达到了最大的 222 。 那对于从 111 到 n−1n - 1n−1 的每个iii我们来分别讨论三种情况： ai+1−ai=0a_{i + 1} - a_i = 0ai+1​−ai​=0 ：在i+1i + 1i+1这个位置放入了一个比i+1i + 1i+1大的数，答案不变。 ai+1−ai=1a_{i +...

洛谷链接 首先对于排列 ppp ，有一个逆序对的条件就是存在一个位置 iii 满足 pi>pi+1p_i > p_{i + 1}pi​>pi+1​ ，其他相邻元素都是递增的。 我们可以对于每个 iii 把 iii 与 pip_ipi​ 连一条无向边，最终会形成一个个环。我们只需要把这些环内部归位再进行一次操作就可以让 ppp 满足条件。对于一个环，它对答案的贡献就是它内部的点数 −1-1−1 。 对于环我们可以用并查集维护，算答案的时候可以让答案初始化为 nnn ，然后每次遇到一个环就把答案减一。 注意我们要是发现相邻两个元素在同一个环里，那么我们可以在复原环的时就省一步让 ppp 满足条件，要特判。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include<bits/stdc++.h>using namespace std;#define int long...

题目 A.Triangular Number 题目描述 你得到一个正整数 NNN 。 输出从 111 到 NNN 的所有整数的和，即 1+2+⋯+N1+2+\cdots+N1+2+⋯+N 。 思路 语法题 代码 1234567891011#include<bits/stdc++.h>#define int long longusing namespace std;signed main(){ int n; cin >> n; cout << n * (n + 1) / 2; return 0;} B.No-Divisible Range 题目描述 给定一个长度为 NNN 的正整数序列 A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N)A=(A1​,A2​,…,AN​) 。 求满足 1≤l≤r≤N1\leq l\leq r\leq N1≤l≤r≤N 的整数 (l,r)(l,r)(l,r) 对满足下列条件的个数： 对于每一个满足 l≤i≤rl\leq i\leq rl≤i≤r 的整数...

又是个蓝莫反水题 首先发现对于位置(x,y)(x,y)(x,y)，中间遮挡的点就是gcd⁡(x,y)−1\gcd(x, y) - 1gcd(x,y)−1个，那么题目就是求： ∑i=1n∑j=1m2×(gcd⁡(i,j)−1)+1\sum_{i = 1}^n \sum_{j = 1}^m 2 \times (\gcd(i, j) - 1) + 1 i=1∑n​j=1∑m​2×(gcd(i,j)−1)+1 我们令f(x)=2×(x−1)+1=2x−1f(x) = 2 \times (x - 1) + 1 = 2x - 1f(x)=2×(x−1)+1=2x−1，那么就是求： ∑i=1n∑j=1mf(gcd⁡(i,j))\sum_{i = 1}^n \sum_{j = 1}^m f(\gcd(i,j)) i=1∑n​j=1∑m​f(gcd(i,j)) 然后就是套路了，假设n≤mn \leq mn≤m： =∑i=1n∑j=1m∑d∣gcd⁡(i,j)g(d)= \sum_{i = 1}^n \sum_{j = 1}^m \sum_{d | \gcd(i,...

感谢@Cute_SilverWolf为这篇文章作出的贡献。 写这篇文章是因为这四节课题目看似很少，内容是真多。在几个月前我就复习过一次这俩东西但是没写笔记现在又忘完了，于是趁自己有时间复习提高组就赶紧写了。 数论部分 整除 对于两个整数aaa，bbb，存在两个唯一的整数qqq，rrr满足： b=aq+r(0≤r≤∣a∣)b = aq + r \left ( 0 \leq r \leq \left | a \right | \right ) b=aq+r(0≤r≤∣a∣) 当r=0r=0r=0，我们就说aaa整除bbb，记作a∣ba | ba∣b。 整除的基本性质 a∣c,b∣c,(a,b)=1⇒ab∣ca|c, b|c, \left ( a, b \right ) = 1 \Rightarrow ab|ca∣c,b∣c,(a,b)=1⇒ab∣c a∣bc,(a,b)=1⇒a∣ca|bc, \left ( a, b \right ) = 1 \Rightarrow a|ca∣bc,(a,b)=1⇒a∣c p∣ab⇒p∣ap|ab \Rightarrow...

题目 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)，请你告诉...