clover_hxy-CSDN博客

原创计算几何总结

计算几何总结一、精度控制计算几何经常牵扯到浮点数的运算，所以就会产生精度误差，因此我们需要设置一个eps（偏差值），一般取1e-7到1e-10之间，并用下面的函数控制精度。const double eps=1e-8;int dcmp(double x){ if (fabs(x)<eps) return 0; else return x<0?-1:1;}二、向量

2017-01-01 15:53:50 17911 8

原创 Nim 游戏及其变形

Nim 在博弈中经常出现，很多看似复杂的题目，在分析和变形之后就回归了最初的nim游戏。经典的nim游戏一共有N堆石子，编号1..n，第i堆中有个a[i]个石子。每一次操作Alice和Bob可以从任意一堆石子中取出任意数量的石子，至少取一颗，至多取出这一堆剩下的所有石子。两个人轮流行动，取走最后一个的人胜利。Alice为先手。我们定义PositionP：表示当前局面

2016-12-22 20:25:37 17869 6

原创一些数论的模板及相关结论

数论总结先从简单的发起啦。。。。。一、整除和同余b整除a记作b|a．a, b除以m所得的余数相同，记作a≡b (mod m) a=b(modm)两侧可以同加、减、乘、乘方a=b(modm),gcd (a,b,m)=d，则a/d=b/d(mod m/d)a=b(modm) 有时可以写为a+xm=b+ym,x,y为整数同余有周期性amod b = a-(a/b)

2016-11-14 07:44:07 473

原创 bzoj 坑&&坑

mobius反演bzoj 2820 yy的gcdbzoj 3529 sdoi 2014 http://blog.csdn.net/iamzky/article/details/40376189

2016-05-03 10:35:37 1776

原创 Link-Cut-Tree 动态树算法

Link-Cut-Tree 动态树算法总结动态树是一类要求维护森林连通性的算法总称，其中最常用的就是lct (Link-Cut-Tree).lct 支持一下操作链上求和链上求最值链上修改（前三项均可用树链剖分+线段树实现）断开树上的一条边连接两个点，保证连接后仍然是一棵树判断森林连通性说到lct，自然需要引入一些概念：Prefer

2016-03-26 16:24:33 1396 2

原创线性规划之单纯形算法

说到单纯形算法，首先就先从线性规划开始介绍。什么是线性规划？在给定有限的资源和竞争约束情况下，很多问题都可以表述为最大化或最小化某个目标。如果可以把目标指定为某些变量的线性函数，而且如果可以将资源约束指定为这些变量的等式或不等式，则得到了一个线性规划问题。求解线性规划的两种常用格式：标准型和松弛型。标准型中所有的约束都上不等式，而在松弛型中约束都是等式。标准型：最大化

2016-03-15 16:57:30 3111

原创网络流算法总汇(ek,dinic,isap)

网络流算法之EK最基础的网络流算法不停地找增广路进行增广，直到无法增广为止时间复杂度O(VE^2)#include#include#include#includeusing namespace std;int maxdata=0x7fffffff;int capacity[200][200],c[1000][1000];//c[i][j]保存初值，因为每次计算都

2016-02-18 10:01:08 1983

原创 bsgs算法

bsgs算法bsgs算法，又称大小步算法（某大神称拔山盖世算法）。主要用来解决 A^x=B(mod C)(C是质数)，都是整数，已知A、B、C求x。（poj 2417 Discrete Logging）具体步骤如下：先把x=i*m-j，其中m=ceil(sqrt(C))，（ceil是向上取整）。这样原式就变为A^(i*m-j)=B(mod C)，再变为A^j

2016-02-18 09:29:36 37620 10

week13作业E-TT的神秘任务3题目大意给定一个环，A[1],A[2],A[3],…,A[n]A[1], A[2], A[3], … , A[n]A[1],A[2],A[3],…,A[n]，其中A[1]A[1]A[1] 的左边是 A[n]A[n]A[n]。要求从环上找出一段长度不超过 KKK 的连续序列，使其和最大。题解#include<iostream>#include<cstdio>#include<algorithm>#define N 2000

2020-06-04 16:56:34 436

原创 week15作业+CSP-M4

week15作业C-ZJM与纸条题目大意输入n组字符串，求串1在串2中的出现次数。题解——poj 3461 OulipoCSP-M4C-宇宙狗的危机题目大意给出一个升序序列，问该序列能否构成一棵二叉搜索树且任意树边相连的两个节点的gcd都超过1题解#include<iostream>#include<cstdio>#include<cstring>#define N 703using namespace std;int a[N],pd[

2020-06-04 15:24:50 398

原创 week11-12作业+CSP-M3+月模拟题

week11作业F-东东开车了题目大意车内提供了 n 张CD唱片，已知东东开车的时间是 n 分钟，找到最能消磨时间的唱片数量，并按使用顺序输出答案假设:CD数量不超过20张没有一张CD唱片超过 N 分钟每张唱片只能听一次（且如果开始听则必须听完）唱片的播放长度为整数N 也是整数题解背包DPf[i]f[i]f[i]表示能否恰好i分钟g[i]g[i]g[i]表示恰好i分钟所选择的最后一张CD的编号然后就可以根据ggg数组倒推找到答案另外这道题因为CD的数量很少，所以其实可以直接暴力

2020-05-13 15:38:14 414

原创 week9-10作业+week10限时模拟+月模拟题

week9作业A-咕咕东的目录管理器题目大意命令类型实现说明MKDIR s操作在当前目录下创建一个子目录 s，s 是一个字符串创建成功输出 “OK”；若当前目录下已有该子目录则输出 “ERR”RM s操作在当前目录下删除子目录 s，s 是一个字符串删除成功输出 “OK”；若当前目录下该子目录不存在则输出 “ERR”CD s操作进入一个子目录...

2020-04-29 14:33:16 280

原创 week7-8作业+CSP-M2

week7作业B-TT的旅行日记题目大意题解#include<cstdio>#include<cstring>#include<queue>#define N 100003#define M 503#define pa pair<int,int>using namespace std;const int inf=1e9;int...

2020-04-15 15:02:17 262

原创 week5-6作业+week6限时模拟+week7月模拟题

week5作业C-平衡字符串题目大意一个长度为 n 的字符串 s，其中仅包含 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符。如果四种字符在字符串中出现次数均为 n/4，则其为一个平衡字符串。现可以将 s 中连续的一段子串替换成相同长度的只包含那四个字符的任意字符串，使其变为一个平衡字符串，问替换子串的最小长度?如果 s 已经平衡则输出0。题解#include<iostrea...

2020-04-02 11:21:47 229

原创 week3-4作业+CSP-M1+week5月模拟题

week3作业C-区间覆盖题目大意题解#include<iostream>#include<cstdio>#include<vector>#include<algorithm>using namespace std;int n,T;struct data{ int l,r;}a[25003];vector<int&gt...

2020-03-19 23:15:34 177

原创 Week2 实验+作业

作业A-maze题目描述一张0/1表示的地图，0表示可以走，1表示不可以走，左上角是入口，右下角是出口，输出入口到出口的最短路题解bfs + 路径记录bfs 的特性可以保证第一次搜索到（x,y）时，此时从（0,0）到（x,y）的路径是最短路径。对于每个点记录一下他的前驱节点（扩展到该点的点），然后就可以通过递归，输出路径。#include<iostream>#inclu...

2020-03-04 15:12:42 269 1

原创省队集训Round3 DAY6

T1题解这道题应该是可以通过组合数直接计算的，但是我不会数学证明，所以就用了一种简单粗暴的方式。 ans=∑2|iC(n,i)∗C(n,n−i)ans=\sum_{2|i} C(n,i)*C(n,n-i) ans=∑2|iC(n,i)2ans=\sum_{2|i} C(n,i)^2 101810^18肯定不能直接枚举，如果要计算的话也需要用到lucas定理。观察发现这题的模数

2017-08-20 11:20:15 1535 1

原创省队集训Round3 DAY5

T1题解考试的时候考虑了两种方法，但是无法处理n%3=1的部分情况。首先n%4==3或n%4==0都可以填成一个两个行的矩阵，先填好前四个，然后四个一循环如果n%3==2或n%3==0，那么先填好前三个，然后三个一循环。剩下的怎么办呢？先把前三个填好，然后剩下的两两一组，每次增加两列一行。如果最后是偶数，那么直接增加两列就可以了。代码#i

2017-08-20 11:19:58 791

原创省队集训Round3 DAY4

T2题解讲序列分成三部分，大根堆，缓冲区s，小根堆。任意时刻保证mid在缓冲区中，并且尽量保证大根堆和小根堆的大小尽量相等。均摊时间复杂度为O(nlogn/s+n)O(nlogn/s+n)代码#include#include#include#include#include#define LL long long #define mod 1000000

2017-08-20 11:19:39 821

原创省队集训Round3 DAY2

T3 题解首先我们需要计算出M。 N为奇数，中间位不受反转的影响(翻转后每一位异或1)，即这一位的位置不会改变，如果反转只可能是0->1。所以我们可以把中间位当成标记位，刚开始编码的时候为0，如果给出的编码中间位为1，那么说明反转过了，需要逆操作后再进行解码,M=2N−1M=2^{N-1} N位偶数，把数列从中间劈开，后一半是前一半反转后的结果，这样的数列如果进行反转操作得到

2017-08-20 11:19:08 581

原创省队集训Round3 DAY1

T1 题解大概的思路就是对于每个位置的数，如果他前面比他大的数的个数>=k，那么将他向前移动k位，否则扔到一个数组中。最后对这个数组从小到大排序，然后将数组中的数插入序列中的空位置。为什么这样做是对的，对于前面比他大的数个数大于等于k的数来说，他们是没有机会自己移动的，只可能是他前面比他大的前k个数向后移而使他向前移动。对于小于k的数来说，首先他前面比他大的数会使他向前移动，

2017-08-20 11:18:51 618

原创省队集训Round2 DAY7

T2 题解考虑最暴力的做法，实际上就是枚举选中区间的左右端点，然后用点分判断选出的点构成的合法路径和未选中的点构成的合法路径的大小。如果再优化一点可以，枚举其中一个端点，另一个端点动态的维护，有点类似动态点分的样子。这么做的瓶颈在于枚举端点。首先如果右端点如果右移的话，那么满足条件的区间左端点的位置实际上是单调不降的。如果我们能预处理出某个东西，然后O(1)的判断，那么

2017-08-20 11:18:30 529

原创省队集训Round2 DAY3

T3 题解要求每一个时间每条边只能有一个人经过，每个人在到达终点前的任意时刻都不能停止。那么我们可以二分一个最晚的时间mid,然后建mid层结点，每条有向边x->y从i层的x结点连向i+1层的y结点，容量为1。然后跑最大流如果最后满流，那么说明mid可行，继续减小二分的范围代码#include#include#include#include#include

2017-08-20 11:17:58 489 1

原创省队集训Round2 DAY2

T3 题解这道题以前做过一个静态的，就是树在开始的时候直接建好，后面直接查询。这道题的关键是需要看出集合的构建实际上是一颗树结构，每次就是找到所以点的lca然后新加入的点就是lca的一个新的儿子。对于查询，我们需要对于所有点按照dfs序排序，然后容斥计算答案。一个点的贡献valval就是他到根路径上所有CiC_i的和。所以我们需要用平衡树动态的维护dfs序和每个点的val

2017-08-19 20:36:27 501

原创省队集训Round2 DAY1

T1 题解对于每个位置都可以暴力的找到最右边的一个点使之后的点再异或异或和下降。可以维护一颗主席树，外层表示的是起点，内层表示的是以该点为起点的所以终点的合法区间。每次利用前缀和作差即可。因为是区间操作所以我们标记永久化一下。代码#include#include#include#include#include#define N 100003using

2017-08-19 20:36:10 599

原创省队集训DAY6

T1 题解f[i]表示以字符i结尾的字符串的个数。那么现在加入一个字符产生的贡献就是∑字符集大小i=0f[i]\sum_{i=0}^{字符集大小}f[i]，然后把这个答案赋值给这个字符对应的位置。考虑这么做会不会产生相同的串？假设acbb，考虑插入第一个b的影响会形成ab,cb,acb.那么插入第二个b会形成abb,cbb,acbb发现这些都是新产生的不会与之前的相同，而

2017-08-19 20:35:50 602

原创省队集训DAY5

T1题解因为是本质不同的字符串，所以考虑什么样的串会产生贡献。对于一个字符串，我们使他出现的位置尽可能的考前，就是如果这个位置能从第i个串中匹配一定不会在第i+1个串中匹配。这样最先拼凑出的字符串产生贡献1。如果一个串我们要求本质不同的所有子串，该怎么做？对于原串建立后缀自动机，因为根节点到后缀自动机中的每个节点形成的路径都是一个本质不同的子串，所以我们按照拓扑须的倒叙更新

2017-08-19 20:35:30 632

原创省队集训DAY4

T1 题解将行与列分开考虑，每两个#之间属于一个连通块。对于每个连通块建立节点，如果只从连通块中选取一个点，那么不会产生相互攻击的棋子。选取第2个点的时候会产生1的贡献，选取第三个点的时候会产生2的贡献。。。。行列都是如此，那么S->行所代表的连通块，列代表的连通块->T。对于每个连通块连size条边，每条边的容量为1，费用依次递增。对于每个不是#的位置，一定属于两个连通

2017-08-19 20:35:09 532

原创省队集训DAY3

T1题解一共要使用六根木棍，那么分割的方法就两种{1,1,1,3},{1,1,2,2} 那么关键就是要计算2,3的数量。 cnt1[i]表示每种长度的木棍的方案数 cnt2[i]最初表示用不同的木棍拼成长度为i边的方案数，后来表示选出四根木棍构成{2,2}的方案数。 cnt22[i]表示用两个长度相同的不同木棍拼成长度为i的边的方案数。 cnt3[i]表示用三根不同的木棍

2017-08-19 20:34:27 534

原创省队集训DAY2

T1题解假设我们枚举数列{ai}中长度为len的区间，那么如何判断两个数列可以匹配呢？对于提取的数列从小到大排序，{bi}从大到小排序，然后两两配对，如果所有的都满足>=h>=h，那么就可以匹配。应该算是贪心吧。这样做的时间复杂度是O(n∗len∗loglen)O(n*len*\log len) 还是上面的思想，我们如何快速判断呢？假设我们确定了{ai}提取出的区间数

2017-08-19 20:34:06 579

原创 [校内互测]20170402

T1 题解因为有限制的商店比较少，且有限制的商店的最高总消费是90000 所以我们考虑对有限制的商店看成是每个组有wi个物品体积是1…wi的多重背包问题。 f[i]表示的是总体积是i的方案数。需要先枚举每个物品，在倒序枚举总体积，然后枚举当前物品选取的体积。这样子会TLE，所以我们需要前缀和优化一下，减去枚举当前物品选取的体积的那一层。那么剩下的都是无限制的商店，可以

2017-08-19 20:32:25 560

原创 FJWC2017 Day3 T2 recollection （后缀自动机+线段树合并）

题目描述传送门题目大意：现在有一棵n个节点的树,点的编号是1到n,1号点是根节点,每条边上有一个字符（用不大于300的非负整数表示）,且对于任意的一个点u,e:u→v(u=father[v])e:u→v(u=father[v])上的字符互不相同。定义r(u)为从节点u到根节点的路径上的字符组成的字符串。两个节点u,v的相似度f(u,v)定义如下： f(u,v)=Lcp(r(

2017-08-19 20:32:05 1700

原创 FJWC2017DAY1题解

T1 矩阵填数题目描述传送门给定一个h∗w的矩阵,矩阵的行编号从上到下依次为1..h，列编号从左到右依次1..w。在这个矩阵中你需要在每个格子中填入1..m中的某个数。给这个矩阵填数的时候有一些限制，给定n个该矩阵的子矩阵,以及该子矩阵的最大值v,要求你所填的方案满足该子矩阵的最大值为v。现在,你的任务是求出有多少种填数的方案满足n个限制。两种方案是不一样的当

2017-08-19 20:31:30 1004

原创 Codeforces 311E. Biologist （最小割）

题目描述传送门题目大意：有n个已经有初值的0/1变量，改变一个变量需要vi的花费。有m个需求，要求某个集合的变量均为0/1，满足需求得到wi的收益，对于某些集合不满足时需要付出额外的代价g。求最大收益。题解最小割。与源点S相连表示选择的值为0，与汇点T相连表示选择的值为1. S->xix_i xix_i初值为0，容量为viv_i ,割掉这条边表示把值变成1，会增加viv_i的花费。

2017-07-06 20:03:18 1023

原创 bzoj 4487: [Jsoi2015]染色问题（容斥原理+组合数学）

题目描述传送门题目大意：棋盘是一个n×m的矩形，分成n行m列共n*m个小方格。现在萌萌和南南有C种不同颜色的颜料，他们希望把棋盘用这些颜料染色，并满足以下规定： 1. 棋盘的每一个小方格既可以染色（染成C种颜色中的一种），也可以不染色。 2. 棋盘的每一行至少有一个小方格被染色。 3. 棋盘的每一列至少有一个小方格被染色。 4. 种颜色都在棋盘上出现至少一次。题解枚举至少

2017-07-06 07:21:41 2257

原创 bzoj 2007: [Noi2010]海拔（最短路）

题目描述传送门题解首先图中只需要0/1两种高度，并且如果按照高度分类，可以把图分成两个连通块，与左上角在同一连通块的全部为0。那么其实我们就是要求一个最小割，将图分成两部分。但是这道题如果直接跑最小割太慢了，所以我们利用平面图转对偶图，然后直接求最短路即可。有向图转对偶图，其实就是将每条有向边逆时针旋转90度。代码#include<iostream>#include<cstdio>#

2017-07-04 21:25:28 369

原创 bzoj 1799: [Ahoi2009]self 同类分布（数位DP）

题目描述传送门题目大意：给出a,b，求出[a,b]中各位数字之和能整除原数的数的个数。题解枚举数位和sum,然后用数位DP计算。 f[i][j][k][0/1]f[i][j][k][0/1]表示到第i位数位和为j，在模sum意义下的余数为k，是否卡上界的数的个数。 ans=∑18∗9i=1f[cnt][sum][0][0]+f[cnt][sum][0][1]，cnt表示最高位的位数ans=\su

2017-06-29 21:00:21 520

原创 bzoj 2743: [HEOI2012]采花（树状数组）

题目描述传送门题目大意：求区间中出现次数超过1的数的个数题解做法与HH的项链类似。区间中出现次数超过1的颜色的个数=区间中出现的颜色数-区间中出现次数恰好为1的颜色数。将询问区间按照右端点排序。一次加入每个位置的贡献。第一个树状数组中，只有每个颜色最靠右的位置贡献为1。第二个树状数组中，每个颜色最靠右的位置贡献为1，他的前驱贡献为-1 每次区间查询即可。代码#include<ios

2017-06-29 18:02:34 331

原创 bzoj 4554: [Tjoi2016&Heoi2016]游戏（最大流）

题目描述传送门题解对于每行每列以#为界限，分成好几个连通块，同一连通块中的点只能选取一个。位置都只能属于一个连通块。 s->列的连通块，容量为1 行的连通块->T ，容量为1 每个空地从他所属的列连通块->行连通块。然后求最大流即可。代码#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>

2017-06-29 16:54:45 404

原创 bzoj 4197: [Noi2015]寿司晚宴（状压DP）

题目描述传送门题目大意：给出2..n，共n-1个数，要求选出两个集合，是两个集合中的数两两互质。求方案数。题解首先考虑暴力DP。对于所有的数进行质因数分解，然后用f[x][y]f[x][y]表示第一个集合选中的质因子的状态为x，第二个集合选中的质因子的状态为y。只有(x and y)=0时方案才合法。但是500以内的质因子有很多，所有考虑减少质因子的数量。对于每个数来说超过sqrt(n)sq

2017-06-29 16:16:36 374

空空如也

空空如也