【题解】HackerRank - Project Euler
彻底咕了,不看也罢。记得有一位著名人物曾说过,现役选手不建议刷 PE。
彻底咕了,不看也罢。记得有一位著名人物曾说过,现役选手不建议刷 PE。
https://www.hackerrank.com/challenges/self-driving-bus/problem
给一棵树,结点编号为 1 ~ n,求有多少个编号区间使得对应结点连通。
2018-2019 Winter Petrozavodsk Camp, Oleksandr Kulkov Contest 1
Ck = ∑mex3(i, j) = kAiBj,其中 mex3 是三进制意义下按位取 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 的长,使得拼接起来是个回文串。
http://www.51nod.com/Challenge/Problem.html#!#problemId=1554
问字符串 s 的每一个前缀能否表示成 A + B + A + ⋯ + B + A 的形式,其中恰好有 k + 1 个 A 以及 k 个 B。