做网站放广告收益,店标logo图片免费制作,金山区做网站公司,网站的类型大全写在前面的话#xff1a;
个人理解 根号分治本身就是一种卡着评测机过题的做法#xff0c;所以非必要不要写 #define int long long #xff01;#xff01;#xff01; 本篇博客参考#xff1a;暴力美学——浅谈根号分治
做到过两三题根号分治了#xff0c;来总结一下…写在前面的话
个人理解 根号分治本身就是一种卡着评测机过题的做法所以非必要不要写 #define int long long 本篇博客参考暴力美学——浅谈根号分治
做到过两三题根号分治了来总结一下这个算法
与其说是算法不如说是一种思维
根号分治的主要思路是数据范围很大的时候指不能接受 n 2 n^2 n2 复杂度但可以接受 n n n\sqrt n nn 复杂度的情况通常是 1 e 8 − 1 e 9 1e8-1e9 1e8−1e9将数据分为两个部分一个是小于 n \sqrt n n 的部分一个是大于等于 n \sqrt n n 的部分两个部分分别采用不同的处理方式
第一个部分需要处理的间隔小的部分使用技巧计算例如前缀和等预处理算法第二个部分需要处理的间隔大的部分暴力计算 下面举例说明几个可以使用根号分治的场景 数据结构数论 数据结构
来一道例题F. Remainder Problem
题目意思是给出一个长度为 5 e 5 5e5 5e5 的序列初始值都是 0给出 q 组操作每组操作包括 op x y
op 1 时a[x] yop 2 时输出下标模 x 等于 y 的位置的值之和
我们可以想到两种做法
暴力处理第一个操作就直接加复杂度 O ( 1 ) O(1) O(1)第二个操作就遍历一遍数组复杂度 O ( n ) O(n) O(n)这样最坏的复杂度是 O ( n q ) O(nq) O(nq)T利用二维数组预处理b[i][j] 表示模 i 等于 j 的位置上的值之和第一个操作就遍历更新 b[i][j]复杂度 O ( n ) O(n) O(n)第二个操作直接输出复杂度 O ( 1 ) O(1) O(1)最坏的复杂度是 O ( n q ) O(nq) O(nq)T
那能不能把两者结合起来呢
我们发现如果 x 比较大的话暴力处理的第二个操作复杂度就不会太高但是不能进行预处理空间上不能接受x 比较小的话可以进行预处理而暴力操作的复杂度就会比较高
说到这里就清楚啦x 大就第一个做法x 小就第二个做法大小的分界线是什么呢就是 n \sqrt n n c o d e code code
#include bits/stdc.husing namespace std;// #define int long long
using i64 long long;typedef pairint, int PII;
typedef pairint, char PIC;
typedef pairdouble, double PDD;
typedef pairint, PII PIII;
typedef pairint, pairint, bool PIIB;const int N 5e5 10;
const int maxn 710;
const int mod 1e9 7;
const int mod1 954169327;
const int mod2 906097321;
const int INF 0x3f3f3f3f3f3f3f3f;int a[N], b[710][710];void solve()
{int q;cin q;while (q -- ){int op, x, y;cin op x y;if (op 1){a[x] y;for (int i 1; i 700; i ) b[i][x % i] y;}else{if (x 700) cout b[x][y] \n;else{int res 0;for (int i y; i 5e5; i x) res a[i];cout res \n;}}}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;// cin t;while (t--){solve();}
}数论
看这题D. Two Arithmetic Progressions
题目给出这样的两个数列 a 1 k b 1 a_1kb_1 a1kb1 a 2 k b 2 a_2kb_2 a2kb2 k 0 k0 k0
然后给出 [ l , r ] [l,\ r] [l, r]问这个区间里有多少数同时存在于上面的两个数列里 a 、 b a、b a、b 的范围都是 2 e 9 2e9 2e9
我们还是想出两种办法
k 从 0 开始枚举第一个数列的数直到找到一个在第二个数列里也出现的数可以发现最多找 max(a1, a2) 次之后每次加上循环节也就是 a 1 a_1 a1 和 a 2 a_2 a2 的最小公倍数即可枚举 a a a 值较大的数列符合条件就答案1完全暴力
设 maxx max(a1, a2) 当 maxx 比较大的时候数列里的值的数量就会比较少可以通过枚举解决问题但使用第一种方法就会T 当 maxx 比较小的时候枚举会T但可以使用第一种找循环节的方法
所以通过这个进行根号分治结束
其实这题的正解并不是根号分治但是使用这种思想可以直接碾过去cf2500的题好爽ovo c o d e code code
#include bits/stdc.husing namespace std;#define int long long
using i64 long long;typedef pairint, int PII;
typedef pairint, char PIC;
typedef pairdouble, double PDD;
typedef pairint, PII PIII;
typedef pairint, pairint, bool PIIB;const int N 2e9;
const int maxn 710;
const int mod 1e9 7;
const int mod1 954169327;
const int mod2 906097321;
const int INF 0x3f3f3f3f3f3f3f3f;void solve()
{int a1, b1, a2, b2, l, r;cin a1 b1 a2 b2 l r;int maxx max(a1, a2);if (maxx sqrt(N)) // 找最小公倍数{for (int i 0; i maxx; i ){int tmp a1 * i b1;if (abs(tmp - b2) % a2 0){int lcmm lcm(a1, a2);int st max({l, b1, b2});if (tmp st){tmp ((st - tmp) / lcmm 1) * lcmm;tmp st (tmp - st) % lcmm;}else tmp st (tmp - st) % lcmm;if (tmp r) continue;cout (r - tmp) / lcmm 1 \n;return;}}cout 0 \n;}else // 暴力{int ans 0;if (a1 a2) swap(a1, a2), swap(b1, b2);for (int i b1; i r; i a1){if (i l || i b2) continue;if ((i - b2) % a2 0) ans ;}cout ans \n;}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;// cin t;while (t--){solve();}
}
