爱飞鱼的blog

title: 字符串哈希 categories: ICPC tags: null abbrlink: ‘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 ++ ) { ...

title: 数论分块 categories: ICPC tags: null abbrlink: 4a670895 date: 2023-09-14 00:00:00 将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 void solve(){ int n,k;cin>>n>>k; int ans=n*k; //注意推导公式字母不要弄混 for(int...

title: 牛客周赛ROUND38 categories: ICPC tags: null abbrlink: 85e1eefd date: 2023-09-14 00:00:00 #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...

title: 长链剖分 categories: ICPC tags: null abbrlink: 478025c date: 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 重链剖分定义子树大小最大的为重子节点，而长链剖分定义子节点中子树 深度最大...

title: 倍增求lca categories: ICPC tags: null abbrlink: 7785d0e8 date: 2023-09-12 00:00:00 倍增求lca struct 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: ICPC tags: null abbrlink: a5678561 date: 2023-09-12 00:00:00 常用树上函数 给定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) auto checkchain = [&](vector<int> &node) { int p1 = 0, p2 = 0; deb(lcarmq.dep); for (auto x :...

title: 5156 categories: ICPC tags: null abbrlink: ae930f07 date: 2023-09-09 00:00:00 https://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');

title: 一些常用到的有用知识(1) categories: ICPC tags: null abbrlink: ba70132f date: 2023-09-07 00:00:00 log⁡21000000=19.931568569324174087221916576936341055188988358147483672328538374...\log_2 1000000=19.931568569324174087221916576936341055188988358147483672328538374... log2​1000000=19.931568569324174087221916576936341055188988358147483672328538374... 1MB = 1024KB 1KB = 1024B...

title: 反悔贪心 categories: ICPC tags: null abbrlink: 9af7656a date: 2023-09-03 00:00:00 反悔贪心

title: 二分图最大匹配——网络流 categories: ICPC tags: null abbrlink: b759e094 date: 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); ...