影院网站建设,万网如何购买网站空间,亚马逊电子商务网站的建设,建设网站程序下载【题解】2022年第四场寒假集训营题解
【题解】2022年第五场寒假集训营题解
【题解】2022牛客寒假算法基础集训营6
子序列权值乘积
思路#xff1a;排序然后枚举 i i i 维护前缀中的信息即可。注意有坑#xff1a;这道题要处理 2 k ( k ≤ 2 1 0 5 ) 2^k(k\leq 2\times…【题解】2022年第四场寒假集训营题解
【题解】2022年第五场寒假集训营题解
【题解】2022牛客寒假算法基础集训营6
子序列权值乘积
思路排序然后枚举 i i i 维护前缀中的信息即可。注意有坑这道题要处理 2 k ( k ≤ 2 × 1 0 5 ) 2^k(k\leq 2\times 10^5) 2k(k≤2×105) 因此需要使用到拓展欧拉定理。p是偶数且 n q nq nq 可以保证 gcd ( n , q ) 1 \gcd(n,q)1 gcd(n,q)1 。因此指数要模 p − 1 p-1 p−1 。
AC代码https://ac.nowcoder.com/acm/contest/view-submission?submissionId68935436
在这冷漠的世界里光光哭哭
思路容斥乱炖。思路太麻烦了见题解。
AC代码https://ac.nowcoder.com/acm/contest/view-submission?submissionId68946163
造梦小孩
思路根号分治。 a k × l e n ak\times len ak×len 加数
对于 l e n ≥ b l o c k c n t len\geq block_{cnt} len≥blockcnt 用分块暴力加即可。对于 l e n b l o c k c n t len block_{cnt} lenblockcnt 加入到lazy数组中 l a z y ( l e n , i ) lazy(len, i) lazy(len,i) 对第二维进行前缀和。
对lazy进行区间查询的话和智乃的模数方程类似因为是循环所以可以加速处理。
数组划分
思路问以 l l l 为左端点右端点的最大值。即找到第一个 j j j 使得 p r e i − 1 p r e j pre_{i-1}pre_j prei−1prej。
接下来我的思路是单调栈处理然后连边建树不断倍增。时间空间都是 O ( n log n ) O(n\log n) O(nlogn) 空间会炸。
因为数组分割有连续性跳父亲也有连续性可以直接在单调栈上二分。
