2020牛客暑期多校第七场

2020牛客暑期多校第八场

08.06训练

动态图连通性

AtCoder Beginner Contest 174

LOJ:

分拆数

「离线可过」动态图连通性

贪心乱搞

暂无

见本周推荐

暂无

暂无

见本周推荐

LOJ:

分拆数

题意:

定义$f(i)$表示整数$i$有多少种不同的拆分方式,求$f(1)$到$f(n)$.

tag:计数,生成函数,多项式

题解:

从生成函数的角度考虑,不难得到,最后答案的生成函数为$\Pi \frac{1}{1-x^{i}}$.求个$ln$,就会得到$\sum \sum \frac{x^{i*j}}{j}$.后面的式子可以通过枚举指数在$O(n \log n)$的时间内得到每一项的系数,然后再用多项式exp转化回去就行了,对应的系数就是答案.总的时间复杂度也是$O(n \log n)$.

comment:还可以通过五边形定理解决,个人感觉上面的手法更巧妙一些,不过常数也更大.

LeetCode. 424

题意

给一个非空字符串 $s$，可以做 $k$ 次操作，每次操作是把串中任意一个位置赋值为任意一个字符。求操作后最长的由同一个字符组成的连续子串的长度。

tag

贪心，双指针

题解

考虑最终完成操作后的那个最长连续子串，它的长度应该 $\le$ 最初那个出现最多的字符的次数 $+k$。那么可以枚举所有的子串，看其中出现次数最多的字符个数 $+k$ 是否 $\ge$ 其长度，满足这个条件的最长子串就是答案。但复杂度 $n^2$ 显然不能接受。

考虑利用单调性来优化枚举子串的过程。实际上可以维护一对距离单调不减的双指针来做：首先初始化 $l=0, r=1$。对于每个时刻，如果此时 $s[l:r]$ 是满足条件的，那么就更新一下答案 $\text{ans}=\max\{\text{ans},~r-l\}$，然后 $r+=1$，扩大双指针间距，再继续检查（$s[l:r]$ 的子串没必要再检查了因为长度只会更短，不会影响答案）；如果此时 $s[l:r]$ 是不满足条件的，易知 $\forall t \in [r, len(s)],~s[l:t]$ 都不满足条件，也就是从 $l$ 开始的所有子串都不会再影响答案了。那么我们只需要 $l+=1,~r+=1$，继续考虑从 $l+1$ 开始的子串就行了。

至于计数，用一下哈希表/直接用数组。最终复杂度是线性的。

代码

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        from collections import defaultdict
        l, r, n = 0, 1, len(s)
        cnt, max_cnt, ans = defaultdict(int), 0, 0
        while r <= n:
            cnt[s[r-1]] += 1
            max_cnt = max(cnt[s[r-1]], max_cnt)
            if max_cnt + k >= r-l:
                ans = max(r-l, ans)
            else:
                cnt[s[l]] -= 1
                l += 1
            r += 1
 
        return ans

https://ac.nowcoder.com/acm/contest/5673/I

题意

给若干对整数，从每对中任选一个或一个都不选，同样的数只能选一次，问最多能选到多少数？

tag

DFS，图

题解

相当于给一个图，每次从每条边上挑一个点选，显然当一个n个节点的图是树的时候就只能选n-1个数，因为只有n-1条边。

当这个图里有一个环的时候，不难理解只要用环上边选择环上点，然后随便一个dfs就能把剩下的点全都选到。

所以原题答案就是把图建起来，挨个判断每个集合是树还是环，把贡献累加起来。