TopCoder SRM 731 Div2 Easy题解报告

秒速五厘米 2022-05-28 04:45 71阅读 0赞

# 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 + 2\*p\], …, 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  
> 更多内容请关注微信公众号  
> ![feicuisenlin\_12x12.jpg][feicuisenlin_12x12.jpg]

[feicuisenlin_12x12.jpg]: /images/20220528/2284f9a106f2484eb6a01af3a213e0eb.png