博客
关于我
CSU 1353: Guessing the Number(字符串周期问题+字符串最小表示法)
阅读量:607 次
发布时间:2019-03-12

本文共 2205 字,大约阅读时间需要 7 分钟。

题目:

Description

    Alice thought out a positive integer x, and x does not have leading zeros. She writes x several times in a line one by one and gets a digits sequence.

    For example, suppose the number Alice thought out is 231 and she writes it 4 times, then she will get the digits sequence 231231231231.
    Now Alice just shows you a continuous part of that digits sequence, and could you find out the minimum probable value of x?
    For example, if Alice showed you 31231, x may be 312, because you will get 312312 if you writes it 2 times, and 31231 is a continuous part of 312312. Obviously x may also be 231, 1231, 31231, 231731, etc. But the minimum probable value of x is 123, write it 3 times and you will see 31231 is a continuous part of 123123123.

Input

    The first line has one integer T, means there are T test cases.

    For each test case, there is only one digits sequence in a line. The number of digits is in range [1, 105].
    The size of the input file will not exceed 5MB.

Output

    For each test case, print the minimum probable value of x in one line.

Sample Input

477731231401230

Sample Output

71231234010

思路:

首先根据kmp求出字符串的周期,参考

然后字符串最小表示法有个专门的方法,思想和kmp很像

代码:

#include
#include
using namespace std;char c[200005];int next_[100005];int l;void get_next(char *t, int m, int next[]){ int i = 1, j = 0; next[0] = next[1] = 0; while (i < m) { if (j == 0 || t[i] == t[j])next[++i] = ++j; else j = next[j]; }}int getmin(int n){ int i = 1, j = 2, k = 0; while (i <= n && j <= n && k <= n) { if (c[i] == '0')i++; else if (c[j] == '0')j++; else if (i == j)j++; else if (c[i + k] == c[j + k])k++; else if (c[i + k] > c[j + k])i += k + (!k), k = 0; else j += k + (!k), k = 0; } return (i <= n) ? i : j;}int main(){ int t; scanf("%d", &t); c[0] = '0'; while (t--) { scanf("%s", &c[1]); l = strlen(c + 1); bool flag = true;//全0 for (int i = 1; i <= l; i++)if (c[i] != '0')flag = false; if (flag) { printf("1%s\n", c + 1); continue; } get_next(c, l, next_); int k = next_[l]; while (k && c[l] != c[k])k = next_[k]; l -= k; for (int i = l + 1; i <= l * 2; i++)c[i] = c[i - l]; int key = getmin(l); c[key + l] = '\0'; printf("%s\n", c + key); } return 0;}

转载地址:http://wtlxz.baihongyu.com/

你可能感兴趣的文章
MySQL不会性能调优?看看这份清华架构师编写的MySQL性能优化手册吧
查看>>
MySQL不同字符集及排序规则详解:业务场景下的最佳选
查看>>
Mysql不同官方版本对比
查看>>
MySQL与Informix数据库中的同义表创建:深入解析与比较
查看>>
mysql与mem_细说 MySQL 之 MEM_ROOT
查看>>
MySQL与Oracle的数据迁移注意事项,另附转换工具链接
查看>>
mysql丢失更新问题
查看>>
MySQL两千万数据优化&迁移
查看>>
MySql中 delimiter 详解
查看>>
MYSQL中 find_in_set() 函数用法详解
查看>>
MySQL中auto_increment有什么作用?(IT枫斗者)
查看>>
MySQL中B+Tree索引原理
查看>>
mysql中cast() 和convert()的用法讲解
查看>>
mysql中datetime与timestamp类型有什么区别
查看>>
MySQL中DQL语言的执行顺序
查看>>
mysql中floor函数的作用是什么?
查看>>
MySQL中group by 与 order by 一起使用排序问题
查看>>
mysql中having的用法
查看>>
MySQL中interactive_timeout和wait_timeout的区别
查看>>
mysql中int、bigint、smallint 和 tinyint的区别、char和varchar的区别详细介绍
查看>>