爱飞鱼的blog

单哈希且用自然溢出代替取模操作，常数小但是容易被卡 单字符串区间内比较，查询子串hash值 123456789101112131415161718192021222324252627282930313233343536typedef 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] = h[i - 1] * P + str[i]; p[i] = p[i -...

将O（n)优化成o（根号n） [CQOI2007] 余数求和 题目描述 给出正整数 nnn 和 kkk，请计算 G(n,k)=∑i=1nk mod iG(n, k) = \sum_{i = 1}^n k \bmod i G(n,k)=i=1∑n​kmodi 对于 100%100\%100% 的数据，保证 1≤n,k≤1091 \leq n, k \leq 10^91≤n,k≤109 1234567891011121314void 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<<"...

#E题 链接：https://ac.nowcoder.com/acm/contest/78292/E 来源：牛客网 小苯非常喜欢等比数列。有一天他得到了一个长为 nnn 的数组 aaa，他想从里面选一些数字使得被选中的数字构成一个等比数列，请问他最多可以选择多少个数字呢 输入包含两行。 第一行一个正整数 n (1≤n≤2×105)n\ (1\leq n \leq 2 \times 10^5)n (1≤n≤2×105)，表示数组 aaa 的长度。 第二行 nnn 个正整数 ai (1≤ai≤2×105)a_i \ (1 \leq a_i \leq 2 \times 10^5)ai​ (1≤ai​≤2×105)，表示数组 aaa...

长链剖分 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 的 k 级祖先q所在的链的长度一定大于 k 证明：分情况讨论。根据定义q→p 链的长度为 k+1 ，如果 p 和 q 在同一条链上，那这条链的长度自然大于 k...

倍增求lca 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748struct 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...

常用树上函数 给定k个点·，判断他们能不能被同一条链覆盖。（也就是能不能构成简单路径） Sol:找到链的两个端点p1,p2，链上的点x一定满足lca(p1,x)=x,lca(p2,x)=lca(p1,p2)lca(p1,x)=x,lca(p2,x)=lca(p1,p2)lca(p1,x)=x,lca(p2,x)=lca(p1,p2)或者lca(p2,x)=x,lca(p1,x)=lca(p1,p2)lca(p2,x)=x,lca(p1,x)=lca(p1,p2)lca(p2,x)=x,lca(p1,x)=lca(p1,p2) 1234567891011121314151617181920212223242526272829auto checkchain = [&](vector<int> &node) { int p1 = 0, p2 = 0; deb(lcarmq.dep); for (auto x : node) { if (p1 == 0 ||...

https://www.acwing.com/problem/content/5156/ 对于能够被某个数整除的数的特征的一些总结 当我们要枚举一个数的后三位来判断这个数是不是能被8整除，可能会遇到这个数不足三位的情况，可以积累一个技巧，在数前面加两个前导零，这样枚举各位百位十位的时候，就可以枚举到个位数和两位数的情况。 下面两种写法等价，第一种是第二种代数变形后的结果。 12int x = s[i] * 100 + s[j] * 10 + s[k] - 111 * '0';int x=(s[i]-'0')*100+(s[j]-'0')*10+(s[k]-'0');

log⁡21000000=19.931568569324174087221916576936341055188988358147483672328538374...\log_2 1000000=19.931568569324174087221916576936341055188988358147483672328538374... log2​1000000=19.931568569324174087221916576936341055188988358147483672328538374... 1MB = 1024KB 1KB = 1024B...

反悔贪心

二分图最大匹配可以转换成网络流模型。 将源点连上左边所有点，右边所有点连上汇点，容量皆为1。原来的每条边从左往右连边，容量也皆为1，最大流即最大匹配。 如果使用 Dinic 算法 求该网络的最大流，可在O(sqrt(n) * m)求出。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#define N 1010#define M 2000010int 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(){ //对点分层，找增广路 ...