TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3036
  • 题目
  • P3036【Codeforces #263 Div2 B】Appleman and Card Game 苹果人和纸牌游戏
    限制 : 时间限制 : 10000 MS   空间限制 : 265536 KB
    问题描述

    Appleman has n cards. Each card has an uppercase letter written on it. Toastman must choose k cards from Appleman's cards. Then Appleman should give Toastman some coins depending on the chosen cards. Formally, for each Toastman's card i you should calculate how much Toastman's cards have the letter equal to letter on ith, then sum up all these quantities, such a number of coins Appleman should give to Toastman.
    Given the description of Appleman's cards. What is the maximum number of coins Toastman can get?

    苹果人有n张纸牌,每张牌上写着一个大写字母。土司人要从中选出k张牌,然后苹果人需要根据选出的牌给土司人一些硬币。对于每个i,你需要计算有多少张土司人选出的牌上的字母与土司人选出的第i张牌上的字母相同,并把所得的所有答案加起来,就是苹果人需要给土司人多少个硬币。
    给出苹果人的纸牌。土司人最多能得到多少硬币?

    输入格式

    The first line contains two integers n and k (1 ≤ k ≤ n ≤ 105).
    The next line contains n uppercase letters without spaces — the i-th letter describes the i-th card of the Appleman.

    第一行包含两个数n和k(1 ≤ k ≤ n ≤ 105)。
    接下来一行包含n个没有间隔的大写字母,第i个字母表示苹果人的第i张纸牌。

    输出格式

    Print a single integer – the answer to the problem.

    输出一个整数,表示问题的答案。

    样例输入

    样例输入1:
    15 10
    DZFDFZDFDDDDDDF


    样例输入2:
    6 4
    YJSNPI

    样例输出

    样例输出1:
    82

    样例输出2:
    4

    提示

    Note:
    In the first test example Toastman can choose nine cards with letter D and one additional card with any letter. For each card with D he will get 9 coins and for the additional card he will get 1 coin.

    第一组样例中,土司人可以选9张字母D和1张任意字母的纸牌。每张字母D的纸牌都将得到9个硬币,另一张纸牌可以得到1个硬币。


    来源  感谢nodgd倾情翻译并提供数据