Codeforces Round #508 (Div. 2)

  • 2018-09-08
  • 11
  • 0

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 occurences of each of the first k letters of the alphabet is the same.
Find the length of the longest good subsequence of s.

Input:

The first line of the input contains integers n (1\le n \le 10^5) and k (1 \le k \le 26).
The second line of the input contains the string s of length n. String s only contains uppercase letters from ‘A’ to the k-th letter of Latin alphabet.

Output

Print the only integer — the length of the longest good subsequence of string s.

Sample Input:

9 3
ACAABCCAB

Sample Output:

6

Sample Input:

9 4
ABCABCABC

Sample Output:

0

题目链接

直接统计字母表中前K个字母在字符串中出现的最小次数即可。

AC代码:

B. Non-Coprime Partition

Description:

Find out if it is possible to partition the first n positive integers into two non-empty disjoint sets S_1 and S_2 such that:
\mathrm{gcd}(\mathrm{sum}(S_1), \mathrm{sum}(S_2)) > 1 Here \mathrm{sum}(S) denotes the sum of all elements present in set S and \mathrm{gcd} means thegreatest common divisor.
Every integer number from 1 to n should be present in exactly one of S_1 or S_2.

Input:

The only line of the input contains a single integer n (1 \le n \le 45\,000)

Output

If such partition doesn’t exist, print “No” (quotes for clarity).
Otherwise, print “Yes” (quotes for clarity), followed by two lines, describing S_1 and S_2 respectively.
Each set description starts with the set size, followed by the elements of the set in any order. Each set must be non-empty.
If there are multiple possible partitions — print any of them.

Sample Input:

1

Sample Output:

No

Sample Input:

3

Sample Output:

Yes
1 2
2 1 3

题目链接

若n为偶数则必定可以分为奇数组和偶数组,其两组之和的最大公约数为2,若n为奇数有两种情况,1.n是第偶数个奇数,则还是可以分为奇数组与偶数组使其两组之和的最大公约数为2,2.n是第奇数个奇数,通过找规律可以发现1~n中的中位数单独分为一组时两组的最大公约数即为1~n的中位数。

AC代码:

评论

还没有任何评论,你来说两句吧