Loj刷题记录

又是一年云参营。

所以一起刷省选题吧。

LOJ2028 「SHOI2016」随机序列

题目链接。

简要社论

发现+和-可以互相抵消，于是有贡献的时候一段前缀的乘积。设$s[i]=prod_{j=1}^i a[j]$，则答案为$2sum_{i=1}^{n-1}3^{n-i}s[i]+s[n]$。 使用线段树维护前缀积就可以了。[code](https://loj.ac/submission/671456)

LOJ2038 「SHOI2015」超能粒子炮・改

题目链接

简要社论

$$ egin{aligned} F(n,k)&=sum_{i=0}^kinom{n}{i} \ &=sum_{i=0}^kinom{n mathrm{mod} p}{i mathrm{mod} p}inom{n/p}{i/p} \ &=sum_{i=0}^pinom{n mathrm{mod} p}{i}sum_{j=0}^{lfloorfrac{k-i}{p} floor}inom{n/p}{j} end{aligned} $$ 差不多转成一个递归的柿子了。预处理$F(n,k)(n,kin [0,p))$，时间复杂度$O(n^2+Tlog n)$.[code](https://loj.ac/problem/2143)

LOJ2143 「SHOI2017」组合数问题

题目链接

简要社论

组合意义，转为在$n$个元素中选$mathrm{mod} k=r$个元素。 矩阵乘法优化转移，时间复杂度$O(k^3log n)$，[code](https://loj.ac/problem/2143)

LOJ2146 「SHOI2017」寿司餐厅

题目链接

简要社论

最大权闭合子图的模板。 闭合子图：在一个有向图中的一个子图$S$，满足$forall xin S$，$x$不能到达$S$之外的点。 最大权闭合子图：字面意思（点带权） 具体到这题就是，我们发现实际上这些元素是一些互相依赖的关系（选了$y$才能选$x$），那么连一条边$x ightarrow y$，构成了一个有向图。 标准做法是使用最小割，设一个源点$S$和一个汇点$T$，对于点$x$，割掉与$S$相连的边表示不选这个物品，否则割掉与$T$相连的边表示选这个物品。若$v>0$，则连一条边$(S,x,v)$，否则连一条边$(x,T,-v)$。 那么我们看边$x ightarrow y$，如果不割$(x,y)$，要保证$S ightarrow x ightarrow y ightarrow T$这条路径不存在，就是不能不选$y$且选$x$。所以连边$(x,y,+infty)$ 直接跑一遍dinic就可以过了。[code](https://loj.ac/submission/671414)

LOJ2192 「SHOI2014」概率充电器

题目链接

简要社论

首先大家都知道是树d，设$f[x]$表示$x$没有通上电的概率，但是我们不能列出一个高斯消元的式子，不然复杂度就炸掉了。 正解是使用up down的方法，首先计算出$g[x]$表示只考虑$x$的子树，$x$通上电的概率，这个直接dfs一遍，并且$f[rt]=g[rt]$。之后推下去，计算$x$对$x$的儿子$v$的贡献，发现$f_x$对$f_v$就是$f_x$去掉$g_v$对它的贡献（这里比较绕，建议画图理解） 注意除0的问题，时间复杂度$O(n)$，[code](https://loj.ac/submission/675269)

LOJ6044 「雅礼集训 2017 Day8」共

题目链接

简要社论

首先要在$n-1$个点中选出$k-1$个点作为奇数的点。 于是就变为了有标号完全二分图$K_{n,m}$有多少个生成树。 你可以手推行列式，也可以使用prufer序列来理解。 首先prufer序列的长度为$n+m-2$，回想一下prufer序列和树互相转化的过程，就知道里面有$m-1$个位置填$[1,n]$的数，有$n-1$个位置填$[1,m]$的数，并且位置是已经固定的。 所以答案就是$inom{n-1}{k-1} imes k^{n-k-1} imes (n-k)^{k-1}$。 代码？雾。。。

LOJ6045 「雅礼集训 2017 Day8」价

题目链接

简要社论

我回想起刚才好像做过一道题叫寿司餐厅，于是开始思考怎么用网络流建图。。。 然后我自闭了。。。日常不会网络流建图。。。 点开了题解，题解说只用连这些边就可以。$(S,i,infty-w_i),(i,j+n,infty),(j+n,T,infty)$，然后用$S$连出的所有边的边权之和-最小割就可以了。其中$i$表示减肥药，$i+n$是药材。 为什么呢？跟刚才一样，割掉$(S,i)$表示不选第$i$个减肥药。首先割掉中间的边没有割掉右边的边优。其次，所有边权都是$infty$级别的，而且求的是最小割，所以割掉$n$条边，也就是不选的减肥药+选的药材=n，所以就是选的减肥药=选的药材。满足这两个条件，跑出来的就是正确答案了。 代码？咕了。。。

LOJ6046 「雅礼集训 2017 Day8」爷

题目链接

简要社论

你发现如果没有$lenle 10$这个限制的话，这是个open题。于是只能从这里入手。 暴力分块的话，外层二分，块内二分要两个log，比$n^2$还慢。 所以考虑去掉一个，~~不容易发现~~相邻几个数都是比较接近的，所以我们可以重新分块。build的时候从左往右扫，当发现$max-min>S$的时候就分出一个块，其中$S$是个常数，大约取2000，然后就可以对每一块维护$le i$的数的个数（因为$iin [min,max]$的值域较小）。 大概1000次修改重构一次整个序列。这样就可以过去了。 代码？咕了。。。

LOJ2036 「SHOI2015」自动刷题机

题目链接

简要社论

QNMD 省选题（逃

LOJ2037 「SHOI2015」脑洞治疗仪

题目链接

简要社论

线段树维护当前区间最大脑洞，和$1$的个数，修改就直接打标记。 QNMD 省选题（逃