Uniontake

原创 初识差分约束

对于差分约束理解差分约束解决了一类不等式组的解的问题，如(0)x1−x0≤a x_1 - x_0 \leq a \tag{0} x1​−x0​≤a(0)(1)x2−x1≤b x_2-x1\leq b \tag{1} x2​−x1≤b(1)(2)x2−x0≤c x_2-x_0\leq c \tag{2}x2​−x0​≤c(2)然后我们需要求的是x2−x0x_2-x_0x2​−x0​的最大...

原创 [数值分析]离散数据拟合-最小二乘法

最小二乘法算法最小二乘法（又称最小平方法）是一种数学优化技术。它通过最小化误差的平方和寻找数据的最佳函数匹配。利用最小二乘法可以简便地求得未知的数据，并使得这些求得的数据与实际数据之间误差的平方和为最小。最小二乘法还可用于曲线拟合。其他一些优化问题也可通过最小化能量或最大化熵用最小二乘法来表达。拟合在实际问题中，常常给定一组测定的离散数据, xi,yix_i, y_ixi​,yi​, 欲求自...

原创 HDU5528 Count a*b 数论函数前缀和

Description定义f(m)=∑i=0m−1∑j=0m−1[gcd(m,i∗j)≠m]f(m) = \sum^{m-1}_{i=0}\sum^{m-1}_{j=0}[gcd(m,i*j) \ne m]f(m)=∑i=0m−1​∑j=0m−1​[gcd(m,i∗j)̸​=m]求g(n)=∑m∣nf(m)g(n) = \sum_{m|n}f(m)g(n)=∑m∣n​f(m)InputT...

原创 除数函数(约数个数函数)前缀和

Problem\color{red} {Problem}ProblemDescription查询[1-n]所有数的约数和。Solution朴素考虑[1−n]的约数个数的和。也就是考虑每个约数的贡献(出现了多少次)朴素考虑 [1-n]的约数个数的和。也就是考虑每个约数的贡献(出现了多少次)朴素考虑[1−n]的约数个数的和。也就是考虑每个约数的贡献(出现了多少次)枚举每一个约数i其出现了⌊...

原创 [数值分析]不动点迭代法求解非线性方程

Promble1求出f(x)=3x2−ex=0f(x)=3x2−ex=0f(x) = 3x^2-e^x = 0的根，精确到小数点后的第4位。解 首先我们利用matlab绘图确定出根的大致区域。 由图可知存在三个有根区间[−1,0],[0,1],[3,4][−1,0],[0,1],[3,4][-1,0],[0,1],[3,4]Step1Step1\color {red}{St...

原创 [数值分析]二分法求解非线性方程根

Problem1描述 用二分法求方程x2−x−1=0x2−x−1=0x^2-x-1=0的正根，要求误差小于0.050.050.05. 题解通过图像我们确定了一个大致的有根区间[−1,0][−1,0][-1,0] 和[1,2][1,2][1,2] 通过二分法求解这两个区间的根。 区间[−1,0]区间[−1,0]区间[-1,0]#include<bits/stdc++...

原创 [数值分析]不动点迭代法

1.1.1.不动点与不动点迭代法对于方程 f(x)=0(1.1)(1.1)f(x)=0f(x) = 0\tag{1.1} 改写成 x=φ(x)(1.2)(1.2)x=φ(x) x = \varphi(x)\tag{1.2} 若要求x∗x∗x^*满足f(x∗)=0f(x∗)=0f(x^*) = 0，则x∗=φ(x∗)x∗=φ(x∗)x^* = \varphi(x^*);反之亦然。则称x∗...

原创 2018 NanJing ICPC Online Contest L Magical Girl Haze (BZOJ - 2763) 分层最短路

Description分层图最短路，就是在分层图上解决最短路问题。 主要是应用于变化的最短路问题，问题常表现为一个最短路问题上加一些手脚，如减小一些边权，改变一些连接，但事先又不知道，或可以自由选择改变哪个边，最终求最短路等等。由于无法知道改变了那些边，所以用到分层图思想。 1.一种解决方法是多开一维记录状态，多开的维度记录状态的种类数即为分层数。1.一种解决方法是多开一维记录状态，多...

原创 AtCoder - 3621 Small Multiple 巧妙建图最短路

Description题意就是给一个数k，问他的正整数倍数中，（十进制下）每一位的和最小是多少。题意就是给一个数k，问他的正整数倍数中，（十进制下）每一位的和最小是多少。题意就是给一个数 k ，问他的正整数倍数中，（十进制下）每一位的和最小是多少。Input2≤k≤1052≤k≤1052\leq k\leq 10^5Outputk的倍数最小的每一位位数和。k的倍数最小的...

原创 Wannafly挑战赛23 A字符串 尺取法

Description给出一个字符串S，保证存在一个子串满足其中包含了所有的26个字母。找出长度最短的子串。给出一个字符串S，保证存在一个子串满足其中包含了所有的26个字母。找出长度最短的子串。给出一个字符串S，保证存在一个子串满足其中包含了所有的26个字母。找出长度最短的子串。Input|S|≤105|S|≤105|S| \leq 10^5Output子串的长度...

原创 Gym - 101572E Emptying the Baltic 优先队列

Description就是说给出一个n∗m的地形块，0表示海平面，负数表示地面在海水下，正数表示是陆地，且高出海平面。就是说给出一个n∗m的地形块，0表示海平面，负数表示地面在海水下，正数表示是陆地，且高出海平面。就是说给出一个n*m的地形块，0表示海平面，负数表示地面在海水下，正数表示是陆地，且高出海平面。 现在在(x,y)处放上一个排水的设备，问其能排出多少的水，对于一个位置，水能够从八...

原创 Gym - 101572G Galactic Collegiate Programming Contest 树状数组|优先队列

Description现在有n个队伍，每个队伍的有两个值(a,b):分别表示通过的题目和罚时。现在有n个队伍，每个队伍的有两个值(a,b):分别表示通过的题目和罚时。现在有n个队伍，每个队伍的有两个值(a,b):分别表示通过的题目和罚时。 题目越多，排名越靠前，如果题目数相同则b罚时越少的队伍越靠前。题目越多，排名越靠前，如果题目数相同则b罚时越少的队伍越靠前。题目越多，排名越靠前，如果题目...

原创 Gym - 101572A Airport Coffee 单调队列优化DP

Description在一个一维坐标轴上，一个人要从0位置走到位置l。在一个一维坐标轴上，一个人要从0位置走到位置l。在一个一维坐标轴上，一个人要从0位置走到位置l。 他的默认速度为a，他希望在最短时间到达位置l他的默认速度为a，他希望在最短时间到达位置l他的默认速度为a，他希望在最短时间到达位置l 幸运的是在坐标轴上存在n个咖啡厅，他可以在任意咖啡厅买一杯咖啡幸运的是在坐标轴上存在n个咖...

原创 Gym - 101572K Kayaking Trip 二分

Description有n个人要进行两两配对的划船，他们的个人能力分为3种级别，新手sb，普通sn，精通se。有n个人要进行两两配对的划船，他们的个人能力分为3种级别，新手sb，普通sn，精通se。有n个人要进行两两配对的划船，他们的个人能力分为3种级别，新手s_b，普通s_n，精通s_e。 共有n/2只船，如果由x，y来开船i，其稳定程度为k=ci(sx+sy)共有n/2只船，如果...

原创 [模板]计算几何-二维Point

浮点精度const double eps = 1e-8;const double inf = 1e20;const double pi = acos(-1.0);const int maxp = 1010;int sgn(double x) { if(fabs(x) < eps) return 0; if(x < 0) return -1; re...

原创 CodeForces - 253D Table with Letters - 2 双指针法

Description给出n∗n的矩阵,求出所有满足以下条件的子矩阵的个数给出n∗n的矩阵,求出所有满足以下条件的子矩阵的个数给出n*n的矩阵,求出所有满足以下条件的子矩阵的个数 1.子矩阵的四个角元素都相同1.子矩阵的四个角元素都相同1.子矩阵的四个角元素都相同 2.子矩阵中′a′字符的数量≤k2.子矩阵中′a′字符的数量≤k2.子矩阵中'a'字符的数量\leq kInput...

原创 HDU - 2430 Beans 线段树|单调队列

Description题意给出n个谷堆,每个谷堆有wi个谷子题意给出n个谷堆,每个谷堆有wi个谷子题意给出n个谷堆,每个谷堆有w_i个谷子 现在要在n个谷堆中找出一个连续的区间[i,j]使得区间的和sumij现在要在n个谷堆中找出一个连续的区间[i,j]使得区间的和sumij现在要在n个谷堆中找出一个连续的区间\begin{bmatrix}i,j\end{bmatrix}使得区间的和sum_...

原创 POJ - 2019 Cornfields 二维RMQ

题意给出n∗n的矩阵。给出n∗n的矩阵。给出n*n的矩阵。 多次查询(x,y)为左上顶点，长度为b的子矩阵的最大值最小值差。多次查询(x,y)为左上顶点，长度为b的子矩阵的最大值最小值差。多次查询(x,y)为左上顶点，长度为b的子矩阵的最大值最小值差。题解二维ST表二维ST表二维ST表 给出两种二维RMQ写法给出两种二维RMQ写法给出两种二维RMQ写法Code1Code...

原创 UVALive - 8270 A Partial Order Relation 哈斯图边数

题目求出n的偏序关系下的哈斯图的边数求出n的偏序关系下的哈斯图的边数求出n的偏序关系下的哈斯图的边数 如图 n = 60 题解考虑对n质因子分解考虑对n质因子分解考虑对n质因子分解 分解为m个质数因子每个因子有ci个分解为m个质数因子每个因子有ci个分解为m个质数因子每个因子有c_{i}个 对于每一质数因子iii会被相关联ci∗∏mj=1(cj+1)(j≠i)...

原创 HDU - 3486 Interviewe RMQ优化

题目有n个人参加面试，公司只需要m个人，于是将n个人分成m段每段⌊nm⌋人，且从每段中选出能力最大的人。有n个人参加面试，公司只需要m个人，于是将n个人分成m段每段⌊nm⌋人，且从每段中选出能力最大的人。有n个人参加面试，公司只需要m个人，于是将n个人分成m段每段{\lfloor \frac{n}{m} \rfloor} 人，且从每段中选出能力最大的人。 现在要求计算出一个最小的m满足选出的...

原创 CodeForces - 372C Watching Fireworks is Fun 单调队列优化DP

题意在nn{\color{red} n}个点的街道上，将有mm{\color{red} m}个烟花要放。每个烟花拥有三个参数a,b,ta,b,t{\color{red} {a,b,t}}。tt{\color{red} t}表示该烟花在t时刻放。 假设现在时间正好为tt{\color{red} t}时刻，一个人站在xx{\color{red} x}点位置则他获得的开心值为bi−|a...

原创 1到n的因数和的和

代码#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e5+10;int main(){ ll n;int caset; scanf("%d",&caset); while(caset--) { scanf...

原创 HDU 6446 Tree and Permutation 树上DP

Tree and PermutationTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 126    Accepted Submission(s): 48 Problem DescriptionThere are N ver...

原创 CodeForces - 91B Queue 单调队列 | 线段树

题目给出n个数的序列，求出每一个数右边最后一个比他小的数的位置差。题解考虑单调队列做法维护一个单调递减的队列。对于一个数来说 最优被定义为 尽可能小，同时位置要小。于是对于一个新入队的数来说，如果他比最小的数大的话。其位置也大于最小的数。则这个数是无用的。于是对于每个新入队的数，在入队前在单调队列中二分查找一下最后一个比他的小的数的位置。如果满足单调性则入队...

原创 POJ - 2559 Largest Rectangle in a Histogram 单调栈

Largest Rectangle in a HistogramTime Limit: 1000MS   Memory Limit: 65536K Total Submissions: 26415   Accepted: 8536 DescriptionA histogram is a polygon composed of a sequence of re...

原创 POJ - 1821 Fence 单调队列优化DP

FenceTime Limit: 1000MS   Memory Limit: 30000K Total Submissions: 5933   Accepted: 1900 DescriptionA team of k (1 <= K <= 100) workers should paint a fence which contains N (...

原创 HDU - 4122 Alice's mooncake shop 单调队列

Alice's mooncake shopTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 4606    Accepted Submission(s): 1226 Problem DescriptionThe Mid-Aut...

原创 HDU - 3706 Second My Problem First 单调队列

Second My Problem FirstTime Limit: 12000/4000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 2362    Accepted Submission(s): 910 Problem DescriptionGive you ...

原创 HDU 3530 Subsequence 单调队列

SubsequenceTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 8797    Accepted Submission(s): 2961 Problem DescriptionThere is a sequence o...

原创 HDU 6319 Ascending Rating 单调队列

Problem A. Ascending RatingTime Limit: 10000/5000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 5019    Accepted Submission(s): 1736 Problem DescriptionBe...

原创 [Wannafly22] A计数器 裴蜀定理

裴蜀定理若a,b是整数,且（a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。它的一个重要推论是：a,b互质的充要条件是存在整数x,y使ax+by=1. 题目题目描述 有一个计数器，计数器的初始值为0，每次操作你可以把计数器的值加上a1,a2,...,an中的任意一个整数，操作次数不限（可以为0次），问计数器...

原创 [Wannafly挑战赛22] D 整数序列 线段树

题目描述 给出一个长度为n的整数序列a1,a2,...,an，进行m次操作，操作分为两类。操作1：给出l,r,v，将al,al+1,...,ar分别加上v；操作2：给出l,r，询问输入描述:第一行一个整数n接下来一行n个整数表示a1,a2,...,an接下来一行一个整数m接下来m行，每行表示一个操作，操作1表示为1 l r v，操作2表示为2 l r保证1≤n,m,ai,...

原创 [FFT] 例题详解

FFT是什么FFT（Fast Fourier Transformation）就是“快速傅里叶变换”的意思，它是一种用来计算DFT（离散傅里叶变换）和IDFT（离散傅里叶反变换）的一种快速算法。这种算法运用了一种高深的数学方式、把原来复杂度为O(n2)的朴素多项式乘法转化为了O(nlogn)的算法。FFT在算法竞赛中的例题FFT能将多项式乘法O(n^2) 优化为 O(nlogn)但是...

原创 原根

模板 求质数P的最小原根#include<bits/stdc++.h>using namespace std;const int maxn = 1e5+10;typedef long long ll;int prime[maxn];void getPrime() { memset(prime,0,sizeof(prime)); for(int i...

原创 凸包中整数点个数

原创 卡牌游戏期望

题引题解题目描述好像有点问题。应该是N种卡牌。M种稀有卡牌，且抽出不放回。对于求期望来说，相比之下我们更容易求出概率。而对于此类题目 期望往往 = 1/概率 (暂时这么理解的)而期望具有可加性。把所有稀有卡牌都抽一遍的期望 = 每次抽得一个稀有卡牌的期望的和。至少抽出k张稀有卡牌的期望 = 抽出k张每次抽的一个稀有卡牌的期望和。考虑当前F[i]表示已经抽到i...

原创 暴力分块矩阵乘法

题引题解朴素的算法 O(4096 * 64 * 4096) = O(1e9) 不用想是超时的。因为每次矩阵乘法中存在很多重复的计算。考虑将矩阵进行分块优化。预处理出每块的值。怎么分块。考虑对A矩阵的列分块，和B矩阵的行分块。因为p是公共的边,且p <= 64需要注意到的是 B矩阵中的取值仅有01那么如果对B矩阵进行分块的话。考虑每块8个01串。那么每一块的...

原创 [HDU多校05] HDU 6354 Everything Has Changed 计算几何

Everything Has ChangedTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 414    Accepted Submission(s): 234Special Judge Problem Descriptio...

原创 Montgomery modular multiplication 快速乘法

题引题解题解显而易见就是对数列的前k项进行前缀乘法。需要注意到的是乘法是会爆longlong的。这时你的直观做法就是使用快速幂的思想规避溢出情况。形如这样的代码:ll mult(ll a,ll b) { a %= mod;b %= mod; ll ans = 0; while(b) { if(b&1) ans = (an...

原创 无向联通图的二分染色与存在奇环的性质分析

题引题解及思路题中给出了无向图的两种存在形状 二分染色 和 存在奇环首先我们需要证明的是两者是互斥的。二分图定义 ：是这样一个图，其顶点可分为两集合X和Y，所有的边关联的两顶点中，恰一个属于Ｘ，另一个属于Ｙ。同一集合的结点不相邻。证明：假设二分图中的环是奇数环。设一个环，x1，x2，x3，，，，x(2*k-1)，k>=1且为整数。相邻两点有边连接，x1与x(2...