-
CF1207G Indie Album
题目链接problem有$n$个字符串,对于第$i$个字符串通过以下两种方式中的一个给出。 $1\; c$,该字符串只含一个字符$c$。 $2\ x\ c$,该字符串为第$x(1\le x < i)$个字符串末尾添加一个字符$c$得到。 有$m$次询问,每次询问给出一个字符串$s$和位置编号$x$,问在上述第$x$个字符串中,字符串$s$出现了几次。solution需要用到$AC$自动机,树状数组,$dfs$序。首先将询问离线下来,对于所有询问的字符串建立一...…
-
在github上搭建个人博客并在线更新
换博客比更博还勤的我终于决定写一篇博客搭建教程了。。FAQQ:$hexo$需要本地编译。$jekyll$虽然可以直接上传$md$。。但是如果在github上直接编辑也太难受了叭,毕竟不能在线预览。。。A:对于$hexo$,博主目前也没有什么很好的办法233。(有个叫$Travis CI$似乎可以做到)。所以这篇文章仅适用于$jekyll$主题的博客哦。$jekyll$其实也有些蛮好的主题的。Q:那我知道了,找个$markdown$在线编辑器编辑好,然后直接去$github$上传不就行了么?...…
-
CF1204D Kirk and a Binary String
题目链接problem给出一个长度为$n(n\le 10^5)$的只包含01的字符串。把尽可能多的1变为0,使得对于所有的$l \in [1,n],r\in [l,n]$,区间$[l,r]$的最长不下降子序列的长度不变。solution【译自官方题解】可以发现有些字符是确定的(即无法修改)。这些确定的字符满足以下几个条件。 所有的$10$是确定的。 如果字符串$p$是确定的且字符串$q$是确定的,那么字符串$pq$是确定的。 如果字符串$p$是确定的,那么字符串$1p0$是确定的。 ...…
-
CF888G Xor-MST
题目链接problem给出n个点,每个点有权值,求最小生成树。定义一条边的代价为所连接两点的权值异或值。solution考虑分治,根据最高位为0还是1分为两部分。然后分别求最小生成树。合并的时候就将最高位为0的一部分插入到trie中,然后从最高位为1的一部分中查询。注意对trie的清空。code/** @Author: wxyww* @Date: 2019-08-18 19:36:04* @Last Modified time: 2019-08-18 20:20:03*/#includ...…
-
图论
最短路变种bzoj2725 给定一个带权有向图,Q 次询问,每次询问删掉某条边后 1 到 n 的最短路solution先选定一条最短路,然后考虑一条不在最短路上的边(u,v,w)。记录下从S到u从哪个点开始离开选定的最短路(记为$S’$),从v到T的最短路从哪个点开始进入选定的最短路(记为$T’$),然后当删掉从$S’到T’$之间的边时,都可以用这条最短路代替。用线段树维护,区间修改单点查询。变种2 给定一个带权有向无环图,Q 次询问,每次询问删掉某个点后1到n的最短路solution...…
-
分治
复杂度分析如果$f(n)=f(\frac{n}{2})+O(n)$则总复杂度为$O(nlogn)$。 证明:每层总复杂度都是$O(n)$递归$logn$层。如果$f(n)=f(\frac{n}{2})+O(n^2)$则总复杂度为$O(n^2)$。 证明:略经典问题 所有区间的最大值之和找到当前区间$[l,r]$的最大值,设位置为$x$.递归$[l,x-1]$和$[x+1,r]$,统计跨过$x$的区间。因为$x$为当前最大值。所以跨过$x$的区间个数为$x\times (r-x+1)$...…
-
概率与期望
概率与期望 —— 洪华敦基础知识期望的线性性质$E(X + Y) = E(X) + E(Y)$证明: $E(X + Y) = \sum\limits_i\sum\limits_jP(X=i \&\& Y=j)(i+j)$$= \sum\limits_i\sum\limits_jP(X=i \&\& Y=j)i + \sum\limits_i\sum\limits_jP(X=i \&\& Y=j)j$$=\sum\limits_ii\sum\...…
-
luogu4570 元素
题目链接problem有$n$个二元组, $(x,y)$,要选出一些二元组,使得他们的$x$的任何一个子集的异或和不为$0$并且$y$的和最大。solution考虑是$x$的子集异或和不为0这个条件。如果他有一个子集异或和为$0$,那么就说明其中有一个数字可以由其他的数字异或得到。所以就是要找出他的线性基。使得线性基中的元素的$y$之和最大。考虑线性基的一个性质: 线性基的数量是一定的,即如果往原线性基中添加一个元素。那么也要删除恰好一个元素。证明:如果首先证明删除最多一个元素。这个根据...…
-
bzoj2115 Xor
题目链接problem考虑一个边权为非负整数的无向连通图,节点编号为$1$ 到 $N$,试求出一条从 $1$ 号节点到 $N$ 号节点的路径,使得路径上经过的边的权值的 $XOR$ 和最大。路径可以重复经过某些点或边,当一条边在路径中出现了多次时,其权值在计算 $XOR$ 和时也要被计算相应多的次数,具体见样例。solution考虑先确定一条从$1$到$n$的不含环的路径。如图,我们先选择$1-2-3-4-9-10$这条路径,然后发现,我们在3这个位置可以通过$3-5$这条边,去环里面转一...…
-
快速傅里叶变换(FFT) 与快速数论变换(NTT)
多项式定义有多个单项式组成的代数式。这些单项式中的最高次项的次数+1称为该多项式的次数界。即:一个次数界为n的多项式可以表示为$A(x) = \sum\limits_{i=0}^{n-1}a_ix^i$系数表示法与点值表示法系数表示法:将一个多项式从$0$到$n-1$项的系数依次写出来(没有该项即为0),所构成的序列即为该多项式的系数表示。即定义中所说的序列$a$点值表示法:将$n$个不同的$x$带入该多项式,得到n个$y$,这$n$个点对$(x_i,y_i)$,即为该多项式的一个点值表示...…