TopCoder SRM 731 Div2 Easy题解报告

Problem Statement

Hero has an infinite periodic string t. You are given the string s that is the period of Hero's string. For example, if s = "abc", Hero's actual string is t = "abcabcabcabc…" Let n be the length of string s. Hero is now going to use the infinite string t to generate a new n-character string by doing the following steps: He will choose an offset: a non-negative integer x. He will choose the length of a step: a prime number p that is less than n. The new string will consists of the first n characters we can read in the string t if we start at the index x and after each character we move p positions to the right. Formally, Hero's new string will consist of the following characters, in order: t[x], t[x + p], t[x + 2p], …, t[x + (n-1)p]. Find and return the lexicographically smallest string Hero can produce.

Definition

Class: RingLex Method: getmin Parameters: string Returns: string Method signature: string getmin(string s) (be sure your method is public)

Limits

Time limit (s): 2.000 Memory limit (MB): 256 Stack limit (MB): 256

Notes

• Given two distinct strings of the same length, the lexicographically smaller one is the one that has a smaller character at the first position where they differ.
• A positive integer p is a prime if it has exactly two distinct divisors: 1 and p. Note that the number 1 is not a prime.

Constraints

• s will contain between 3 and 50 characters, inclusive.
• Each character in s will be between 'a' and 'z', inclusive.

Examples

0)
"cba"
Returns: "abc"
Hero should choose the offset x=2 and the step p=2. The resulting string is t[2]+t[4]+t[6] = 'a'+'b'+'c' = "abc".
1)
"acb"
Returns: "abc"
Here, Hero should choose x=0 and p=2.
2)
"abacaba"
Returns: "aaaabcb"
3)
"aaabb"
Returns: "aabab"
4)
"azzzabbb"
Returns: "abazabaz"
Note that Hero cannot choose x=0 and p=4, because 4 is not a prime number.
5)
"abbaac"
Returns: "aaaaaa"
6)
"fsdifyhsoe"
Returns: "dehifsfsoy"

分析

本题要求最小的字符串，可以考虑使用set来存放所有的字符串。因为set是默认是按从小到大的顺序排列的，最终咱们取出set里的第一个字符串即为所求。 本题的数据量不大，直接穷举即可。

代码

#include <iostream>
#include <set>
using namespace std;
bool is_prime(int val)
{
    for(int i = 2; i < val; i++)
    {
        if(0 == val % i)
        {
            return false;
        }
    }
    return true;
}
class RingLex
{
public:
    string getmin(string s)
    {
        int len = s.length();
        set<string> res_set;
        for(int x = 0; x < len; x++)
        {
            for(int p = 1; p < len; p++)
            {
                if(is_prime(p))
                {
                    string newstr = "";
                    for(int step = 0; step < len; step++)
                    {
                        newstr += s[(step * p + x) % len];
                    }
                    res_set.insert(newstr);
                }
            }
        }
        return (*final_set.begin());
    }
};
int main()
{
    RingLex r;
    cout << r.getmin("cba");
    return 0;

Codeforces & TopCoder QQ交流群：648202993 更多内容请关注微信公众号