当前位置: 首页 > 工具软件 > doggo > 使用案例 >

CF-1025A-Doggo Recoloring

庄宇
2023-12-01

题源:http://codeforces.com/problemset/problem/1025/A
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 x such that there are currently at least two puppies of color xx and recolor all puppies of the color x into some arbitrary color y. Luckily, this operation can be applied multiple times (including zero).
For example, if the number of puppies is 7 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 x=‘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.
Input
The first line contains a single integer n (1≤n≤10^5) — the number of puppies.The second line contains a string s of length n consisting of lowercase Latin letters, where the i-th symbol denotes the i-th puppy’s color.
Output
If it’s possible to recolor all puppies into one color, print “Yes”. Otherwise print “No”. Output the answer without quotation signs.
——————————————————————————————————
翻译:自然界中共有26种可能的小狗颜色,用字母“a”到“z”表示。因此所有的小狗都应该是相同的颜色。因此,委员会的工作人员Slava被分配了一项任务,将一些幼犬重新上色为其他颜色,以消除差异,使所有幼犬都有一种共同的颜色。斯拉瓦只能执行一个操作:他可以选择一种颜色使当前至少有两个颜色为x的幼犬,并将所有颜色为x的幼犬重新上色成任意颜色y。幸运的是这个操作可以应用多次(包括0次)。例如,如果小狗的数量是7它们的颜色被表示为字符串“abababc”,那么在一次操作中Slava就可得到“zbzbzbc”、“bbbbbbc”、“aaaaaac”、“acacc”等结果。但是,如果当前的颜色序列是“abababc”,那么他现在不能选择x=“c”,因为目前只有一只小狗的颜色是“c”。帮助Slava和委员会确定是否有可能对所有的幼犬进行标准化,即在Slava手术后,所有幼犬都应该有相同的颜色。输入第一行包含一个整数n(1≤n≤105) -小狗的数量。第二行包含一个长度为n的字符串s由小写拉丁字母组成,其中第i个符号表示第i只小狗的颜色。输出如果可以将所有小狗重新上色,请打印“Yes”。否则打印“不”。输出没有引号的答案。
————————————————————————————————
分析:一看这题挺长的。简单说,就和cf僵尸感染一样,26个字母代表僵尸的不同种类,两个及以上的同种僵尸才可以一次同化另一种僵尸(就是把后者变得和前者相同),总共可以同化n次,n可以是0。然后需要你输入一个整数代表僵尸数目,再输入n个字母代表所有僵尸,让你判断经过n次同化,能不能变成一种僵尸。
思路:当只有一只僵尸时,可以变成一种僵尸(因为只有这一种嘛~当时好多次wrong answer就是因为忽略了这种情况!),当僵尸数目大于1时,遍历整个字符串儿,只要有任意一种僵尸数目大于1,就可以,否则不可以。
AC代码如下:

#include<stdio.h>
#include<string.h>
int main(){
 int color[27]={0},i,flag=0;		//color数组用于计数
 long int n;
 char s[100010];
 scanf("%ld",&n)!=0;
 getchar();
 gets(s);
 if(n>1&&n<=26)  //注意!!!这里单独一个是可以的!!
     			//注意定义域内每种情况!!! 
 for(i=0;i<strlen(s);i++){
  color[s[i]-96]++;	//因为'a'的acsii码是96,所以假如读到僵尸'a',那么color[0]这一僵尸(原题是颜色嘛)就增加一个
  if(color[s[i]-96]>1)	//随时判断有没有一种僵尸大于1
  {flag=1;break;}
 }
 else flag=1;  //当只有一只僵尸的时候 是可以的 
 if(flag) printf("Yes");
 else printf("No");
 return 0;
}
 类似资料: