布克波波

分类

题解(4)

/ 注册

全部文章（共4篇）

题解 | #欢迎来到辽宁省赛#

L 区间与绝对值用莫队先离线操作，用树状数组维护两个东西，一个是小于（大于）一个数的个数和小于（大于）一个数的和，那我们每次加入一个数时产生的贡献时（），删除一个数时时我们对应删除掉即可。我们这样只维护了一半，乘2即是答案。 #include <bits/stdc++.h> #d...

C++ 树状数组

2023-10-31

4 632

题解 | #The Number Of Black Edges#

C小红的子串直接考虑每一个位置作为左端点时对于答案的贡献，比如第对于从第位开始来说，在第L位置开始有了l个字母，第R+1位置时有了R+1个字母，则第个位置的贡献为 R-L+1。那么我们只要知道每一个位置后面的每一种字母最早在哪里出现即可。可以使用序列自动机进行维护。 for (int i = l...

C++ 字符串

2023-10-16

0 334

题解 | #The Number Of Black Edges#

从横向和纵向分别扫描，每一行或列记录1的长度，Y横向有两张长度，纵向有三种长度，E和S横纵不同长度都是2，但E的四个角上有1，而S没有，通过这个分辨出来E还是S即可 #include <bits/stdc++.h> #define int long&nb...

C++

2023-05-23

0 385

题解 | #小竹与妈妈#

用埃氏筛O(nlog(logn))求得1~5e6每个数的质因数个数,用并查集来维护连通块的大小，合并时判断两个数的最大公约数是否含有两个以上的质因数，如果是则合并，最后遍历所有位置，输出最大连通块大小即可。维护连通块不难，建图用dfs搜索也可以实现。困难的是想到可以用gcd的约数个数判断是否优雅，和...

C++ 数学深度优先搜索并查集

2022-11-28

0 443