CF653E
不难发现其实就是在假想中建立出可以存在的边的图,要求跟 \(1\) 相连的连通块个数 \(\leq k\) 且与 \(1\) 的连边个数 \(\geq k\) 且 全图联通,这个我们只需要知道其去掉 \(1\) 的连通性就很好讨论了。
我们其实不能直接建出这个极度稠密的图,但是我们可以用数据结构优化建图,直接线段树优化建图即可,具体而言我们维护线段树区间 \([l,r]\) 对应一个点 \(node_{l,r}\),比如说 \(x\) 第一次需要这个区间的就往 \([l,r]\) 上面依次连边,然后记录好 \(node_{l,r}\gets x\),之后如果要这个区间直接跟 \(x\) 连上就行了,但是这样子还是会 mle 喵,我们可以加一个小剪枝,就是说如果我们理论上要去拿一个 \(x\) 去连接已经有 \(node_{l,r}\) 的 \([l,r]\) 的子区间,可以直接连到 \(node_{l,r}\) 上面,反正连通性一样,然后这样就过掉了喵喵喵 >w<
CF965E
比较滴唐,直接建立出字典树,然后结点可能是有/无字符的,然后一个无字符点可以换一个子树中的有字符点上去,这个东西还是比较随便的,直接树上从下往上合并就可以了,可以 dfn 一个序列每次找区间 rmq + 带修改是一个可爱的线段树。听课的时候说,字典树的 \(\sum dep_i=\sum |S_i|\),其实暴力合并复杂度也很对。
CF1260E
你的朋友具有贿赂他人的能力,其实你的朋友才是最强的,对于原题中在 \(-1\) 左边的 \(a_i\gets 0\) 之后变成了,打败一个人 \(i\) 的代价是 \(a_i\) 询问最小代价。
然后有两个比较显然的观察,除去你的朋友能力值最强的人肯定会贡献 & 将除了你的朋友的人分成 \(1,2,\dots,\frac{n}{2}\) 这样一块一块然后每一块最强的人 win 肯定会贡献。
那我们照着这两个比较显然的东西往下想,但是我们好像没办法直接钦定除了你的朋友的意义下的最强者的一个很具体的连通块,那我们应该考虑一个合法的 winner 集合,这个 winner 集合的第一位一定是第一好孩子,假设这个第一好孩子喵了一个大小为 \(x_1\) 的连通块,那么去掉之后前 \(x_1+1\) 的超级好孩子都可以成为第二好孩子,假设这个第二好孩子喵了一个大小为 \(x_2\) 的连通块,那么去掉第一第二好孩子后前 \(x_1+x_2+1\) 的超级好孩子都可以成为第三好孩子,以此类推,贪心的想,\(x_i\) 肯定直接倒序给嘛,然后具体的获得 winner 就直接在堆里面贪心就好啦。
CF623B
首先注意到 \(m<n\),然后质数不劣,那 \(a_1,a_n\) 的质因数可能成为一个公约数且一定存在一个最优的公约数,现在考虑这个 \(p\) 的答案是什么,直接 dp 求出就可以了,具体的必须删除的位置要多仔细考虑一下。
CF1088E
首先观察到答案为 \(Ans\),那么选和 \(<Ans\) 都很没有必要,那么 \(k=1\) 肯定可以卷出一个 \(Ans\),卷出 \(Ans\) 之后最大化 \(k\) 就直接 dp 的时候碰到最好的置 \(0\) 答案 \(+1\),相当于一个尽量往下选的贪心。
CF794D
首先先考虑这个图长成什么样子,然后不难发现假设自己能到达自己,那么同一种 \(x\) 的能到达集合是相同的,我们对能到达的集合的点进行哈希,然后 \(x\) 相同的颜色块就可以拿出来了,然后连接不同颜色块的边的约束其实是一个差为 \(1\),使用 dfs 染色就可以了,为了方便可以从链的端点出发去染色。染完色之后暴力判定就行了,我觉得方便的判定方式是先判定边数是否正确,再判定原题中的边现在是否合法。
gosh 计划 7.18 A. 发牌姬(card)
第一位 \(1\) 对准,起点和下一个起点的 \(\mod M\) 已经被钦定了,建立边表示这个字符串然后就变成了欧拉回路。
gosh 计划 7.18 A. 发牌姬(card)
gosh 计划 7.18 A. 发牌姬(card)
标签:node,妄自,2024.7,好孩子,可以,然后,顾影自怜,直接,发牌 From: https://www.cnblogs.com/chelsyqwq/p/18312318