本帖最后由 michael_llh 于 2016-12-25 22:42 编辑
Magical Word
Dhananjay has recently learned about ASCII values.He is very fond of experimenting. With his knowledge of ASCII values and character he has developed a special word and named it Dhananjay's Magical word. A word which consist of alphabets whose ASCII values is a prime number is an Dhananjay's Magical word. An alphabet is Dhananjay's Magical alphabet if its ASCII value is prime. Dhananjay's nature is to boast about the things he know or have learnt about. So just to defame his friends he gives few string to his friends and ask them to convert it to Dhananjay's Magical word. None of his friends would like to get insulted. Help them to convert the given strings to Dhananjay's Magical Word.
Rules for converting: 1.Each character should be replaced by the nearest Dhananjay's Magical alphabet. 2.If the character is equidistant with 2 Magical alphabets. The one with lower ASCII value will be considered as its replacement.
Input format: First line of input contains an integer T number of test cases. Each test case contains an integer N (denoting the length of the string) and a string S. Output Format: For each test case, print Dhananjay's Magical Word in a new line.
Constraints: 1 <= T <= 100 1 <= |S| <= 500
prime number：质数，定义为在大于1的自然数中除了1和它本身不再有其他因数的数。
题意分析： 首先我们给出了上面这概念，就是质数的概念，这个是这道题的关键，什么是一个Magic Word呢，说白了就是说这个单词是一个ASCII都为质数构成的单词，我们在转换这个单词的时候是安装一定的原则的，当我们判断这个字母是否是Magic Word当中的一个组成字母的时候如果是，那保留，如果不是的话那就需要对字母的ASCII进行加1操作，然后再进行判断，直到这个字母的ASCII变成质数。这道题就是这样的一个思路。 按照这个思路给出的参考代码如下：
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
int T = 0;
int N = 0;
string S;
cin >> T;
for(int i=0; i<T; i++){
cin >> N;
char* s = new char[N+1];
cin >> s;
strcpy(s,S.c_str());
cout << s;
for(int j=0; j<N; j++){
if(s[j]<='Z' && s[j]>='A'){
for(int k=0; k<(int)s[j]; k++){
if((((int)s[j]/k)==0)&&(k!=(int)s[j])){
s[j] = (int)s[j] +1;
j--;
break;
}
}
}
}
cout << s << endl;
}
return 0;
}
但是这道题有个Bug，我看了下其他的人提交的答案，他们其实用了非常投机的方式，因为我们总的判断字母只有26个，所以当中的质数其实是可以数出来的，所以就直接写死了参考代码如下：
#include <iostream>
using namespace std;
int main()
{
/*ascii prime number = 67,71,73,79,83,89,97,101,103,107,109,113,127*/
string s;
long long int t,n;
cin>>t;
int temp;
char a;
while(t--){
cin>>n>>s;
for(long long int i=0;i<n;i++){
temp=s[i];
if(temp<=69)
a=67;
else if(temp<=72)
a=71;
else if(temp<=76)
a=73;
else if(temp<=81)
a=79;
else if(temp<=86)
a=83;
else if(temp<=93)
a=89;
else if(temp<=99)
a=97;
else if(temp<=102)
a=101;
else if(temp<=105)
a=103;
else if(temp<=108)
a=107;
else if(temp<=111)
a=109;
else
a=113;
cout<<a;
}
cout<<endl;
}
return 0;
}
| 
楼主
标题置顶
标题高亮
