【HDU5442 2015长春网络赛F】字符串最小表示法+函数逆用循环节法+翻转串字符串哈希法

本文主要是介绍【HDU5442 2015长春网络赛F】字符串最小表示法+函数逆用循环节法+翻转串字符串哈希法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

这道题有两种比较优秀的O(n)做法

前者是函数逆用循环节法,抓住了字符串最小表示法的所有性质

后者是反转字符串哈希法,使用了字符串哈希。



【HDU5442 2015长春网络赛F】字符串最小表示法+函数逆用循环节法——

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<functional>
#include<string>
#include<algorithm>
#include<time.h>
#include<bitset>
void fre(){freopen("c://test//input.in","r",stdin);freopen("c://test//output.out","w",stdout);}
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned int UI;
typedef int Int;
template <class T> inline void gmax(T &a,T b){if(b>a)a=b;}
template <class T> inline void gmin(T &a,T b){if(b<a)a=b;}
using namespace std;
const int N=20000+10;
int casenum,casei;
int n;
char s[N];
int getmax0()
{//i是前起点,j是后起点,k是匹配长度int i=0,j=1,k=0;while(i<n&&j<n&&k<n){int t=s[(i+k)%n]-s[(j+k)%n];if(t==0)k++;else{t>0?j+=k+1:i+=k+1;if(i==j)j++;k=0;}}return min(i,j);
}
int getmax1()
{//i是后起点,j是前起点,k是匹配长度int i=n-1,j=n-2,k=0;while(i>=0&&j>=0&&k<n){int t=s[(i-k+n)%n]-s[(j-k+n)%n];if(t==0)k++;else{t>0?j-=k+1:i-=k+1;if(i==j)j--;k=0;}}if(k==n){int cir=abs(i-j);return i%cir;}if(i>=0&&j>=0)return min(i,j);return i>=0?i:j;
}
int cmp(int p0,int p1)
{for(int i=0;i<n;i++){int t=s[(p0+i)%n]-s[(p1-i+n)%n];if(t>0)return 1;if(t<0)return -1;}return 0;
}
int main()
{scanf("%d",&casenum);for(casei=1;casei<=casenum;casei++){scanf("%d",&n);scanf("%s",s);int p0=getmax0();int p1=getmax1();int v=cmp(p0,p1);if(v==1)printf("%d %d\n",p0+1,0);//正着字典序大else if(v==-1)printf("%d %d\n",p1+1,1);//逆着字典序大else p0<=p1?printf("%d %d\n",p0+1,0):printf("%d %d\n",p1+1,1);//一样大看位置}return 0;
}
/*
【题意】
T(20)组数据。
对于每组数据,给你一个长度为n(2e4)的字符串,1base,即位置分别是1,2,3,4,……,n
这个字符串是环状,而且可以正着来或者反正来读。这样一共就存在2n种串,长度都为n。
我们想要知道——从哪个位置以什么方向开始读,读出的字符串的字典序是最大的。输出:
位置(1~n)和方向(0表示正着,1表示反着)输出要求:
1,如果存在多个位置,我们输出起点编号最小的位置。
2,如果从该位置正反读都可以得到最大字典序的串,那么我们正着读。【类型】
字符串最小表示法
(+字符串哈希)【分析】
这道题因为涉及到串的旋转和最大字典序。
所以一眼就想到其可以用字符串最小表示法做。
正着来的话,用字符串最小表示法就已经可以得到字典序最大的位置中编号最小的那个位置了。
不过,反着来的话,要怎么搞?
方法一:把串反转
方法二:把字符串最小表示法的模板反一下。
我们正着使用字符串最小表示法的时候,首先得到的字典序最大的串一定是编号最小的那个。
而如果倒着来,因为编号的顺序是与我们扫描的顺序相逆的。我们得到的是倒着出现的第一个。为了解决这个问题,我们有两种策略——
方法一:
既然我们现在已经得到了字典序最大的串。
那么我们用字符串哈希的方式,从1到n扫描,求出以所有位置为开头,方向是逆着来,哪个的字典序一样是最大。
方法二:
我们看到这个可能是倒着出现的第一个,而不是最后一个。
什么时候会出现多个字典序相同的串呢?
当这个串出现循环节的时候。即——最小表示法终止的条件是k==len。
这时,直接mod循环节,就可以得到第一个起点位置。【时间复杂度&&优化】
O(n)【数据】
input
9
abcabcabc
output
3 1
*/

【HDU5442 2015长春网络赛F】字符串最小表示法+翻转串字符串哈希法——

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<functional>
#include<string>
#include<algorithm>
#include<time.h>
#include<bitset>
void fre(){freopen("c://test//input.in","r",stdin);freopen("c://test//output.out","w",stdout);}
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned int UI;
typedef int Int;
template <class T> inline void gmax(T &a,T b){if(b>a)a=b;}
template <class T> inline void gmin(T &a,T b){if(b<a)a=b;}
using namespace std;
const int N=20000+10,M=40000+10;
int casenum,casei;
int n;
char a[M];
LL u[N];
LL f[M];//f[i]表示以a[i-1]为结尾字符串的哈希前缀和
int getmax()
{//i是前起点,j是后起点,k是匹配长度int i=0,j=1,k=0;while(i<n&&j<n&&k<n){int t=a[(i+k)%n]-a[(j+k)%n];if(t==0)k++;else{t>0?j+=k+1:i+=k+1;if(i==j)j++;k=0;}}return min(i,j);
}
int cmp(int p0,int p1)
{for(int i=0;i<n;i++){int t=a[(p0+i)%n]-a[(p1-i+n)%n];if(t>0)return 1;if(t<0)return -1;}return 0;
}
int hashit(int p)
{int m=n+n;for(int i=0;i<n;i++)a[n+i]=a[i];//把字符串二倍化——扩环成链for(int i=1;i<=m;i++)f[i]=(f[i-1]*26+a[i-1]-'a')%Z;//计算字符串哈希值int V=(f[p+n]-f[p]*u[n]%Z+Z)%Z;//得到最大字典序串的哈希值for(int i=0;i<n;i++)if((f[i+n]-f[i]*u[n]%Z+Z)%Z==V)return i;//对于多个最大字典序串,返回最小的位置
}
int main()
{u[0]=1;for(int i=1;i<=20000;i++)u[i]=u[i-1]*26%Z;scanf("%d",&casenum);for(casei=1;casei<=casenum;casei++){scanf("%d",&n);scanf("%s",a);int p0=getmax();//正方向字典序最大串的最小点位strrev(a);int p1=n-1-getmax();//逆方向字典序最大串的最大点位strrev(a);p1=hashit(p1);//哈希一下就能得到逆方向字典序最大串的最小点位啦。int v=cmp(p0,p1);if(v==1)printf("%d %d\n",p0+1,0);//正着字典序大else if(v==-1)printf("%d %d\n",p1+1,1);//逆着字典序大else p0<=p1?printf("%d %d\n",p0+1,0):printf("%d %d\n",p1+1,1);//一样大看位置}return 0;
}
/*
【题意】
T(20)组数据。
对于每组数据,给你一个长度为n(2e4)的字符串,1base,即位置分别是1,2,3,4,……,n
这个字符串是环状,而且可以正着来或者反正来读。这样一共就存在2n种串,长度都为n。
我们想要知道——从哪个位置以什么方向开始读,读出的字符串的字典序是最大的。输出:
位置(1~n)和方向(0表示正着,1表示反着)输出要求:
1,如果存在多个位置,我们输出起点编号最小的位置。
2,如果从该位置正反读都可以得到最大字典序的串,那么我们正着读。【类型】
字符串最小表示法
(+字符串哈希)【分析】
这道题因为涉及到串的旋转和最大字典序。
所以一眼就想到其可以用字符串最小表示法做。
正着来的话,用字符串最小表示法就已经可以得到字典序最大的位置中编号最小的那个位置了。
不过,反着来的话,要怎么搞?
方法一:把串反转
方法二:把字符串最小表示法的模板反一下。
我们正着使用字符串最小表示法的时候,首先得到的字典序最大的串一定是编号最小的那个。
而如果倒着来,因为编号的顺序是与我们扫描的顺序相逆的。我们得到的是倒着出现的第一个。为了解决这个问题,我们有两种策略——
方法一:
既然我们现在已经得到了字典序最大的串。
那么我们用字符串哈希的方式,从1到n扫描,求出以所有位置为开头,方向是逆着来,哪个的字典序一样是最大。
方法二:
我们看到这个可能是倒着出现的第一个,而不是最后一个。
什么时候会出现多个字典序相同的串呢?
当这个串出现循环节的时候。即——最小表示法终止的条件是k==len。
这时,直接mod循环节,就可以得到第一个起点位置。【时间复杂度&&优化】
O(n)【数据】
input
9
abcabcabc
output
3 1
*/


这篇关于【HDU5442 2015长春网络赛F】字符串最小表示法+函数逆用循环节法+翻转串字符串哈希法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/610494

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1171(母函数或多重背包)

题意:把物品分成两份,使得价值最接近 可以用背包,或者是母函数来解,母函数(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v)(1 + x^v+x^2v+.....+x^num*v) 其中指数为价值,每一项的数目为(该物品数+1)个 代码如下: #include<iostream>#include<algorithm>

Linux 网络编程 --- 应用层

一、自定义协议和序列化反序列化 代码: 序列化反序列化实现网络版本计算器 二、HTTP协议 1、谈两个简单的预备知识 https://www.baidu.com/ --- 域名 --- 域名解析 --- IP地址 http的端口号为80端口,https的端口号为443 url为统一资源定位符。CSDNhttps://mp.csdn.net/mp_blog/creation/editor

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路: 1. 用一个 hash[ ] 数组存放输入的数字,令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ,检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999,第二行数从 10到99。 4. 剪枝。 代码: /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

hdu 1102 uva 10397(最小生成树prim)

hdu 1102: 题意: 给一个邻接矩阵,给一些村庄间已经修的路,问最小生成树。 解析: 把已经修的路的权值改为0,套个prim()。 注意prim 最外层循坏为n-1。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstri