CF1025A.Doggo Recoloring

入门

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Panic is rising in the committee for doggo standardization — the puppies of the new brood have been born multi-colored! In total there are 26 possible colors of puppies in the nature and they are denoted by letters from 'a' to 'z' inclusive.

The committee rules strictly prohibit even the smallest diversity between doggos and hence all the puppies should be of the same color. Thus Slava, the committee employee, has been assigned the task to recolor some puppies into other colors in order to eliminate the difference and make all the puppies have one common color.

Unfortunately, due to bureaucratic reasons and restricted budget, there's only one operation Slava can perform: he can choose a color xx such that there are currently at least two puppies of color xx and recolor all puppies of the color xx into some arbitrary color yy. Luckily, this operation can be applied multiple times (including zero).

For example, if the number of puppies is 77 and their colors are represented as the string "abababc", then in one operation Slava can get the results "zbzbzbc", "bbbbbbc", "aaaaaac", "acacacc" and others. However, if the current color sequence is "abababc", then he can't choose xx='c' right now, because currently only one puppy has the color 'c'.

Help Slava and the committee determine whether it is possible to standardize all the puppies, i.e. after Slava's operations all the puppies should have the same color.

狗狗标准化委员会正陷入恐慌——新一批幼犬出生时竟呈现出多种颜色!自然界中幼犬共有 26 种可能的颜色,分别用小写字母 'a' 到 'z' 表示。

委员会的规定严格禁止狗崽之间存在任何差异,因此所有幼犬必须具有相同的颜色。于是,委员会职员斯拉瓦被委派执行一项任务:将部分幼犬重新染色,以消除颜色差异,使所有幼犬最终呈现同一种颜色。

不幸的是,由于官僚主义原因及预算限制,斯拉瓦仅能执行一种操作:他可以选择一种颜色 xx,前提是当前至少有两只幼犬的颜色为 xx,然后将所有颜色为 xx 的幼犬全部重新染成任意一种颜色 yy。幸运的是,该操作可重复执行多次(包括零次)。

例如,若幼犬总数为 77 只,其颜色序列表示为字符串 "abababc",则通过一次操作,斯拉瓦可得到 "zbzbzbc"、"bbbbbbc"、"aaaaaac"、"acacacc" 等结果。然而,若当前颜色序列为 "abababc",则他此时无法选择 xx = 'c',因为目前仅有 1 只幼犬的颜色为 'c'。

请帮助斯拉瓦和委员会判断:是否有可能实现幼犬的标准化,即经过斯拉瓦的操作后,所有幼犬均呈现同一种颜色。

输入格式

The first line contains a single integer nn (1≤n≤1051 \le n \le 10^5) — the number of puppies.

The second line contains a string ss of length nn consisting of lowercase Latin letters, where the ii-th symbol denotes the ii-th puppy's color.

第一行包含一个整数 nn(1≤n≤1051 \le n \le 10^5)—— 表示小狗的数量。

第二行包含一个长度为 nn 的字符串 ss,由小写拉丁字母组成,其中第 ii 个字符表示第 ii 只小狗的颜色。

输出格式

If it's possible to recolor all puppies into one color, print "Yes".

Otherwise print "No".

Output the answer without quotation signs.

如果可以将所有小狗重新染成同一种颜色,则输出“Yes”。

否则输出“No”。

不带引号地输出答案。

输入输出样例

  • 输入#1

    6
    aabddc

    输出#1

    Yes
  • 输入#2

    3
    abc

    输出#2

    No
  • 输入#3

    3
    jjj

    输出#3

    Yes

说明/提示

In the first example Slava can perform the following steps:

  1. take all puppies of color 'a' (a total of two) and recolor them into 'b';
  2. take all puppies of color 'd' (a total of two) and recolor them into 'c';
  3. take all puppies of color 'b' (three puppies for now) and recolor them into 'c'.

In the second example it's impossible to recolor any of the puppies.

In the third example all the puppies' colors are the same; thus there's no need to recolor anything.

在第一个例子中,斯拉瓦可以执行以下步骤:

  1. 将所有颜色为 'a' 的小狗(共两只)重新染色为 'b';
  2. 将所有颜色为 'd' 的小狗(共两只)重新染色为 'c';
  3. 将所有颜色为 'b' 的小狗(此时共三只)重新染色为 'c'。

在第二个例子中,无法对任何一只小狗进行重新染色。

在第三个例子中,所有小狗的颜色均相同;因此无需进行任何重新染色。

输入解题思路,AI测评打分。不知道怎么写?

首页