loj#6436. 「PKUSC2018」神仙的游戏

原题传送门:>Here<

我们发现$f(i)=0$,当且仅当存在一对01满足01间的距离为$n-i$的倍数。这样就可以得到第4个部分分了。

我们考虑优化这个过程。

定义$A_i=[s_i=0]$,$B_i=[s_i=1]$。

现在我们想要使得

我们考虑翻转$B$,即使得

这样就变成

这样就OK了。

luoguP3321 [SDOI2015]序列统计

原题传送门:>Here<

定义$f$为$S$的生成函数。

则答案为

其中多项式卷积定义为

这个卷积比较难做。

我们发现出题人给了一个性质:$M$为质数。因此$M$必定有原根。

所以$1\cdots M-1$中的每一个数都可以被表示为原根的整次幂。

我们定义

则卷积就变成

答案就变成

0108模拟赛 无人生还

原题传送门:>Here<

第一问

$prufer$序列乱搞即可,

P4183 [USACO18JAN]Cow at Large P

原题传送门:>Here<

我们先考虑只求一个点时怎么做。

设$f_i$为$i$到叶结点的最短距离。

假设我们在处理$root$的答案。可以发现,

当$dis_{root,i}\ge f_i$时,$i$的子树只需要放一个人就可以“封锁”。

可以发现满足这个条件的点构成很多棵子树,而我们的答案就是子树的个数。

现在我们考虑怎么得到子树个数。

设$val_i=2-d_i$,其中$d_i$表示点$i$的度数。

我们可以发现,一棵子树的权值和正好等于$1$。

考虑为什么是这样。

设一棵子树中有$x$个点,那么有$x-1$条在子树内的边。所以贡献即为$2*x-2(x-1)=2$。因为我们求的是“子树”权值和,所以必有一条连出去的边。这样贡献即为$2-1=1$。

所以我们只要对于$dis_{i,j}\ge f_j$,将$ans_i$加上$2-d_j$即可。

这样复杂度是$O(n^2)$的。

考虑点分治。则对于$i$,满足条件的$j$满足$dis_i+dis_j\ge f_j$。

移项一下,得到$dis_i\ge f_j-dis_j$。后面那个东西用树状数组维护一下即可。

bzoj4179 2015湖南省队集训 B

原题传送门:>Here< and >There<

我们首先考虑对给出的字符串建$AC$自动机。

考虑$AC$自动机上找子串的过程,我们发现一个点可以被达到当且仅当该点沿着$fail$向上走没有一个点是一个字符串的终点,且沿着$fa$向上走也没有。

我们把这些点挑出来,从$1$开始跑最长路。如果发现存在正环即必定有解,否则判断最长路是否$\ge L$。

loj#6131. 「2017 山东三轮集训 Day1」Fiend

原题传送门:>Here<

答案可以看作是

其中$\tau$表示排列$p$的逆序对个数。

我们(考后)发现这个东西等价于求一个$n*n$矩阵$M$的行列式,其中$M$满足$M_{i,j}=[j\in [l_i,r_i]]$

这个行列式显然不能直接求,我们又发现查到几个性质:

  • 一个单位矩阵(只有主对角线上是$1​$,其他地方均为$0​$的矩阵,即$M_{i,j}=[i=j]​$)的行列式为$1​$;(性质1)
  • 交换矩阵的两行(列),矩阵的行列式变为相反数;(性质2)
  • 把矩阵的某一列(行)的各元素乘以同一数然后加到另一列(行)对应的元素上去,行列式不变。(性质3)

loj#6130. 「2017 山东三轮集训 Day1」Fable

原题传送门:>Here<

(考场上居然没写出来。。。心态爆炸)

我们发现,对于每轮冒泡排序,

  • 如果一个数前面有比它大的数,则该数向前移动一位;
  • 否则该数一直往后移,直到碰到一个$\ge$该数的数。

设$w_i$为$i$前面大于$a_i$的数的个数。

我们发现对于每个数,第一种移动会进行$min(w_i,k)$次。所以对于$w_i\ge k$的点,我们知道它会移动到$i-k$。

对于其他点,他们最后的值必定是有序的,所以拖出来排序,并插入原来的空当中即可。

luoguP4003 无限之环

前言

原题传送门:>Here<

网络流神仙题。。。我服了。

建模

我们发现一对联通的接头可以看做一条从一个格子到相邻格子的路径。我们考虑按奇偶分开,奇数点连源点,偶数点连汇点。

把每个格子拆成上下左右中五个点,对于有接头的方向,从中间点到对应点连边。

接下来我们考虑如何表示旋转。

loj#6503. 「雅礼集训 2018 Day4」Magic

原题传送门:>Here<

首先对题意进行一些转换:

  • 我们发现枚举格子肯定不可行,考虑枚举颜色;

  • 直接做无标号排列也不可行,考虑先对卡牌进行编号,最后再将答案除以本质相同的排列数,即

  • 恰好$K$的魔术对也不能处理,考虑先做出$\ge K$的方案数,再容斥出答案,即$\sum_{i=K}^{n}(-1)^{i-K}\binom{i}{K}f_i$。

loj#6041. 「雅礼集训 2017 Day7」事情的相似度

原题传送门:>Here<

我们发现两个前缀的$LCS$等价于这两个前缀在后缀自动机上的$LCA$的$len$。

我们可以发现字符串的一个前缀可以被后缀自动机上加入该点后的$last$表示。

在下文中,一个点的编号被定义为它代表的前缀的结束位置。对于一个在建自动机时新建的点,其编号为$0$。

这样我们可以想到一个暴力的算法:

HH的项链一样,把询问对右端点排序。

枚举到$i$时,设$val_j$为$j$的前缀与$[1,i]$的前缀的最大$LCS$,即

考虑更新$1\cdots i-1$与$i$的答案,举个例子:

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×