代码#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 ...

题解给定一个长度为$n$的排列，有两种操作，分别为区间取$mex$与交换两个相邻位置的元素。 考虑到所给序列是一个排列，所以$0~n-1$的每个元素要么在查询区间中出现，要么在区间外出现，所以区间内最小未出现的元素即区间外的最小元素（当区间包含整个序列时，答案应为$n$，没有在区间外出现，这种情况特判即可）。记录前缀后缀最小值，查询时答案即为$min(mnl[l-1],mnr[r+1])$。当交换相邻元素时，只有这两个相邻位置的前缀后缀最小值可能会发生改变。所以整体复杂度为$O(n+Q)$ （由 ...

题解若后继状态存在偏序关系（即如果状态$S_1$可以转移到$S_2$，状态$S_2$可以转移到状态$S_3$时，那么$S_1$一定可以转移到$S_3$），假设$SG(S_2)=x$，那么所有$0x-1$的$SG$值都在$S_2$的后继状态中出现过，又因为存在偏序关系，$S_1$的后继状态包含$S_2$的所有后继状态。所以$0x-1$和$x$的$SG$值一定在$S_1$的后继状态出现过，所以$SG(S_1)>x$。又因为$SG$是未在后继状态中出现过的最小自然数，所以$SG(S_1)=max ...