字符串哈希
title: 字符串哈希categories: - ICPCtags: - nullabbrlink: ‘51e82117’date: 2023-09-18 00:00:00单哈希且用自然溢出代替取模操作，常数小但是容易被卡单字符串区间内比较，查询子串hash值typedef unsigned long long ULL; const int N = 100010, P = 131; int n, m; char str[N]; ULL h[N], p[N]; ULL get(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; } int main() { scanf("%d%d", &n, &m); scanf("%s", str + 1); p[0] = 1; for (int i = 1; i <= n; i ++ ) { h[i] =...
数论分块
title: 数论分块categories: - ICPCtags: - nullabbrlink: 4a670895date: 2023-09-14 00:00:00将O（n)优化成o（根号n） [CQOI2007] 余数求和题目描述给出正整数 $n$ 和 $k$，请计算 $$G(n, k) = \sum_{i = 1}^n k \bmod i$$ 对于 $100%$ 的数据，保证 $1 \leq n, k \leq 10^9$ void solve(){ int n,k;cin>>n>>k; int ans=n*k; //注意推导公式字母不要弄混 for(int l=1,r=1;l<=n;l=r+1){ if((k/l)==0)break;//注意特判分母为0的情况，不然会RE r=k/(k/l); r=min(n,r);//防止多算 //cerr<<l<<"...
牛客周赛ROUND38
title: 牛客周赛ROUND38categories: - ICPCtags: - nullabbrlink: 85e1eefddate: 2023-09-14 00:00:00#E题链接：https://ac.nowcoder.com/acm/contest/78292/E来源：牛客网 小苯非常喜欢等比数列。有一天他得到了一个长为 $n$ 的数组 $a$，他想从里面选一些数字使得被选中的数字构成一个等比数列，请问他最多可以选择多少个数字呢 输入包含两行。第一行一个正整数 $n\ (1\leq n \leq 2 \times 10^5)$，表示数组 $a$ 的长度。第二行 $n$ 个正整数 $a_i \ (1 \leq a_i \leq 2 \times 10^5)$，表示数组 $a$ 的元素。 ####solution：比较经典的不同范围不同做法，由于公比过大的时候会乘几次就结束，所以我们对此暴力。对于公比小的部分进行dp递推 #include<bits/stdc++.h> using namespace std; #define endl...
长链剖分
title: 长链剖分categories: - ICPCtags: - nullabbrlink: 478025cdate: 2023-09-14 00:00:00长链剖分https://blunt-axe.github.io/2019/11/25/20191125-Longest-Decomposition-Notes/ Problem - E - Codeforces [P3899 湖南集训] 更为厉害 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) [P5904 POI2014] HOT-Hotels 加强版 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) https://www.cnblogs.com/maoyiting/p/14178833.html#/cnblog/works/article/14178833 重链剖分定义子树大小最大的为重子节点，而长链剖分定义子节点中子树 深度最大 的子节点为重子节点。如果有多个子树深度最大的子节点，取其一。如果没有子节点，就无重子节点。 性质：链的长度定义为链包含的点数 任意节点 p...
倍增求lca
title: 倍增求lcacategories: - ICPCtags: - nullabbrlink: 7785d0e8date: 2023-09-12 00:00:00倍增求lcastruct edge{ int v,w; }; //思考：要想知道一个数有几个二级制位，直接n=__lg(x) //我们可以知道<n最近的2的次幂，9最大的是8，8虽然是2的3次方，但要遍历它的每一位 //需要3到0开始，也就是考虑到0的影响，我们可以正好满足偏移。 //2的3次方有四位，也就是__lg(x)就是我们需要的最高位，从它开始往低遍历 vector<edge>e[N]; int dep[N]; int d[N]; const int len=__lg(N); int f[N][len+2]; int cnt[N]; int ans=0; void dfs(int u,int fa){ dep[u]=dep[fa]+1; f[u][0]=fa; for(int...
常用树上函数
title: 常用树上函数categories: - ICPCtags: - nullabbrlink: a5678561date: 2023-09-12 00:00:00常用树上函数给定k个点·，判断他们能不能被同一条链覆盖。（也就是能不能构成简单路径） Sol:找到链的两个端点p1,p2，链上的点x一定满足$lca(p1,x)=x,lca(p2,x)=lca(p1,p2)$或者$lca(p2,x)=x,lca(p1,x)=lca(p1,p2)$ auto checkchain = [&](vector<int> &node) { int p1 = 0, p2 = 0; deb(lcarmq.dep); for (auto x : node) { if (p1 == 0 || lcarmq.dep[p1] < lcarmq.dep[x]) p1 = x; ...
5156
title: 5156categories: - ICPCtags: - nullabbrlink: ae930f07date: 2023-09-09 00:00:00https://www.acwing.com/problem/content/5156/ 对于能够被某个数整除的数的特征的一些总结 当我们要枚举一个数的后三位来判断这个数是不是能被8整除，可能会遇到这个数不足三位的情况，可以积累一个技巧，在数前面加两个前导零，这样枚举各位百位十位的时候，就可以枚举到个位数和两位数的情况。下面两种写法等价，第一种是第二种代数变形后的结果。 int x = s[i] * 100 + s[j] * 10 + s[k] - 111 * '0'; int x=(s[i]-'0')*100+(s[j]-'0')*10+(s[k]-'0');
一些常用到的有用知识(1)
title: 一些常用到的有用知识(1)categories: - ICPCtags: - nullabbrlink: ba70132fdate: 2023-09-07 00:00:00$$\log_2 1000000=19.931568569324174087221916576936341055188988358147483672328538374…$$ 1MB = 1024KB 1KB = 1024B 1B(byte,字节)=8b(bit,比特). $25610241024/4=67108864.0$(一个int四字节不用考虑bit换算，我们全部统一成B进行计算。256mb可以开67,108,864个int,6.7*1e7大约，longlong直接减半。 1e6(1000000)(一百万）里有78498个质数 对于13的阶乘不超过int 整数范围需要作为常识熟知$$13!=6227020800 =6.2270208 × 10^9 $$...
反悔贪心
title: 反悔贪心categories: - ICPCtags: - nullabbrlink: 9af7656adate: 2023-09-03 00:00:00反悔贪心
二分图最大匹配——网络流
title: 二分图最大匹配——网络流categories: - ICPCtags: - nullabbrlink: b759e094date: 2023-09-02 00:00:00二分图最大匹配可以转换成网络流模型。 将源点连上左边所有点，右边所有点连上汇点，容量皆为1。原来的每条边从左往右连边，容量也皆为1，最大流即最大匹配。 如果使用 Dinic 算法 求该网络的最大流，可在O(sqrt(n) * m)求出。 #define N 1010 #define M 2000010 int n,m,k,S,T; struct edge{int v,c,ne;}e[M]; int h[N],idx=1; //从2,3开始配对 int d[N],cur[N]; void add(int a,int b,int c){ e[++idx]={b,c,h[a]}; h[a]=idx; } bool bfs(){ //对点分层，找增广路 memset(d,0,sizeof d); ...