搞颓记录

9-3

Process

代码能力还是太差,写T4写了一上午。T2、T3根本来不及看

以后还是要合理分配时间。。。

T1

随便搞,我是直接枚举[n23,n2+3][\lfloor \frac{n}{2}\rfloor - 3, \lfloor\frac{n}{2}\rfloor + 3]内的数划分...

显然两个数差得越小越好

T2

考虑和连通图计数类似的做法

fi,jf_{i, j}表示ii个点的连通图,每种方案为边数的j[0,1,2]j\in[0, 1, 2]次幂的答案,gi,jg_{i, j}表示ii个点任意图的答案

显然,j=0j=0时就是裸的连通图计数

fn,0=gn,0i=1n1(n1i1)fi,0×gni,0 f_{n, 0} = g_{n, 0} - \sum_{i=1}^{n - 1}\binom{n - 1}{i - 1}f_{i, 0} \times g_{n - i, 0}

考虑j=1j=1

j=0j=0类似的方法,前面都是一样的,只是最后一坨东西算法不一样

假设枚举出来的ii个点图的连边方案的边数为集合SSnin-i个点图的连边方案的边数为集合TT

那么我们就是要分别枚举S,TS,T中的元素,然后合并起来,即

xSyT(x+y) \sum_{x\in S}\sum_{y\in T}(x + y)

化下式子:

xSx×(yT)+(xS)×yTy \sum_{x\in S}x\times \Big(\sum_{y\in T}\Big) + \Big(\sum_{x\in S}\Big) \times \sum_{y\in T}y

到这一步就很显然了

fn,1=gn,1i=1n1(n1i1)(fi,1×gni,0+fi,0×gni,1) f_{n, 1} = g_{n, 1} - \sum_{i=1}^{n - 1}\binom{n - 1}{i - 1}\Big(f_{i, 1} \times g_{n - i, 0} + f_{i, 0}\times g_{n - i, 1}\Big)

继续考虑j=2j=2

xSyT(x+y)2=(xSx2)×(yT)+2(xSx)×(yTy)+(xS)×(yTy2) \begin{aligned} &\sum_{x\in S}\sum_{y\in T}(x + y)^2\\ =&\Big(\sum_{x\in S}x^2\Big) \times \Big(\sum_{y\in T}\Big) + 2\Big(\sum_{x\in S}x\Big)\times\Big(\sum_{y\in T}y\Big) + \Big(\sum_{x\in S}\Big) \times \Big(\sum_{y\in T}y^2\Big) \end{aligned}

dp式子就不放了


然后考虑求gg,设m=i(i1)2m = \frac{i (i - 1)}{2}

gi,0=2mgi,1=m2m1gi,2=m2m1+m(m1)2m2 \begin{aligned} g_{i, 0} &= 2^m\\ g_{i, 1} &= m2^{m-1}\\ g_{i, 2} &= m2^{m-1} + m(m-1)2^{m-2}\\ \end{aligned}

解释一下

j=1j=1时,考虑每条边的贡献,保证它出现,然后其他边随便选或不选的方案

j=2j=2时,对于某个边数为dd的图,考虑把贡献看成 的形式

即枚举图中的两条边,它们两的贡献是1×1=11\times1 = 1,这样就把乘积转化为求和的形式了

讨论一下这两条边是否是同一条边

T3

首先,对于一条边(li,ri,si)(l_i, r_i, s_i)而言,若被lil_i选,则权值为sis_i;否则为si-s_i

那么和这道题一样的转化后,显然是一棵基环树森林,每个基环树上只有可能是两种取值,假设它们为a,b(a>b)a, b(a > b)

我们需要求出两种方案,一种的权值和在数轴上正方向最接近00,另一种在负方向上最接近00

先每个基环树都取aa权值(较大的),求出来的权值和在tt的位置

  • t0t \le 0,则再换小的肯定不会更优

  • t>0t > 0,则有可能通过把某些aa换成bb之后,tt会减小,且仍>0>0

    再抽象一下,即现在有若干个的物品(权值为aba-b),需要用它们填一个容积为tt的背包,问最多能填多少

    因为权值比较小,重复的物品较多,所以跑多重背包即可

再对每个基环树取bb权值,做一遍类似操作即可,即从负方向逼近00一次

T4

我直接写的三维k-d tree,过了

9-4

Process

三道题都比较简单,没有挂分

T1

我直接用的set+链表模拟,实际上就是求最长上升子序列的长度

T2

dp[i][j]dp[i][j]表示到填第ii位,从i4i - 4ii构成的数等于jj的方案数

转移的时候注意一下前导0

T3

直接模拟,用BIT链加即可

9-5

Process

半个小时写完T1,想了很久的T2,无果,复习了一下SAM之后把T3写了。最后把T2写了个退火,获得了20分的好成绩

T1

a=E(A),b=E(B)a = E(A), b = E(B),则f[i]=f[i1]a+bf[i] = f[i - 1] * a + b

ans=f[k]ans = f[k]

等比数列求和即可,比较简单


注意特判公比为11的情况!!!

T2

首先需要注意到,最终的01串中的每一个数字展开(还原后)是一系列不相交的区间!!!

于是可以区间dp,设f[i][j][S]f[i][j][S]表示区间[i,j][i, j],合成的状态为SS的最大分数

因为区间长度确定,且每次操作后,长度都会减少K1K-1,因此SS的位数是确定的

len(i)len(i)表示区间长度为ii时, 最终合成的状态的长度,那么区间dp转移时枚举的kk需要满足len(ki+1)+len(jk)Klen (k - i + 1) + len(j - k) \le K

因此,所有>K>K的状态都可以通过若干个K\le K的状态合并出来

再优化一下,发现只需要保证len(jk)=1len(j - k) = 1即可,道理是一样的

时间复杂度O(n32k)O(n^3 2^k),常数很小


一道dp好题!

只不过一开始的区间dp我就没想到,一开始觉得转移之间会有问题,就没去想了,自己yy了一个假做法

后面的一些优化都比较套路,只是我不会巧妙

T3

广义SAM ,处理出size[i]size[i]表示ii节点,只有SS串的传统节点11的贡献的子树大小 ×\times ii节点的maxlenminlenmaxlen - minlensum[i]sum[i]ii到根的sizesize之和

SAM上匹配TT串,找到每个前缀的对应节点,答案加上该结点的sumsum

即对TT的每个前缀,把答案加上所有后缀在SS中的出现次数

每个点到根的sizesize之和,就是其所有后缀的出现次数

9-6

Process

T1的小结论我讲课讲过,积分部分也不难;T3是已经没有什么好害怕的了的弱化版。。。

T2题没看懂,写了个乱搞拿了20分

考场上T3搞了很久才想起来做法,反映出自己容斥还是比较弱,需要加强

T1

首先有

D(X)=E(X2)E2(X) D(X) = E(X^2) - E^2(X)

后面显然就是(l+r2)2(\frac{l+r}{2})^2,前面可以积分,原函数是h(x)=13x3+C\displaystyle h(x) = \frac{1}{3}x^3 + C,那么E(X2)=13x3rl\displaystyle E(X^2) = \frac{\frac1 3x^3}{r - l}

最后化简一下,D(X)=(rl)212\displaystyle D(X) = \frac{(r - l)^2}{12}

T2

插头dp

T3

容斥,设fif_i为恰好违反ii次规则的方案数,gig_i为至少违反ii次规则的方案数

gk=i=kn(ik)fifk=i=kn(1)ik(ik)gi \begin{aligned} &g_k = \sum_{i=k}^{n}\binom{i}{k}f_i\\ \Rightarrow &f_k = \sum_{i=k}^{n} (-1)^{i-k}\binom{i}{k}g_i \end{aligned}

然后考虑如何求gg

显然题目中的vv没有意义,把vv排序后就是一个nn的排列。于是转化为,求有多少个排列pp,至少有kk个位置满足pi<ip_i < i

dpi,jdp_{i, j}表示考虑到第ii位,有jj个位置满足限制(不考虑顺序)的方案数,那么gi=dpn,i×(ni)×(ni)!g_i = dp_{n, i}\times\binom{n}{i}\times (n - i)!

今天才搞懂容斥是怎么回事。。。

这里dpn,idp_{n, i}表示的,有ii个限制的方案,指的是只保证这ii个限制一定满足,而其他的数完全不考虑如何填的方案数,它并没有什么实际意义。乘上(ni)×(ni)!\binom{n}{i}\times(n-i)!之后才表示至少有ii个限制的方案数

而这里定义的,至少有ii个限制的方案数,也并不是真正意义上的至少。因为这里的至少是会算重的,否则fif_i为什么不等于gi+1gig_{i + 1} - g_i

正确的定义应该是,强制(钦定)ii个条件满足的方案数,只有这样才能从根本上使计数更加方便

这个dpdp转移很简单,若第ii个数满足限制,那么它能填前i1i-1个数的某一个;又因为前面已经选了j1j-1个数,所以它只有iji-j种选法

dpi,j=dpi1,j+(ij)×dpi1,j1 dp_{i, j} = dp_{i - 1, j} + (i - j)\times dp_{i - 1, j - 1}

注意到,把数组第二维翻转后就是第二类斯特林数的形式

多项式可以优化到O(nlogn)O(n\log n)

9-8

Process

T1几分钟写完,T2看错题,以为所有关键点都要在联通块中,浪费了很久时间

T3最后二十分钟rush出来了

T1

或的答案就是整个数组,与的答案就是每个长度为kk的区间

T2

总联通块数 减去 不满足条件的联通块数即可

对于每个点,统计以它作为联通块的最低点的方案

T3

贪心枚举最右边到了哪一列,中间每一列至少选一个,最多选nn个,总共要选kk

用一个小根堆随便维护一下

9-9

Process

T1搞了好久,矩阵快速幂推式子又推了半天!!!

然后剩下时间都在搞T2,写了一个退火乱搞只拿到了35分。考完之后发现T3是sb题

简单题还是做得太慢!!!

T1

随便找规律/搞系数,矩阵快速幂优化

T2

显然先缩边双。一个直观的贪心是枚举每个点为根,然后每个点从父亲往它连边

但是这个做法很容易被hack掉

19-9-9-1

19-9-9-2

注意,题解中deg[i]deg[i]是表示ii这个边双的大小。。。

第一部分就是那个看成树的贪心,第二部分直接背包

T3

因为ai100a_i\le 100,于是考虑和值域相关的做法

对于每个权值维护一个set,存该权值的出现位置

每次枚举一个权值,求出其位于当前区间内的出现次数,然后删掉这一段

计算出平均值后,按照题意重新赋值

直接暴力搞肯定不行,发现每次赋值都是一些连续段,于是set维护pair,存这样的连续段即可

时间复杂度不太会分析,但是看上去很对,跑得也很快

9-10

Process

现在开始联考了,考场状态还是有点问题,要多锻炼

先写的T2,写了个O(nm)O(nm)的做法,随便找赵规律就找出来了。T1暴力状压,复杂度O(3nk2)O(3^nk^2),可以随便跑。T3考场上想了个O(n3)O(n^3)的背包,结果没调出来,应该是有问题的,因为不好组合

最后T3暴力还挂了分,很不应该

T1

暴力状压

T2

找规律

T3

把题目中pkp^k的贡献拆开,把pp拆到每个kk

先枚举根,然后设f[i]f[i]表示只考虑ii子树时的期望答案,因为ii的每个子树是独立的,所以可以直接把期望乘起来,再考虑ii这个点的影响。若在值域序列中,ii插到最前面的位置(1size[i]\frac{1}{size[i]}的概率),则贡献pp;否则(size[x]1size[x]\frac{size[x] - 1}{size[x] }的概率)贡献11

f[x]=yson[x]f[y]×(psize[x]+size[x]1size[x]) f[x] = \prod_{y\in son[x]} f[y] \times (\frac{p}{size[x]} + \frac{size[x] - 1}{size[x]})

然后换根dpdp即可

因为p+size[x]1size[x]\frac{p + size[x] - 1}{size[x]}可能等于0,所以要记个前后缀积来dp

另外一种做法:考虑每个点的贡献,设sz[x]sz[x]表示在11为根情况下的sizesize,则它的sizesize要么是szsz,要么是nszn-sz,要么是nn

dfndfn上差分一下即可

9-12

Process

玩了好久的T1。T2考过。T3暴力没写完

Summary

不知道为什么还是感觉时间不够,又出现了暴力写不完的情况

感觉这几天有点集中不了精力去想题。。。

T1

先从大到小贪心,然后前十二位爆搜一下所有方案

T2

平面图转对偶图,把原图中的面看成点

具体见此

T3

...