Doraemon's Blog

__int128C++支持的最大数据类型就是longlong，再大就会爆掉，所以出现了_int128类型，默认gcc是不支持编译的，但是在各大OJ上是可以运行的，\_int128不支持cin、cout，所以需要自己写读入打印函数，也就是传统的快读快写 1234567891011121314151617181920212223242526272829303132#include<bits/stdc++.h> using namespace std; typedef unsigned long long ll; void read(__int128 &x){ int y=1;x=0; char c=getchar(); while(c<'0' || c>'9'){ if(c=='-') y=-1; c=getchar(); } while(c>='0' && c<='9'){ x= ...

Early Orders 题意n个数从中找出一个包含1-k的字典序最小子串，注意子串可以断开，但是相对顺序不能变 题解求得是字典序最小的子串，用一个单调栈维护，从栈底到栈顶依次表示子串的从前到后，为什么用栈呢？考虑子串的先后性，必须先把后面的更新了才能更新前面的，如何维护栈呢？对于栈顶元素，从左往右遍历的过程中如果这个数字比栈顶数字小，而且右面还有栈顶数字，那就可以出栈，还有就是当栈内有一个元素了，这时就不能再往里面塞这个元素，搞一个标记数组标记栈中是否有这个元素 CODE123456789101112131415161718192021222324252627282930313233#include <bits/stdc++.h>#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0) using namespace std;const int MAXN=1e6;stack<int> st;bool vis[MAXN];int ans[MAXN],a[MAXN],pos[MAXN];int mai ...

B 比武招亲（上） 题目大意给定n,m，每次从1-n中挑选出m个数，可以重复挑选，挑选出的数的贡献值等于排序后最大值减去最小值，挑选的序列不同当且仅当两个序列排序后不同，求所有可能的序列的总贡献值？ 解法可以枚举贡献值，差值一共有n-1种，差值固定了，也就是在m-2个空位中随意放置[min,max]的数，这里有一个坑，也不是随便放的，因为要求排过序后序列不同，也就是放置要求是单调不减，于是可以把+1看成一个隔板，就是在m-2+1个隔板中放置d(差值)个隔板，可是隔板可以连续放置，所以放置一个隔板后空位就会增多！所以答案不是C(m-1,d)，雨巨的想法NB，考虑每一个隔板的左面带有一个空位，那么所有的隔板放完后空位就增加到了m-1+d个，在这些空位中放进去d个隔板，这个时候隔板就不能连续放了，因为每一个隔板左面都带有一个空位，所以每一个隔板左面都必须至少有一个空位，那最左面也不能放了，所以空位变成了m-1+d-1，答案就变成了从m-2+d个空位中放置d个隔板，隔板不能连续放，C(m-2+d,d)，到这里题目就做出来一大半了，组合数复杂度为O(n)，这里的n和m都是1e5，所以每次都算一遍 ...

整数分块可以以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 ...