- 博客(202)
- 资源 (49)
- 收藏
- 关注
RSS订阅
转载 积性函数
原文：http://blog.csdn.net/skywalkert/article/details/50500009 以下是本人整理~一些函数定义： 元函数e(n)=[n=1]e(n)=[n=1]，狄利克雷卷积的乘法单位元，完全积性。 恒等函数I(n)=1I(n)=1，完全积性。 单位函数id(n)=nid(n)=n，完全积性。 幂函数idk(n)=nkid^k(n)=n^k，完全积性。
2017-04-08 12:58:57
3131
原创 KD-tree
bzoj4520 bzoj2850√Ax+By<CAx+By<C bzoj4605 bzoj2648 bzoj2716插入点时要每插入n√\sqrt n个点重构一次 //查询一个点到另一个点的最短曼哈顿距离 int gdis(node a,node now){ //询问的当前点到搞到的kd-tree的矩形的距离 int res=0;
2017-03-24 12:58:34
548
原创 fft/ntt
题bzoj3160 题意：在一个仅仅含有a,b的字符串里选取一个子序列，使得： 1.位置和字符都关于某条对称轴对称； 2.不能是连续的一段。 分析： 对于每一条对称轴只要求在对称轴两边的对应位置上有相同字符的位置有多少个。 答案就是2len−1−len2^{len}-1-len(减去空串和连续的串) 但这东东它可以是不连续的….. 我们可以将 a b a a b a 1 0
2017-03-18 15:34:12
769
原创 字符串
哈希bzoj3098 bzoj3162 bzoj2085hash+快速幂 题意： Tz养了一群仓鼠，他们都有英文小写的名字，现在Tz想用一个字母序列来表示他们的名字，只要他们的名字是字母序列中的一个子串就算，出现多次可以重复计算。现在Tz想好了要出现多少个名字，请你求出最短的字母序列的长度是多少。分析： 设dis[i][j]dis[i][j]为第i个字符串后接第j个字符串要加多少个字母。
2017-03-08 21:29:43
2112
原创 分块
题cf375D—莫队裸题 bzoj3509 bzoj2821 bzoj3289 bzoj3757 bzoj3781 bzoj2002 bzoj2141 bzoj2821 bzoj2724 bzoj2388 bzoj2120 bzoj2453 bzoj3343 bzoj2038 bzoj1101 bzoj4216 bzoj1086 bzoj3236 bzoj380
2017-02-23 14:28:36
646
原创 高斯消元
题： bzoj4184 bzoj3168 bzoj4031 bzoj3270 bzoj3601 bzoj3143bzoj4184题意：给出一堆数的插入和删除顺序，询问每一次操作后，选出某些数异或起来的最大值a1a_1^a2a_2^a3a_3^…^ana_n (数的个数≤500000\le 500000)分析：有插入和删除操作不好处理，于是我们尝试经过一波预处理将其转化为只有插入~ 显
2017-02-20 21:06:32
507
原创 平面几何
凸包题：bzoj3203 bzoj1185 bzoj1069 bzoj2300 bzoj2961解一：分治法时间复杂度：O(n㏒n)。 思路：应用分治法思想，把一个大问题分成几个结构相同的子问题，把子问题再分成几个更小的子问题……。然后我们就能用递归的方法，分别求这些子问题的解。最后把每个子问题的解“组装”成原来大问题的解。 步骤： 1.把所有的点都放在二维坐标系里面。那么横坐标最
2017-02-04 17:23:02
1150
原创 windows
一、变量 1.HWND（一个窗口句柄变量） 2.POINT （一个坐标，x横坐标，y纵坐标）二、函数 1.FindWindow(NULL,”……窗口名…..”); ——获得该窗口的句柄2.SendMessage(HWND，消息类型，消息附带信息，消息附带信息)； —–给某个窗口传送信息 例如：给某个窗口输入字符’g’ SendMessage(HWND，WM_CHAR， ‘
2017-01-28 00:54:08
459
原创 网络流总结
时间复杂度上限O(n2∗m)O(n^2*m)，n为点数m为边数 网络流24题 搭配飞行员： 最大匹配 魔术球问题： 最少路径覆盖 餐巾纸 : 拆点最小费用最大流 太空飞行计划： 条件依赖最小费用最大流 最小路径覆盖： 最大流（点数-最大匹配数） 圆桌聚餐： 最大流（二分图） 最长递增子序列： 分层图最大流 试题库： 条件依赖最大流 方格取数
2017-01-27 22:00:02
3005
1
原创 左偏树
圈内为权值，蓝色数为距离。 bzoj1367题意：给定一个序列t1,t2,...,tnt_1,t_2,...,t_n，求一个递增序列z1<z2<...<znz_1<z_2<...<z_n， 使得R=|t1−z1|+|t2−z2|+...+|tn−zn|R=|t_1−z_1|+|t_2−z_2|+...+|t_n−z_n|的值最小。本题中，我们只需要求出这个最小的R值。 题解： 若序列t
2017-01-22 21:18:51
499
原创 CDQ分治&&整体二分
CDQ分治bzoj2244bzoj2683bzoj1176bzoj1492bzoj3262bzoj3295bzoj2716hdu5618整体二分xsy1270（bzoj4009）√bzoj2738√bzoj2527√bzoj3110√(注意开long long)poj2104√
2017-01-09 20:24:27
1154
原创 link-cut-tree
注意： ①左父亲右儿子！！每棵splay中的点左子树的深度都比当前点小，右节点的深度都比当前节点的深度大。 题： xsy1173(YES) 一个朴素的想法就是暴力加入区间中的每一条边。 对于加入的一条边，它可能将两个联通块连起来，也可能没有任何贡献。 定义一个c[]，c[x]=1就是有贡献，c[x]=0为没有贡献。 对于没有贡献的情况我们将链中编号最小的边删去，将其在c[]中变为0，强
2016-12-18 21:19:42
752
原创 莫比乌斯反演
莫比乌斯函数定义μ(n)={(−1)m0,,p1,p2...pm=1∃k|pk>1 \mu(n)=\left\{\begin{aligned}&(-1)^m&, & p1,p2...pm=1\\&0 &,&\exists k|pk>1\\\end{aligned}\right.性质1（积性函数）μ(ab)=μ(a)∗μ(b)|gcd(a,b)=1\mu(ab)=\mu(a)*\mu(b)
2016-11-25 10:17:05
454
原创 数论
重要知识点1.最大公约数ll gcd(ll x,ll y){ if (!x || !y) return x+y; if (x%y==0) return y; return gcd(y,x%y);}2.扩展欧几里得int exgcd(int a,int b,int &x,int &y){ if (b==0) { x=1,y=0;
2016-11-02 16:48:39
783
原创 数位dp
bzoj1833 bzoj3780 bzoj3652 bzoj3598 bzoj1026 bzoj2757 bzoj3131 bzoj1902 bzoj3209 bzoj4513 bzoj3679 bzoj4521 bzoj3329 bzoj3530 bzoj1183
2017-07-06 16:09:52
516
原创 xsy1025 link-cut-tree+线段树
题意：分析： 代码：#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=200100;typedef long long ll;int fa[N],c[N][2],rev[N],q[N];int dep[N],a[N][21],h[N],w[N],lst[N],tmp[N
2017-05-27 19:13:52
587
原创 日常
字符串HashKMP后缀数组AC自动机后缀自动机Trie扩展KMPManacher回文自动机最小表示法sunday算法后缀平衡树图论拓扑排序最短路生成树tarjan一类的问题2-SAT网络流匈牙利几何凸包三角剖分半平面交旋转卡壳动态规划数位dp概率、期望dp树形dp状压dp插头dp斜率优化，四边形不等式优化，单调队列优化矩阵快速幂优化数学离散对数积性函数高斯消元FFT/NTT莫比乌斯反演自适应 si
2017-04-27 20:02:38
698
原创 2-SAT
一坨题bzoj1997 bzoj2199 bzoj1823 bzoj4078poj2723 题意： 有2*n把钥匙分成n组，每组两个钥匙如果选择了一把另一把就会消失。有m个门，每个门上有两把锁，只要打开一把锁就能打开门，要打开第i+1个门必须先打开第i个门。 求最多能打开多少门。poj2749 题意: 好像是平面上有两个点s1s_1和s2s_2，这两个点是连在一起的，然后给了n个点，
2017-04-18 17:22:47
933
原创 数论杂题
orz链接杂题：1.hdu1717题意：将小数化为分数（小数可为循环小数和不循环的普通小数） [题解]2.hdu1452题意：输入x，求2004^x的所有因子的和，结果对29取余。题解： 2004=22∗3∗1672004=2^2*3*167 2004x=22x∗3x∗167x2004^x=2^{2x}*3^x*167^x ∴2004x2004
2017-04-18 11:06:18
793
原创 矩阵乘法
xsy2041 bzoj4002 题意： ⌊(b+d√2)n⌋ mod 7528443412579576937\lfloor(\frac{b+\sqrt{d}}{2})^n\rfloor~~mod~~7528443412579576937分析： 构造数列an=(b+d√2)n+(b−d√2)na_n=(\frac{b+\sqrt{d}}{2})^n+(\frac{b-\sqrt{d}}{
2017-03-17 16:33:19
1702
转载 类欧几里得
【xsy2126】超级绵羊异或 类欧几里德算法题意分析 根据位运算的位独立性，我们逐位考虑当前位的异或值，即分析每一位的个数是有奇数个，还是偶数个。 我们从最后一位开始进行分析。答案即为 ∑i=0n−1((bi+a)mod2)mod2=(∑i=0n−1bi+a)mod2\sum_{i=0}^{n-1}((bi+a)\mod 2)\mod 2=(\sum_{i=0}^{n-1}bi+a)\m
2017-03-14 19:16:22
658
转载 如何调试fft与ntt
FFT(快速傅里叶变换)/NTT(数论变换)是卷积运算常见而实用的优化但是FFT/NTT的处理过程并不像暴力运算(差不多是多项式乘法)那样能够直观地反映卷积结果的实时变化。因此在使用FFT时将会或多或少地加大调试的难度。如果调试程序时直接跟踪变量，每步手算结果比对，不仅会耽误大量时间，而且效果可能并不理想。直接肉眼查错效率可能也不太高。但也正由于FFT的特点，实际上也有一些很方便而实用的调试方法，能
2017-03-11 11:48:50
781
原创 后缀自动机
应用简便起见，我们假设字母表的大小k为常数。存在性查询问题.给定文本T，询问格式如下：给定字符串P，问P是否是T的子串。复杂度要求.预处理O(length(T))，每次询问O(P)。算法.我们对文本T用O(length(T))建立后缀自动机。现在回答单次询问。假设状态——变量v，最初是初始状态T_0.我们沿字符串P给出的路径走，因此从当前状态经转移来到新的状态v。如果在某时刻，当前状态没有要求字符的
2017-03-10 20:00:55
677
转载 sunday算法
假设我们有如下字符串： A = “LESSONS TEARNED IN SOFTWARE TE”; B = “SOFTWARE”; Sunday算法的大致原理是： 先从左到右逐个字符比较，以我们的字符串为例： 开始的时候，我们让i = 0, 指向A的第一个字符; j = 0 指向B的第一个字符，分别为”L”和”S”，不等；这个时候，Sunday算法要求，找到位于A字串中位于B字符串后面的第
2017-03-09 10:38:52
675
原创 树链剖分
题bzoj3924YES bzoj4034YES bzoj1576YES bzoj3626YES神转化 bzoj2325 bzoj3694YES bzoj1146二分+树链剖分+线段树套平衡树 bzoj3531YES bzoj1984YES bzoj2243YES bzoj1036YES poj3237YES//bzoj3531#include<cstdio>#includ
2017-03-02 18:27:38
407
原创 斯特林数
题：bzoj4555题解 bzoj2159题解 bzoj3000 hdu4676 hdu3625 poj1671 poj1430 poj1423第一类斯特林数s(p,k)的一个的组合学解释是：将p个物体排成k个非空循环排列的方法数。s(p,k)的递推公式： s(p,k)=(p−1)∗s(p−1,k)+s(p−1,k−1),1≥k≥p−1s(p,k)=(p-1)*s(p-1,k)+s
2017-02-26 12:06:19
558
原创 bzoj2159
【题意】 给出一棵nn个点的树，求对于每个点ii的d(i)d(i)值。d(i)=∑i≠x1≤x≤ndist(x,i)kd(i) = \sum_{1\leq x \leq n}^{i \not= x}dist(x, i)^{k}数据范围：1≤n≤50000,1≤k≤1501 \leq n \leq 50000, 1\leq k \leq 150【题解】这题非常的神……首先我们发现，xnx^n能用St
2017-02-26 08:16:38
701
原创 dfs序
题： bzoj3779——lct+线段树+dfs序 bzoj4034——树剖….. bzoj3991——set+dfs序 bzoj3881——fail树+dfs序/树剖 bzoj3786——lct特殊姿势 bzoj2819——博弈+dfs序
2017-02-22 08:05:20
465
原创 bzoj3779 lct+线段树+dfs序
题意：有一棵n个节点的树，每个节点有一个颜色，初始每个节点颜色不相同，且以节点1为根。定义每个点的权值为这个点到根的路径上不同颜色的个数。现在进行m次操作，每次操作为下列三种之一： 1、将x到当前根路径上的所有点染成一种新的颜色； 2、将x到当前根路径上的所有点染成一种新的颜色，并且把这个点设为新的根； 3、查询以x为根的子树中所有点权值的平均值。分析：首先我们观察到：操作一每次修改都是
2017-02-21 22:05:07
473
原创 poi2007
一、旅游景点atr题：Description FGD想从成都去上海旅游。在旅途中他希望经过一些城市并在那里欣赏风景，品尝风味小吃或者做其他的有趣 的事情。经过这些城市的顺序不是完全随意的，比如说FGD不希望在刚吃过一顿大餐之后立刻去下一个城市登山， 而是希望去另外什么地方喝下午茶。幸运的是,FGD的旅程不是既定的，他可以在某些旅行方案之间进行选择。由于 FGD非常讨厌乘车的颠簸，他希望在满足
2017-02-13 07:24:30
813
原创 倍增
一、树上倍增 从一步一步跳变为一跳“一大步” int getlca(int x,int y){ if (dep[x]<dep[y]) swap(x,y); for (int i=20;i>=0;i--)//跳到同一深度 if ((dep[x]-dep[y])&(1<<i)) x=fa[x][i]; if (x==y)
2017-02-04 15:44:15
377
原创 poj一句话题解
1000:a+b 1001:高精度乘法，小数点最后加就好了 1002:模拟，将字符串转换成数字排序 1003:求出使得 不等式 1/2 + 1/3 + … + 1/(n+1) >= c 成立的最小 n 1004:求平均数 1005:列式解方程 1006:中国剩余定理 1007:排序模拟 1008:模拟 1009:模拟 1010:dfs+剪枝 1011:dfs+剪枝 1012:
2017-01-31 12:20:44
326
小z的袜子（数据）
2016-01-30
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人