斯坦纳树入门

0 序

这个东西看了半天没想明白为啥不是最小生成树,然后发现最小生成树实际上是最小斯坦那树的特殊形式
— 最小生成树里的所有点都是关键点。

最小斯坦那树是指在一个无向图中,求其最小生成网络使得其

  1. 包含所有关键点
  2. 总权值在满足 1 的情况下最小。
Continue reading “斯坦纳树入门”

XJOI 2022 游记

-1 序

寄啦,哈哈。

今年是新疆维吾尔自治区第一次组织省选。

今年有很多神奇的事情,比如特派员换了,新疆成立竞赛组委会了,办省选了,有 $\frac{1}{3}$ 了,有实体 NOI Linux。当然也不都是好事,疫情精准防控的代表上海已经被奥米克戎攻陷,全国疫情更是此起彼伏,见不到头。这种情况下信息学竞赛还能基本上「出淤泥而不染」,维持较为正常的赛季流畅已是相当不易。

在疫情的限制下,XJOI 最终未能选择新疆大学作为考点,而是选择了一所高中 — 乌鲁木齐市第一中学。

Continue reading “XJOI 2022 游记”

Atcoder Beginner Contest 246 解题报告

A Four Points

题目大意

给定矩形的三个顶点,求其剩下的顶点。

思路

签到

B Get Closer

题目大意

给定直线过点 $(0,0)$, $(a,b)$,求从 $(0,0)$ 出发,方向朝右,长度为一的线段的右端点。

思路

一开始是二分硬做的,然后被卡精度了。

求出两点距离,对 $a,b$ 分别除于这个这个距离即可。

Continue reading “Atcoder Beginner Contest 246 解题报告”

Codeforces 1208F Bits And Pieces

题目链接:https://codeforces.com/contest/1208/problem/F

1 题目大意

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

求最大 $a_i|(a_j\&a_k)$ 满足 $i < j < k$

$3 \leq n \leq 10^6, 0 \leq a_i \leq 2 \cdot 10^6$

2 思路

先考虑 $a_j\&a_k$,显然可以通过 SOS DP 来求出对于任意 $s$,其最靠后 $j$ 的能够有 $k$ 使得 $s \subseteq a_j\&a_k$ 的位置。

然后考虑贪心来最大化按位或,从高位往低位处理,如果能够有一位新为 $1$,则有限选择位数高的。

Continue reading “Codeforces 1208F Bits And Pieces”

Codeforces 383E Vowels

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

1 题目大意

给定 $n$ 个长度为 $3$,字符集为 a-x 的字符串。

对于 $s, s \subseteq [ \texttt{a}, \texttt{x} ]$,有 $f(s)$ 表示有多少个给定字符串和 $s$ 交集非空。

输出 $\sum^{\oplus}_s f(s) * f(s)$

2 思路

注意到基本上是 SOS DP 的模版,除一个问题 — 对于一个字符串可能会被统计多次。

简单容斥即可。

Continue reading “Codeforces 383E Vowels”

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 游记”