Codeforces Round #581 (Div. 2) 比赛链接：LInk

C - Anna, Svyatoslav and Maps

Description

给出一张有向图，每条边的边权都是 1。给出一个 m 个点的路径序列 $\{p_i \}$，表示依次经过这 m 个点的路径。路径序列中相邻元素之间有边相连。
现在需要你找出这个序列的一个最短的子序列 $\{v_i \}$，长度为 k，使得经过这 k 个点的路径也经过 $\{p_i \}$ 中所有点。

More...

Description

给出一个长度为 n 的数列，$2\leq n\leq 4\ast 10^5$，每个数字 $a_i$ 都在 $[1,20]$ 内。
可以对这个数列中相邻的两个数字交换位置，最终要使得相同的数字都在一起。
求最小交换次数。

Link

More...

这是我的博客发布的第 100 篇文章！🎉

D - Open Communication

Description

有两个玩家，给出分别 n 和 m 个数对，$1\leq n,m\leq 12$，所有数字都 $\in [0,9]$，并且一个数对里的数字不相同，不会有重复的数对。现在有一个“共享数字”，这个数字在 A 玩家的数对里和 B 玩家的数对里都至少出现一次。如果你可以推断出这个数字，输出这个数字；如果你无法推断出这个数字，但是你确信两个玩家都知道这个数字，输出 0；如果连玩家也不知道，输出 -1。

More...

Description

Link

Ivan wants to make a necklace as a present to his beloved girl. A necklace is a cyclic sequence of beads of different colors. Ivan says that necklace is beautiful relative to the cut point between two adjacent beads, if the chain of beads remaining after this cut is a palindrome (reads the same forward and backward).

More...

Description

Yaroslav has n points that lie on the $Ox$ axis. The coordinate of the first point is $x_1$, the coordinate of the second point is $x_2$, ..., the coordinate of the n-th point is — $x_n$. Now Yaroslav wants to execute $m$ queries, each of them is of one of the two following types:

More...

Description

Link

In mathematical terms, the sequence $F_n$ of Fibonacci numbers is defined by the recurrence relation

$$F_1 = 1; F_2 = 1; F_n = F_{n - 1} + F_{n - 2} (n > 2)$$

DZY loves Fibonacci numbers very much. Today DZY gives you an array consisting of n integers: $a_1, a_2, \dots, a_n$. Moreover, there are $m$ queries, each query has one of the two types:

More...

Description

牛客练习赛 17 F 【玩游戏】：Link

给定两个串 S 和 T，|S| >= |T|。alice 和 bob 轮流操作串 S，bob 先手。
对于每次操作，alice 或 bob 会选择删掉 S 的第一位或最后一位。当操作以后的串的长度等于 |T| 时，游戏停止。如果停止时的串=T，则 alice 获胜，否则 bob 获胜。问在 alice 和 bob 均采取最优策略的情况下，谁赢？

More...

快看看 CCF 是怎么把初赛完成脑筋急转弯竞赛的……

孙某和张某是考古学家老李的学生。有一天，老李拿了一件古物来考验两人，两人都无法验证出来这件古物试谁的。老李告诉了孙某拥有者的姓，告诉张某拥有者的名，并且在纸条上写下以下几个人的人名，问他们知道谁才是拥有者？
纸条上的名字有：沈万三、岳飞、岳云、张飞、张良、张鹏、赵括、赵云、赵鹏、沈括。

• 孙某说：如果我不知道的话，张某肯定也不知道。
• 张某说：刚才我不知道，听孙某一说，我现在知道了。
• 孙某说：哦，那我也知道了。

请问：那件古物是谁的？

More...

Description

Link: LightOJ 1873 DNA Sequence

You are given a list of strings over the alphabet A (for adenine), C (cytosine), G (guanine), and T (thymine), and your task is to find the shortest string (which is typically not listed) that contains all given strings as substrings. If there are several such strings of shortest length, find the smallest in alphabetical/lexicographical order.

Time Limit: 4 second(s)
Memory Limit: 32 MB

More...

简单来说，数位 DP 大概就是把一个数字拆开按位进行 DP 的一种思想。

HDU 3555 Bomb

The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence "49", the power of the blast would add one point.
Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?

More...