hsl-beat的blog

这题好像根本不难。 假如我们对于一个数确定了它模 nnn 的余数 iii，和它的最后一位 jjj，那么这个数的长度一定越短越好。 所以我们可以考虑记录每个状态 (i,j)(i, j)(i,j) 可以到达的最短长度，一个一个数字的往后面拼，假如我们拼数字 kkk，那么 ((i×10+k)%n,k)((i \times 10 + k) \% n, k)((i×10+k)%n,k) 这个状态的步数就是 (i,j)(i, j)(i,j) 的步数加 111。 那直接 BFS 这题就做完了，因为每一次我们可以在扩展的时候拼尽量小的数，所以找到的第一个模 nnn 余数位 000 的状态就是我们想要的答案，我们可以记录每一个状态的前一个状态，一个一个回溯回去就可以得到答案啦。 123456789101112131415161718192021222324252627282930313233343536373839404142#include<bits/stdc++.h>using namespace std;#define int long longint...

题意 nnn 只猫娘，每只猫娘每天要么自己举行了排队，要么会追随自己最好的朋友去参加她要去的派对。 举办的派对有 333 种类型，在每一天晚上都会有一只猫娘举办了某种类型的派对，这只猫娘会一直举行下去直到自己换类型，问每天晚上这三种类型的派对都几只猫娘参加。 思路 首先把猫 iii 与自己的朋友连一条有向边，那么整张图就是一个内向基环树。每当一只猫娘举行了派对，这个结点相当于把自己和父亲结点的连边断开了，我们就需要统计每个举办派对的结点子树大小。 如果我们直接对着每一天的修改一个一个做，那么要处理分裂的问题，也能做但是不是很好写，所以我们考虑倒着做。 具体来说，每一天把当前猫娘举办的派对的答案回溯到这只猫娘举办的上一个派对那里（因为这只猫娘从上一个派对到举行当前派对这段时间一直都没变），但是如果这是这只猫娘举办的第一个派对了，那么来她排队里的猫娘和她自己都会跟随她的父亲结点，相当于连上了一条边，可以直接用 dsu...

反正是复习，我长话短说只写这玩意重点了. CRT 题目 给定 nnn 组非负整数 mi,aim_i, a_imi​,ai​ ，求解关于 xxx 的方程组的最小非负整数解。 {x≡a1(modm1)x≡a2(modm2)…x≡an(modmn)\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \dots \\ x \equiv a_n \pmod{m_n} \end{cases} ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​x≡a1​(modm1​)x≡a2​(modm2​)…x≡an​(modmn​)​ 对于 100%100 \%100% 的数据，1≤n≤1051 \le n \le {10}^51≤n≤105，1≤mi≤10121 \le m_i \le {10}^{12}1≤mi​≤1012，0≤ai≤10120\leq a_i \leq 10^{12}0≤ai​≤1012，保证所有 mim_imi​ 的最小公倍数不超过 1018{10}^{18}1018，保证 mmm...

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

洛谷全站推荐 坏了，比赛当天上午我网络流的算法笔记刚过审，晚上就用上了。（忽略这一篇文章发布的日期） 这道题当然可以树形 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,...