hsl-beat的blog

我们固定了 AAA 队中的人数之后一共会有三类人，分别是只能放 AAA 的，只能放 BBB 的，和 AAA 与 BBB 都能去的，这里可以用差分数组维护。（可以通过当前能去 AAA 队的人数推出 BBB 队的范围就是 n−rn - rn−r 到 n−ln - ln−l） 这个时候我们可以通过容斥原理先判断一下当前情况合不合法，然后就是能去两个队的用组合数分配就好啦。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include<bits/stdc++.h>using namespace std;#define int long longconst int mod = 998244353;int fact[222222], invf[222222];int fastpow(int a, int b){ int res = 1; ...

直接做肯定不好弄，考虑把每一位拆开算贡献。 首先第 iii 位的贡献取决于它的右边有多少个数没有被删掉。对于 iii，如果删掉的数都是左面的，那么贡献就是 (i−1)×i2×10n−i\displaystyle\frac{(i - 1) \times i}{2} \times 10^{n - i}2(i−1)×i​×10n−i，这个可以直接算。 如果删掉的数是右面的，需要考虑删去了多少个数的情况，假如当前数的贡献是 10k10^k10k，就一共有 k+1k + 1k+1 种删除办法，可以倒着循环一次然后累加。 于是这题就做完了。 123456789101112131415161718192021222324252627#include<bits/stdc++.h>using namespace std;#define int long longconst int mod = 1e9 + 7;signed main(){ string s; cin >> s; int n = s.length(); s = '...

我这一周都在写暴力。 根号分治 其实就是把两个暴力拼起来，只不过我们可以规定一个范围 BBB，使得这两种暴力都可以利用这个限制满足题目限制的时间。 AT_abc259_h [ABC259Ex]Yet Another Path Counting 题目描述 给你一个网格图，每个方格都有一个标签，每次从某个节点出发，每一步只能往右或往下，最终必须停在和起点标签相同的位置，问不同路径数量。 1≤N≤4001 \leq N \leq 4001≤N≤400。 思路 对于固定的标签我们可以对着整个网格图跑一个 dp 来算答案，也可以枚举起始点和结束点用组合数算答案，前者需要颜色的个数尽量小，后者需要网格次数尽量小。 所以我们可以按照出现次数分开处理颜色，如果按照出现次数与 BBB 的关系分开，总的时间复杂度就是 O(nB2+n4B)O(nB^2 + \displaystyle\frac{n^4}{B})O(nB2+Bn4​)，令 B=nB = nB=n 就可以得到 O(n3)O(n^3)O(n3) 的复杂度，这题就过了。 对于组合数和 dp 的过程都很简单，我就不写了。 ...

是不是比 F 难。 然后你们写数论分块干啥。 首先把式子里 AiA_iAi​ 提出来。 ∑i=1NAi∑j=1MBj×(i mod j)\displaystyle \sum_{i=1}^{N} A_i \sum_{j=1}^{M} B_j \times (i \bmod j) i=1∑N​Ai​j=1∑M​Bj​×(imodj) 注意到每次 iii 加上 111 之后式子右边的 $ \sum_{j=1}^{M} B_j \times (i \bmod j)$ 很容易可以通过上一个状态转移过来，具体来说就是 所有 i+1i + 1i+1 的因数 BiB_iBi​ 的贡献都会是 000，剩下的都会系数增加 111，又发现 NNN 很小，所以可以预处理每个 iii 的因数，两秒轻松能过，然后一个一个推每个 BiB_iBi​ 的贡献，具体实现可以看代码。 1234567891011121314151617181920212223242526272829303132333435363738394041#include<bits/stdc++.h>using...

这是绿？？？ 首先不难发现，对于所有点集，我们都可以找到一个确定的点满足是这 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...