_Gion-CSDN博客

原创「置顶」OI 注意事项

二元组如果需要二维比较就使用pairpairpair，不需要就手写结构体，不然效率会差很多平衡树输出之前记得pushdownpushdownpushdown todo

2018-09-22 12:42:40 243

原创「置顶」NOI To do list

未学习、待重学及待刷题的知识点Treap / Splay / 替罪羊树最大流2-SAT匈牙利算法二分图最大匹配拉格朗日插值FFT 快速傅里叶变换NTT 数论变换Miller-RabinPollard RhoBSGSexBSGS *exLucas *生成函数Burnside引理Polya定理crtexcrt容斥 *概率期望 *高斯消元法 *Matrix...

2018-08-29 21:01:40 476

原创博客废弃通知

本博客废弃了，搬到了cnblogs。这里之前写的垃圾东西实在看不下去都有点想删掉了（2333），但是好像访问数还挺多的，就留着做纪念吧。博客园地址

2019-10-23 13:49:00 335

原创「UVA 11475」Extend to Palindrome「后缀数组」

这题算是经典题了，可以用KMP/Manacher/SAKMP/Manacher/SAKMP/Manacher/SA做这里丢上一个代码最长的做法：后缀数组做法是将原串sss翻转得到s′s&#x27;s′,将s′s&#x27;s′接到sss后做SASASA这样就会有一个很好的性质：我们可以快速求出以某个点或某两个点为中心的最长回文串长度。以xxx为中心的答案为LCP(suffix...

2018-12-05 11:54:53 350

原创「JLOI 2015」城池攻占「左偏树」

对每个点维护一个左偏树（小根可并堆），一开始把骑士插入然后dfs，从下往上把骑士送上去每次在取左偏树的堆顶找死亡骑士，不断pop，直到堆顶骑士不会死亡为止然后最后在根上打修改懒标记（加或乘）#include &lt;cstdio&gt;#include &lt;vector&gt;using namespace std;typedef long long LL;const in...

2018-10-28 22:14:09 361

原创「BZOJ 1251」序列终结者「Splay」

像线段树那样，维护一个懒标记就行#include <algorithm>#include <cstdio>using namespace std;namespace Splay { const int N = 1e5 + 10; int root, ch[N][2], sz[N], fa[N]; int tag[N], mx[N], va[N]; bool...

2018-10-28 17:21:19 228

原创「SDOI 2015」约数个数和「莫比乌斯反演」

题意设d(x)d(x)d(x)为xxx的约数个数，求∑i=1n∑j=1md(ij)\sum_{i=1}^{n}\sum_{j=1}^{m}d(ij)∑i=1n∑j=1md(ij)。题解首先有个公式：d(ij)=∑x∣i∑y∣j[gcd(x,y)=1]d(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]d(ij)=x∣i∑y∣j∑[gcd(x,y)=1]OIO...

2018-10-27 10:41:13 380

「HNOI 2008」玩具装箱TOY首先O(n2)O(n^2)O(n2)做法是显然的，使用前缀和然后暴力枚举转移dp[0] = 0;for(int i = 1; i &amp;amp;lt;= n; i ++) { dp[i] = 1LL &amp;amp;lt;&amp;amp;lt; 62; for(int j = 0; j &amp;amp;lt; i; j ++) { LL x = i - (j + 1) +

2018-10-26 21:28:25 283

原创「NOIP 2015」运输计划「树链剖分」

这题就没往二分上想，直接使用线段树+树剖大暴力做法就是枚举每一条边(u,fa[u],w)(u, fa[u], w)(u,fa[u],w)，求出删除这条边后的答案。假设已经求出了两个数组past[u],nopast[u]past[u], nopast[u]past[u],nopast[u]分别表示经过u的路径长度最大值, 不过u的路径长度最大值那么删除边(u,fa[u],w)(u, fa[u]...

2018-10-26 13:13:27 306

原创「学习笔记」网络流题单

[ZJOI 2009][\text{ZJOI 2009}][ZJOI 2009] 狼和羊的故事：注意题意是说把狼和羊完全分开，不能连通。可以看出是最小割，暴力把所有相邻结点建边，把SSS连到羊，狼连到TTT，Dinic\text{Dinic}Dinic即可.P3254\text{P3254}P3254 圆桌问题：每个单位向每个桌子连容量为111的边，SSS向单位连单位...

2018-10-17 13:18:09 231

原创「学习笔记」容斥原理及其应用

错排问题HDU 1465#include &amp;amp;amp;amp;lt;cstdio&amp;amp;amp;amp;gt;long long dp[21];int main() { dp[0] = dp[1] = 0; for(int i = 2; i &amp;amp;amp;amp;lt;= 20; i ++) dp[i] = i * 1ll * dp[i - 1] + ((i &amp;a

2018-10-03 15:54:27 497

原创「ZJOI 2005」午餐「DP」

题目传送门题解贪心+DP\text{DP}DP，思想巧妙。首先确定先后顺序，不确定站在哪边。贪心策略是按吃饭时间从大到小排序，证明如下：设按某个顺序站，第AAA个人打饭时间为aaa，吃饭时间为bbb；第B(A&amp;lt;B)B(A&amp;lt;B)B(A&lt;B)人打饭时间为ccc，吃饭时间为ddd；b&amp;lt;db &amp;lt; db&lt;dt1=max(a+b,a...

2018-10-02 21:30:06 165

原创「学习笔记」C++与C++11的语法技巧

随机打乱序列与生成随机数。#include <algorithm> //random_shuffle#include <cstdio>#include <random>using namespace std;int main() { int a[] = {0, 1, 2, 3, 4, 5}, n = 5; srand(1e7 + 7); rand...

2018-10-02 12:23:06 259

原创「学习笔记」Fast Fourier Transform 快速傅里叶变换

快速傅里叶变换（Fast&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;ThickSpace;Fourier&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;ThickSpace;Transform,FFTFast \;Fourier \;Transform,FFTFastFourierTransform,FFT ）是一种能在O(nlog⁡n)O(n \log n)O(nlogn)的时间内完成多项式乘法的算法，

2018-10-01 21:29:11 3613

原创「SCOI 2010」连续攻击游戏「并查集」

题目传送门题解巧妙的并查集做法。把每个装备的两个属性a,ba,ba,b看成边(a,b)(a,b)(a,b)，会形成一些连通块如果连通块大小为kkk，无环（树），答案是k−1k-1k−1，有环就是kkk考虑如何合并两个连通块。合并并查集x,yx,yx,y，若x̸=yx\not =yx̸=y，把数字小的父亲设为数字大的，给数字小的打上visvisvis标记。若x=yx=yx=y，给树根打...

2018-09-30 22:38:53 464

原创「SCOI 2014」方伯伯的 OJ「动态开点线段树」

题目传送门备注：洛谷，2018/9/26，此题题面有误，见讨论。题解动态开点线段树。线段树的叶子的结点有个值，vvv，它表示这个位置上的人编号是多少。我们记录两个变量lb,rblb,rblb,rb表示当前位置的最小值和最大值。每次把一个人提到第一时，把他从原位置删除，放到lb−1lb-1lb−1；提到最后也是一样。询问的时候就在线段树上询问从左往右第kkk个位置上的人的编号，因此每...

2018-09-26 19:25:07 218

原创「BJWC 2012」冻结「分层图+最短路」

题目传送门题解分层图是一种不错的技巧。对于这题来说，把图复制成k+1k+1k+1份，分别命名为0,1,...,k0,1,...,k0,1,...,k层。第iii层的含义就是已经用了iii次加速魔法。读入一条边，每层连双向边，层与层之间，底层往上层连权值减半的单向边，单向意味着只能上不能下。然后答案就是跑最短路然后取k+1k+1k+1层的dis(n)dis(n)dis(n)最小值.#inc...

2018-09-24 13:38:50 216

原创「USACO13OPEN」Photo「单调队列」

题目传送门题解看起来是差分约束，但是USACO出题人又卡SPFA了！这里有一种巧妙的DP方法。l[i]l[i]l[i] : 完全在iii左边的区间，左端点的最大值 (不能不放)r[i]r[i]r[i] : 包含iii的区间中，左端点的最小值−1-1−1 (只能放111个)f[i]f[i]f[i] : iii必须放，最多能放多少个.#include &amp;lt;cstdio&amp;gt;#in...

2018-09-23 15:35:56 321

原创「学习笔记」初赛中的排序与主定理

排序稳定性的含义：如果数组中存在两个不同位置元素x=yx=yx=y，排完序后原来的x,yx,yx,y的相对位置发生了改变，则称这种排序是不稳定的（发生无意义的变换）.排序算法最坏复杂度平均复杂度是否稳定插入排序O(n2)O(n^2)O(n2)O(n2)O(n^2)O(n2)稳定选择排序O(n2)O(n^2)O(n2)O(n2)O(n^2)O(n2)不稳...

2018-09-22 16:24:53 341

原创「清华集训 2012」模积和「数论分块」

题目传送门题意∑i=1n∑j=1m(n&amp;ThickSpace;mod&amp;ThickSpace;i)(m&amp;ThickSpace;mod&amp;ThickSpace;j),i≠j\sum_{i=1}^{n}\sum_{j=1}^{m} (n \;mod \;i)(m \;mod \;j),i\ne ji=1∑nj=1∑m(nmodi)(mmodj),i̸=j题解先...

2018-09-21 13:26:52 275

原创「APIO 2015」八邻旁之桥「权值线段树」

题目传送门题解对于在河同侧的，直接累加进答案。剩下的直接看做mmm条线段li,rili,ril_i,r_i（因为桥宽度为111，最后加上mmm就行）.然后当k=1k=1k=1时：就是找到一个ppp来最小化∑mi=1abs(li−p)+abs(ri−p)∑i=1mabs(li−p)+abs(ri−p)\sum_{i=1}^{m} abs(l_i-p)+abs(r_i-p)直接...

2018-09-16 09:36:47 316

原创「学习笔记」Splay Tree 伸展树

Splay是一种能快速分裂与合并的平衡树，常用于解决某些序列问题.rotate : 单旋先理解一下右旋，左旋与右旋是完全对称的操作.如图，右旋的作用就是一个结点是左儿子，它旋转到父亲的位置，并且可以发现旋转后依然满足二叉搜索树的性质双旋双旋就是一次往上旋两层，保证复杂度，而单旋不保证.定义dir(x)dir(x)dir(x)表示xxx是左子树还是右子树。如果dir(...

2018-09-14 22:04:36 215

原创「学习笔记」虚树

虚树就是一棵树上选一些点，它们之间形成的树形路径就是虚树。虚树也就是把一些与操作无关的点略去，节省复杂度直接上例题~[SDOI2015] 寻宝游戏题目传送门可以发现是这些有宝藏的关键点形成的树，路径权值和的两倍。我们可以按dfs序从小到大走一遍，就是答案了定义dfs序上的前驱指的是dfs比它小的点中dfs序最大的点。如果没有，就是dfs序最大的那个点（尾部）。后继同理。...

2018-09-08 16:52:21 270

原创「SPOJ 5971」LCMSUM

题目传送门题意求∑ni=1lcm(i,n)∑i=1nlcm(i,n)\sum_{i=1}^{n} lcm(i,n)，TTT组询问1≤T≤3×105,1≤n≤1061≤T≤3×105,1≤n≤1061\leq T \leq 3\times 10^5, 1 \leq n \leq 10^6 题解∑i=1nlcm(i,n)∑i=1nlcm(i,n)\sum_{i=1}^{n}...

2018-08-31 21:33:49 268

原创「BZOJ 2154」Crash的数字表格「莫比乌斯反演」

题目传送门题意求∑ni=1∑mj=1lcm(i,j)∑i=1n∑j=1mlcm(i,j)\sum_{i=1}^{n} \sum_{j=1}^{m} lcm(i,j)，对201010092010100920101009取模题解∑ni=1∑mj=1lcm(i,j)∑i=1n∑j=1mlcm(i,j)\sum_{i=1}^{n} \sum_{j=1}^{m} lcm(i,j)=∑...

2018-08-30 16:13:41 235

原创「POI2007」ZAP-Queries「莫比乌斯反演」

题目传送门题意T组询问求，∑i=1a∑j=1b[gcd(i,j)=d]∑i=1a∑j=1b[gcd(i,j)=d]\sum_{i=1}^{a} \sum_{j=1}^{b} [gcd(i, j)=d]，T,a,b,d≤5×104T,a,b,d≤5×104T,a,b,d\leq 5 \times 10^4题解不妨设a≤ba≤ba \leq b.∑i=1a∑j=1b[gcd(i...

2018-08-29 16:10:11 211

原创「学习笔记」矩阵乘法与矩阵快速幂

矩阵乘法定义一个n×mn×mn \times m矩阵AAA乘上一个m×pm×pm\times p的矩阵BBB，得到一个n×pn×pn \times p的矩阵CCC：Ci,j=∑mk=1Ai,k×Bk,j(1≤i≤n,1≤j≤p)Ci,j=∑k=1mAi,k×Bk,j(1≤i≤n,1≤j≤p)C_{i,j}=\sum_{k=1}^{m} A_{i,k} \times B_{k,j}\...

2018-08-28 22:36:13 199

原创「Luogu P2257」YY的GCD「莫比乌斯反演」

题目传送门题意求 ∑ni=1∑mj=1[gcd(i,j)isprime]∑i=1n∑j=1m[gcd(i,j)isprime]\sum_{i=1}^{n} \sum_{j=1}^{m} [gcd(i, j)\;is\;prime]题解不妨设n≤mn≤mn \leq m，推一下式子∑i=1n∑j=1m[gcd(i,j)isprime]∑i=1n∑j=1m[gcd(i,j)ispr...

2018-08-28 16:34:09 218

原创「NOI 2018」屠龙勇士「扩展中国剩余定理」

题目传送门题解首先，每条龙使用哪把剑是确定的，我们可以根据题意使用multisetmultisetmultiset（可重集）求出.#include &lt;iostream&gt;#include &lt;cstdio&gt;#include &lt;cmath&gt;#include &lt;set&gt;using namespace std;#

2018-08-28 15:49:52 271

原创「ZJOI 2008」骑士「基环树DP」

BZOJ 题目传送门 Luogu 题目传送门题意求由基环树组成的森林的最大权独立集，n&amp;lt;=106n&amp;lt;=106nfi,0fi,0f_{i,0}和fi,1fi,1f_{i,1}分别表示在以结点iii为根的子树内，iii选/不选的最大独立集的权值转移：fi,0=∑j∈son(i)max(fj,0,fj,1)fi,0=∑j∈son(i)max(fj,0,fj,1)f_{i,0}=...

2018-08-26 18:00:48 368

原创「学习笔记」BSGS及扩展

离散对数问题：给定求y,z,p,y,z,p,y,z,p,求 yx≡zyx≡zy^x \equiv z (mod(mod(mod p)p)p)的最小整数解.BSGSShank的大步小步算法(Shank’s Baby-Step-Giant-Step Algorithm)这里介绍一种避开求逆元的BSGS（常数小令m=⌈p–√⌉m=⌈p⌉ m = \lceil\sqrt p\rceil，...

2018-08-26 15:49:48 230

原创「学习笔记」泰勒级数

多项式函数是长这样的函数：f(x)=a0+a1x+a2x2+…+anxnf(x)=a0+a1x+a2x2+…+anxnf(x)=a_0+a_1x+a_2x^2+\ldots+a_nx^n它有一个很NiceNiceNice的特点：代人xxx，在O(n)O(n)O(n)的时间内就可以求出f(x)f(x)f(x)，没有任何障碍.但是这样的函数：g(x)=exg(x)=exg(x)...

2018-08-26 15:15:34 747

原创「学习笔记」级数与检验法

Warning：这篇文章都是定理公式若级数∑∞n=1an=S∑n=1∞an=S\sum_{n=1}^{\infty} a_n=S，则说这个级数收敛到SSS。否则说该级数发散。级数1+1+1+…1+1+1+…1+1+1+\ldots的发散的.级数12+14+18+…12+14+18+…\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\ldots是收敛的，收...

2018-08-26 15:09:47 1146

原创「学习笔记」自适应辛普森法

引例计算积分：∫RLcx+dax+bdx∫LRcx+dax+bdx\int_{L}^{R} \frac{cx+d}{ax+b} dx题解其实可以直接求导然后做，然而太弱根本推不出来.于是就可以使用自适应辛普森积分。辛普森（Simpson）公式是牛顿-科特斯公式当n=2时的情形。∫RLf(x)dx≈(R−L)[f(L)+f(R)+4f(mid)]6∫LRf(x)dx≈...

2018-08-26 15:07:24 755

原创「学习笔记」牛顿迭代法

牛顿迭代法（Newton′smethodNewton′smethodNewton's method）一般用于求函数的一个零点。牛顿迭代法牛顿迭代法三个步骤：随机 / 猜一个ppp值求x=px=px=p时的切线，即求导数令p=p=p=切线零点，返回步骤222，重复若干次.即：xn+1=xn−f(xn)f′(xn)xn+1=xn−f(xn)f′(xn)x_{n+1} = x...

2018-08-26 14:51:34 859

原创「学习笔记」基环树

基环树是一种图，它由一个环组成，环上每个点都是一棵树点树根，所以称为基环树。当然，一棵树上连一条边也会变成基环树。下图是一个基环树.基环树一般分成环和树来分别处理（显然环的处理较为麻烦），那首先得找到环.找环大概就是dfs一下，找到一个在此结点之前走过的相邻结点就开始记录环.vector&amp;amp;lt;int&amp;amp;gt; G[MAXN]; //基环树int fa[MAXN]; ...

2018-08-26 14:34:33 9539 3

原创「CF535D」Tavas and Malekas「KMP」

题意一个有小写字母组成的长度为nnn文本串，给出匹配串及匹配的mmm个位置（按顺序给出），求原串有多少种可能.题解可以转化为判定这些匹配点有没有冲突。有冲突就是000，没有冲突就是26k26k26^k，kkk是没有被匹配覆盖的位置个数.显然两个匹配有冲突他们一定有重叠。重叠的一定是匹配串的后缀和前缀。所以假设两个匹配位置他们重叠的部分长度为xxx，我们只需要判断匹配串长度为xxx的...

2018-08-23 16:39:40 230

原创「CF126B」 Password「KMP」

题意在字符串中找一个子串，满足既是前缀也是后缀，还在中间出现过.题解首先预处理出KMPKMPKMP的nextnextnext数组，然后从nextnnextnnext_n开始跳，不停让i=nextii=nextii=next_i。考虑nextnnextnnext_n的含义：前缀等于后缀。每跳一次相当于这个前缀等于后缀的长度减小了。每次枚举的时候使用KMPKMPKMP匹配中间位置，...

2018-08-23 15:07:04 278

原创「Luogu P2398」GCD SUM「莫比乌斯反演」

题目传送门题意求∑ni=1∑nj=1gcd(i,j)∑i=1n∑j=1ngcd(i,j)\sum_{i=1}^{n}\sum_{j=1}^{n} gcd(i,j)，n&lt;=105n&lt;=105n∑i=1n∑j=1ngcd(i,j)∑i=1n∑j=1ngcd(i,j)\sum_{i=1}^{n}\sum_{j=1}^{n} gcd(i,j)=∑d=1n∑i=1n∑j=1n[g...

2018-08-23 14:09:11 192

原创「学习笔记」爬山算法与模拟退火

爬山算法（Hill Climbing ）爬山算法（Hill Climbing ）是一种局部择优的方法，采用启发式方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策。属于人工智能算法的一种。有一些问题，是找全局最大值的。题目所述出自变量与值之间的关系是函数，而这函数图像往往像山的形状，可能有许多局部最大、局部最小。于是“爬山”、“高地”、“山脊”等词形象地表示了算法的作用与函...

2018-08-22 09:50:45 925

空空如也

空空如也