段三园的小迷弟

题解

心得(37) 未归档(1) 模板题(7) 读书笔记(2)

/ 注册

全部文章 / 题解（共110篇）

acwing799，双指针算法+桶排序（哈希表）

双指针算法：一般把有单调性质的序列（满足：（循环顺序从左开始，右则相反）小段性质不满足，左扩大段性质肯定不满足）从暴力o[N2]的复杂度降到o[N] 一般双指针算法板子： for(int i=0,j=0;i<n;i++){右指针向前 while(j<=i...

算法双指针哈希

2019-08-26

0 646

acwing788，求逆序对的数量，归并思想

如果暴力时间复杂度是o(N2) 用归并，我们可以把数组一分为二，左边和右边的逆序对数量相加在加上横跨左右两边逆序对数量（*截图来源于acwing基础算法课）因为i是第一个大于j 的位置且上数组已经排序好，所以i后面的数都大于j 此方法相对于暴力来说每次只要找到第...

搜索归并

2019-08-25

0 610

acwing786，第k小数，快速查找（快排思想）

每次抽一个数x，整个数小于x的放左边，大于x的放右边然后比较j是不是大于等于k，是的话取左边继续重复上述操作，不是取右边，直到只剩一个数，就是k 两个指针i，j操作，但每***作i j所指不一定是等于x的数；快速查找相对于快排来说每次只处理一半，大多数情况是2N，最差是o(N2...

搜索

2019-08-25

0 567

acwing791/2/3/4,高精度，大数的加减乘除

https://www.acwing.com/problem/content/793/ https://www.acwing.com/problem/content/794/ https://www.acwing.com/problem/content/795/ https:/...

高精度模板

2019-08-23

0 547

acwing870,求约数个数

如果则约数个数为 #include <bits/stdc++.h> using namespace std; const int mod=1e9+7; int n; int a; unordered_...

数论模板

2019-08-22

0 521

poj1039，直线交点

x最大存在于一上一下的端点，换句话说就是x最长的线一定经过一个上端点和一个下端点 #include <iostream> #include <cmath> #include <cstdio> using&nbs...

计算几何

2019-08-21

0 719

poj1265，皮克定理：多边形面积，边点数，内部点数

😎皮克定理： S:多边形面积 ——累加叉积/2 I:多边形内部点数 E:多边形边上的点数——每次求出端点的最大公约数，其他约数构成最小子增加，最大公约数就是可以放大多少次，就是新增的点数，每次起点不计，终点计入，因为是封闭多边形，所以最开始的起点是最后的终点 ...

计算几何

2019-08-21

0 1043

poj1066，线段上的点能否到另一点+规范相交

一个线段是否存在一点能到另一点，可以看线段的两端点能否到目标点，因为线段两端点的能到情况包含了线段上的点的能到所以情况但必须满足一下：（自己总结的）障碍物必须是直的本题把所有的墙的端点造成的线段与目标点进行匹配看要穿过墙，（按题目意思从端点出发不算穿自己的墙） ...

计算几何

2019-08-20

0 571

poj2398,（模板）计算几何，用叉积判点在线左右

https://blog.csdn.net/zt2650693774/article/details/99676149 #include #include #include #include using namespace std; struct Point{ doubl...

计算几何模板

2019-08-18

0 779

poj1061，斐蜀定理

费蜀定理：对于任意正整数x，y，一定存在整数a，b，使得： ax+by=gcd(x,y); 定理1 gcd(a,b)是ax+by的线性组合的最小正整数定理2 如果ax+by=c，x，y∈z；则c%gcd==0; 定理3 如果a，b是互质的正整数，...

数论因数约数

2019-08-14

1 500