hsl-beat的blog

这是绿？？？ 首先不难发现，对于所有点集，我们都可以找到一个确定的点满足是这 kkk 个点的 LCA，并且这 kkk 个点满足在这个 LCA 的不同儿子的子树里，且深度相同。 发现 nnn 和 kkk 小的可怜，于是我们考虑动态规划，每次确定 LCA 和一个深度，令 dpi,jdp_{i,j}dpi,j​ 为前 iii 个子树中有 jjj 个子树里放了点的答案，对于第 iii 个儿子的就是 dpi,j=dpi−1,j+dpi−1,j−1×cnti,ddp_{i,j} = dp_{i - 1,j}+dp_{i-1,j-1}\times cnt_{i,d}dpi,j​=dpi−1,j​+dpi−1,j−1​×cnti,d​，这里 cnti,dcnt_{i,d}cnti,d​ 意思就是以 iii 为根节点的时候深度为 ddd 的点个数，这里需要预处理，ddd 是我们前面确定的一个深度。 然后做完了。 小心常数太大会...

当成有权树做了一整天都没想出来（ 首先需要注意到，存在边 (i,j)(i,j)(i,j) 当且仅当 di,j=1d_{i,j} = 1di,j​=1。 可以想一想我们怎么样可以不重不漏找到所有边，显然就是隔一个点问一个，这样把所有满足条件的 di,jd_{i,j}di,j​ 都可以算作一个答案，一定不重复也不会遗漏。然后你发现树其实就是个二分图，黑点和白点个数肯定有一个小于 n2\frac{n}{2}2n​，然后这题做完了，找到点数更小的一个颜色查询就做完啦。 #include<bits/stdc++.h> using namespace std; #define int long long int n; vector<int> ask(int x) { cout << "? " << x << '\n'; cout.flush(); vector<int> d(n + 1); for (int i = 1; i <= n;...

前情提要：我的一位巨佬朋友自从学会珂朵莉树之后每天满脑子都是珂朵莉，看到什么问题就先想到珂朵莉，于是我也来学一学。 由于是自己在oiwiki上抄板子会的，所以代码有大量的相似，这篇文章讲的也很烂所以看看就好不要喷我 概述 珂朵莉树的思路其实很简单，就是维护一段段权值相同的段，这里用 set 实现。 split 既然是维护值相同的段，我们就要支持把一个段拆分开方便操作。假如我们要把包含 xxx 位置的区间 [l,r][l,r][l,r] 拆成 [l,x][l, x][l,x] 和 [x+1,r][x + 1, r][x+1,r]，可以直接 二分出位置然后直接用 set 的特性分割就好了。 123456789101112set<node>::iterator split(int x) // 分割包含位置x的区间，然后返回分割后右侧区间的迭代器{ auto it = chtholly.lower_bound(node(x)); if (it != chtholly.end() && x == it -> l) {...

日常写水题题解。 首先发现我们的魔力值是一条条斜率为 111 一次函数。 对于第 iii 个怪物，不难发现 ki−hi+1k_i - h_i + 1ki​−hi​+1 时刻的时候 xxx 至少要是 111，我们记录这个时刻为 pip_ipi​。 做法就很显然了，我们从后往前遍历，每次维护当前对应魔力值直线对应的段末尾和开头的时间，如果当前怪物不在它后面这一段的开头时间之后，那就直接更新答案。否则就更新最早的开头时间就好。 感觉口胡的很乱，还是看代码。 12345678910111213141516171819202122232425262728293031323334353637#include<bits/stdc++.h>using namespace std;#define int long longvoid solve(){ int n; cin >> n; vector<int> h(n), k(n); for (int i = 0; i < n; i++) { cin...

首先发现需要查询的字符串长度也就到 101810^{18}1018，大概九十多次操作就超过这个长度了。 所以我们考虑把查询改为从开头到当前位置的该字符个数，然后用前缀和来维护 SiS_iSi​ 中对于每个小写字母的出现次数。 具体来说就是我们可以递归查询答案，每次看一下查询的位置和对应的 SiS_iSi​ 的长度关系，如果发现当前的位置超过了字符串的长度就直接返回前缀和数组存储的东西，否则我们先把前一个 Si−1S_{i - 1}Si−1​ 里面的字符数量加上，然后递归到前一个字符串查找超出的部分就好了。 虽然是绿，但是场上写了一万年。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include<bits/stdc++.h>using namespace std;#define int long longsigned main(){ string s, t; ...

DAY0 三月七号我不是要去pixiv看三月七的吗 怎么突然让我到酒店了 怎么还有旅游团 DAY1 导游呢，导游怎么把我们送到学校参观了，怎么还要坐牢。 第一题期望不会。 第二题在草稿纸乱算 1h 以为想出正解了，笑点解析：写完代码发现字典序不是长度短的字典序就小，这个时候我打算去找监考老师理论。 小魔卡是谁。 第三题“奇异的”性质有啥用啊，它除了中间三个 1 不会发生运算还能咋样。然后其实晚上回酒店学长讲完我才知道自己适合退役。 笑点解析：坐牢5h打了三四十分。 笑点解析：T1那 8 分没拿，室友拿了，但是不小心输出了 1。 没事我还年轻喵喵喵我还有好几年 晚上邀请室友来床上打abc，没邀请室友报名比赛却遭到了大量学长入侵房间。 然后随便看了看学过的板子很早睡觉了，但是焦作迎宾馆自助餐咖啡机免费使用，实际睡觉时间严格大于 0 点，其实是因为给学长室友配梯子。 DAY2 我不是来焦作旅游的吗怎么又让我去学校机房参观学习。 第一题是什么呢。 笑点解析： 选手不需要，也不应该实现 main 函数。 我不是学 oi 的吗，怎么让我写 main 函数呢。 我不是学 oi...

赛时怎么忘记看了 这道题题意很明确，就是求最大独立集。对于 a=b=1a=b=1a=b=1 的情况大佬们肯定都会（不会求的自行学习二分图），所以我们可以根据 aaa 和 bbb 的奇偶性按照某种策略给棋盘黑白染色，满足能够一步之内相互到达的点颜色不同就可以。 首先 aaa 和 bbb 一奇一偶的情况是最简单的，由于走完之后横纵坐标之和的奇偶性会改变，直接把棋盘黑白交替染色就可以。 第二个是 aaa 和 bbb 都是奇数的情况，这个时候可以按照行或者列的奇偶性染色，因为横坐标和纵坐标的奇偶性会改变。 最后一个是 aaa 和 bbb 都是偶数的情况。我们想一想怎么把情况转化成上面两种，不难想到可以把 aaa 和 bbb 每次都同时除掉 222，但这个时候我们把棋盘变小了，横纵坐标也要同时除 222 才能保证原来的位置关系，然后你会发现就做完了。 剩下的上一个 dinic...

这题好像根本不难。 假如我们对于一个数确定了它模 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...