Codeforces 165E Compatible Numbers

题目链接:https://codeforces.com/contest/165/problem/E

1 题目大意

给定一个长度为 $n$ 的序列 $a$。

对于每一个 $a_i$,询问是否存在 $a_j$ 使得 $a_i \& a_j = 0$,如果有输出 $a_j$(如果有多个,输出任意一个),否则输出 $-1$。

$1 \leq n \leq 10^6, 1 \leq a_i \leq 4\cdot 10^6$。

2 思路

注意到 $a_i \& a_j = 0$,其实就是询问是否有数字满足其是 $a_i$ 的补集的子集。

SOS DP 求出每个集合是否有数字是其子集即可。

Continue reading “Codeforces 165E Compatible Numbers”

Sum over Subsets DP 入门

0 引

为什么没在标题里写 SOS DP ?因为这 SOS 这个名字我第一次看的时候怎么看怎么觉得不正经,所以写全称让他看着正经一些。

个人感觉这个东西更像是一个套路而不是 DP 类型。

1 什么是 SOS DP

Sum over Subsets DP,即求子集和的 DP。更具体的说,用于在 $O(k \cdot 2^k)$ 的时间求出以下式子:

$$
f_{mask} = \sum_{i \subseteq mask} a_i
$$

Continue reading “Sum over Subsets DP 入门”

Codeforces 1549E / 1548C

原题链接:https://codeforces.com/contest/1549/problem/E

题目大意

给定 $n$,$q$ 次询问。

每次询问给定一个 $x$,求 $\sum_{i=0}^n \binom{3i}{x}$

思路

考虑定义 $f_{i,j}$ 表示 $\sum_{k=0}^{n-1} \binom{3k + j}{i}$,令 $0 \leq j < m$

注意到

  1. $\sum_{j=0}^{m-1} f_{i,j} = \sum_{j=0}^{3n – 1} \binom{j}{i} = \binom{3n}{i + 1}$
  2. $f_{i,j} = f_{ i – 1, j – 1 } + f_{i, j – 1 }$

发现可以解出 $f_{i,0}$

$O(n)$ 递推即可。

Continue reading “Codeforces 1549E / 1548C”

NOI 2021 游记

为了适应传统的 Day1 Day2 定义,本文中 Day 1 为 2021/07/26,Day1.5 为一个地球日。

0 Day -3

正睿提供了一场信心赛,打开发现是大家都做过的题目,便回去看各自之前做过的题目了。

中午去忆九家吃的饭,恍惚间发现是可能最后一顿在忆九家吃饭,心情竟有点沉重。怀着敬重的心情吃完了这顿饭。

下午则是看看题目顺便唆使还在新疆的选手快跑,结果催着催着 CCF 突然发通知要求 07/23 到校。

走之前大家都拍了几张照

Continue reading “NOI 2021 游记”

PKUSC 2021 游记

-1 申请

在今年五月的时候突然发现 PKU 和 THU 要举办夏令营的消息先后到来

THU 的报名不需要学生做什么,我就没有在意。
PKU 的报名需要填写不少资料还需要去打印并盖章申请书。人不在鸟市,就让教练帮忙了。

随后前往镇海中学参加训练。

天天都有的考试一直持续到 10 号,虽然 THU 方面似乎抛弃了新疆一直没有给我们教练回话,但是 PKU 还是通过了我的申请。

0 Day 0

5.13 镇海中学 -> 宁波火车站 -> 余姚北站 -> 余姚中学

在上午考试的时候向镇海教练询问,发现他们将会于明天早上出发。考虑到由镇海到余姚由 1h + 的车程,但我并没有教练或者家长随行,故选择在 13 日自行前往余姚。

Continue reading “PKUSC 2021 游记”

玄学,从入门到炼丹 — 初识遗传算法

0 说在之前

正常来说,一个正常的 Oier 是不会碰这种东西

但是我们综合实践小组的组长不知道为啥对这东西出奇的感兴趣, 我就试着理解一下

因为也仅仅是试着理解,如有理论错误还往各位在评论区斧正

本文的代码实现可以在 https://gitee.com/yingziyu/task 看到

Continue reading “玄学,从入门到炼丹 — 初识遗传算法”

树上启发式合并(dsu on tree)简介

1 树上启发式合并

1.1 启发式算法

我并没有找到比较正式的定义,在这里引用 OI Wiki 里的

启发式算法是基于人类的经验和直观感觉,对一些算法的优化。

例子:并查集的按秩合并

1.2 树上启发式合并

基于「减少节点多的子树的处理次数」的思想为主的算法

1.3 实现

我们希望节点多的子树处理次数尽可能少,也就是我们希望重儿子的处理次数尽可能少

注意到许多树上问题的处理过程是可延续的,即当前子树的处理完后可以直接将数据移交到父亲节点继续处理

基于这点,我们可以优先处理重儿子,然后直接继承到父亲节点。这样对于一个节点来说,其重儿子只需要处理一次,其轻儿子需要处理两次。

因为从树上任意一条路径上,关键点(即轻儿子)在 $O(\log(n))$ 范围内,所以这东西的复杂度是 $O(n\log(n))$ 的。

Continue reading “树上启发式合并(dsu on tree)简介”