scmmm's blog

P5648 Mivik的神力 神！ deco\color{black}{\text{d}}\color{red}{\text{eco}}deco 神 原来的题意就是问 ∑i=lrRMQ(l,i)\sum\limits_{i=l}^{r}{\text{RMQ}(l,i)}i=l∑r​RMQ(l,i) 强制在线 拿到题的网友直呼不可做，分析也没分析啥，但是考虑一个点要作为[l,i][l,i][l,i] 的RMQ的话说明左边都比它小，也就是最大的比他小，然后这样就可以牵出一条链，根据性质还可以进一步推出这是一颗树！ 然后怎么办，统计[l,r][l,r][l,r] 的答案 [l,i][l,i][l,i] 的 ansansans 就是 lll 牵出来到 iii 的一条链中最大的节点，这样可以拿 $ 90$ 分 再考虑性质，发现上面那部分可以倍增来做 原题时限0.1s，下面的做法常数大了 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#incl ...

P3224 [HNOI2012]永无乡 这题太丢人了 本来想写一个 fhq 的启发式合并，但是觉得很麻烦（每次启发式合并的时候不知道怎么弄（貌似只要split根节点和它的有的儿子就行了？，当时我想的是每次取出这个小平衡树的第1大然后split这个值貌似复杂度是 log⁡3\log^3log3 的？于是果断放弃） ） 然后写了一个权值线段树的启发式合并，然后丢人地调了两个多小时才发现线段树里面的 szszsz 数组和并查集那个 szszsz 用混在一起了然后交上去直接给A了怪毙了 实际利用一个 DFS 就可以两 log⁡\loglog 做 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112 ...

P1841 JSOI2007 重要的城市 怎么还有这么水的蓝（ 根据定义满足 dis(i,j)=dis(i,k)+dis(k,j)dis_{(i,j)}=dis_{(i,k)}+dis_{(k,j)}dis(i,j)​=dis(i,k)​+dis(k,j)​ 并且有且只有一个 kkk 就可以说是一个重要的城市 这个等于很好找，就是一个 O(n3)O(n^3)O(n3) 的 floyd\text{floyd}floyd 关键是这个有且只有一个的条件比较毒瘤，所以想到了计算最短路 其实我是xjb计算的，只需要满足我们这个式子算出来只有一条最短路的时候为 111 就行了 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879#include<stdio.h>#include<iostream>#include<cmath& ...

P4910 帕秋莉的手环 首先你需要明白每一段都可以拼接，因此只需要找到存在“金”的序列个数即可 设 dp 方程 f[i][j]f[i][j]f[i][j] 表示第 iii 个位置有 jjj 个“金” 的方案数，发现转移有点重复，于是设 f[i][1/0]f[i][1/0]f[i][1/0] 表示第 iii 个位置是“金”/"木"的合法方案数目，转移很显然 f[i][0]=f[i−1][1]f[i][1]=f[i−1][0]+f[i−1][1]f[i−1][0]=f[i−2][1]f[i][1]=f[i−1][1]+f[i−2][1]\begin{aligned} f[i][0]&=f[i-1][1]\\ f[i][1]&= f[i-1][0]+f[i-1][1]\\ f[i-1][0]&=f[i-2][1]\\ f[i][1]&=f[i-1][1]+f[i-2][1]\\ \end{aligned} f[i][0]f[i][1]f[i−1][0]f[i][1]​=f[i−1][1]=f[i−1][0]+f[i−1][1]=f[i ...

呜呼呼呼呼呼呼呼 FFT 只说FFT在优化多项式乘法的应用。 首先我们有两个系数表达的多项式f,gf,gf,g f(x)=a1xk+a2xk−1....akx+ak+1f(x)=a_1x^k+a_2x^{k-1}....a_{k}x+a_{k+1}f(x)=a1​xk+a2​xk−1....ak​x+ak+1​ g(x)=a1xp+a2xp−1....apx+ap+1g(x)=a_1x^p+a_2x^{p-1}....a_{p}x+a_{p+1}g(x)=a1​xp+a2​xp−1....ap​x+ap+1​ 现在我们要求得F=f∗gF=f*gF=f∗g 显然我们可以爆算，时间复杂度O(n2)O(n^2)O(n2) 然而对nnn较大的时候，上面显然超时，所以我们就得学习一个更优秀的解决问题的办法:FFT FFT的具体思路：先把系数表达转换成点值表达，然后可以O(n)O(n)O(n)地把点值表示相乘，最后通过IDFT转化回系数表达 前置芝士 下面这一部分其实可以跳过，不会讲FFT具体操作 点值表示 就是用n+1n+1n+1个点来表示一个多项式 至于为啥是n+1n+1n+1，我们有n+1n ...

图论入门 前言 可能有锅 内容 比较基础的定义 图的定义 ： 一个G={V,E,w}G=\{V,E,w\}G={V,E,w} 分别为边集，点集，关系 也有二元组定义 重边的定义：(u,v)(u,v)(u,v)重复的边 独立集(或者稳定集)定义：图 $G $中两两互不相邻的顶点构成的集合 二部图(或二分图)定义:设G=(V,E)G=(V,E)G=(V,E)是一个无向图，如果顶点VVV可分割为两个互不相交的子集(A,B)(A,B)(A,B)，并且图中的每条边(i，j)(i，j)(i，j)所关联的两个顶点iii和jjj分别属于这两个不同的顶点集 图的色数χ(G)\chi(G)χ(G) 给定图形边缘所需的最少颜色数量称为图形的边色数。 一个图是k−k-k−分的当且仅当色数为kkk 子图的定义 V(H)⊆V(G),E(H)⊆E(G)V(H) \subseteq V(G),E(H)\subseteq E(G)V(H)⊆V(G),E(H)⊆E(G)或者说GGG包含HHH 同构是在数学对象之间定义的一类映射，它能揭示出在这些对象的属性或者操作之间存在的关系。若这两个 ...

乱搞 讲乱搞之前我们先来闲聊一点 好像真的只有乱搞了（字符串好像只有咕咕） 这篇尽量用难度顺序吧 如果还是难了的话真没办法了。 前一半尽量让所有人听懂吧 后一半能听就听吧 由于不知道你们有没有在听，所以下面这些题准备只说简述题面 如果你发现这些题目的正解的话，请不要说出来 没有准备多少题 前置芝士 对于骗分你需要准备的 在其他题都做不来的时候调试超过300行代码的能力 在一小时内调试超过150行代码 能独立调出比较大的模拟 熟练掌握线段树，平衡树的基础操作 （比如曾老师555分钟打完splaysplaysplay的赌约） 杂题 先不讲知识点 先开一下思维8 Q:怎样O(1)O(1)O(1)判断一个数是不是二进制节点 君克陷阱 首先这个是一个比较怪的题目，毕竟这道题也不叫这个 看完了吧，我们来讲讲 先告诉你们正解是一个背包，但是现在假设你想不出来是背包 然后你就打了个一个2n2^n2n的dfsdfsdfs来选择吃这个垃圾还是不吃这个垃圾 我们来思考思考剪枝 1.层数到达i+1,return 这个必须有 2.当前剩余生命吃不到垃圾，return，必须有 3.当前答案比目前最优解大，r ...

Splay 呜呼今天终于搞懂splay了 学习之前你需要知道的 这东西深度并不是 log⁡n\log nlogn 的，但是复杂度是均摊 O(nlog⁡n+mlog⁡n)O(n\log n+m\log n)O(nlogn+mlogn) 的 初学者可能会把它当做一个平衡树 基础的函数 1234567 inline void pushup(int x){sz[x]=sz[ls]+sz[rs]+cnt[x];}//字面意思 inline int pd(int x){return c[f[x]][1]==x;}//判断是左子树还是右子树 inline void clear(int x){ls=rs=sz[x]=f[x]=val[x]=cnt[x]=0;}//清空这个节点 splay的函数 rotate 123456789101112void rotate(int x){ int y=f[x],z=f[y],k=pd(x),m=c[x][!k]; //其实rotate的本质就是x与子节点改变方向（因为原本在y下方的x到了y上方） ...

一个裸的很的推式子、 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151#include<iostream>#include<cmath>#include<cstdio>#include<cstring>#include<queue>#include<stack>#include< ...

放在开头的话 1.本人1月13日才刚刚接触了淀粉汁，所以可能很多东西没有理解完全甚至出错，如果您有什么疑问的话，请发在下面的评论区。 2.淀粉汁是跟着一篇题解学的，因此可以有些代码很像，但是原来题解的部分没讲到的地方我可能会提出来 3.这东西目前可能会更的很慢 初级 什么是点分治？ 点分治是处理树上问题的一种高效的办法，时间复杂度很优秀，而且思想比较巧妙。 怎么来做呢？ 首先我们引入树的重心 树的重心 树的重心也叫树的质心。找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡。 什么意思呢? 我们可以从这里推得以树的重心为根的任意一颗子树大小不超过n/2n/2n/2 证明就不用了吧 于是我们求log2Nlog_2Nlog2​N次重心，那么每个点就能被确定了。 于是时间复杂度就变成了O(NlogN)O(N log N)O(NlogN) 怎么求呢？ 根据它的定义，树的重心一定是最大子树最小的点。 感性理解即可 于是照着求就可以了啊。 但是我们要多次求，因此我们得加一个条件，判断是否可以访问 vis[]或者fw[]就可以了 于 ...