hsl-beat的blog

duel 到了这种题也是幸运，但是这题评测好慢。 如果不知道 ppp 序列是什么肯定没有做法，发现我们花掉 nnn 次的代价之后剩余的 303030 次一定是能把答案处理出来的，因为给我们返回的结果有单调性，mmm 也不超过 2302^{30}230。 因此只需要先求出 ppp，然后直接二分，同时根据 ppp 对应的说不说谎推出当前中间点的结果就好啦。 注意题目不能问大于 mmm 的数，所以找 ppp 的时候如果每次询问 mmm 拿到了一个 000 就直接退出就好了。 1234567891011121314151617181920212223242526272829303132333435363738#include<bits/stdc++.h>using namespace std;#define int long longint ask(int x){ cout << x << '\n'; cout.flush(); cin >> x; return...

书接上回 队友：豆包，2_16鸡扒拌面。 省流：我还是个铜。 赛时 hzm 上来给了我个 C 的错误思路，然后直接吃了三发。 我们怎么会觉得这题很难，然后 hzm 去看 I，豆包狂占着机子写 K。后来不知道过了多久 K 过了，我已经会了 C 和 L，但是 C 写完之后少了 n>mn > mn>m 的特判，hzm 最后告诉我了。 对于神秘 L 题，我照着书抄了丢番图方程的板子，结果充满恶臭的大样例始终差 222，改了半天也没改出来。后来豆包说他会 D 了，然后写一个神秘的按性价比贪心的构式代码过样例了，然后疯狂获得答案错误。 我等了十几年打印的 L 代码，但我不是列文虎克，没看出来哪里错了，就听他们在那里讨论 D，我越听越不对，寻思这不应该枚举剩余能量然后从前两个转移吗，怎么是性价比，然后把他们赶走就一发过了。 然后他们看 E，我继续调 L，但是用了一个多小时我们都没人做出来任何题，惨淡收场，最后拿铜。（什么傻福榜单，他们一直以为E简单，我就是没办法调 L），发现罚时少一点三题也是银，悲痛。 ...

发现每次移动都会改变奇偶性，所以说想要判断合不合法很容易，就是判断原本的图中每个连通块是不是二分图就好。这个时候对于一个颜色就全是 222，剩下的一个颜色都填 111 或者 333。 但是题目要求构造出答案，假设数字是 222 的颜色都为白色，那么就会出现一个问题：对于同一个连通块里，颜色为白色的可能会有两种取值。 这个时候会发现 nnn 非常小，于是我们可以跑一个背包 dp 来判断从 000 开始，在每个连通块里选一个点个数的取值，最后看能不能凑出 n2n_2n2​，顺便随手记一下上一个的状态。 构造的时候就从 n2n_2n2​ 往回跳，然后对于白色点就放 222，剩下的点都任意放 1,31,31,3...

好像很简单，为什么我不会。 首先考虑怎么 DP，记 dpi,0dp_{i,0}dpi,0​ 表示第 iii 个位置不是节假日，dpi,1dp_{i,1}dpi,1​ 表示是节假日。 那我们的转移也很容易： dpi,0=dpi−1,1dp_{i,0} = dp_{i - 1, 1} dpi,0​=dpi−1,1​ （如果连着两个都不是节假日，那么这两天就不可能通过在两个节假日之间变成节假日，不符合题意） dpi,1=min⁡(dpi−1,0,dpi−1,1)+Aidp_{i, 1} = \min(dp_{i - 1, 0}, dp_{i - 1, 1}) + A_i dpi,1​=min(dpi−1,0​,dpi−1,1​)+Ai​ 初始化就是区间往前一个位置的值了，按照定义就是 dpl−1,0=0dp_{l - 1, 0} = 0dpl−1,0​=0 和 dpl−1,1=Al−1dp_{l - 1, 1} = A_{l - 1}dpl−1,1​=Al−1​。由于 A0A_{0}A0​ 根本不存在，所以我们直接把它设置成...

这能评蓝？ 我们需要查询原数组里面有多少对数满足无法进位，首先把不到 777 位的数高位全部补上 000，假设这个数的第 kkk 位为 ai,ka_{i, k}ai,k​，那么满足条件的数 jjj 就必须满足所有的 kkk 都 aj,k≤9−ai,ka_{j, k} \leq 9 - a_{i, k}aj,k​≤9−ai,k​。于是这题就转化成了一个前缀和问题，但是有 777 维。 这里我选择了无脑写一个树状数组解决，时间复杂度 O(n×log⁡710)O(n \times \log^7 10)O(n×log710)，发现 atcoder 神机 444 秒轻轻松松就能过。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071#include<bits/stdc++.h>using namespace std;#define int long...

发现对于每个草地，假设距离和它最近的敌方牛距离为 ddd，那么想要拥有这块草地的话必须把点放在 (pi−d,pi+d)(p_i - d, p_i + d)(pi​−d,pi​+d) 这个开区间里。 下面是一个错误思路： 如果思考方向是往这些区间里放点，每次选择能给答案带来最大贡献的一段有效区间放一个点，是会挂掉的，因为可能不选最优的方法可以在更少点数把所有草场都选上，但是贪心的话可能选到了中间的区间导致无法覆盖所有的。 一个草场如果对应区间选了多次，也就只能算一次，这个方法的问题就在于可能忽略了这一点。但是样例是能过的。 我们考虑两个相邻敌方牛之间的所有草地，很容易发现我们最多放 222 个点就可以把这段区间里面所有的覆盖。 所以我们考虑如何往这几个敌方牛之间的区间放点最优，其实就是一个物品重量为 111 或 222...

做的最舒服的一道蓝题，在语文课上睡觉想出来了。 首先我们发现，假如我们在位置 iii，就表示 xjx_jxj​ 小于 iii 的虫洞必须都是开着的（因为都从它们经过了）。 所以为了避免重复计算，我们可以记录 ansians_{i}ansi​ 表示如果到达这个点的时候是开启的，（从 yiy_iyi​ 开始）下一次回到这个点要走多少步，那么借助我们前面说的所有点都是开启的，ansians_{i}ansi​ 应该就是 (xi−yi)(x_i - y_i)(xi​−yi​) 加上在 [yi,xi][y_i,x_i][yi​,xi​] 这段区间里所有点的 ansansans 值之和，这里可以用前缀和维护。 最后计算答案也很简单，每次找到一个开启的点，然后计算它和上一个出发点之间的距离加上之间所有点的 ansansans 值之和，然后更新出发点为当前点就好啦。 123456789101112131415161718192021222324252627282930313233343536373839#include<bits/stdc++.h>using namespace...

我们固定了 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 的过程都很简单，我就不写了。 ...