L - Ferris Wheel String
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 43000/43000KB (Java/Others)
Have you ever been to London?
Our Master Qiu will tell you how amazing in London and how funny a Ferris Wheel String is.
One day, while our Master Qiu was recovering Great Britain, he was thinking about an interesting problem about string. In front of him, a London Ferris Wheel was revolving. There were some seats on the large Ferris Wheel. However, in Master Qiu's mind, each seat was a lower-case letter so that the Ferris Wheel was a beautiful string that was revolving all the time. Let's call it Ferris Wheel String
.
In the revolving operation, you can put several front letters to the last of the string. Of course, you can also put all the letters to the last, so you will get the string itself. For example, you can change string abcd
into 4 strings, such as bcda
, cdab
, dabc
, abcd
. Obviously, in the revolving operation, a string of length n can be changed into n strings.
Master Qiu found out an interesting phenomenon that the Ferris Wheel String spent exactly one second revolving one letter. For example, at the beginning(0 second),the Ferris Wheel String was abcd,after one second,it became bcda ... and after four seconds, it became abcd.
Master Qiu is a Romantic guy. He thought after exactly K second(s), the Ferris Wheel String became extremely beautiful.
Now, he would like to ask you a question:
After exactly K second(s), among the n strings obtained by revolving a string of length n, how many distinct
strings are lexicographically smaller than the beautiful string, how many distinct
strings are lexicographically equal to the beautiful string and how many distinct
strings are lexicographically bigger than the beautiful string ?
(If you really can not understand Master Qiu's mind, see examples and Hint)
Input
The first line contains a string of length n(1≤n≤2⋅105) and the second line contains an integer k(1≤k≤n).
The string only contains lower-case letters.
Output
Output three integers separated by two spaces that are your answer to Master Qiu. Do not output anything after the last integer.
Sample input and output
Sample Input | Sample Output |
---|---|
abcabc |
1 1 1 |
aaaaaaa |
0 1 0 |
himverihimverihimveri |
0 1 6 |
lvhqsjtdgckrznjsbargcojiyuf |
7 1 19 |
abbabaabbaababbabaababbaabbaba |
3 1 26 |
Hint
Let's define that <
means lexicographically smaller,>
means lexicographically bigger and =
means lexicographically equal.
Also, ans1
means the number of strings < bcabca,ans2
means the number of strings = bcabca and ans3
means the number of strings > bacabca.
Explain for lexicography :
Let's only consider lexicographical order between two strings when |S|=|T|.
If S<T, there exits a position p (0≤p<|S|) satisfying that Si=Ti when 0≤i<p but Sp<Tp.
If S>T, there exits a position p (0≤p<|S|) satisfying that Si=Ti when 0≤i<p but Sp>Tp.
If S=T, then Si=Ti for all i (0≤i<|S|)
And we all know that a<b<c< ⋯ <x<y<z.
Explain for the first example :
The Ferris Wheel String is abcabc and K=1 , so that the beautiful string is bcabca
After 1 second, it becomes cabcab, cabcab>bcabca;ans3+=1;
After 2 seconds, it becomes abcabc, abcabc<bcabca;ans1+=1;
After 3 seconds, it becomes bcabca, bcabca=bcabca;ans2+=1;
After 4 seconds, it becomes cabcab. But it has appeared. So, do not count it.
After 5 seconds, it becomes abcabc. But it has appeared. So, do not count it.
After 6 seconds, it becomes bcabca. But it has appeared. So, do not count it.
Therefore, ans1=1, ans2=1 and ans3=1.
Use double hash rather than single hash if you wanna hash.
解题报告:
首先我们将移动后的字符串 * 2处理出来,之后Hash处理,注意使用双哈希.
相同字符换的判断我们将字符串本身的哈希值再哈希即可..
那么字典序如何判断呢?
我们考虑字典序时,前面一段都是一样的,之后在某个位置就不同了,满足二分性质,因此我们通过二分来找到第一个不一样的位置,从而比较字典序的大小
#include <iostream>
#include <cstring>
#include <cstdio>
typedef long long ll;
using namespace std;
const int maxn = 2e5 + , p1 = , mod1 = 1e9 + , p2 = , mod2 = 1e9 + , MaxHashSize = , MaxStatusSize = 2e5 + ;
char str[maxn*],temp[maxn];
int k,len,stdhash1,stdhash2,head[MaxHashSize],next_new[MaxStatusSize],size = ;
ll hash1[maxn*],fac1[maxn+],hash2[maxn*],fac2[maxn+];
typedef struct status
{
int hash1,hash2;
}; status st[MaxStatusSize]; int gethashvalue(int l,int r,int id)
{
ll ans;
if (id == )
{
ans = (hash1[r] - hash1[l-]*fac1[r-l+])%mod1;
if (ans < )
ans += mod1;
return ans;
}
else
{
ans = (hash2[r] - hash2[l-]*fac2[r-l+])%mod2;
if (ans < )
ans += mod2;
return ans;
}
} void init_hash()
{
memset(head,-,sizeof(head));
hash1[] = ,hash2[] = ;
for(int i = ; i <= *len ; ++ i )
hash1[i] = (hash1[i-]*p1 + str[i]) % mod1;
for(int i = ; i <= *len ; ++ i )
hash2[i] = (hash2[i-]*p2 + str[i]) % mod2;
fac1[] = ;
for(int i = ; i <= maxn ; ++ i)
fac1[i] = (fac1[i-]*p1) % mod1;
fac2[] = ;
for(int i = ; i <= maxn ; ++ i)
fac2[i] = (fac2[i-]*p2) % mod2;
} int HashValue(const status &x)
{
return (x.hash1 + x.hash2) % MaxHashSize;
} bool insert(int id)
{
int val = HashValue(st[id]);
int u = head[val];
while(u != -)
{
if (!memcmp(&st[u],&st[id],sizeof(status)))
return false;
u = next_new[u];
}
next_new[id] = head[val];
head[val] = id;
return true;
} void dump(int l,int r)
{
for(int i = l ; i <= r ; ++ i)
printf("%c",str[i]);
printf("\n");
} int main(int argc,char *argv[])
{
scanf("%s%d",str+,&k);len = strlen(str+);
memcpy(temp,str+,k);memcpy(str+,str+k+,len-k);memcpy(str+len-k+,temp,k);memcpy(str+len+,str+,len);init_hash();
stdhash1 = gethashvalue(,len,);
stdhash2 = gethashvalue(,len,);
ll ans1 = , ans2 = , ans3 = ; // < = >
for(int i = ; i <= len+ ; ++ i)
{
st[size].hash1 = gethashvalue(i,i+len-,);
st[size].hash2 = gethashvalue(i,i+len-,);
if (!insert(size))
{
//dump(i,i+len-1);
continue;
}
int thishash1 = st[size].hash1;
int thishash2 = st[size++].hash2;
if (thishash1 == stdhash1 && thishash2 == stdhash2)
{
ans2 ++ ;
continue;
}
if (str[i] != str[])
{
if (str[i] < str[])
ans1++;
else
ans3++;
continue;
}
int l = , r = len-;
while(l < r)
{
int mid = l + (r-l+)/;
int stdh1 = gethashvalue(,mid,);
int stdh2 = gethashvalue(,mid,);
int thish1 = gethashvalue(i,i+mid-,);
int thish2 = gethashvalue(i,i+mid-,);
if (stdh1 == thish1 && stdh2 == thish2)
l = mid;
else
r = mid - ;
}
if (str[i + l] < str[ + l])
ans1++;
else
ans3++;
}
printf("%lld %lld %lld\n",ans1,ans2,ans3);
return ;
}
UESTC_Ferris Wheel String 2015 UESTC Training for Search Algorithm & String<Problem L>的更多相关文章
-
UESTC_Palindromic String 2015 UESTC Training for Search Algorithm &; String<;Problem M>;
M - Palindromic String Time Limit: 3000/1000MS (Java/Others) Memory Limit: 128000/128000KB (Java ...
-
UESTC_韩爷的梦 2015 UESTC Training for Search Algorithm &; String<;Problem N>;
N - 韩爷的梦 Time Limit: 200/100MS (Java/Others) Memory Limit: 1300/1300KB (Java/Others) Submit Stat ...
-
2015 UESTC Training for Search Algorithm &; String - M - Palindromic String【Manacher回文串】
O(n)的复杂度求回文串:Manacher算法 定义一个回文值,字符串S是K重回文串,当且仅当S是回文串,且其长度为⌊N/2⌋的前缀和长度为⌊N/2⌋的后缀是K−1重回文串 现在给一个2*10^6长度 ...
-
2015 UESTC Training for Search Algorithm &; String - J - 全都是秋实大哥 【KMP】
给出一个字符串,求每个前缀的最小循环节长度,并输出整个字符串的最小循环节.字符串长度为3*10^6 找循环节这种问题还是要用KMP对于长度为i的字符串 i%(i-f[i])==0 此时,它的最小循环节 ...
-
UESTC_秋实大哥の恋爱物语 2015 UESTC Training for Search Algorithm &; String<;Problem K>;
K - 秋实大哥の恋爱物语 Time Limit: 5000/2000MS (Java/Others) Memory Limit: 32000/32000KB (Java/Others) Su ...
-
UESTC_全都是秋实大哥 2015 UESTC Training for Search Algorithm &; String<;Problem J>;
J - 全都是秋实大哥 Time Limit: 5000/2000MS (Java/Others) Memory Limit: 32000/32000KB (Java/Others) Subm ...
-
UESTC_Infected Land 2015 UESTC Training for Search Algorithm &; String<;Problem G>;
G - Infected Land Time Limit: 6000/3000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others ...
-
UESTC_Eight Puzzle 2015 UESTC Training for Search Algorithm &; String<;Problem F>;
F - Eight Puzzle Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others) ...
-
UESTC_吴队长征婚 2015 UESTC Training for Search Algorithm &; String<;Problem E>;
E - 吴队长征婚 Time Limit: 10000/4000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others) Submi ...
随机推荐
-
ios开发中超简单抽屉效果(MMDrawerController)的实现
ios开发中,展示类应用通常要用到抽屉效果,由于项目需要,本人找到一个demo,缩减掉一些不常用的功能,整理出一个较短的实例. 首先需要给工程添加第三方类库 MMDrawerController: 这 ...
-
block 做参数
三部分 1,定义函数 /* 传出类定义block */ //定义block typedef void (^ItemClickBlock)(NSInteger selectedIndex); //blo ...
-
Ajax学习(三)——XMLHttpRequest对象的五步使使用方法
Ajax的核心技术是XMLHttpRequest对象,它能够在不向server提交整个页面的情况下.实现局部更新网页.通过这个对象,Ajax能够像桌面应用程序那样仅仅与server进行数据层的 ...
-
如何配置 Health Check?- 每天5分钟玩转 Docker 容器技术(107)
容器状态是 UP 的,应用就是健康的吗? 还真不一定!Docker 只能从容器启动进程的返回代码判断其状态,而对于容器内部应用的运行情况基本没有了解. 执行 docker run 命令时,通常会根据 ...
-
C#语言中的XmlSerializer类的XmlSerializer.Deserialize (Stream)方法举例详解
包含由指定的 XML 文档反序列化 Stream. 命名空间: System.Xml.Serialization程序集: System.Xml(位于 System.Xml.dll) 注意: 反序 ...
-
SAP基础:定位点运算
先看一下下面简单的代码: REPORT zlytest003. ) VALUE '21.00'. ) . b = a. WRITE b. 运行结果是: 这时候到程序属性页面: 修改固定点算术为空. 保 ...
-
apply 和call 的区别,apply实用小技巧
Js apply方法详解 我在一开始看到javascript的函数apply和call时,非常的模糊,看也看不懂,最近在网上看到一些文章对apply方法和call的一些示例,总算是看的有点眉目了,在这 ...
-
谈谈MySQL死锁之二 死锁检测和处理源码分析
这一篇主要是通过一个实验来进行描述,过程是比较枯燥的. 实验准备 create table test_lock(id int auto_increment primary key ,stock int ...
-
Python3中Urllib库基本使用
什么是Urllib? Python内置的HTTP请求库 urllib.request 请求模块 urllib.error 异常处理模块 urllib.par ...
-
ORACLE分组查询和统计等
select flow_id,rw from (select t.flow_id ,rownum as rw from apex_030200.wwv_flow_list_templates t) ...