A. Equality

Description:

You are given a string $s$s of length $n$n, which consists only of the first $k$k letters of the Latin alphabet. All letters in string $s$s are uppercase.
A subsequence of string $s$s is a string that can be derived from $s$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$s called good if the number of occurences of each of the first $k$k letters of the alphabet is the same.
Find the length of the longest good subsequence of $s$s.

Input:

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

Output

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

Sample Input:

9 3
ACAABCCAB

Sample Output:

6

Sample Input:

9 4
ABCABCABC

Sample Output:

0

题目链接

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

AC代码:

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int main(int argc, char *argv[]) {
    int N, K;
    scanf("%d%d", &N, &K);
    string str;
    cin >> str;
    map<int, int> Cnt;
    for (int i = 0; i < N; ++i) {
        Cnt[str[i] - 'A']++;
    }
    int Ans = INF;
    for (int i = 0; i < K; ++i) {
        Ans = min(Ans, Cnt[i]);
    }
    printf("%d\n", Ans * K);
    return 0;
}

B. Non-Coprime Partition

Description:

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

Input:

The only line of the input contains a single integer $n$n ( 1≤n≤45000)

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$S1​ and $S_2$S2​ 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代码:

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char *argv[]) {
    int N;
    scanf("%d", &N);
    if (N <= 2) {
        printf("No\n");
    }
    else {
        printf("Yes\n");
        if (N & 1) {
            int Num = (N - 1) / 2 + 1;
            if (Num & 1) {
                printf("%d %d\n", 1, (N + 1) / 2);
                printf("%d ", N - 1);
                for (int i = 1; i <= N; ++i) {
                    if (i == (N + 1) / 2) {
                        continue;
                    }
                    printf("%d ", i);
                }
                printf("\n");
            }
            else {
                printf("%d ", (N + 1) / 2);
                for (int i = 1; i <= N; i += 2) {
                    printf("%d ", i);
                }
                printf("\n");
                printf("%d ", N / 2);
                for (int i = 2; i <= N; i += 2) {
                    printf("%d ", i);
                }
                printf("\n");
            }
        }
        else {
            printf("%d ", N / 2);
            for (int i = 1; i < N; i += 2) {
                printf("%d ", i);
            }
            printf("\n");
            printf("%d ", N / 2);
            for (int i = 2; i <= N; i += 2) {
                printf("%d ", i);
            }
            printf("\n");
        }
    }
    return 0;
}