(马后炮)Codeforces Round 508 做题记录.
Table of Contents
A - Equality
Description
You are given a string $s$ of length $n$, which consists only of the first $k$ letters of the Latin alphabet. All letters in string $s$ are uppercase.
A subsequence of string $s$ is a string that can be derived from $s$ by deleting some of its symbols without changing the order of the remaining symbols. For example, “ADE” and “BD” are subsequences of “ABCDE”, but “DEA” is not.
A subsequence of $s$ called good if the number of occurrences of each of the first $k$ letters of the alphabet is the same.
Find the length of the longest good subsequence of $s$.
Solution
Bouvardia以为是DP来的, 但这是个A啊.
统计到每一位位置, 对每个字母出现次数取个min, 再乘字符集大小对ans取个max.
B - Non-Coprime Partition
Description
Find out if it is possible to partition the first $n$ positive integers into two non-empty disjoint sets $S1$ and $S2$ such that:
$gcd(sum(S1),\,sum(S2)) > 1$
Solution
构造吧. 枚举最小质因子就好了.
C - Gambling
Description
Two players A and B have a list of $n$ integers each. They both want to maximize the subtraction between their score and their opponent’s score.
In one turn, a player can either add to his score any element from his list (assuming his list is not empty), the element is removed from the list afterward. Or remove an element from his opponent’s list (assuming his opponent’s list is not empty).
The player A starts the game and the game stops when both lists are empty. Find the difference between A’s score and B’s score at the end of the game, if both of the players are playing optimally.
Solution
排个序, 照着样例做就是了.
D - Slime
Description
There are $n$ slimes in a row. Each slime has an integer value (possibly negative or zero) associated with it.
Any slime can eat its adjacent slime (the closest slime to its left or to its right, assuming that this slime exists).
When a slime with a value $x$ eats a slime with a value $y$, the eaten slime disappears, and the value of the remaining slime changes to $x−y$.
The slimes will eat each other until there is only one slime left.
Find the maximum possible value of the last slime.
Solution
口胡一会就发现不同DP, 当然DP也行, 其实保证有一个人不被吃, 保证有一个人被吃了奇数次就行了.
贪心好写啊.
E - Maximum Matching
Description
You are given $n$ blocks, each of them is of the form [color1|value|color2], where the block can also be flipped to get [color2|value|color1].
A sequence of blocks is called valid if the touching endpoints of neighboring blocks have the same color. For example, the sequence of three blocks A, B and C is valid if the left color of the B is the same as the right color of the A and the right color of the B is the same as the left color of C.
The value of the sequence is defined as the sum of the values of the blocks in this sequence.
Find the maximum possible value of the valid sequence that can be constructed from the subset of the given blocks. The blocks from the subset can be reordered and flipped if necessary. Each block can be used at most once in the sequence.
Solution
事情变得不妙了.
Bouvardia以为是网络流, 但其实边的种类不多, 枚举哪种不能转移, 跑欧拉路, 更新答案.
细节听多的, 记得再看看.
F - Wrap Around
Description
You are given a binary string $s$.
Find the number of distinct cyclical binary strings of length $n$ which contain $s$ as a substring.
The cyclical string $t$ contains $s$ as a substring if there is some cyclical shift of string $t$, such that $s$ is a substring of this cyclical shift of $t$.
For example, the cyclical string “000111” contains substrings “001”, “01110” and “10”, but doesn’t contain “0110” and “10110”.
Two cyclical strings are called different if they differ from each other as strings. For example, two different strings, which differ from each other by a cyclical shift, are still considered different cyclical strings.
Solution
这什么神仙题. Bouvardia并不会做. 大概就是枚举结果包含 $s$ 的前缀后缀之类的.
还什么KMP优化. 以后再说吧.