- 博客(194)
- 收藏
- 关注
RSS订阅
原创 数学杂记
记录一些琐碎的数学知识。以下内容重点放在记结论，以便作者复习。慢慢补充吧。最大公约数由公约数的基本性质可得：inline int gcd(int a,int b){return b?gcd(b,a%b):a;}扩展欧几里得求解关于x,yx,yx,y的二元一次方程：ax+by=gcd(a,b)ax+by=gcd(a,b)ax+by=gcd(a,b)当等式右端不是gcd(a,b)gcd(...
2019-11-11 21:09:56
234
原创 基础向模板收集(字符串篇)
KMP模板在循环中，iii表示当前要去匹配第iii位，jjj表示TTT的前jjj位和SSS的前i−1i-1i−1位可以匹配上。现在就看T[j+1]T[j+1]T[j+1]和S[i]S[i]S[i]是否匹配。读入需要判断EOF。#include<bits/stdc++.h>#define VI std::vector<int>#define ll long lon...
2019-11-15 09:40:23
149
原创 基础向模板收集(图论篇)
最短路计数要记录visvisvis数组避免算重。if(dis[v]>dis[u]+W[i]) dis[v]=dis[u]+W[i],num[v]=num[u],Q.push(mp(-dis[v],v));else if(dis[v]==dis[u]+W[i]) num[v]+=num[u];这里必须加elseelseelse，因为上面那个算完之后下面那个就成立了。模板#incl...
2019-11-11 22:02:03
178
原创 HDU6172 Array Challenge
传送门佛辣。推出前几项后可以用BMBMBM算法得出⌊an⌋\lfloor \sqrt{a_n} \rfloor⌊an⌋的最短线性递推式。注意是直接算出来不取模，然后开根，并不是CipollaCipollaCipolla。嗯就是这个东西。。很神奇。它居然可以线性递推。所以要勇敢大胆打表蒙结论啊。#include<bits/stdc++.h>#define ll long...
2019-11-08 20:24:31
161
原创 bzoj4162 shlw loves matrix II
传送门对于一个k∗kk*kk∗k的矩阵AAA，它的特征多项式是一个kkk次多项式。下面我们把多项式的自变量xxx看做一个矩阵。首先我们假设已经求出了特征多项式f(x)f(x)f(x)特征多项式满足：f(A)=0f(A)=0f(A)=0。(Cayley-Hamilton定理)我们令G(x)=xnG(x)=x^nG(x)=xn，那么AnA^nAn即为G(A)G(A)G(A)，也就是要求的东西...
2019-11-07 22:06:26
186
原创 bzoj4161 Shlw loves matrixI
传送门常系数齐次线性递推学习学习了任意模数多项式乘除法O(n2)O(n^2)O(n2)。除法就是手动模拟大除法。需要的东西就是一个转移矩阵AAA的特征多项式。要把AnA^{n}An看做是一个只有一项的nnn次多项式。然后知道初始的那几个就可以推出来了。#include<bits/stdc++.h>#define ll long long#define re regist...
2019-11-07 11:35:36
141
原创 SDOI2017 文本校正
传送门分为6种情况。ABC:ABC:ABC:哈希O(1)O(1)O(1)判断CAB:CAB:CAB:枚举CCC的位置，哈希判断ABABAB，O(n)O(n)O(n)BCA:BCA:BCA:枚举AAA的位置，哈希判断BCBCBC，O(n)O(n)O(n)CBA:CBA:CBA:金策字符串算法选讲如果s=abs=abs=ab，a,ba,ba,b都是回文串，称sss为一个双回文串。引理：如...
2019-11-01 19:19:52
648
原创 NOIp模拟 数对
传送门很神的DPDPDP题。首先要确定一个DPDPDP的顺序保证答案的正确性。对于两个元素，分四种情况讨论它们的关系：如果ai⩽bj and bi<aja_i \leqslant b_j\ and\ b_i < a_jai⩽bj and bi<aj，那么iii必须排在jjj的前面。如果ai>bj and&nb...
2019-10-31 09:56:45
119
原创 NOIp模拟 光线追踪
传送门这种问题考虑怎么一步一步把问题化简。首先可以把一个矩形右边和上面的边都丢掉。和那个speikespeikespeike有点像。然后可以把剩下的横边和竖边独立开来看。如果可以分别求出询问向量所碰到的横和竖的最短距离问题就解决了。取最小距离即可。在对应的角度区间里面更新一下最小的横/纵坐标以及对应的编号即可。查询碰到的最近的竖/横边就是单点查询最小值。于是把角度离散化一下就可以用线段...
2019-10-31 09:21:26
126
原创 NOIp模拟 二叉搜索树
船送门用四边形不等式优化的区间DPDPDP。至于四边形不等式，特征一般都很明显，而且这东西很偏。记结论，然后给决策点打表找规律就行了吧。由决策点的单调性把O(n3)O(n^3)O(n3)优化成O(n2)O(n^2)O(n2)。#include<bits/stdc++.h>#define ll long long#define re register#define cs c...
2019-10-31 09:07:02
170
原创 NOIp2012 开车旅行
传送门以后序列上的问题可以想一想倍增。。sa[i]/sb[i]sa[i]/sb[i]sa[i]/sb[i]记录在iii这个位置让A/BA/BA/B开车到达的点。把AAA和BBB都跳一次称为一轮。dis[i][j]dis[i][j]dis[i][j]表示从iii跳2j2^j2j轮的总路程。pos[i][j]pos[i][j]pos[i][j]表示从iii跳2j2^j2j轮后的位置。dis...
2019-10-28 15:49:40
123
原创 SCOI2018 Numazu 的蜜柑
传送门无解时统计0有多少对。有解时要注意统计值是否相同。dfs时维护的是当前点到根的链上的和。注意快速乘#include<bits/stdc++.h>#include<tr1/unordered_map>#define pll std::pair<ll,ll>#define mp std::make_pair#define ll long lo...
2019-10-27 20:42:43
187
2
原创 NOIP2017 跳房子
传送门几个小细节：中途达到kkk可以直接退出。双端队列是先把后面的元素压进去，再把前面的弹出来，顺序不能反。如果先弹再压，可能会导致后面不合要求的新压进来的没有弹掉。#include<bits/stdc++.h>#define cs const#define re register#define ll long long#define fi first#define...
2019-10-25 13:24:21
212
原创 SCOI2018 TREE
无传送门对于一条实链，记录它从链顶延伸出的最长路径，以及从链底延伸出的最长路径。开一个multisetmultisetmultiset维护虚子树的anslanslansl。一个点的转移就是：从链顶/底出发，不经过这个点？经过这个点穿进虚子树？经过这个点穿到下面去？这三种情况。询问点uuu，就是accessaccessaccess之后uuu成为链底，询问一下它延伸出的最长路径即可。初始化的时...
2019-10-24 20:53:14
327
原创 SCOI2018 pipi酱的日常
无传送门又是拆绝对值的套路。绝对值拆掉后有八种情况，绝对值之和一定是这几个里面最大的。因为∣a+b∣⩾a+b|a+b| \geqslant a+b∣a+b∣⩾a+b，∣a+b∣⩾−a−b|a+b| \geqslant -a-b∣a+b∣⩾−a−b。于是维护一个全局和，维护每个位置连续三位的八种和就完了。pushuppushuppushup写错调了1h1h1h。0皿0#include&l...
2019-10-23 20:47:13
202
原创 woj4764 子矩阵
无传送门枚举上下界，上下界确定后在区间中统计答案。对于这些上下界相同，左右端不同的矩形，可能的贡献对象在每一列的最小值中。记一下每一列的最小值，然后找左边、右边比它小的第一个位置，就可以统计出该列的贡献了。用单调栈维护即可。#include<bits/stdc++.h>#define cs const#define re registercs int N=305;nam...
2019-10-23 14:41:03
130
原创 woj4765 BestJob
无传送门分类讨论k1k1k1和k2k2k2的情况。把相同的字符串染成相同的颜色。然后还要记一下每个串的反串（每一位取反）。pospospos记录每种颜色的一个位置。枚举一下答案是什么再判一下是否可行。写的时候要想清楚下标是颜色还是字符串标号。注意k1=0,k2=0k1=0,k2=0k1=0,k2=0的情况是unsigned long longunsigned\ l...
2019-10-23 13:49:31
99
原创 SDOI2017 序列计数
传送门dp[i][j][0/1]dp[i][j][0/1]dp[i][j][0/1]表示前iii个数的和模ppp余数为jjj，没有质数/有质数。cnt[i]cnt[i]cnt[i]表示111~mmm中模ppp余数为iii的数的个数。pcnt[i]pcnt[i]pcnt[i]表示111~mmm中模ppp余数为iii的质数的个数。下面的数组下标减法为模ppp意义下的。那么dp[i][j][0...
2019-10-22 18:13:47
152
原创 SDOI2017 树点涂色
传送门涂色的操作和accessaccessaccess很像啊，如何用LCTLCTLCT维护这个东西呢。由于每次覆盖的颜色都不同，且是从当前到结点覆盖到根节点。那么如果把颜色相同的一段维护在一条重链上，一个点到根要经过多少虚边也就包含多少颜色。所以用LCTLCTLCT模拟覆盖的过程，用线段树维护即可。虚变实就是子树减，实变虚就是子树加。询问1就是val[x]+val[y]−2∗val[...
2019-10-22 14:25:33
140
原创 SDOI2017 数字表格
传送门f[0]=0,f[1]=1,f[i]=f[i−1]+f[i−2](i⩾2)f[0]=0,f[1]=1,f[i]=f[i-1]+f[i-2](i \geqslant2)f[0]=0,f[1]=1,f[i]=f[i−1]+f[i−2](i⩾2)ans=∏i=1n∏j=1mf[gcd(i,j)]ans=\prod_{i=1}^{n} \prod_{j=1}^{m} {f[gcd(i,j)]}a...
2019-10-21 19:16:23
102
原创 SHOI2012 信用卡凸包
传送门顶点凸包+一个圆周长。#include<bits/stdc++.h>#define re register#define cs constcs int N=4e4+10;cs double eps=1e-8,oo=1e9,pi=acos(-1);struct Grid{ double x,y; Grid(double X=0,double Y=0){x=X,y=...
2019-10-21 16:26:54
171
原创 SDOI2016 模式字符串
传送门写法很显然，问题是怎么写。。哈希是把长度为1~n的全部哈希出来，因为树的深度不超过nnn嘛。哈希出左到右和右到左两个方向。把模式串不断重复即可。然后就好写了。注意一个去掉k∗mk*mk∗m的长度为ddd的链，需要匹配的是长度为m−d+1m-d+1m−d+1的。因为当前的重心相当于是一个共用的字符。#include<bits/stdc++.h>#define cs co...
2019-10-21 12:06:17
133
原创 SDOI2016 排列计数
传送门为什么又是结论题。令D[n]D[n]D[n]为长度为nnn的错排方案数。考虑增量法求D[n]D[n]D[n]。假设已知D[1]D[1]D[1]~D[n−1]D[n-1]D[n−1]：现在令所有元素有序排列好，即a[i]=ia[i]=ia[i]=i。第nnn个元素可以选择前n−1n-1n−1个位置中的任意一个放进去，假设选了某个位置kkk，那么这个位置的元素kkk就被挤出来了。如果...
2019-10-19 16:09:49
185
原创 SDOI2016 游戏
传送门仔细一看：每个节点动态维护半平面交？？一搜，原来是李超线段树。把原树剖分一下，就转化为二维平面内如下操作：①加上一条线段。②询问一段区间内的最小值。该线段树利用了标记永久化的思想。每个区间[l,r][l,r][l,r]只保留一条线段：k∗mid+bk*mid+bk∗mid+b最小的那条。也就是与直线x=midx=midx=mid相交的最下面的一条。插入线段的时候根据交点维护这个...
2019-10-18 19:38:25
127
原创 SDOI2016 数字配对
传送门裸费用流。建边：对于a[i]a[j]=prime&a[j]∣a[i]\frac{a[i]}{a[j]}=prime \& a[j]|a[i]a[j]a[i]=prime&a[j]∣a[i]，需要iii向j+nj+nj+n连，并且jjj向i+ni+ni+n连。费用即为c[i]∗c[j]c[i]*c[j]c[i]∗c[j]，流量无穷大。而源点向左侧每个点连边，费用为...
2019-10-18 08:44:52
96
原创 SDOI2016 储能表
传送门要求出答案，首先要知道异或值大于kkk的异或和，还要知道方案数，因为每个要减去kkk。那么用pairpairpair记录答案，firstfirstfirst为方案数，secondsecondsecond为异或和。数位DPDPDP枚举iii和jjj的每一位，需要满足i⩽n,j⩽mi \leqslant n,j \leqslant mi⩽n,j⩽m且异或出的数大等于kkk。f[pos][...
2019-10-17 18:21:06
112
原创 插头DP
入坑题参考博客适用范围：数据范围极小，与连通性有关，网格图。转移时用括号序来表示插头情况，然后分类讨论一下当前格子的左轮廓与上轮廓，也就是看有没有右插头与下插头，主要分为三大类：①两个插头都没有②只有一个插头③两个插头都有再分别讨论一下插头是“(”“(”“(”还是“)”“)”“)”即可。当一层转移完时，要从这一层的最后一个格子跳到下一层的第一个格子。那么当前所有的合法状态的四进制表...
2019-10-17 08:05:48
280
原创 最小表示法
模板传送门参考博客算法流程：把原串复制，接在后面。记两个指针p,qp,qp,q。初始化p=1,q=2p=1,q=2p=1,q=2。从两个指针开始往后逐位比较。若a[p+k]==a[q+k]a[p+k]==a[q+k]a[p+k]==a[q+k]，则++k++k++k。若最后k==nk==nk==n，说明原串只由一个字符组成，任意输出即可。否则此时kkk满足：a[p+k]!=a[q+...
2019-10-16 14:39:35
65
原创 SDOI2010 魔法猪学院
传送门kkk短路模板。kkk短路算法大致流程（A∗A^*A∗）：以下SSS为起点，TTT为终点，a→ba \rightarrow ba→b表示从aaa到bbb这条路径的长度。①反向图跑一个最短路求出每个点到终点最短距离dis[u]dis[u]dis[u]。②正向图bfsbfsbfs，每扩展到一个点vvv，就把node(v,S→v)node(v,S \rightarrow v)node(v...
2019-10-16 11:51:58
97
原创 BJOI2019 奥术神杖
传送门首先w1w2w3⋯wnn\sqrt[n]{w_1w_2w_3\cdots w_n}nw1w2w3⋯wn可以利用对数转化：log2w1w2w3⋯wnn=1n∑log2 wilog_2{\sqrt[n]{w_1w_2w_3\cdots w_n}}=\frac{1}{n}\sum log_2\ w_ilog2nw1w2w3⋯wn=n1∑log2 w...
2019-10-16 09:08:15
619
原创 cf643d Bearish Fanpages
传送门把C[i]C[i]C[i]中的E[A[i]]E[A[i]]E[A[i]]分离开，于是一个点xxx的答案即为C[x]+E[A[x]]C[x]+E[A[x]]C[x]+E[A[x]]令Son[i]Son[i]Son[i]表示一个集合：{A[j]=i∣C[j]−E[A[j]]}\{A[j]=i|C[j]-E[A[j]]\}{A[j]=i∣C[j]−E[A[j]]}。每个点都维护这个集合。然后...
2019-10-15 18:13:28
145
原创 bzoj2716 天使玩偶
传送门用之前的那种估值函数过不去。。要记录每个点所包含的最大范围才过得去，每次查就看查询点与这个范围的最小可能距离。搜的时候先搜估值距离小的。如果插入的点超过一定数量就重构一下，防止过于不平衡，不过貌似并没有什么卵用。#include<bits/stdc++.h>#define cs const#define re register#define lc(x) T[x].s...
2019-10-15 07:38:43
4402
原创 bzoj3262 陌上花开
传送门首先按照aaa排序。在分治的时候就没有第一维的影响了。然后分治的时候两个区间分别按照第二维排序。记左右两个指针。右边指针一个一个向右跳，左边指针移到第二维小等于右边指针的最大位置。并且在左指针跳的时候把对应的ccc记入权值树状数组里面。左指针跳完之后用右边的ccc查一查前缀和即可。分治完之后要把影响消掉。树状数组要开权值大小。并且要去重。因为相同的之间是相互大于。#includ...
2019-10-14 17:02:49
111
原创 BJOI2017 魔法咒语
传送门参考博客l⩽100l \leqslant100l⩽100的dpdpdp很好做。对于l⩽1e8l \leqslant 1e8l⩽1e8，由于有基本词汇长度不超过222，于是考虑如何构造这个矩阵。ans[i][j]ans[i][j]ans[i][j]表示当前长度为iii，最后在自动机上jjj节点的方案数。trans[l][i][j]trans[l][i][j]trans[l][i][j...
2019-10-14 15:39:06
169
原创 HNOI2006 最短母串问题
传送门在ACACAC自动机上bfsbfsbfs即可。用vis[id][state]vis[id][state]vis[id][state]表示当前处于ACACAC自动机上ididid号节点，已包含串的状态为statestatestate。由于是bfsbfsbfs，所以可以保证第一次搜到的即为最短的。搜到包含所有串的状态输出即可。要把一个节点的failfailfail的贡献加到该节点身上。#i...
2019-10-14 10:40:19
160
原创 SDOI2015 排序
传送门可以把这个东西想象成一个完全二叉树。那么可以发现，操作的顺序无关紧要。因为当长度小的移动之后，长度大的改变不了内部顺序。-_-正解就是搜索。由于与操作顺序无关，我们可以按照长度从小到大操作。相当于是二叉树从最后一层往上走。每走一层，就要保证这一层的每个区间里面都是连续的。在最后一层时，长度为1，显然是成立的。现在处理完某一层后，走到了上一层：当前层有若干个区间，每个区间内含有两个内部...
2019-10-13 19:43:08
101
原创 SDOI2015 寻宝游戏
传送门这题最关键的一点是要想清楚这个路径长度是咋算的。要注意到他是走到所有关键点去取宝藏然后回来。我们假想这些关键点构成一棵虚树，那么这就相当于是虚树上的一个dfsdfsdfs。当关键点确定的时候，其实最短路径长就确定了，也就是在虚树上从一个点开始dfs直到到回到这个节点所经过的路径长之和。起点其实无所谓，不选虚树外面的点就行。如果我们把虚树上的点按照dfs序从小到大排为p1,p2,⋯ ,...
2019-10-12 22:57:11
200
原创 woj4751 上网
内网传送门线段树优化建图+拓扑排序。注意赋值从111开始。#include<bits/stdc++.h>#define re register#define cs constcs int N=3e6+10,oo=1e9;namespace IO{ cs int Rlen=1<<22|1; char buf[Rlen],*p1,*p2; inline cha...
2019-10-12 17:02:34
135
1
原创 SNOI2017 礼物
传送门令FiF_iFi为前iii项的和。那么有：Fi=2∗Fi−1+ikF_i=2*F_{i-1}+i^kFi=2∗Fi−1+ik我们考虑如何让后面可以用矩阵转移！由于有二项式定理：ik=∑t=0k(kt)(i−1)ti^k=\sum_{t=0}^{k} \binom{k}{t}(i-1)^tik=t=0∑k(tk)(i−1)t那么可以把原式写成：Fi=2∗Fi−1+(k0...
2019-10-12 16:47:40
94
原创 woj4750 中等的字符串
内网传送门ACACAC自动机+矩阵优化DPDPDP初始化的时候，matrixmatrixmatrix里面不能写for(int i=0;i<=tot;++i)for(int\ i=0;i<=tot;++i)for(int i=0;i<=tot;++i)因为这时候tottottot为000。(o皿o)。#include<bits/stdc++.h&...
2019-10-12 16:02:18
110
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人