Zerol's Notes

彻底咕了，不看也罢。记得有一位著名人物曾说过，现役选手不建议刷 PE。

仅供娱乐。

这里（如果无法访问，我只能说一句抱歉了）有一个表单，有一些与我相关的问题，每道题都标注了分数。

如果能有 70 分，我们就是好朋友（至少曾经），非常感谢你的关心，我不会忘记你的，我会珍惜共同创造的记忆，直至终结。

发布时间被我提前了一年，因为我不希望它出现在首页。

题目

https://www.hackerrank.com/challenges/self-driving-bus/problem

题意

给一棵树，结点编号为 1 ~ n，求有多少个编号区间使得对应结点连通。

题目

http://acm.ecnu.edu.cn/problem/3437/

题意

有点复杂，请自行读题。

题目

2018-2019 Winter Petrozavodsk Camp, Oleksandr Kulkov Contest 1

题意

$C_k = \sum_{mex_3(i,j)=k} A_i B_j$，其中 $mex_3$ 是三进制意义下按位取 $mex$（其中 $mex(x,y)$ 的值等同于和 $x$ 以及 $y$ 都不相等的最小非负整数）。

Ear decomposition 的定义见 Wikipedia。粗略地讲，在无向图中，耳朵就定义为一条路径，其中除了端点外的点的度数均为 2（端点可以重合），而且删去后不破坏图的连通性。耳分解就是将图中的耳朵依次删去直至删完，不是所有无向图都能被耳分解，同时耳分解的方案很可能是不唯一的。

充要条件

图中没有桥。必要性感受一下，还是显然的，证明就不证了。充分性可以用算法本身来证明，对于满足条件的无向图，算法一定能给出一个合法的耳分解。

题目

GYM101205D: https://codeforces.com/gym/101205/problem/D

UVA1282: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=247&page=show_problem&problem=3895

题意

$F[0] = 0, F[1] = 1, F[n] = F[n - 1] + F[n - 2]$，其中 $+$ 是字符串连接。问给定 01 串在 $f[n]$ 中的出现次数。

系统休眠是个好东西，首先它不需要耗电，其次如果双系统切换的话，睡眠无法保存工作环境。

启用休眠功能的大致步骤如下：

对于有向图 $G$（可能有环），其中起点 $r$ 可以到达所有点，当 $u$ 是所有到达 $v$ 的路径的必经点时，称 $u$ 支配 $v$。

可以构建支配树，其中每个点被所有它的祖先支配，又支配它子树中的结点。

题目

https://codeforces.com/gym/101981/problem/M

题意

给出两个字符串 $s$ 和 $t$，要求从 $s$ 切出一段非空子串，$t$ 中切出一段非空前缀，且 $s$ 的比 $t$ 的长，使得拼接起来是个回文串。