项目网址,seo在线优化排名,自己如何做公司网站,seo在哪可以学文章目录 根号分治例题选讲哈希冲突Time to Raid Cowavans[ARC150B] Make Divisible无向图三元环计数雅加达的摩天轮[ABC259Ex] Yet Another Path Counting 根号分治 根号分治#xff0c;与其说是一种算法#xff0c;更不如说是一种 思想。它是将问题按照不同的数据规模划分与其说是一种算法更不如说是一种 思想。它是将问题按照不同的数据规模划分分别使用 不同 的算法进行求解。一般是将规模按照 根号 分组已达到 根号平衡 的目的。一般来说一些题目并不难想到使用根号分治去解决但是根号分治需要 根据具体问题设计具体算法是很灵活的。因此想到了使用根号分治并不是难点难点是如何 分段 进行求解。
例题选讲 哈希冲突
题目
简要题意 给你一个长度为 n n n 的序列 a i a_i ai m m m 次操作。操作有两种 A A A 操作给你 x x x 和 y y y询问序列里所有下标 模 x x x 等于 y y y 的元素之和。 B B B 操作给你 x x x 和 y y y把序列里下标为 x x x 的元素的值修改成 y y y。 1 ≤ n , m ≤ 150000 1 ≤ a i ≤ 1000 1 \leq n,m \leq 1500001 \leq a_i \leq 1000 1≤n,m≤1500001≤ai≤1000。
分析 这是根号分治的入门题。 对于询问而言 不难想到当 x ≥ n x \geq \sqrt{n} x≥n 时我们可以从 y y y 暴力每次往后跳 x x x 个单位然后统计一下当前位置的元素之和就好了。时间复杂度是 O ( n ) O(\sqrt{n}) O(n )。 那么如果 x n x \sqrt{n} xn 呢暴力往后跳的复杂度无法保证我们考虑换一种算法。发现此时 x x x 的取值只有 n \sqrt{n} n 种。我们预处理出一个 f f f 数组。 f x , y f_{x, y} fx,y 表示模 x x x 为 y y y 的所有位置的元素之和。那么 f f f 数组的空间复杂度是 O ( n ) O(n) O(n) 的预处理的时间复杂度是 O ( n n ) O(n \sqrt{n}) O(nn ) 的。每次询问直接 O ( 1 ) O(1) O(1) 输出就好了。 对于修改而言。 我们发现修改会对 f f f 数组的值造成影响。因为数组的第一维只有 n \sqrt{n} n 的规模我们直接暴力修改 f f f 数组。具体来讲我们枚举数组的第一维 x x x然后设当前位置是 p p p y p % x y p \ \%\ x yp % x。那么直接让 f x , y f_{x, y} fx,y 减去修改前的元素大小再加上修改后的元素大小就好了。时间复杂度 O ( n ) O(\sqrt{n}) O(n )。 这样整体时间复杂度就是 O ( ( n q ) n ) O((n q)\sqrt{n}) O((nq)n )空间复杂度是 O ( n ) O(n) O(n)。可以通过。
CODE
#includebits/stdc.h
#define N 160000
#define LL long long
using namespace std;
int n, m, val[N], f[410][410], x, y;
char op;
int main(){scanf(%d%d, n, m);for(int i 1; i n; i) scanf(%d, val[i]);for(int i 1; i 400; i){for(int j 1; j n; j){f[i][j % i] val[j];}}for(int i 1; i m; i){scanf(\n%c%d%d, op, x, y);if(op A){if(x 400){int sum 0;for(int j y; j n; j x) sum val[j];printf(%d\n, sum);}else printf(%d\n, f[x][y]);}else{for(int i 1; i 400; i){f[i][x % i] - val[x];f[i][x % i] y;}val[x] y;}}return 0;
}Time to Raid Cowavans
题目 简要题意 给一个序列 a a a m m m 次询问每次询问 t t t k k k。求 a t a t k . . . a t p k a_t a_{t k} ... a_{t pk} atatk...atpk。其中 t p k ≤ n t pk \leq n tpk≤n 且 t ( p 1 ) k n t (p 1)k n t(p1)kn。 1 ≤ n , m ≤ 300000 , 1 ≤ a i ≤ 1 0 9 1 \leq n,m \leq 300000, 1 \leq a_i \leq 10^9 1≤n,m≤300000,1≤ai≤109。 时间限制 4 s 4s 4s空间限制 68.36 M B 68.36MB 68.36MB。
分析 发现这道题 往后跳 的操作与上一道题类似。我们仍然能够想到 当 k ≥ n k \geq \sqrt{n} k≥n 时我们可以直接暴力往后跳。那么一次询问的时间复杂度就是 O ( n ) O(\sqrt{n}) O(n ) 的。 当 k n k \sqrt{n} kn 时那么 k k k 的取值仍然是小于 n \sqrt{n} n 的我们可以维护一个 f i , j f_{i, j} fi,j 数组表示 步长为 i i i起点为 j j j 的答案。可以用递推来求出 f f f 数组。 但是事情好像并没有那么简单这样空间复杂度是 O ( n n ) O(n\sqrt{n}) O(nn ) 的显然是会被卡的。 我们发现这一道题相对于上一道题 没有修改操作。考虑 离线。我们把询问按照步长从小到大排序 如果当前步长跟上一次不一样并且小于 n \sqrt{n} n 那么我们 O ( n ) O(n) O(n) 跑一遍每一个点作为起点的答案存到 f i f_i fi 数组中。 如果当前步长跟上一次一样并且小于 n \sqrt{n} n 那么我们直接 O ( 1 ) O(1) O(1) 输出 f f f 数组里面的值就好了。 如果当前步长大于 n \sqrt{n} n 那么我们暴力跳。 这样时间复杂度 O ( n n ) O(n\sqrt{n}) O(nn )空间复杂度 O ( n ) O(n) O(n)。可以通过了。
CODE
#includebits/stdc.h
#define N 300100
#define LL long long
using namespace std;
int n, m;
LL a[N], f[N * 2], ans[N];
struct query{int t, k, id;bool operator (query const a)const{return k a.k;}
}q[N];
int main(){scanf(%d, n);for(int i 1; i n; i) scanf(%lld, a[i]);scanf(%d, m);for(int i 1; i m; i) scanf(%d%d, q[i].t, q[i].k), q[i].id i;sort(q 1, q m 1);for(int i 1; i m; i){if(q[i].k 548){if(q[i].k ! q[i - 1].k){for(int j n; j 1; j--){f[j] f[j q[i].k] a[j];}}ans[q[i].id] f[q[i].t];}else{LL sum 0;for(int j q[i].t; j n; j q[i].k) sum a[j];ans[q[i].id] sum;}}for(int i 1; i m; i) printf(%lld\n, ans[i]);return 0;
}[ARC150B] Make Divisible
题面
简要题意 给定两个正整数 A , B A,B A,B求满足 B Y B Y BY 是 A X A X AX 倍数的非负整数 X , Y X,Y X,Y 中 X Y X Y XY 的最小值。 T T T 组数据。 数据规模 1 ≤ T ≤ 100 , 1 ≤ A , B ≤ 1 0 9 1 \leq T \leq 100, 1 \leq A,B \leq 10^9 1≤T≤100,1≤A,B≤109。
分析 这道题很不好想。 首先如果 B ≤ A B \leq A B≤A那么答案就是 A − B A - B A−B。 否则可以令 X 0 X 0 X0那么 Y ≤ A Y \leq A Y≤A。这也就意味着答案不会超过 A A A。 另外我们可以想到如果我们枚举 X X X那么可以在 O ( 1 ) O(1) O(1) 的复杂度内算出合法的最小的 Y Y Y。因此考虑 根号分治 当 A ≤ B A \leq \sqrt{B} A≤B 时我们枚举 X X X然后 O ( 1 ) O(1) O(1) 算出一个 Y Y Y 跟答案取 m i n min min。这里 X X X 的枚举范围是 [ 0 , A ] [0, A] [0,A]时间复杂度 O ( B ) O(\sqrt{B}) O(B )。 当 A B A \sqrt{B} AB 那么容易注意到 B A B \frac{B}{A} \sqrt{B} ABB 。我们思考能否根据这一点做文章。 如果有性质 B Y A X ≤ B A \frac{B Y}{A X} \leq \frac{B}{A} AXBY≤AB 并且如果我们 知道比值可以快速算出最小的合法 X X X 和 Y Y Y 的话那么问题可以解决。 这里证明一下性质对于最优的 Y Y Y 和 X X X B Y A X ≤ ⌈ B A ⌉ \frac{B Y}{A X} \leq \left \lceil \frac{B}{A} \right \rceil AXBY≤⌈AB⌉。 设 d ⌈ B A ⌉ , d ′ B Y A X d \left \lceil \frac{B}{A} \right \rceil, d \frac{B Y}{A X} d⌈AB⌉,d′AXBY。 假设 d ′ d d d d′d。 那么 d ′ ( A X ) ≥ ( d 1 ) ( A X ) d(A X) \geq (d 1)(A X) d′(AX)≥(d1)(AX) 即 B Y ≥ ( d 1 ) A d X B Y \geq (d 1)A dX BY≥(d1)AdX B Y ≥ B A d X B Y \geq B A dX BY≥BAdX Y ≥ A d X Y \geq A dX Y≥AdX Y A Y A YA 因为 Y Y Y 一定小于等于 A A A。所以假设不成立。证毕。 还有一个问题就是如果我们知道比值该怎么算 X , Y X,Y X,Y 呢 我们设 B Y A X d \frac{B Y}{A X} d AXBYd那么就有 B Y d ( A X ) B Y d(A X) BYd(AX) Y d A d X − B Y dA dX- B YdAdX−B X Y ( d 1 ) X d A − B X Y (d 1)X dA - B XY(d1)XdA−B 发现这是一个关于 X X X 的一次函数我们只要求出最小的 X X X 就好了。 这个只需要找到最小的 X X X满足 d ( A X ) ≥ B d(A X) \geq B d(AX)≥B 就好了时间复杂度可以做到 O ( 1 ) O(1) O(1)。 因此总时间复杂度 O ( T × B ) O(T \times \sqrt{B}) O(T×B )。
#includebits/stdc.h//根号好题
#define LL long long
using namespace std;
int T;
LL a, b;
int main(){cin T;while(T--){cin a b;if(a b) cout a - b endl;//a b 那么Y a - b 就好了else{LL k sqrt(1.0 * b);if(a k){// a √b, 答案一定不会超过a所以偏移去找就好了 LL ans b - a;for(LL i 0; i a; i){// 枚举X if(b % (a i) 0) ans min(ans, i);else ans min(ans, i (a i) - (b % (a i)));}printf(%lld\n, ans);}else{// a √b, 那么 b / a √b 可以证明a x / b y b / a枚举一下就可以了 LL d, ans b - a;d (b - 1LL) / a 1LL;for(LL i 1; i d; i){//枚举 d b y / a xLL x;if(a * i - b 0) x 0;//求一下x else{x (b - a * i - 1LL) / i 1LL;//向上取整}ans min(ans, a * i - b (i 1) * x);}cout ans endl;}} }return 0;
}无向图三元环计数
题面
分析 详见这里
雅加达的摩天轮
题面
分析 我们考虑把楼看做 点把狗的跳跃方式看做 一种边。对于点 x x x 里的狗而言设它的跳跃步长是 p p p那么我们从 x x x 向 x p x − p x px-p xpx−p 连一条长度为 1 1 1 的边。向 x 2 p , x − 2 p x 2p, x-2p x2p,x−2p 连一条长度为 2 2 2 的边。向 x k p , x − k p x kp, x - kp xkp,x−kp 连一条长度为 k k k 的边。 如果每只狗的步长都大于 n \sqrt{n} n 那么显然整个图最多有 m n m\sqrt{n} mn 条边。我们直接跑 d i j k s t r a dijkstra dijkstra 就好了。 但是如果狗的步长小于 n \sqrt{n} n 这样做显然会导致边数达到 m n mn mn。那么我们可以想到类比 s p f a spfa spfa 的思想每次拓展一步跑最短路。但是这样有一个问题我们不确定每一个点能够使用哪一种边。我们考虑 拆点 记录状态。因为步长大于 n \sqrt{n} n 的不用记录。因此我们把点拆成 n 1 \sqrt{n} 1 n 1 个状态。 d i s i , j dis_{i, j} disi,j 表示 i i i 号点由某一个点通过 j j j 步长到达的最优值。特别的当 j n j \sqrt{n} jn 时我们看做状态 0 0 0。然后对于每一个点而言它内部本身就有的边我们 只在它的某一状态成为堆头时 使用其它时候不用。然后每次使用 状态 记录的边向左右跳一步松弛一次。这样一共有 n n n\sqrt{n} nn 个点由于我们是按照 d i j k s t r a dijkstra dijkstra 的方式写时间复杂度是 O ( n n l o g 2 n n ) O(n\sqrt{n}log_2n\sqrt{n}) O(nn log2nn )。
CODE
#includebits/stdc.h//考虑最短路
#define N 31000//瓶颈在于如果 pi √n 那么边的数量太多
#define M 181
using namespace std;
vector int G[31000];
set int s[M];
int n, m, b, p, dis[N], st, ed, d[N][M];// d[i][j]由j状态更新出来的最小值
int pre[N][M];
bool vis[N];
bool bok[N][M];
struct state{int x, f, w;bool operator (const state a)const{return a.w w;}
};
priority_queue state q;// 把一个点拆成 (√n 1) 个状态
int main(){scanf(%d%d, n, m);for(int i 0; i m; i){scanf(%d%d, b, p);G[b].push_back(p);if(i 0) st b;if(i 1) ed b;}memset(d, 0x3f, sizeof d);d[st][0] 0;q.push((state){st, 0, 0});// 0代表没有从一个小于等于√n的边转移过来 while(!q.empty()){state u q.top(); q.pop();int x u.x, f u.f, w u.w;if(bok[x][f]) continue;if(!bok[x][0]){for(auto v : G[x]){if(v 177){//直接跑int cnt 0; for(int j x; j n; j v){if(d[j][0] d[x][f] cnt){d[j][0] d[x][f] cnt;q.push((state){j, 0, d[j][0]});}cnt;}cnt 0;for(int j x; j 0; j - v){if(d[j][0] d[x][f] cnt){d[j][0] d[x][f] cnt;q.push((state){j, 0, d[j][0]});}cnt; }}else{//跑一次 if(x - v 0){if(d[x - v][v] d[x][f] 1){d[x - v][v] d[x][f] 1;q.push((state){x - v, v, d[x - v][v]});}}if(x v n){if(d[x v][v] d[x][f] 1){d[x v][v] d[x][f] 1;q.push((state){x v, v, d[x v][v]});}}}}bok[x][0] 1;} if(f ! 0){// 转移一次就行 if(x - f 0){if(d[x - f][f] d[x][f] 1){d[x - f][f] d[x][f] 1;q.push((state){x - f, f, d[x - f][f]});} }if(x f n){if(d[x f][f] d[x][f] 1){d[x f][f] d[x][f] 1;q.push((state){x f, f, d[x f][f]});}}}bok[x][f] 1;//标记已经跑了不用重复跑 }int res 0x3f3f3f3f;for(int i 0; i 177; i) res min(res, d[ed][i]);if(res 0x3f3f3f3f) printf(-1\n);else printf(%d\n, res);return 0;
}[ABC259Ex] Yet Another Path Counting
题面
简要题意 有 N N N 行 N N N 列的网格图只能向下或向右走合法路径的开端和结尾的格子上数字一样 找到合法路径条数对 998244353 998244353 998244353 取模。 1 ≤ N ≤ 400 , 1 ≤ a i ≤ N 2 1 \leq N \leq 400, 1 \leq a_i \leq N^2 1≤N≤400,1≤ai≤N2。 如果枚举起点和终点那么可以 O ( 1 ) O(1) O(1) 算出一个方案数。但是这样时间复杂度是 O ( N 4 ) O(N^4) O(N4) 的显然过不去。 我们考虑根号分治 设数字 c c c 的格子数量为 k k k如果 k ≤ N k \leq N k≤N那么我们直接 k 2 k^2 k2 枚举算贡献。这一部分的时间复杂度是 O ( N 2 k × k 2 N 2 × k N 3 ) O(\frac{N^2}{k} \times k^2 N^2 \times k N^3) O(kN2×k2N2×kN3) 的。 如果 k n k n kn那么会发现最多有 N 2 k \frac{N^2}{k} kN2 种这样的数字。能发现 N 2 k N \frac{N^2}{k} N kN2N我们对于每一种这样的数字如果能设计一种 O ( N 2 ) O(N^2) O(N2) 的算法求解就行了。 我们考虑每一次对于整个网格图做一遍 D P DP DP。设 d p i , j dp_{i, j} dpi,j 表示从一个数字为 c c c 的格子走到 ( i , j ) (i, j) (i,j) 的方案数。那么转移非常简单。如果 ( i , j ) (i, j) (i,j) 上的数字是 c c c那么我们把 d p i , j dp_{i, j} dpi,j 累加到答案中就好了。 时间复杂度 O ( N 3 ) O(N^3) O(N3)。
CODE
#includebits/stdc.h
#define LL long long
#define mod 998244353
#define N 410
#define PII pair int, int
#define pb push_back
#define F first
#define S second
using namespace std;
int n, mp[N][N];
LL c[N * 2][N * 2], res, sum[N][N];//sum[i][j] 表示范围内的合法点到i, j的方案数
vector PII vec[N * N];
void solve1(int k){//暴力 for(auto x : vec[k]){for(auto y : vec[k]){if((x.F y.F) (x.S y.S)) res (res 1) % mod;else if((x.F y.F) (x.S y.S)) res (res c[y.F - x.F y.S - x.S][y.F - x.F]) % mod;}}
}
void solve2(int k){//前缀和搞一搞 for(int i 1; i n; i)for(int j 1; j n; j)sum[i][j] 0;for(int i 1; i n; i){for(int j 1; j n; j){sum[i][j] (sum[i - 1][j] sum[i][j - 1]) % mod;if(mp[i][j] k) sum[i][j] (sum[i][j] 1) % mod, res (res sum[i][j]) % mod;}}
}
int main(){for(int i 0; i 800; i){for(int j 0; j i; j){if(j 0) c[i][j] 1LL;else c[i][j] (c[i - 1][j] c[i - 1][j - 1]) % mod;}}scanf(%d, n);for(int i 1; i n; i){for(int j 1; j n; j){scanf(%d, mp[i][j]);vec[mp[i][j]].pb(make_pair(i, j));}}for(int i 1; i n * n; i){if(vec[i].empty()) continue;else{if(vec[i].size() n) solve1(i);else solve2(i); }}printf(%lld\n, res);return 0;
}
