- 博客(30)
- 收藏
- 关注
RSS订阅
原创 CSP-S 2019总结
Day 0从jz出发,车上fb一会就到了.入住办的很快,call了个甜品吃了不久就睡了.Day 17点起床很清真,早餐感觉没啥能吃.拿了碗面加点酱油和油凑合吃了.车上听了几首电音提神,很快就到了.进了考场不给试机,问题不大.到点之后配了vimrc很快就开始看题了.gvim8.1它安装的时候竟然没有remap那些Windows的快捷键,也就是说…复制粘贴全选保存那些都用不了…人...
2019-11-18 21:15:16
224
原创 NOIP2018总结
Day 0晚上到酒店吃了个披萨,十一点睡了Day 1早上大巴出锅,结果8:20才到考场,不过还好,还没迟到.看题:T1大水,T2可能要想一会,T3应该不会.T1看了一会之后就想出来了,还写了另外一个做法去拍.搞完大概9:30T2看了一下之后手玩了一会发现只会在原序列里选.然后我脑残了没写DP只写了暴力枚举系数.不过80分也还OK因为很短且不好对拍,写完这题也就十点左右T3一...
2018-11-11 19:18:28
203
原创 一些套路的记录
1.如果一个数存在于多个LIS中,那么它在多个LIS中排名是一样的.2.设startistart_istarti表示以iii为开头的LIS,endiend_iendi表示以iii为结尾的LIS,那么总LIS为max(starti+endi−1)max(start_i+end_i-1)max(starti+endi−1)3.一个数列[l..r][l..r][l..r]及kkk,使aia_...
2018-11-04 11:48:35
238
原创 图的同构
定义存在一个映射f:G→G′f: G \rightarrow G'f:G→G′，使得对于任意一条边e=(vi,vj)e=(v_i,v_j)e=(vi,vj)，在G′G'G′中存在e′=(f(vi),f(vj))e'=(f(v_i),f(v_j))e′=(f(vi),f(vj))，且数量相同。必要条件1.点数相同2.边数相同3.相同度数的点数量相同...
2020-02-06 14:48:31
340
原创 回文树
用途用于解决一些关于回文的问题，处理回文问题的利器。定义有2个根，odd和even。even的长度是0，odd的长度是-1，什么意思呢？就是比如说插入一个字符’a’,插入even时会变成‘aa’，而插入odd时会变成’a’。所以odd代表长度为奇数的回文串，而even代表长度为偶数的回文串。len为一个点所代表的字符串实际长度。fail为失配指针，指向最长回文后缀。构建考虑我们...
2019-12-12 16:01:14
133
原创 JZOJ6392 僵尸
题目大意n<=2e3n<=2e3n<=2e3solution首先转化问题,考虑求全部被占领的方案.不难想到树形DPDPDP,但是该怎么设置DPDPDP的状态呢?考虑f[x][i]f[x][i]f[x][i]表示xxx的子树全部被占领,xxx的子树内最强的僵尸为iii.(离散僵尸)但是问题来了,僵尸并不只从子树内走过来,也有可能从外面走过来.所以将状态设置为f[x]...
2019-10-30 10:08:10
149
原创 JZOJ6395 消失的序列
题目大意有一个长度为nnn的序列,其中元素为1 n1~n1 n的排列,其中第pospospos位的元素为xxx,问有多少种合法的序列是有规则的.有规则的序列被定义为,如果利用一个栈可以将这个序列排成升序,那么这个序列就是有规则的.n<=1e6n<=1e6n<=1e6solution如果将入栈操作设为’(’,将出栈操作设为’)'的话,那么序列可以变成一...
2019-10-30 08:45:06
298
原创 高斯消元
简介高斯消元,一般用于求解nnn元一次方程组.求解方法也很简单.解法其实就是暴力的求解.nnn元一次方程组的系数可以写成一个矩阵的形式,而我们的目标就是将矩阵的每一行都消的只剩下一个数.其实剩下的看代码里面的注释就好了.因为实在是太简单了#include <cstdio>#include <cmath>#include <algorithm>...
2019-10-25 20:36:07
130
1
原创 JZOJ6340 B
题目大意给定一个长度为NNN的数列aaa每次操作在[1..N][1..N][1..N]中等概率选择一个ai>0a_i>0ai>0的aia_iai,并将其-1.问期望多少次操作后a1a_1a1变为000.N,ai<=5e5N,a_i<=5e5N,ai<=5e5Solution设bib_ibi表示对于aia_ia...
2019-09-06 22:44:03
200
原创 (ex)BSGS(大步小步)算法
用途给出三个整数&a,b,p$求最小的自然数xxx,使得 ax≡b(mod p)a^x \equiv b (mod \ p)ax≡b(mod p)特殊情况:若b=1b=1b=1,则x=1x = 1x=1BSGS由费马小定理可知ap−1≡1(mod p)a^{p-1}\equiv 1(mod \ p)ap−1≡1(mod p)所以只用考虑...
2019-09-03 17:03:54
168
原创 平衡树(术)之splay
有人能告诉我spaly是什么吗二叉搜索树保证对于一个点xxx.val[x]>=val[lson[x]]val[x] >= val[lson[x]]val[x]>=val[lson[x]]且val[x]<=val[rson[x]]val[x]<=val[rson[x]]val[x]<=val[rson[x]]一些基础操作g...
2019-08-08 21:09:17
176
原创 (扩展)中国剩余定理
用途求解线性方程组{x≡a1(mod b1)x≡a2(mod b2)…x≡an(mod b2) \left\{\begin{aligned}x \equiv a_1 (mod\ b_1)\\ x \equiv a_2 (mod\ b_2) \\\ldots\\x \equiv a_n (mod\ b_2)\end{aligned}\right....
2019-08-04 19:31:03
90
原创 费马小定理与欧拉定理
欧拉定理aφ(n)≡1(mod n)a^{\varphi(n)}\equiv1(mod\ n)aφ(n)≡1(mod n)证明待填.费马小定理ap−1≡1(mod p)a^{p-1}\equiv1(mod\ p)ap−1≡1(mod p)前提是ppp为质数.可以理解为欧拉定理的特殊情况.应用这两个式子和应用条件要记牢....
2019-07-25 12:35:07
167
原创 点分治小结
大致过程1.找子树重心作为根2.处理出子树内每个点到根的信息（异或值,距离等等）3.利用求出的信息的性质解决问题4.注意判重（可能有可能没有）找重心这个8说了随便搞一搞就行处理信息直接遍历整棵子树就行解决问题依题目而定发挥奇思妙想判重利用容斥的性质在做的时候减掉儿子就行.（口胡了一发，下午写几道题）...
2019-07-20 11:04:28
104
原创 记闭自考中9102
6.20上午大课间和同学们玩跳楼梯,最后一次和他们玩了,有点感伤.整个上午在发呆和欧亨利小说选中度过.下午考语文.课内文言文:岳阳楼记(意料之中)名著:西游记(喵喵喵?)感觉整张试卷都比较easy,语文很稳健?!(flag)6.21上午考政治和化学.总结:这试卷怎么这么JB简单.大学教授?!下午考数学.这…比初三任何一次模拟都简单…无语了.6.22上午考物理和历史...
2019-07-09 21:44:36
146
原创 三分法
用途用于寻找单峰函数的极值.单峰函数:存在某个点,使得这个点的左侧保持单调递增(递减),右侧保持单调递减(递增).意思就是说,一个数列同样可以使用三分法.实现其实很简单,画个图稍微讨论一下就行.设midl=(l+r)/2midl=(l+r)/2midl=(l+r)/2,midr=(midl+r)/2midr=(midl+r)/2midr=(midl+r)/2.比较二者的大小关系即可....
2019-07-09 20:15:16
716
原创 矩阵乘法学习小结
运算规律对于矩阵A=n∗pA=n*pA=n∗p和B=p∗mB=p*mB=p∗m,C=n∗mC=n*mC=n∗m即为Ci,j=∑k=1pAi,k∗Bk,jC_{i,j}=\sum_{k = 1}^{p}A_{i,k}*B_{k,j}Ci,j=k=1∑pAi,k∗Bk,j运算规律是关键,掌握好了才能推矩阵....
2019-07-02 16:11:15
166
原创 AC自动机复习
AC自动机全称Aho-Corasick Automation,不是Accept Automation.用途用于多模匹配.实质就是在一棵TrieTrieTrie上建立节点之间的关系.具体那个关系称为failfailfail数组,表示其他串中与该字符相等的字符位置.实现同样非常easy.由于这是个匹配的过程,所以跳到failfailfail所指的位置后显然前面的也必须一样.所以就可以...
2019-06-26 20:27:54
101
原创 字符串基础算法之(ex)kmp
因为自己是个菜B所以老实点复习算法假设两个字符串s1,s2s1,s2s1,s2.需要找出s2s2s2在s1s1s1中出现次数(包含0次).基本定义nextinext_inexti:在s21..is2_{1..i}s21..i中最长公共前缀后缀的长度.匹配过程(因为我懒得贴图所以只会口胡)(贴个不错的博客忘记了就看这个)http://www.ruanyifeng.com/blog...
2019-06-24 21:36:02
153
原创 背包问题总结
01背包最基础的背包问题.给你 nnn 个物品及容量为 mmm 的背包.每个物品有体积和价值,问最大的价值是多少.转移方程显然Fj=max(Fj,Fj−t[i]+w[i])F_j=max(F_j,F_{j-t[i]}+w[i])Fj=max(Fj,Fj−t[i]+w[i])注意枚举顺序是倒序,因为01背包每个物品只能选一次,所以状态之间不能互相影响.代码如下完全背包同01背...
2019-04-19 13:30:07
126
原创 决策单调性DP学习小记
四边形不等式解决形如这样的DP式子的问题Fi,j=min{Fi−1,k+wk+1,j}(i&lt;=k&lt;=j)F_{i,j} = min\{{F_{i - 1,k} + w_{k + 1,j}}\}(i&lt;=k&lt;=j)Fi,j=min{Fi−1,k+wk+1,j}(i<=k<=j)或者是Fi,j=min{Fi−1,k,Fk+...
2018-12-11 13:18:36
234
1
原创 ## 【SDOI2010】大陆争霸
##题目大意带限制的最短路,一个点被一些点所限制,一个点能被到达当且仅当限制它的点都被到达.你可以释放无限个机器人代替你跑路.Solution记录d1d1d1表示到达它的最短路,d2d2d2为到达所有限制它的点的最短路,那么实际就是max(d1,d2)max(d1,d2)max(d1,d2).一个点能进行增广,当且仅当它不被任何点限制.增广的时候判一下就OK.Codes#inclu...
2018-11-04 09:20:54
268
原创 5936. 【NOIP2018模拟10.29】逛公园
题目大意给定一个nnn个点的序列,每个点有aia_iai和lil_ili两个信息,aia_iai表示可以获得的贡献,lil_ili表示获得贡献的上限.有qqq个询问,每个询问l,r,x0l,r,x0l,r,x0,表示从lll到rrr这个区间,选择一个子区间,从子区间的左端走到右端,获得的贡献最大.(子区间可以为空)要求你输出最大可以获得的贡献数据范围对于100%100\%100%...
2018-10-30 22:55:48
250
原创 题解合集(NOIP2018赛前集训)
每天做的题的题解都扔上来,以后好复习10.22jzoj5919:找出所有环,拿出左右端点,set维护r[i]表示以i作为左端点时右端点最右是多少,二分统计答案jzoj5920:先求出两个数组start,end.start[i]表示以i为开头的LIS,end[i]表示以i为结尾的LIS.一个结论:如果一个数存在于多个LIS中,那么它的排名是一样的,如果start[i] + end[i] =...
2018-10-23 22:03:30
237
转载 因为我们是oier
我们是OIer，所以我们不用在跑道上挥汗如雨；不用在球场上健步如飞；更不用在没事的时候，经受非人的体能训练……但是，我们却要把头脑高速运转，还要接受一大堆大学生也只是“了解即可”的知识，把一个个抽象的问题转化为一篇篇优美的代码，才能在F9按下以后获得欢呼。不要以为我们机房里没有风吹，没有日晒，就比勤劳的体育生们轻松，只不过是大脑和四肢的区别罢了。可是，...
2018-10-18 19:48:21
202
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人