Doraemon's Blog

整数分块可以以log(n)的时间复杂度内求出${\sum_{i=1}^n\lfloor n/i \rfloor}$ 小G的约数 解法单纯求F(n)O(n)求出，现在求$\sum{i=1}^nF_i$，可以换种思路，从个体对整体的贡献下手，对于每一个约数求有这个约数的所有数数量，显然是n/i个，然后乘上i，那么问题就转化为了${\sum{i=1}^n\lfloor n/i \rfloor*i}$，很明显的整数分块模板，什么是整数分块，考虑n=10的时候n/i的表 i: 1 2 3 4 5 6 7 8 9 10 n/i: 10 5 3 2 2 1 1 1 1 1 发现数字呈从大到小块状分布，只要知道了一个块的左端和右端就能直接算出这个块的n/i的和，这里有一个结论：$N/i==N/i’时，i’的最大值：N/(N/i)$,i’也就是右端点，因此可以枚举每一段区间，n/i的所有数字中不同数字的数量不会超过2*sqrt(n)个，因此时复就是sqrt(n) 整数分块函数123456789ll get(ll x){ ll ret=0; for(ll i=1;i<=x; ...

bitset用途这个东西相当于一个bool数组，int是32位表示一个数，而这个32位表示32个数，每一位只能存1或者0，这就使得可以开的空间是int的32倍，时间复杂度为（位数）N/W(计算机常数一般为32)，而访问其中某一位时间复杂度为O(1)，这个的用处多用于数组开不下1e9以上的空间，用unordered_map插入时复O(logn)级别，就可以用bitset优化时间为O(1) 定义与初始化使用bitset类型需#include<bitset> bitset类型在定义时就需要指定所占的空间，例如 1bitset<233>bit; bitset类型可以用string和整数初始化（整数转化成对应的二进制） 123456789101112#include<iostream>#include<bitset>#include<cstring>using namespace std;int main(){ bitset<23>bit (string("11101001")); ...

P1197 [JSOI2008]星球大战 题意n个星球，m条边，k此摧毁，每次都会摧毁一个星球，摧毁一次求一次联通块，没摧毁时也要输出一次 解法求联通块有两种方法 利用dfs或者bfs从每一个点出发，把能到达的点都标记，每一个点都走一次，时间复杂度为O(n)， 使用并查集，单独n个点联通块就是n个，当两个点连接起来并且这两个点分别属于两个不同的联通块时，把他们合并成一个集合，联通块数量-1，时间复杂度差不多等于边的数量，>O(m) 如果只是求一次联通块的数量显然第一种方法更优，但是这道题每少一个点就要求一次联通块，如果用第一种方法时复O(kn)，这道题会超时，这时如果用并查集正着来做，时复O(mk)，也会超时，但是换一种思路，这道题要摧毁星球，我们倒着来，修建星球，每修建一个求一次联通块，而这时并查集时复就是常数级别O(max(m,k))，每修建一个多了一个点，联通块+1，看看和这个点相连的点是否属于一个集合，属于就-1，一个pair存点，再用链式前向星存一下图 CODE12345678910111213141516171819202122232425262728293031 ...

种类并查集可以解决多种关系的问题，比如两个人不是朋友的关系，其思想是多开几倍的空间，假如有n种关系，就开n倍的空间，然后用+n来表示两个不同集合的关系 食物链P2024链接：https://www.luogu.com.cn/problem/P2024 开3倍空间维护3个集合，分别表示A、B、C，例如1和2是朋友，那就把3个集合中的1和2合并，1吃2，就把A集合中1和B集合中的2合并，B集合中的1和C集合的2合并，C集合的1和A集合的2合并，再来一个2吃3，这样一来C中的3和A中的1也在一个集合里了，维护了C吃A的关系，也就是如果Ai和Bj的祖先相同就表示Ai吃Bj，另外两个同理 CODE12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include <bits/stdc++.h>#define debug freopen("in.txt","r",stdin); freopen("out.txt" ...

题目链接 题目描述 题目大意：有n种不同数量的细胞，每一个细胞每一秒都会分裂出一个新的，现在要把某一种细胞平均分到m1^m2^个容器里面，问选一种细胞，使得等待的时间最短，如果无法均分到容器中，就输出-1 做法要均分就表示Si^t^%m1^m2^==0求t的最小值，看一下数据范围发现m1比较小，而Si很大，分别对Si和m1分解质因子，只要m1中的每一个质因子Si中都有，那么Si就可以通过分裂均分到m1^m2^中，因此不需要把Si的所有质因子都找到，只需要找到小于等于m1的所有质因子即可，因此时间复杂度就是n*3e3就是3e7，对于m1和Si共有的质因子需要满足pi*t>=pm1*m2，要让满足条件的t最小就是取所有共有质因子的最大比值，然后所有比值中取最小 CODE12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include <bits/stdc++.h>#defi ...

B 二进制题目链接: https://ac.nowcoder.com/acm/contest/8564/B 单纯与或者单纯或单纯异或都支持交换律，但是他们放在一起就不支持交换律了，比如1先和0与再和1或结果是1，但是1先和1或再和0与结果就不一样，可以设两个数，一个所有位都是0，一个所有位都是1，把这两个分别进行上述操作，最后得出来的结果按位对比，如果0变成了1且1变成了0则这个位肯定是异或1，如果0变成0且1变成0则这一位是与0，如果0变成1且1变成1这一位肯定是或1，按照这个规律可以求出这个数，任何一个数与1或0异或0都不变，所以可以设置三个数，一个全设为1，另外两个全设为0，当这个位是与0时，就用全为1的变量减去(1<<i)这一位上的数，另外两个同理 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include <bits/stdc++.h>#define debug freopen("in.txt",& ...

凸包（百度百科）: 讲解凸包之前先讲解一下极角排序、叉积 叉积就是数学上的叉乘，两个向量叉乘，有正有负，相乘的两个向量前后顺序颠倒符号相反，乘出来的的结果也是一个向量，值等于以这两个向量作为平行四边形的两条边长的面积，方向指向与两个向量垂直的方向，右手定则，拇指指向x轴弯向y轴大拇指指向方向就是叉积的方向 数学上叉积非常重要，利用它可以计算出来不规则图形的面积，只需要知道不规则图形的顶点坐标。 利用叉积求多边形面积 两个向量的叉积值等于以这两个向量作边的平行四边形的面积 求多边形面积，就可以把多边形分解成许多三角形，求各个三角形面积加起来即可，从原点到各个点做向量，逆时针或者顺时针依次作叉积/2求和即可，顺时针和逆时针求出来的叉积方向不同，正负不同逆时针为正，顺时针为负 例题：HDU2036 123456789101112131415161718192021222324252627282930313233>#include <bits/stdc++.h>>#define debug freopen("in.txt","r&q ...

A. Cards for Friends给一个宽度和一个长度的蛋糕，只有为长或宽为偶数时才能切一刀数量乘以2，问给定尺寸的蛋糕能否分够k块。 分别对宽和长除2，只要是偶数就除，看看能除几次，得到两个次数相乘就是能分的最大数量，和k比较一下 123456789101112131415161718192021222324252627282930313233#include <bits/stdc++.h>#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)using namespace std;typedef long long ll;const int SUP=0x800000;const int MAXN=1e5;const int INF=0x3f3f3f3f;const double eps=1e-4;int num[MAXN];int main(){ ios; int t; cin>>t; while(t--){ int w,h,k; cin>>w> ...

朴素版的线段树只能实现单点修改区间查询，修改和查询的时间复杂度都是O(logn) 懒标记问题加上懒标记后的线段树就可以实现区间修改了，比如我要把[a,b]的值加上k，肯定不会傻到n次单点修改，是个人都会想到假如递归到一个包含在[a,b]的区间时就不用继续往下递归了，直接告诉这个区间的管理员，把这个区间的和直接给修改了，但是假如你上面第一次增加时增加区间为[c,d]，并且区间[c,d]是包含在[a,b]中间的，现在又要在[e,d]增加k，e>c的，这个时候你就会发现[e,d]这个区间增加了两次，因为第一次增加时你根本没有递归到[e,d]，而是递归到这个区间的上一层就直接返回了，现在你再在[e,d]区间增加值就会出错，因为少加了第一次的增值，所以应该找一个东西记录下来第一次增值，并且把他带到下面去，这时懒标记就出来了，新开一个数组lazy[i]，表示编号为i的区间的累计增值，那么第一次修改[c,d]时，lazyu\就会记录下来增值，lazy[u]+=c，第二次修改经过这个已经修改过的区间时，就要顺带着把这个区间的修改值一起带过去，正所谓父亲欠下的债儿子去偿还，当修改[e,d]时，经过 ...

2020年度总结 转眼间已是2021，想一想我的大学生活已经过去将近一半，真是快呀！总结一下我的2020年叭~ 成就 ACM 天梯赛(铜奖) CCPC省赛银奖 CET 成绩还没出，不过感觉是考的不错 体测 79，已经非常满意了，只要过了75就满足了~ 学业 比较满足了，相比于上学期确实进步了好多，可能是因为新图书馆建好了的缘故叭~ 想说的话寒假​ 2020年寒假在家，对视频剪辑，PS，特效制作兴趣比较大，就学了十多天吧，当时还去淘宝上买了好几个教学视频呢，现在都还在百度网盘存着，就是做特效的时候才发现AE对电脑的配置需求太大了！5千多的电脑根本带不起来…CPU在燃烧🔥~最后也是做出来了一个爱情公寓版的开头片，个人感觉还是不错的，做了两天呢！遗憾的是最后失误把源文件了导致图片链接不上了，最后也是啥也没做成，现在也忘了软件咋用了。 接触Hexo​ 从过年开始疫情就开始了，过年的那两天啥也没干，亲戚也不敢串，都窝在家里，当时一整天有半天多都是躺在被窝里玩游戏或者看爱情公寓5，好慵懒😶~然后就是因为疫情一直没有开学，从2月底开始上网课，记得刚听说要上网课 ...