洛谷:P1603:斯诺登的密码


洛谷:P1603:斯诺登的密码

题目

P1603:斯诺登的密码

分析

这道题目建议用一些高级的C++语法来完成。

从字符串中读入数据

给出的输入是一个字符串,可能包含一些特定的单词来表示数字。当然,我们可以用不断cin的方式,但更推荐的方式是用stringstream,将一个字符串作为输入来源,然后像从cin中读入数据一样,从stringstream中读取数据。

    string input;
    getline(cin, input); // getline用来读入可能包含空格的字符串

    stringstream ss(input);
    string word;

    while(ss>>word)
    {
        // ...
    }

处理每个word

一旦读入了每个word,就可以去找出它是否是那些特定的可以代表数字的单词。

本题的解法用到了STL中的mapmap<string, string> converts;。这个声明将一个字符串和另一个字符串加以关联。

通常,将第一个值称为key(键),而第二个值称为value(值)。一个映射可以用类似数组的方式加以访问:convert[key]=value。可以将其视作一种扩展了的数组,其索引不再必须是非负整数。

while(ss>>word)
{
    if(word[word.length()-1]=='.')
    {
        word=word.substr(0, word.length()-1);
    }

    if(converts.find(word)!=converts.end())
    {
        output.push_back(converts[word]);
    }
}

这里我们先处理最后一个单词带.的情况——这也是英文句子结尾的标记,在ss>>word的时候,这个.是会和单词一起读入的。如果一个单词结尾是.,我们将其去掉,然后在映射converts中找是不是有这个单词的key,如果有,就将它代表的两位数字放入output数组中。

设置word对应的“数值”

我们没有将value设置为整数类型,是因为题目要求的操作是,对应的数字(one->1)平方,然后取%100的值,而且取两位。这样的话,我们不能简单地用数字保存,否则会出现前导0丢失,排列顺序出错而导致结果错误。

例如:

(0)9 16会得到最小排列是1609,这个0是不能丢的:因为09中的0是可以成为一个最终数字中的中间位的。而09 16会得到准确的(0)916,最终我们才处理前导0

因此,按照这个思路,我们可以初始化所有有意义的word对应的“数值”:

void init()
{
    converts["one"]="01";
    converts["two"]="04";
    converts["three"]="09";
    // ... ...

    converts["a"]="01";
    converts["both"]="04";
    // ... ... 
}

最终处理

output中的“数字”(按照“字典序”)排序,并串联起来,然后去掉前导0就可以输出:

    sort(output.begin(), output.end());
    string final_output="";
    for(int i=0; i<output.size(); i++)
    {
        final_output+=output[i];
    }
    if(final_output.length()>0)
    {
        cout<<strip_leading_zeroes(final_output)<<endl;
    }
    else 
    {
        cout<<"0"<<endl;
    }

当然,我们要考虑边界情形:原始输入中没有任何一个有意义的单词,那么此时output就是空的,final_output就是一个空的字符串,此时应该输出0

答案

思考

本题是一道很好的综合运用题:数组、STL中的映射、向量等都得到了使用。而且还有一些很细微的地方需要考虑:单词结尾为.,以及最终结果字符串为空等。

Previous Next