根号分治 + 入门题目"/>
根号分治 + 入门题目
根号分治解决的问题有这种特点:
- 可以将问题按照某个界限拆分为两个子问题,通常界限设为 n \sqrt n n
- 对于拆分出来的两个子问题,一部分可以暴力求解,另一部分可以使用算法求解。这样分治的话,可以使得两个子问题的时间复杂度刚好都是 n ⋅ n n\cdot \sqrt n n⋅n ,得以解决问题
题目:
E. Array Queries
题意:
- 给定长度为 n n n 的序列 a a a。 m m m 次询问。
- 每次询问给出 p , k p,k p,k。您要不断地执行操作 p ← p + a p + k p\gets p+a_p+k p←p+ap+k,直到 p > n p>n p>n 为止。询问的答案为操作次数。
- 1 ≤ n , q ≤ 1 0 5 1\le n,q\le 10^5 1≤n,q≤105, 1 ≤ a i ≤ n 1\le a_i\le n 1≤ai≤n, 1 ≤ p , k ≤ n 1\le p,k\le n 1≤p,k≤n。
思路:
对于 k > n k> \sqrt n k>n 的询问,暴力即可,枚举的次数不超过 n \sqrt n n 。
对于 k ≤ n k\leq \sqrt n k≤n 的询问,可以预处理 ( p , k ) (p,k) (p,k) 状态需要跳的步数,时空复杂度 O ( n ⋅ n ) O(n\cdot \sqrt n) O(n⋅n ) 。
AC代码:
D1. Frequency Problem (Easy Version)
题意:
给定 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1,a2,...,an,求最长的满足区间众数有至少两种的区间长度。如果不存在这样的区间,输出 0 0 0。
n ≤ 2 × 1 0 5 , 1 ≤ a i ≤ min ( 100 , n ) n\leq 2\times 10^5,1\leq a_i\leq \min(100,n) n≤2×105,1≤ai≤min(100,n)
思路:略。详见 题解 。
AC代码:
D2. Frequency Problem (Hard Version)
题意:将上一题的 1 ≤ a i ≤ min ( 100 , n ) 1\leq a_i\leq \min(100,n) 1≤ai≤min(100,n) 改为 1 ≤ a i ≤ n 1\leq a_i\leq n 1≤ai≤n 。
题解:题解 CF1446D1 【Frequency Problem (Easy Version)】
思路:
对于 a i > n a_i> \sqrt n ai>n 的数字,最多有 n \sqrt n n 种,按照 easy.ver 的思路即可。
对于 a i ≤ n a_i\leq \sqrt n ai≤n 的数字,枚举出现次数上界,然后双指针找最长子区间。
AC代码:
更多推荐
根号分治 + 入门题目
发布评论