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 更多内容请关注微信公众号

原文发布于微信公众号 - 海天一树(gh_de7b45c40e8b)

原文发表时间:2018-03-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏草根专栏

用C# (.NET Core) 实现迭代器设计模式

本文的概念来自深入浅出设计模式一书 项目需求 有两个饭店合并了, 它们各自有自己的菜单. 饭店合并之后要保留这两份菜单. 这两个菜单是这样的: ? 菜单项Men...

36550
来自专栏码匠的流水账

聊聊eureka client的fetch-remote-regions-registry属性

本文主要研究一下eureka client的fetch-remote-regions-registry属性

17510
来自专栏landv

c语言_头文件_stdlib

25630
来自专栏Hongten

原来还有这样的记词方法_Java版记不规则动词_博主推荐

昨天在看一本英语书的不规则动词的时候,突然产生的灵感:就是想把这样记单词简单方式,用程序代码实现,然后,使用户可以与之进行交互

9920
来自专栏HansBug's Lab

3386/1752: [Usaco2004 Nov]Til the Cows Come Home 带奶牛回家

3386/1752: [Usaco2004 Nov]Til the Cows Come Home 带奶牛回家 Time Limit: 1 Sec  Memory...

379110
来自专栏Hongten

java开发_数字转换汉语中人民币的大写_完整版

======================================================

46630
来自专栏小樱的经验随笔

BZOJ 3098: Hash Killer II(新生必做的水题)

3098: Hash Killer II Time Limit: 5 Sec  Memory Limit: 128 MBSec  Special Judge S...

28970
来自专栏草根专栏

Typescript 查缺补漏

Types Casting: let input = xxx as HTMLInputElement; let input = <HTMLElement>xxx...

23030
来自专栏十月梦想

JavaScript一维数组遍历

通过for循环获取数组的下标循环输出数组,和php的遍历类似,这里for循环遍历一维数组

11320
来自专栏函数式编程语言及工具

PICE(1):Programming In Clustered Environment - 集群环境内编程模式

首先声明:标题上的所谓编程模式是我个人考虑在集群环境下跨节点(jvm)的流程控制编程模式,纯粹按实际需要构想,没什么理论支持。在5月份的深圳scala mee...

8830

扫码关注云+社区

领取腾讯云代金券