• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

题目总结

开发技术 开发技术 1周前 (04-08) 3次浏览

感觉有些时候题目也做不动,而且有些题目貌似也是似懂非懂,虽然写出来了,但是未必理解,还经常要看题解。于是总结一下题目写过的题目也比颓废发呆好。

题目基本是我认为比较“好”的题或者一些经典题,不保证不咕,主要是写给自己看的,不保证对其他人有价值。


如果我写的部分有错误可以直接和我说。


P4766 [CERC2014]Outer space invaders

题意:有 (n) 个外星人,第 (i) 个外星人在 ([l_i,r_i]) 时段出现,需要 (d_i) 的成本打败。在某一时刻使用 (x) 的成本能够打败所有在该时刻出现的需要成本 (le x) 的外星人,求最小要多少成本。

看到数据范围想到区间 dp 与离散化,然后我就不会了。

首先离散化,使时间区间为 ([1,p])(dp_{i,j}) 表示杀死出现时间 ([l,r] in [i,j]) 的所有外星人的最低成本,则答案为 (dp_{1,p}),考虑转移。

  • 如果没有外星人,那么 (dp_{i,j}=0)
  • 如果有外星人,那么设 (maxn_i=max(d_p) ([l_p,r_p]in [i,j])),不难得到 (dp_{i,j}=min(dp_{i,k-1}+maxn_k+dp_{k+1,j}) (k in [i,j]))

然后发现预处理 (maxn) 数组是 (O(n^2)) 的,时间复杂度是 (O(n^4)) 貌似并不过的,如果用线段树维护 (maxn) 的话也要 (O(n^3 times logn)),因为离散化之后 (n) 达到了 (600) 的规模也很难过去。(但是我并没有尝试过,可以尝试一下)。

接下来是一个比较重要的结论了:我们并不用处理 (maxn) 数组,只要直接找到一个 (p) 满足 (d_p) 在所有满足条件的点中最大,这样子就能够做到 (O(n^3)) 了。

为什么这样子是对的呢?绝大部分题解都没有解释,可能他们觉得这个太简单了。感性理解一下,枚举的这个 (k) 就意味这在 (k) 这个时间点上进行一次操作。那么对于 (p),必然有一个操作是在 ([l_p,r_p]) 之间的(为了消除 (p)),而且因为 (p) 是最大的,那么 (maxn) 就显然是 (d_p) 不用预处理了。

code。


P4180 [BJWC2010]严格次小生成树 经典题。

如果是非严格的最小生成树怎么做?

首先用 Kruskal 建出最小生成树,然后枚举每一条边并且加入这条边 ((u,v)),减去树上 ((u,v)) 这条路径上的最大边,取 (min) 即可。

最大边怎么求呢?用类似于 (LCA) 求法的倍增即可。

可是严格的怎么做呢?注意到非严格的做法之所以是非严格的,是因为有可能加入的边的权值和删去边的权值相同。所以倍增的时候记录下非严格的第二大的边,倍增即可,写起来有点麻烦,但是数据强度很低。

code。


CF981D Bookshelves

题意:给你一个数组 (a_{1…n}),将 (a) 划分为 (k) 段,使每段按位与和最大。

首先弄个前缀和,(sum_i=sum_{j=1}^i a_j)

因为是按位与和,所以从高到低安慰考虑。若现在的答案是 (ans),那么就要判断 (ans’=ans|2^i) 是否可行。

那么怎么判断呢?直接判断 (ans’) 比较困难,可以尝试判断是否存在 (x) 满足 (x And ans’ = ans’)。有一个结论: ((aAnd b) And ans’=ans’ Leftrightarrow (a And ans’=ans’)And (b And ans’=ans’))。设 (dp_{i,j}) 表示前 (i) 个数分成 (j) 段之后能否存在 (x) 满足(x And ans’ = ans’)。状态转移方程为 (dp_{i,j}|=dp_{p,j-1} And ((sum_i-sum_p) And ans’==ans’))。其中 (dp_{0,0}=1)

看上去到这里就结束了?其实小蒟蒻自己在做题的时候还有一个疑惑:为什么 (dp_{0,0}=1)?实际上,因为 (dp_{0,0}) 的意义是前 (0) 个数选 (0) 个,后面若有一段为 (x),那么这两段的按位与和就是 (x)(因为实际上只有一段),说明 (dp_{0,0}) 所“代表”的数 (And) 任何数都是它自身。那么显然 (And ans’=ans’),所以 (dp_{0,0}=1)可能说的并不是很好,请轻点 D 我

code。


CF1491D Zookeeper and The Infinite Zoo

题意:对于点 (u),有一条 (u to (u+v)) 的单向边当且仅当 (uAnd v=v),多组询问,每次给出一个 ((u,v)),询问是否存在一条 (uto v) 的路径。

虽然只是 Global Round 的 D 题,但是我好菜。。。

第一个结论:若 (u>v),则无解,原因显然。

第二个结论:对于每个 (u),不妨每次增加一个 (v) 满足 (v=2^i(iin N))

为什么呢?如果增加的是另一个数 (x=2^{a_1}+2^{a_2}+…+2^{a_n}),那么加 (n) 次,第 (i) 次加 (2^{a_i}),显然是可行的,并且最终结果是一样的。

第三个结论:因为已知 (u le v),设 (v) 中第一个为 (1) 的数位为 (k),那么 (u) 中第一个为 (1) 的数位必须 (le k),同时,第二,第三个都同理。即:设 (sum1_k)(u)(1-k) 位中 (1) 的个数,(sum2_k)(v)(1-k) 位中 (1) 的个数,那么对于任何时候都要有 (sum2_kle sum1_k)。必要性显然。充分性我们可以这么构造:因为 (u le v),可以一位一位的把当前最高的不相同的位推到相同的,然后就可以了。建议手玩几个试一下。比如:((011010)_2)((100100)_2),可以 ((011010)_2 to (100010)_2 to (100100)_2)

代码就很好写了。code。


CF125E MST Company 经典题。

因为 (n le 5000),考虑 (n^2) 算法

首先断掉与 (1) 号点连接的所有边,形成若干个联通块。对于每个联通块做一个最小生成树。然后连一条到 (1) 号点最小的边。设有 (x) 个联通块,如果 (x > k) 则无解,否则还要加上 (k-x) 条边。

对于每次加边,找到所有除去与 (1) 连接的边后所有森林中每个点 (i) 到当前(除去 (1) 号点)的根最大的边 ((p1_i,p2_i)) 以及其权值 (maxn_i),求出边 ((1,u)) 满足 (w-maxn_u) 最小并且加入 ((1,u)),删去 ((p1_u,p2_u))。时间复杂度 (O(n^2))

实现比较难,有比较多的细节。code。


P3978 [TJOI2015]概率论 生成函数经典题,可以找规律。

下面给出生成函数的推法:

(g_n)(n) 个点的二叉树的数量,(f_n)(n) 个点的所有二叉树的儿子的和,那么不难得到:(ans=frac {f_n} {g_n})

先考虑 (g_n) 怎么算。若左儿子的节点数为 (displaystyle i (0le i le n-1)),那么对于(g_n) 的贡献为 (displaystyle g
_i times g_{n-i-1})
,那么不难得到 (displaystyle g_n = sum_{i=0}^{n-1}g_i times g_{n-i-1})(g_0=g_1=1),不难发现这是个卡特兰数,即 (displaystyle g_i=frac{C_{2times n}^{n}}{i+1})

然后考虑 (f_n),若左节点的个数为 (displaystyle i (0le i le n-1)),那么左儿子对于答案的贡献为 (displaystyle f_i times g_{n-i-1}),因为左右对称,所以不难得到 (displaystyle f_n=2times sum_{i=1}^{n-1} f_i times g_{n-i-1}),这个怎么推呢?

考虑 (g_i) 的生成函数 (G) 以及 (f_i) 的生成函数 (F),那么不难得到:(G(x)=xtimes G(x)^2+1,F(x)=2times xtimes F(x)times G(x)+x)

对于前面一个式子我们可以得到 (G(x)=frac {1-sqrt{1-4times x}}{2 times x})(G(x)=frac {1+sqrt{1-4times x}}{2 times x}),后者显然不是收敛的,舍去。

再通过后面一个式子可以得到:(F(x)=x times (1-4 times x)^{- frac 1 2})

我们需要找到 (G(x))(F(x)) 的关系。不难发现:(displaystyle (G(x)times x)’=(1-4 times x)^{- frac 1 2}=frac {F(x)} x),即 (displaystyle F(x) = x times (G(x)times x)’)

则:(displaystyle f_n=[x^n]F(x)=[x^{n-1}](G(x)times x)’=n times g_{n-1}=C_{2times n-2}^{n-1})

(displaystyle C_{2times n-2}^{n-1}=frac {(2times n-2)!}{((n-1)!)^2}=frac{(2times n)!}{(n!)^2} times frac{n^2}{2times n times (2 times n-1)}=C_{2times n}^{n} timesfrac{n}{2 times (2 times n-1)})

那么:(displaystyle ans=frac {f_n}{g_n}=frac {C_{2times n}^{n} timesfrac{n}{2 times (2 times n-1)}}{frac {C_{2times n}^{n}}{n+1} }=frac{ntimes (n+1)}{2times (2times n-1)})

代码就不贴了。


CF708E Student’s Camp 毒瘤推式子题。

首先考虑朴素的 dp:设 (dp_{i,l,r}) 表示第 (i) 天剩下区间 ([l,r]) 并且合法的几率,剩下 ([l,r]) 的几率很好算,不妨设为 (P_{l,r})。设 (d_x) 表示 (t) 天中有 (x) 个被吹走的几率,(p = frac a b) 为一天的几率,那么不难得到 (d_x = C_{t}^{x}times p^x times {(1-p)}^{t-x}),那么显然 (P_{l,r} = d_{l-1} times d_{m-r})

同时我们不难推出转移方程:(displaystyle dp_{i,l,r} =P_{l,r} times sum_{[l’,r’] cap [l,r] ne varnothing}dp_{i-1,l’,r’}),然而这样显然是不够的,考虑优化

使用容斥的思想不难得到:(displaystyle dp_{i,l,r} =P_{l,r}times sum_{[l’,r’] cap [l,r] ne varnothing}dp_{i-1,l’,r’} =)
(displaystyle P_{l,r} times (sum_{l’,r’}dp_{i-1,l’,r’}-sum_{l’le r'<l}dp_{i-1,l’,r’}-sum _{r<l’ le r’}dp_{i-1,l’,r’}))

(displaystyle f_{x,l}=sum_{l’ le r’ < l}dp_{x,l’,r’}),不难得到:(displaystyle dp_{i,l,r}= P_{l,r} times (f_{i-1,m} – f_{i-1,l-1}-f_{i-1,m-r}))。而且显然,(f_{n,m}) 就是答案。

再设 (displaystyle g_{x,r}= sum _{l<r}dp_{x,l,r}),那么有 (displaystyle f_{x,l}=sum_{l'<l}g_{l’})

(displaystyle g_{x,r}= sum _{l<r}dp_{x,l,r}=sum_{l<r} D_{l-1} times D_{m-r} times (f_{x-1,m}-f_{x-1,l-1}-f_{i-1,m-r})=)
(displaystyle D_{m-r} times (sum _{l<r}D_{l-1} times (f_{x-1,m}-f_{i-1,m-r+1})-sum_{l<r}D_{l-1}times f_{x-1,l-1}))

对于 (D_{i})(D_{l} times f_{x-1,l}) 做一个前缀和就可以做到 (O(n^2)) 了。

code。


CF516D Drazil and Morning Exercise

首先考虑把 (f_i) 求出来。

这部分先咕了,等我找到一个说的清楚的方法再来。

然后我们可以观察到一个性质,找到点 (u) 满足 (f_{u}) 最小,那么以 (u) 为根,对于任何 (v1) 以及在 (v1) 的子树中过的 (v2),有 (d_{v1} le d_{v2})

要证明这个结论,只需证明:对于任何 (v1) 以及在 (v1) 的儿子的 (v2),有 (d_{v1} le d_{v2})。证明如下(建议画个图理解):

  • (v1) 的最长路径不经过 (v2),那么因为 (v2)(v1) 的儿子,那么 (v2) 先经过 (v1),然后走 (v1) 的最长路径,那么显然有 (d_{v1} le d_{v2})
  • (v1) 的最长路径经过 (v2),那么 (u) 就可以先到 (v1),然后走 (v1) 的最长路径,即 (d_{v1} le d_{u}),矛盾,不可能。

综上,结论成立。

那么使用双指针,并且用并查集维护。根据结论,每次删除的点都是最外面的点,不会影响连通性,那么直接把 (size) 减一就可以了。

code看代码可能更能够理解。


CF643F Bears and Juice 神仙题。

其实这是一道构 造 题。

题意:先咕了。

首先考虑,我们能够得到的“信息”是什么?

  • 有哪些熊去睡觉了,有哪些熊没有去。
  • 睡觉的哪些熊,他们是在什么时候睡觉的。

那么共有 (x) 天时,我们能够得到的信息的种类数即为:(displaystyle sum=sum_{i=0}^{min (p,n-1)}( dbinom{n}{j} times x^i))

解释一下这个式子:首先枚举睡觉的熊的数量 (i),因为有 (n) 头熊,那么有 (C_{n}^i) 种情况。此外,睡觉的熊可以在 (1-x)(x) 天中任选一天睡觉,那么就是 (x^i),乘一下再加一下就可以了。

但是这个信息数只是答案的“上限”,因为一般来讲这个上限都是达得到的,而且你如果交一发你就会发现你过了,所以考虑如何构造出一种方案可以达到这个上限 (sum)

我们把所有方案编号为 (1-sum),酒的编号也为 (1-sum),显然,每种方案是要恰好对应一个酒的。那么对于熊 (a),若方案 (i) 中他没有睡觉,那么他就不喝第 (i) 桶的饮料。否则,如果他在 (j) 时刻去睡觉了,那么他就在 (j) 时刻喝第 (i) 桶的饮料。不难发现,这样做事一一对应的。

那么我们就能够得到答案 (displaystyle xor_{i=1}^{q} (i times sum_{j=0}^{min(p,n-1)}(dbinom{n}{j} times i^j)) mod 2^{32})

结果我们发现 (2^{32}) 不是质数,(dbinom{n}{j}) 比较难求。注意到 (p) 比较小,把分母里的数约掉就可以 (O(p^3)) 预处理了。

时间复杂度 ((p^3 times log n + q times p))

code。


CF891E Lust 生成函数,多项式。

首先观察到一个简单的结论:设一开始的数是 (a_i)(题目已经给出),结尾的数是 (a_i-b_i)(displaystyle 0 le b_ile k,sum_{i=1}^n b_i=k)),那么这样子的答案为 (displaystyle prod_{i=1}^n a_i – prod_{i=1}^n(a_i-b_i))

虽然这个结论很简单但是我还是没有发现。我们可以用数学归纳法证明:对于某次将 (a_x) 减一的操作,这次操作所产生的贡献是 (displaystyle prod_{i ne x,1le x le n}a_i=a_xtimes prod_{i ne x,1le x le n}a_i-(a_x-1)times prod_{i ne x,1le x le n}a_i)。显然成立。

那么我们只要算出 (displaystyle prod_{i=1}^n(a_i-b_i)) 的期望 (E) 就可以了。

不难得到:$ displaystyle E = frac 1 {n ^ k } times k! sum_{ b_i } ( frac {prod_{ i=1 }^n( a_i – b_i) }{ prod_{i=1} ^ n (b_i !)}) = displaystyle frac 1 {n^k} times k! sum_{ b_i }( prod_{ i = 1 }^n( frac { a_i – b_i }{b_i!}))$。

考虑把上述式子写成生成函数的形式 (displaystyle F_i(x)=sum_{j=0}^{infty}frac {a_i-j}{j!}=sum_{j=0}^{infty}frac {a_i}{j!} -sum_{j=0}^{infty} frac j {j!}=(a_i-x)times e^x)

那么不难得到答案为 (displaystyle [x^k](frac 1 {n^k} times k! times prod_{i=1}^n F_{i}(x))=[x^k](frac 1 {n^k}times k! times prod_{i=1}^n(a_i-x) times e^{ntimes x}))

因为 (displaystyle prod_{i=1}^n(a_i-x)) 是一个 (n) 次多项式,(n le 5000) 直接暴力算出来就可以了,设 (displaystyle prod_{i=1}^n ( a_i – x ) = sum_{i=0}^n f_itimes x^i),又已知 (displaystyle e ^{n times x}=sum_{i=0}^{ infty } frac {n^ktimes x^k}{k!})。不难有 (displaystyle [x^k](frac 1 {n^k}times k! times prod_{i=1}^n(a_i-x) times e^{ntimes x}) = frac {k!}{n^k} times sum_{i=0}^k f_i times frac { n^{k-i}}{(k-i)!}=displaystyle sum_{i=1}^k f_i times n^{-i}times frac {k!}{(k-i)!}),发现后面那个东西就是一个下降幂,提前预处理就可以了。

时间复杂度 (O(n^2))。因为题目没给 NTT 模数而且 (n le 5000) 就没必要再一步优化了。

code。


CF521D Shop

((opt,x,y)) 为一次操作 ,首先考虑只有 (3) 操作的情况。因为要求的是 (displaystyle prod_{i=1}^n a_i),那么不难发现乘在哪里都是一样的,所以把所有的值从大到小排序就可以了。

然后我们不难发现一个性质:所有操作必然是先 (1),再 (2),再 (3) 的。

这启示我们把 (1) 操作和 (2) 操作也转换成 (3) 操作(即乘上一个数)。

先考虑 (2) 操作。对于同一个下标 (x),对他进行的操作必然是要从大到小操作的。那么不妨先从大到小排序。每次操作 ((2,x,y)),那么就算出这次操作前下标为 (x) 的值 (sum),那么这次就相当于乘了一个数 (displaystyle frac {sum+y}{sum}),这样就转换成操作 (2) 了。

那么操作 (1) 呢?首先,对于每个数,我们只需要找到最大的操作 (1),设为 ((1,x,y)),然后就可以把这个操作转换成 ((2,x,y-a_x)) 就可以了。

然后把所有乘起来的东西从大到小排序。找到前 (m) 个就可以了。

但是,这样子就可能做不到 (1 to 2to 3) 的顺序了,怎么办呢?实际上,因为乘法满足交换律,对于前 (m) 个操作,我们再对于 (opt) 从小到大排序就可以满足了。

code。


P3758 [TJOI2017]可乐 经典题,没看题解。

观察数据范围,考虑矩阵加速。

留在原地和去别的城市都是经典问题,直接连边就可以,难点在与自爆怎么处理,虽然也不是很难

可以考虑新建一个点 (s=n+1),一个点到了这里就表示他在自爆了,那么加上 ((i,s) (1 le i le s)) 的边就可以了。接下来就是常规操作矩阵加速了。时间复杂度 (O(n^3 log t))

code。


AT2046 [AGC004F] Namori 神仙题。

(本题解的图来自 @unputdownable

首先 (n) 为奇数显然不可能。

先考虑是一棵树的情况。树显然是一个二分图。把二分图左边的点染成黑,右边的点染成白色(即奇偶染色)。规定左边的点是黑色或者右边的点是白色的时候,这个点的真实颜色是白,否则就是黑。那么不难发现,一个合法的操作必然就是对于两个颜色不同的点交换其颜色,而最终的要求就是把所有白色换成黑色,黑色换成白色。

那么显然有白色的数量等于黑色的数量,否则不合法。

那么对于每个子树,设黑色的点与白色的点的差为 (x),那么这个子树的根节点与其父亲之前的这条边至少要运输 (|x|) 个点,即交换 (|x|),那么答案的下界就是 (sum |x|)

其实我们完全可以猜测答案就是 (sum |x|)。只要让每条边不进行多余的操作就行,观察一下并且感性理解一下这是做得到的。

其实非常的不严谨。我以后如果记得的话会补一个严谨的东西上来的。

实现的时候把白点设为 (-1),黑点设为 (1),那么记录一下子树中所有和就可以了。

那么树的情况就解决了,接下来考虑基环树的情况。

  • 环上的点数为偶数。

先断掉一条边,然后算出子树和 (s_i)

题目总结

然后考虑被断掉的这条边,如果这条边运输 (x) 的权值,那么:

题目总结

左边的点的权值为 (s_i+x),对答案的贡献为 (|s_i+x|=|-s_i-x|),右边的点的权值为 (s_i-x),对答案的贡献为 (|s_i-x|),设左边的点有一个 (k_i=-1),右边的点 (k_i=1)

设环上的点组成的集合为 (S) 那么就能得到:(displaystyle ans = min(|x|+ sum_{i in S}|k_itimes s_i-x|+sum_{i notin S}|s_i|)),就相当于求 (displaystyle min(sum_{i in S}|k_i times s_i -x|+|x|)=min(sum_{i in S}|k_i times s_i -x|+|0-x|))。这是一个经典问题。把所有的 (k_i times s_i)(0) 放入数组中,取中位数就可以了。

  • 环上的点数为奇数。

题目总结

这个时候图就不是二分图了,考虑如何断掉这条边。

此时操作这条边的效果就是使黑点数量 (+2)(-2)

那么设此时 (sum =sum c_i),那么可以操作 (frac {sum} 2) 次让它变成 (0)

然后就转化成树的问题了。

code。


CF1119H FWT 好题。

一个非常 naive 的想法就是对于每个 ((a_i,b_i,c_i)),设 (F_i[a_i]=x,F_i[b_i]=y,F_i[c_i]=z),然后答案就是 (F_1 oplus F_2 oplus.. oplus F_n),其中 $ oplus $ 表示异或卷积,时间复杂度 (O
(ntimes ktimes 2^k))
,明显不能通过。

我们可以进行优化,对于每个 (F_i),算出其 (FWT_i),然后将其每项相乘再 (IFWT) 回去,时间复杂度 (O((n+k)times 2^k)),还是不能通过。

我们发现每个 (F) 只有三个数有值,考虑在这方面进行操作。

(displaystyle prod_{k=1}^n FWT(F_k)[i]= prod_{k=1}^n ((-1)^{cnt(i And a_k)}times x+ (-1)^{cnt(i And b_k)}times y +(-1)^{cnt(i And c_k)}times z))

注意到上面这个东西必然只有 (8) 种可能。然而还是太多了。不妨让 (a_i=0,b_i=b_i oplus a_i,c_i=c_i oplus a_i),那么最后 (ans_{i oplus a_1 oplus a_2 oplus … oplus a_n}) 就是 (i) 的答案。

这样子的话就只有 (4) 种可能:(x+y+z,x+y-z,x-y+z,x-y-z)。设这四种出现的次数分别为 (w1,w2,w3,w4)。那么就有 (displaystyle prod_{k=1}^n FWT(F_k)[i]= (x+y+z)^{w1}times (x+y-z)^{w2} times (x-y+z)^{w3} times (x-y-z)^{w4})

那么对于每个 (i) 算出 (w1,w2,w3,w4) 就可以得到 (displaystyle prod_{i=1}^n FWT(F_k)),再 (IFWT) 回去就可以得到答案。

那么怎么算出 (w1,w2,w3,w4) 呢?首先不难有 (w1+w2+w3+w4=n)

(F1_{k}[b_k]=1),那么 (FWT(F1_k)[i]=(-1)^{cnt(iAnd b_k)}),设 (displaystyle s1= sum_{k=1}^n FWT(F1_k)[i]),那么有 (s1=w1+w2-w3-w4)

怎么算出 (s1) 呢?我们有 (displaystyle sum_{k=1}^n FWT(F1_k)[i]= FWT(sum_{k=1}^nF1_k)[i]),然后就可以快速求出来了。

同理令 (F2_{k}[c_k]=1),那么有 (displaystyle s2=sum_{k=1}^n FWT(F2_k)[i]=FWT(sum_{k=1}^nF2_k)[i])

接下来令 (F3_{k}[b_k oplus c_k]=1),那么 (displaystyle FWT(F3_{k})[i] = (-1)^{cnt(iAnd (b_k oplus c_k))}=(-1)^{cnt(i And b_k)}times (-1)^{cnt(i And (c_k))})

那么有 (displaystyle s3=sum_{k=1}^nFWT(F3_k)[i]=FWT(sum_{k=1}^n F3_k)[i]=w1-w2-w3+w4)

那么我们就有 (4) 个方程 (4) 个未知数,不难手算出 (w1,w2,w3,w4)

然后得到 (FWT(F))(IFWT) 回去就可以了。

code。


CF348D Turtles 容斥 dp,经典题。

首先考虑只有一只乌龟的时候怎么做,

这就是一个经典的 (dp) 问题,设 (f_{i,j}) 表示点 ((1,1))((i,j)) 的方案数,(a_{i,j}) 表示 ((i,j)) 是否可走,那么有不难有:

(f_{i,j}=begin{cases} 0 (a_{i,j}=0) \ f_{i,j}+f_{i-1,j}+f_{i,j-1} (a_{i,j}=1)end{cases})

然而题目让我们求的是两条不相交的路径,这个怎么求呢?

我们不难注意到,不相交的路径必然是一条 ((1,2) to (n-1,m)) 的路径和 一条 ((2,1) to (n,m-1)) 的路径,而一条 ((1,2) to (n,m-1)) 和一条 ((2,1) to (n-1,m)) 必然是相交的。那么我们因为我们能求助所有 ((1,2) to (n-1,m)) 的路径和 ((2,1) to (n,m-1)) 的路径,那么我们只要减去满足上述条件,并且相交的路径总数就可以了。

对于两条有交点的路径,不妨在最后一个交点处,交换剩下的两个路径。那么这就转换成了一条 ((1,2) to (n,m-1)) 和一条 ((2,1) to (n-1,m)) 的路径。并且不难发现,这些路径是一一对应的。所以相交的路径总数就是 一条 ((1,2) to (n,m-1)) 和一条 ((2,1) to (n-1,m)) 的路径总数。

画几幅图可能更容易理解:如果原来的两条相交的路径是这样的:

题目总结

其中黄线和绿线分别表示两条路径,红圈表示最后一个交点处。那么可以讲此图转换成:

题目总结

这样就是满足第二个条件的路径了。同理,每个满足第二个条件的两条路径也能够转化回来。

然后就转换成上述的经典问题了。设 (F(x1,y1,x2,y2)) 表示 ((x1,y1) to (x2,y2)) 的路径总数,那么有 (ans=F(1,2,n-1,m)times F(2,1,n,m-1)-F(1,2,n,m-1)times F(2,1,n-1,m))。时间复杂度 (O(n^2))

(吐槽:用 stringcin 读入字符串会被卡常)。

code。


CF727F Polycarp’s problems dp。

首先不难发现,答案其实是有单调性的。具体的说,若初始的心情是 (p),留下了 (x) 个数,那么有 (x) 越大,(p) 越小((0 le p))。

因为有多个询问,所以每次对二分出来的值必须快速判断,这提示我们可以预处理。

具体的说,设 (dp_{i,j}) 表示点 (i-n) 中,保留 (j) 个数,所需的最小的初始值。

那么有 (dp_{i,j}=max(dp_{i+1,j},min(0,dp_{i+1,j-1}-a_i)))。这个式子应该很容易理解。

那么预处理出 (dp_{i,j}) 之后,在 (dp_{1,x}) 上二分或者把所有询问离线双指针就可以了。

code。


CF1016F Road Projects。

首先不难发现,答案不会小于原来 (1 to n) 的路径长度。

(dis_i) 表示 (1to i) 的路径长度,考虑什么时候答案就是 (dis_n)

(1to n) 的所有路径上的点拉出来形成一条链在,设这个链的集合为 (S),那么整棵树必然是这个链上的每个节点以及其子树构成(子树可以没有)的一个树。

题目总结

那么如果一个节点的子树除了它自身有超过 (2) 个节点的话,那么取两个节点连一条边,答案就是 (m)(dis_n) 了。

接下来考虑不是这样的情况,即一个节点的子树除了它最多只有一个节点。

题目总结

不难发现,要是连 (u to v) 的边,如果 (u) 有子节点 (s),那么连 (s to v) 会更优, (v) 同理。

(f_u) 表示点 (u) 到其子节点的距离。如果其没有子节点就为 (0),那么有 (displaystyle ans=max_{l,r in S,dis_l < dis_r}(x+dis_l+f_l+dis_n-dis_r+f_r)=x+ max_{l,r in S,dis_l < dis_r}(dis_l+f_l+dis_n-dis_r+f_r))。发现和 (x) 是没有关系的。预处理出 (displaystyle max_{l,r in S,dis_l < dis_r}(dis_l+f_l+dis_n-dis_r+f_r)) 就可以了。对于 (dis_l+dis_r) 做个前缀最大值就可以了。

时间复杂度 (O(n^2))。写代码的时候要注意判断 (l,r) 能否相邻,这个自己想一想就好了。

code。


CF1146E Hot is Cold 数据结构。

因为 (a_i) 的值域是 ([-10^5,10^5]),而且对于 (x),他最后只能变成 (x) 或者 (-x)

所以考虑用数据结构维护每个数 (x) 最后变成了 (-x) 还是 (x),如果是 (-1) 则表示为 (-x)(1) 则表示为 (x)。接下来考虑 $s = ‘>’ $ 的情况。

  • (x ge 0) 的情况。

那么对于 ([-x,x]) 的数 (a),无论是 (-a) 还是 (a)(ge x),不用进行操作。

对于 ([x+1,10^5]) 之间的数 (a),若是 (-a),那么不会有变化。否则 (a) 就会变成 (-a),这样对于 ([x+1,10^5]) 之间的数全部设置为 (-1) 就可以了。同意,对于 ([-10^5,-x-1]) 之间的是要全部设置为 (1)

  • (x < 0) 的情况。

对于 ([x+1,-x-1]) 之间的数 (a),无论 (a) 上维护的值是 (1) 还是 (-1),都需要乘上 (-1),即区间 (times -1)

对于 ([-10^5,x-1]) 之间的数 (a),维护的值必然会变成 (1)。对于 ([-x+1,10^5]) 之间的数,维护的值必然会变成 (-1)

(s='<‘) 是同理的,所以只要维护一颗能做到区间乘 (-1),区间赋值为 (1)(-1) 的线段树就可以了。

code。


[ZJOI2015]地震后的幻想乡 概率dp,状压。

神仙题,先咕了。


P3750 [六省联考2017]分手是祝愿

先考虑 (k=n) 的时候怎么做。不难发现,必然是从大到小对于每一个亮的灯进行操作,时间复杂度 (O(n sqrt n))

如果当前还需要进行 (i) 次操作,那么显然在下一步操作中,有 (frac i n) 的几率让需要操作的次数 (-1) ,有 (displaystyle frac {n-i} n) 的几率让需要操作的次数 (+1)

(f_i) 表示进行 (i) 次操作 $to $ 进行 (i-1) 次操作的期望时间,那么不难有 (displaystyle f_i=frac {n-i} n (f_{i+1}+f_i+1)+ frac i n),化简后得 (displaystyle f_i=frac {(n-i) times f_i + n}{i})。不难有 (f_n=1)

算出 (f_i) 之后我们还需要算出此时最少的操作 (cnt),如果有 (cnt le k),那么答案就是 (cnt),否则答案就是 (displaystyle sum_{i=k+1}^{cnt}f_i+cnt),别忘了还有乘上 (n!)

code。


P6669 [清华集训2016] 组合数问题 数位dp。

注意到 (k) 很小,联想到卢卡斯定理:

(displaystyle dbinom{i}{j} equiv dbinom {frac{i}{k}}{frac {j}{k}} times dbinom{i bmod k}{j bmod k}pmod k)

(i)(j)(k) 进制拆分。设 (i)(j) 的第 (p) 位分别是 (a1_p,a2_p),长度为 (len),那么 (displaystyle dbinom {i}{j} equiv prod_{p=1}^{len} dbinom{a1_p}{a2_p}pmod k)

又有 (a1_p,a2_p<k),那么 (dbinom{i}{j} equiv0 pmod k) 等价于存在 (p) 满足 (a1_p<a2_p)。用数位dp做一下就好,具体细节可以看代码。code。









咕了。


程序员灯塔
转载请注明原文链接:题目总结
喜欢 (0)