搜索结果
查询Tags标签： 分治，共有 147条记录-
CDQ分治学习笔记
CDQ分治学习笔记目录CDQ分治学习笔记 前言 CDQ分治思想例题 1、翻转对 分析 codeP3810 三维偏序（陌上花开）输入格式 输出格式样例 #1 样例输入 #1 样例输出 #1提示分析 code前言 之前在gdkoi讲解是有人用 \(CDQ\) 分治A了day1 T3。好像分治FFT要用到，而且其他人都学过了…
2023/4/28 1:22:17 人评论 次浏览 -
【Coel.学习笔记】【半途跑路】CDQ 分治
最近在刷状压 DP，结果发现太难不会做，跑来学点别的。 反正 CSP-S2 之前刷完就行了，吧？ 放在数据结构里面是因为 CDQ 分治和数套树能解决的问题差不多，所以放了进去（绝不是因为懒得开一个“离线算法”的 Tag！） 引入 CDQ 分治是一种通过把动态询问/点对问题等离线处…
2022/9/8 23:56:09 人评论 次浏览 -
归并排序与分治法
目录分治法的思想分治模式的步骤归并排序算法算法步骤注意事项伪代码归并排序MergeSort()辅助函数: 合并Merge()归并排序代码实例函数声明函数定义归并排序辅助函数：合并注意事项 分治法的思想将原问题分解为几个规模较小但类似于原问题的子问题，递归地求解这些子问题，…
2022/9/6 23:22:54 人评论 次浏览 -
Problem P05. [算法课分治] 寻找第 k 个最大元素
先sort进行排序，然后输出第k大的元素即可#include<iostream> #include<bits/stdc++.h> #include<cstdio>using namespace std;int n, k; int arr[10005];int main() {scanf("%d %d", &n, &k);for (int i = 0; i < n; i++){scanf(…
2022/9/4 1:24:11 人评论 次浏览 -
Problem P04. [算法课分治] 找到 k 个最小数
先sort排序，在输出最小的k个数。#include<iostream> #include<bits/stdc++.h> #include<cstdio>using namespace std;int n, k; int arr[10005];int main() {scanf("%d %d", &n, &k);for (int i = 0; i < n; i++){scanf("%d…
2022/9/4 1:24:10 人评论 次浏览 -
cdq分治
cdq分治，一种广为人知的离线分治算法。大体的思想是：将左右两边区间分开递归处理。 统计左边区间修改对右边区间查询的影响。第一步很简单，写两个递归就行了。关键在第二步。我们搞个cdq的经典问题——三维偏序来具体解释这个东西。 P3810 【模板】三维偏序（陌上花开）…
2022/9/3 23:22:59 人评论 次浏览 -
树的难题 BJOI2017 点分治 单调队列
P3714 [BJOI2017]树的难题 没时间码 先口胡。 明显有一个n^2的暴力。可以拿到20分。 链的情况也非常容易 一个简单的单调队列 就可以解决 当然可以暴力的采用线段树。 这样可以拿到40分。 对于60分 直接考虑线段树合并 利用线段树维护每种颜色的最大值 由于不考虑边数问题…
2022/8/30 23:52:53 人评论 次浏览 -
331 树分治 点分治
视频链接： Luogu P3806 【模板】点分治1#include<iostream> #include<algorithm> using namespace std;const int N=10005; const int INF=10000005; struct node{int v,w,ne;}e[N<<1]; int idx,h[N]; //加边 int del[N],siz[N],mxs,sum,root;//求根 i…
2022/8/23 23:25:42 人评论 次浏览 -
树上分治
1. 点分治 现在有一棵大小为 \(n\) 的树，要求出路径长度小于 \(k\) 的路径。 每次可以通过选择重心的方式，将整棵树分为一堆不大于 \(\dfrac{n}{2}\) 的子树，所以将整棵树分为大小为 \(1\) 的子树需要 \(\log n\) 次。 对于现在求出重心的子树，显然有三种情况可以组成…
2022/7/25 23:24:18 人评论 次浏览 -
如何理解分治一定能分到所有区间
考虑当前层，是不是只分到左端点在 \([l,mid]\)，右端点在 \([mid+1,r]\) 的区间？ 那么是不是还差左右端点都在 \([l,mid]\) 的区间，左右端点都在 \([mid+1,r]\) 的区间？于是推锅分治下去即可，因为 \(solve(l,r)\) 的定义就是遍历了左右端点在 \([l,r]\) 的区间。
2022/7/14 6:21:30 人评论 次浏览 -
点分治
int siz[Z], kid[Z], root, size;//kid[rt]：该点的最大子树的大小 bool vs[Z]; void getroot(int rt, int fa)//求树的重心 {siz[rt] = 1, kid[rt] = 0;for (re i = head[rt]; i; i = e[i].ne){int son = e[i].v;if (vs[son] || son == fa) continue;getroot(son, rt);si…
2022/7/5 0:01:24 人评论 次浏览 -
小学期程序设计竞赛基础 听课记录
第一天： 无具体算法。 思维性：囚徒困境、三姬分金、纳什均衡、算法时间复杂度分析…… 第二天：分治法、排序 二分搜索、快速幂、大整数乘法、快速傅里叶变换、归并排序、（稳定的）快速排序、第k大的数 第三天： 分治法、动态规划 最近点对问题、矩阵连乘问题、最长公共…
2022/6/30 1:25:48 人评论 次浏览 -
浅谈线段树分治
思想 离线，把询问拆成若干个区间，放到线段树上，在线段树上递归处理，进一个区间就执行操作，出一个区间就撤销执行了的操作，需要支持可回退。 题 P5787 二分图 /【模板】线段树分治 以时间为轴建线段树，把所有的边都放到线段树对应的区间里，走到这个区间时就连边，可…
2022/6/2 23:21:15 人评论 次浏览 -
点分治
介绍 点分治是用来解决树上路径问题的一种方法。 在解决树上路径问题时，我们可以选取一点为根，将树转化为有根树，然后考虑经过根的所有路径（有时将两条从根出发的路径连接为一条）。统计完这些路径的答案后，将根节点标记为删除，对剩下的若干棵树进行同样的操作。如图…
2022/5/5 23:44:14 人评论 次浏览 -
java分治实现汉诺塔
java分治实现汉诺塔 /*** 分治实现汉诺塔** @param num 盘子的数量* @param a* @param b* @param c*/ public static void hanoiTower(int num, char a, char b, char c) {// 如果只有一个盘if (num == 1) {System.out.println("第1个盘从" + a + " => …
2022/4/25 1:12:50 人评论 次浏览
