Z3phyrFT

分类

算法学习(8) 题解(2)

/ 注册

全部文章（共10篇）

【数据结构】ST表

ST表 ST表基于倍增的思想，可以做到的离线预处理和的在线查询。它可以用于解决满足结合律的可重复贡献问题。可重复贡献问题是指对于运算，满足，则对应的区间询问就是一个可重复贡献问题。例如，最大值有，gcd 有，所以 RMQ 和区间 GCD 就是一个可重复贡献问题。像...

数据结构 ST表

2021-08-18

0 538

【数据结构】单调队列

单调队列单调队列是主要用于解决类似滑动窗口类问题的数据结构：在长度为的序列中，求每个长度为的区间的区间最值问题，时间复杂度为 deque<int> q; int v[N]; int n,m; int main(){ cin >> n >> m; ...

数据结构单调队列

2021-08-17

0 379

【计算几何】半平面交

半平面交算法对于平面上的所有有向边（角度范围）将向量按照角度排序(atan2(y,x)) 按顺序扫描所有向量，用双端队列维护双平面交轮廓只要队尾的两个线和队头的两个线的交点在当前直线的右侧（因为保存左侧），将队尾或者队头删除用直线的参数方程存储直线时间复杂度 int cnt; s...

计算几何

2021-08-03

0 427

【计算几何】二维凸包-Andrew算法

Andrew算法将所有点排序，x为第一关键字，y为第二关键字从左到右维护上半部分，从右至左维护下半部分栈顶反向延长线的顺时针方向就留下，反之删除栈顶 double andrew(){ sort(q,q+n); int top = 0; for (int i = 0;...

计算几何二维凸包

2021-08-01

0 625

树上DP例题及思路总结

树上dp整理大体思路以树为载体的最优值问题是建立在遍历的基础上的。不同状态的表示往往按照节点分类，状态转移往往发生在父节点和子节点之间。建树的方式还是使用建图的方式。两个基本模型树的最长路径：即所有节点的子路径的最大值加次大值的最大值 int dfs(int u,int father){...

dp 动态规划树形dp

2021-07-31

0 538

【题解】POJ3304Segments-计算几何

POJ3304 大致题意给定个线段，求是否存在一条直线，所有的线段在该直线上的投影都有一个公共点。思路题目可以转化为，是否存在一条直线可以穿过所有的线段。我们可以将所有的线段的两个端点全部存在一个数组里，任取两个不同的点构成直线，判断这条直线是否穿过所有线段。如果有一条这样的线段存在就输出Ye...

计算几何

2021-07-29

0 540

【题解】POJ2318Toys-计算几何

POJ2318 大致题意给定一个矩阵的四个顶点坐标，和矩阵内的条直线和个点，求每个被直线分成的区域内各包含多少点思路对于条边，我们通过二分查找到当前点右边的第一条边（因为点不可能存在于边上）就是该点所存在的区域。我们可以通过这个点和边的有向面积的正负判断点在线段的哪个方位。代码 #inclu...

计算几何

2021-07-29

0 564

计算几何的基本知识和模板

简单总结几何最重要的计算单位就是向量，可以使用pair<>来定义变量，或者自定义结构体（需要重载一些运算符）向量最重要的两个操作点积，用来计算向量夹角叉积，用来计算面积（方向性面积），通过不同点和一个线段的面积的正负可以判断这个点的相对直线的位置向量的旋转也是比较重要的内...

计算几何

2021-07-29

0 552

区间DP思路和题型总结

区间DP的总结和整理基本思路确定状态表示，即表示的状态是什么确定划分依据，即的含义和取值（是否能取到L或者R）基本框架（枚举区间长度和左端点，并确定右端点，通过k进行转移） for (int len = 2;len <= n;++len){ for (int i = 1;...

dp 动态规划区间dp

2021-07-28

0 477

状态压缩DP总结

状态压缩DP 棋盘类即对于地图类的问题，当前行只受上一行或者前两行的影响，而不受其他因素的影响，此时可用状态压缩DPAcwing1064 小国王只受上一行影响 #include <bits/stdc++.h> using namespace std; const int N...

dp 状态压缩dp 动态规划

2021-07-27

0 538