贪心乱搞

暂无

见本周推荐

LeetCode. 424

题意

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

tag

贪心，双指针

题解

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

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

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

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

题意

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

tag

DFS，图

题解

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

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

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