代码#include<bits/stdc++.h> using namespace std;typedef double db;const int N = 1e5+1;int n,cnt;struct P{ db x,y; P(db _x=0,db _y=0){x=_x;y=_y;} friend P operator - (P a,P b){return P(a.x-b.x,a.y-b.y);} friend db operator ...

代码#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef double db;const int N = 1e5+1;const db inf = 1e9;struct P{ db x,y,k; P(db _x=0,db _y=0,db _k=0){x=_x;y=_y;k=_k;} friend bool operator < (P a,P b){ ...

题解直线的交凸多边形的判定点在多边形内的判定线段在多边形内的判定多边形的重心 代码#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef double db;#define zero(x) (((x)>0?(x):-(x))<eps)#define _sign(x) ((x)>eps?1:((x)<-eps?2:0))const int N = 1e3+5;const in ...

题解序列自动机即一种建立在序列上的有穷自动机。有字符集，状态集合，起始状态，接收状态集合，转移函数五个要素。 其基本操作包括以下三种： 统计一个串本质不同的子序列的个数。(复杂度为$O(n*|S|)$) 查找一个子序列是否在该串中出现过。(复杂度为$O(n*|S|)$) 找到两个串所有的公共子序列。(复杂度为$O(nn|S|)$) 这三种操作的状态集合即位置集合$0~n$，起始状态即位置$0$，接收状态集合为所有状态，转移函数和第一种操作的具体实现如下。 代码void prepare( ...

题解给定序列$a$，求$max{ lcm(a_i,a_j)}(n,a_i\leq 10^5)$ 首先考虑将序列排序去重，并在过程中计算任意相等两数$lcm$的最大值 考虑枚举$gcd$的值，将所有$gcd$的倍数加入新序列内，问题转化为求序列中任意互质数对乘积的最大值 考虑维护一个栈，并将新序列中的元素从大到小依次加入，对于新加入的元素$x$，如果栈中存在$y$与其互质，那么栈中所有比$y$小的元素都可以删除，因为此时$x*y$一定大于接下来可能出现的答案$x’*y’$。($y’$是栈中比$y$ ...

题解启发式分治是为了解决序列上的一类特殊分治问题，一般的分治每次将区间的中点作为划分点将区间划分成两部分递归下去，而此类特殊分支问题的划分点选取与问题的要求有关，无法自行规定，所以对于每一次分治$(l,r)$进行处理的复杂度也不能高达$O(r-l+1)$，否则整个问题的复杂度将会退化为$O(n^2)$。 举例说明：设整个序列$(a_i>=0)$的权值为$good$的区间个数，设区间$good$当且仅当区间最大值的两倍大于等于区间和。 此时问题可以用从大到小枚举最大值并划分区间来解决，进而推 ...

题解$Lyndon$串： 对于字符串$x$，如果$x$的字典序严格小于x的所有后缀的字典序，我们称$x$是简单串，或者$Lyndon$串。 近似$Lyndon$串： 若$x$为$Lyndon$串，则$xxxx′$为近似$Lyndon$串，$x′$为$x$的前缀。 $Lyndon$分解： 将一个串$x$分作$x_1x_2..x_k$，每一个部分都是$Lyndon$串，且$x_i≥x_{i+1}$。 定理 $Lyndon$串是循环同构中字典序最小的一个。 $Lyndon$分解唯一。 两个$Lyndo ...