精华内容
下载资源
问答
  • 最小表示法

    千次阅读 2019-09-03 23:21:11
    最小表示法 作用 详解 前置知识 定义 暴力方法 优化 时间复杂度 代码 例题 汉语名:最小表示法 时间复杂度:线性 wiki 博客园 作用 求最小表示。 详解 前置知识 IT已入门还未入土。 懂得...


    汉语名:最小表示法
    时间复杂度:线性

    作用

    求最小表示。

    详解

    前置知识

    • IT已入门还未入土。
    • 懂得字符串的基本知识。

    定义

    循环同构:对于串 s s s,某个数字 i i i,满足 s [ 1 , 2 … i ] + s [ i , i + 1 … n ] = T s[1,2\ldots i]+s[i,i+1\ldots n]=T s[1,2i]+s[i,i+1n]=T,则称串 T T T是串 s s s的循环同构。
    最小表示:串 s s s字典序最小的循环同构称为 s s s的最小表示。

    暴力方法

    求最小表示,可以暴力比较每个循环同构的大小。

    for(int i=1,j=2,I,J;i<=n&&j<=n&&k<=n;j++)
    {
    	for(;s[I=(i-1)%n+1]==s[J=(j-1)%n+1]&&k<=n;k++)
    	if(s[I]>s[J])i=j;
    }
    

    在随机数据下,该方法表现良好。
    但在构造数据如 " a a a … a " "aaa\ldots a" "aaaa",时间复杂度退化为 O ( n 2 ) O(n^2) O(n2)

    优化

    • 引理
      如果比较起始位置 i i i和起始位置 j j j发现 s [ i , i + 1 … i + k − 1 ] = s [ j , j + 1 … j + k − 1 ] s[i,i+1\ldots i+k-1]=s[j,j+1\ldots j+k-1] s[i,i+1i+k1]=s[j,j+1j+k1] s [ i + k ] < s [ j + k ] s[i+k]<s[j+k] s[i+k]<s[j+k]则起始位置 j , j + 1 … j + k j,j+1\ldots j+k j,j+1j+k都不合法。
      证明:对于每个数字 0 < = l < = k 0<=l<=k 0<=l<=k都有起始位置 i + l i+l i+l比起始位置 j + l j+l j+l优,因为 s [ i + l , i + l + 1 … i + k − 1 ] = s [ j + l , j + l + 1 … j + k − 1 ] a n d s [ i + k ] < s [ j + k ] s[i+l,i+l+1\ldots i+k-1]=s[j+l,j+l+1\ldots j+k-1]\quad and\quad s[i+k]<s[j+k] s[i+l,i+l+1i+k1]=s[j+l,j+l+1j+k1]ands[i+k]<s[j+k]

    因此当发现 i i i不合法的时候,可以直接将 i = i + k + 1 i=i+k+1 i=i+k+1

    时间复杂度

    O(n)
    证明

    证毕

    代码

    //C++
    template<typename name>name* expression(name* l,name* r)
    {
    	int n=r-l,i=0,j=1;
    	for(int k=0,I,J,bound;i<=n&&j<=n&&k<=n;)
    	{
    		I=(i+k-1)%n+1,J=(j+k-1)%n+1;
    		if(l[I]==l[J])k++;
    		else
    		{
    			if(l[I]<l[J])swap(i,j);
    			bound=max(i+k,j-1);//被排除部分的边界,即是指i,i+1……bound,都不合法。
    			if(i<j)j=bound+2;
    			i=bound+1,k=0;
    		}
    	}
    	return l+min(i,j);
    }
    

    例题

    工艺

    展开全文
  • 字符串的最大、最小表示法 前言 什么是字符串的最大、最小表示法? 对于一个字符串,求它的循环的同构字符串中字典序最大的就是最大表示法,同理字典序最小的就是最小表示法。 如:给定字符串为s=bacds=bacds=bacd...

    字符串的最大、最小表示法


    前言

    什么是字符串的最大、最小表示法?

    对于一个字符串,求它的循环的同构字符串中字典序最大的就是最大表示法,同理字典序最小的就是最小表示法。

    如:给定字符串为 s = b a c d s=bacd s=bacd,则最大表示法为 d b a c dbac dbac,最小表示法为 a c d b acdb acdb



    求解字符串的的最小表示法

    对于求最小表示法的实质就是找到一个位置,从这个位置开始的字符串的字典序最小,那么就可以利用指针来进行操作。

    可以令 i = 0 i=0 i=0, j = 1 j=1 j=1来表示最小位置,同时来维护更新两个指针求解位置。

    s [ i ] > s [ j ] s[i]>s[j] s[i]>s[j]时,i=j,j++

    s [ i ] < s [ j ] s[i]<s[j] s[i]<s[j]时,j++

    s [ i ] = s [ j ] s[i]=s[j] s[i]=s[j]时,添加一个新指针k,分别从 i + k i+k i+k j + k j+k j+k的位置进行比较,当 s [ i + k ] = s [ j + k ] s[i+k]=s[j+k] s[i+k]=s[j+k]时k++;当 s [ i + k ] > s [ j + k ] s[i+k]>s[j+k] s[i+k]>s[j+k] i = i + k + 1 i=i+k+1 i=i+k+1;当 s [ i + k ] < s [ j + k ] s[i+k]<s[j+k] s[i+k]<s[j+k] j = j + k + 1 j=j+k+1 j=j+k+1

    在第三种情况中为什么要让 i = i + k + 1 i=i+k+1 i=i+k+1或者 j = j + k + 1 j=j+k+1 j=j+k+1呢?

    因为当 s [ i + k ] < s [ j + k ] s[i+k]<s[j+k] s[i+k]<s[j+k]时,在s串中从j到j+k这个区间里的任意位置开始的串的字典序都是大于从i开始的字符串的,所以为了降低复杂度直接令 j = j + k + 1 j=j+k+1 j=j+k+1,同理 i = i + k + 1 i=i+k+1 i=i+k+1也是这个道理。

    最大表示法的求解思路也类似。


    模板

    int Min_or_Max(int op,char *a)//op=0求最小表示法,op=1求最大表示法
    {
        int i,j,k,t;
        i=0,j=1,k=0;
        while(i<len&&j<len&&k<len)
        {
            t=a[(i+k)%len]-a[(j+k)%len];
            if(!t) k++;
            else
            {
                if(op)
                {
                   if(t>0) j+=(k+1);
                   else i+=(k+1);
                }
                else
                {
                    if(t>0) i+=(k+1);
                    else j+=(k+1);
                }
                if(i==j) j++;
                k=0;
            }
        }
        return min(i,j)+1;
    }
    

    例题

    hdu-3374

    题意:

    求最小、最大表示法的开始位置和出现的次数。


    思路:

    对于最小、最大表示法可直接套模板求即可。至于出现次数不就是就最小循环节,然后用长度除最小循环节就是出现次数了。


    参考代码:

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+10;
    char a[maxn];
    int nex[maxn],len;
    void getnext()
    {
        for(int i=2,j=0;i<=len;i++)
        {
            while(j&&a[i]!=a[j+1])j=nex[j];
            if(a[i]==a[j+1])j++;
            nex[i]=j;
        }
    }
    int Min_or_Max(int op,char *a)
    {
        int i,j,k,t;
        i=0,j=1,k=0;
        while(i<len&&j<len&&k<len)
        {
            t=a[(i+k)%len]-a[(j+k)%len];
            if(!t) k++;
            else
            {
                if(op)
                {
                   if(t>0) j+=(k+1);
                   else i+=(k+1);
                }
                else
                {
                    if(t>0) i+=(k+1);
                    else j+=(k+1);
                }
                if(i==j) j++;
                k=0;
            }
        }
        return min(i,j)+1;
    }
    int main()
    {
        while(~scanf("%s",a+1))
        {
            len=strlen(a+1);
            int maxx=Min_or_Max(1,a+1);
            int minn=Min_or_Max(0,a+1);
            getnext();
            int ans=len-nex[len];
            if(ans!=len&&len%ans== 0)ans=len/ans;
    		else ans=1;
            printf("%d %d %d %d\n",minn,ans,maxx,ans);
        }
        system("pause");
        return 0;
    }
    
    展开全文
  • 字符串最小表示法 O(n)算法

    万次阅读 多人点赞 2014-10-07 15:58:26
    求字符串的循环最小表示:   上面说的两个字符串同构的,并没有直接先求出Min(s),而是通过指针移动,当某次匹配串长时,那个位置就是Min(s)。而这里的问题就是:不是给定两个串,而是给出一个串,求它的Min(s),...

    网上看了这篇文章后还是感觉有些地方讲的没有详细的证明所以添加了一点 红色字是博主写的

    求字符串的循环最小表示:

     

    上面说的两个字符串同构的,并没有直接先求出Min(s),而是通过指针移动,当某次匹配串长时,那个位置就是Min(s)。而这里的问题就是:不是给定两个串,而是给出一个串,求它的Min(s),eg:Min(“babba”) = 4。那么由于这里并非要求两个串的同构,而是直接求它的最小表示,由于源串和目标串相同,所以处理起来既容易又需要有一些变化:我们仍然设置两个指针,i, j,其中i指向0,j指向1,仍然采用上面的滑动方式:

     

    (1)  利用两个指针i, j。初始化时i指向0, j指向1。

     

    (2)  k = 0开始,检验s[i+k] 与 s[j+k] 对应的字符是否相等,如果相等则k++,一直下去,直到找到第一个不同,(若k试了一个字符串的长度也没找到不同,则那个位置就是最小表示位置,算法终止并返回)。则该过程中,s[i+k] 与 s[j+k]的大小关系,有三种情况:

      证明的时候假设(i<j)的,无伤大雅 ;

         (A). s[i+k] > s[j+k],则i滑动到i+k+1处 --- 即s1[i->i+k]不会是该循环字符串的“最小表示”的前缀。

     证明如下

        

         (B). s[i+k] < s[j+k],则j滑动到j+k+1处,原因同上。

     证明如下


         (C). s[i+k] = s[j+k],则 k++; if (k == len) 返回结果。 

        注:这里滑动方式有个小细节,若滑动后i == j,将正在变化的那个指针再+1。直到p1、p2把整个字符串都检验完毕,返回两者中小于 len 的值。

     

    (3)   如果 k == len, 则返回i与j中的最小值

     

          如果 i >= len   则返回j

     

          如果 j >= len   则返回i

    如果看了上一篇文章 很容易对这里的i,j 产生误会  误以为i为ans,j为比较指针

    实际上这题中 i,j 都可能存有ans 两者互相更新,直到有一个更新后超过了len(包括len) 的时候 另一个即为正解

    (4)   进一步的优化,例如:i要移到i+k+1时,如果i+k+1 <= p2的话,可以直接把i移到 j+1,因为,j到j+k已经检验过了该前缀比以i到i+k之间任何一个位前缀都小;j时的类似,移动到i+1。

     这个优化就无需解释了

    至此,求一个字符串的循环最小表示在O(n)时间实现,感谢大牛的论文。其中实现时的小细节“如果滑动后p1 == p2,将正在变化的那个指针再+1”,开始没有考虑,害得我想了几个小时都觉得无法进行正确的移动。具体例题有两个:http://acm.zju.edu.cn 的2006和1729题。一个是10000规模一个是100000规模。运行时间前者是0S,后者是0.05S。



    上自己丑陋的代码
    int MinimumRepresentation(int *s, int l)  
    {  
    	int i,j,k;
    	i=0;j=1;k=0;
    	while(i<l&&j<l)
    	{
    		k=0;
    		while(s[i+k]==s[j+k]&&k<l) k++;
    		if(k==l) return i;
    		if(s[i+k]>s[j+k]) 
    		 if(i+k+1>j) i=i+k+1;
    		 else i=j+1;
    		else if(j+k+1>i) j=j+k+1;
    		else  j=i+1; 
    	}
    	if(i<l) return i;
    	else return j;
    } 
    


    展开全文
  • 最小表示法—介绍

    2018-08-08 19:41:44
    最小表示法使得一个环形字符串有唯一的读法,这个读法是所有读法中字典序最小的。 本文讲解的是最小表示法的O(n)求法。 对于这种环形问题,一个常规的做法是把它自己复制一遍,接到原串之后。问题就转换成了求在...

    最小表示法使得一个环形字符串有唯一的读法,这个读法是所有读法中字典序最小的。
    本文讲解的是最小表示法的O(n)求法。
    对于这种环形问题,一个常规的做法是把它自己复制一遍,接到原串之后。问题就转换成了求在字符串s中长度为n的最小子串。

    先思考暴力做法。找到所有同构串,两两间比较一下,找到最小的。
    优一点的做法,存下一个最小的同构串,逐一比较,如果有更小的则替换之。即便是这样时间复杂度O(n*|S|)。

    想到这,其实已经命中了正解的一半。想要提速,最根本的办法就是减少无用状态空间的遍历
    再仔细思考暴力的过程。假设在比较s[i~i+len]和s[j~j+len]中s[i+k]与s[j+k]不同(假设s[i+k]<s[j+k]),按暴力,我们仅仅得到s[i~i+len]小于s[j~j+len],然后舍弃j,选择i。深入地再想想,s[i+1~i+1+len]与s[j+1~j+1+len]的大小关系呢?因为s[i+1~i+k-1]与s[j+1~j+k-1]是相同的,而s[i+k]<s[j+k],所以s[i+1~i+1+len]小于s[j+1~j+1+len]。所以s[j+1~j+1+len]这个状态我们可以直接跳过。
    像这样可以跳过的从s[j+1~j+1+len]一直到s[j+k~j+k+len]。我们可以对应的从s[i+1~i+1+len]到s[i+k~i+k+len]中找到比前者小的同构串。


    举个例子,看图。
    假设出现了(实际并不会这样匹配)i=1,j=4,k=2。现在s[i+k]>s[j+k],那么①>④。按照上面所说的,②、③都是可以直接跳过的,因为分别有⑤<②、⑥<③,②、③绝不肯能为最小表示法。所以i可以直接跳到i+k+1的位置。

    实现时i、j就成了两个指针,表示同构串的起始位置。还要注意几处特殊的地方,看代码注释。

     

    例题(bzoj2882 工艺)

    代码

    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int maxn=300010;
    
    int n;
    int a[2*maxn];//2倍空间
    
    int main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            a[i+n]=a[i];
        }
        int i,j,k;
        for(i=1,j=2;i<=n && j<=n;)
        {
            for(k=0;k<n && a[i+k]==a[j+k];k++);//寻找不相同的位置 
            if(k==n) break;//由一个相同元素构成 
            if(a[i+k]<a[j+k])
            {
                j=j+k+1;
                if(i==j) j++;//i和j相同时有一个数要+1
            }
            if(a[i+k]>a[j+k])
            {
                i=i+k+1;
                if(i==j) i++;//i和j相同时有一个数要+1
            }
        }
        int begin=i>n?j:i;//未超出n的是最终胜者
        for(i=0;i<n;i++) printf("%d ",a[begin+i]);
        return 0;
    }

     

    展开全文
  • 最小割集求.docx

    2020-12-18 18:38:43
    最小割集求法最小割集求相关概念求解方法(行列结构法布尔代数化简法)相关概念割集——也叫做截集或截止集,它是导致顶上事件发生的基本事件的集合。也就是说事故树中一组基本事件的发生,能够造成顶上事件发生,...
  • 最小生成树算法例题

    2021-04-21 14:43:02
      最小生成树是由n个顶点,n-1条边,将一个连通图连接起来,且使权值最小的结构。最小生成树可以用Prim算法或Kruskal算法求出。Prim算法又称“加点”,用于边数较多的带权无向连通图。其方法主要是每次找与之...
  • 单纯形法例题讲解

    千次阅读 2021-01-12 23:48:07
    基可行解单纯形是针对标准形式的线性规划问题进行演算的,任何线性规划问题都可以化为标准形式。min (1)cxfs.t (2)bA(3)0x其中 TmmnmnTnn bbaaaaAxxcc ).,(, .,),.(),,.( 2121 2221 112121 ...
  • 最小生成树 设G是无向图。 子图:K是G的子图,则K的顶点和边都包含于G。 生成子图:若K是G的子图,且K包含G的所有顶点,则K是G的生成子图。 生成树:若T是树,且T是G的生成子图,则T是G的生成树。 最小生成树:若G是...
  • 最小割集求 -

    千次阅读 2020-12-18 18:38:38
    最小割集求相关概念 求解方法(行列 结构 布尔代数化简法) 相关概念割集——也叫做截集或截止集,它是导致顶上事件发生的基本事件的集合。也就是说事故树中一组基本事件的发生,能够造成顶上事件发生,这组基本...
  • #include #include ...用最小表示法求字符串S的最小字典序 返回字典序最小的串的首字母位置 */ int minSub(char * p) {  int i=0,j=1,len=strlen(p),k=0;  while(i)  {  if(k==len) brea
  • 『算法原理』 ... Prim算法之所以叫加点,就是因为其本质是一个点一个点地加入到最小生成树中。 算法步骤如下: 设有一无向连通图G,有n个顶点。 a.初始化——任意找图中的一点作为源点,...
  • 最大最小表示法用于解决字符串的同构问题,其在复杂度为 O(n) 的时间内求出一个字符串的所有同构串中字典序最大(小)的串的起始位置。 应用: 给出 n 个循环字符串判断有多少不同字符串:逐个用最大(小)表示法...
  • 而一个队伍的团结力取决于每个人的性格,每个人都有一个性格基因【(由字符串表示),比如小明的性格基因为:abbcde】,性格基因的排列方式是可以通过一个人的后天培养而改变的,其改变方式就是类似于循环,【小明的...
  • 数学归纳例题分析

    万次阅读 多人点赞 2019-03-27 15:57:42
    学算法,不得不提的就是数学归纳。许多算法都会用到归纳假设的思想,其追溯回去便是数学归纳。 数学归纳 最简单和常见的数学归纳是证明当n等于任意一个自然数时某命题成立。证明分下面两步: 证明当n= 1...
  • 『算法原理』 在一个连通网的所有生成... Kruskal算法之所以叫加边,就是因为其本质是一个边一个边地加入到最小生成树中。 算法步骤如下: 设有一无向连通图G,有n个顶点。 a.将所有边的权值从小到大排列。 ...
  • 使用正规方程组的方法实现最小二乘: 1、 方程组Ax=b,其中A为m行n列的系数矩阵,其转置矩阵为n行m列的矩阵,使A的转置矩阵和A自身相乘可得到一个n行n列的系数矩阵,同时等号右侧也让A的转置矩阵和n维的向量b相乘...
  • 时间复杂度的渐进表示法 T(n)=O(f(n))T(n)=O(f(n))T(n)=O(f(n))表示存在常数C>0C>0C>0,n0>0n_0>0n0​>0使得当n>geqn0n>geq n_0n>geqn0​时有T(n)≤C⋅f(n)T(n)\leq C·f(n)T(n)≤C⋅f...
  • nbsp微积分第二章 线性规划与单纯形(补充例题123页开始).ppt189页本文档一共被下载:次,您可全文免费在线阅读后下载本文档。 下载提示1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的...
  •  //pre[i]=0表示顶点i未标记,pre[i] >0 表示前向边,pre[i] < 0表示后向边 //数组初始化 memset(rest,0,sizeof(rest)); memset(visited,0,sizeof(visited)); memset(flow,0,(n+1)*sizeof(flow[0])); memset(L,0x...
  • 最大流最小割基本

    2020-12-23 13:18:14
    输出 第1行:2个整数A B,A表示最小割的容量,B表示给定图G最小割S集合的点数。 第2行:B个空格隔开的整数,表示S集合的点编号。 若存在多个最小割可以输出任意一个的解。 样例输入 6 7 1 2 3 1 3 5 2 4 1 3 4 2 3 ...
  • 输出 第1行:2个整数A B,A表示最小割的容量,B表示给定图G最小割S集合的点数。 第2行:B个空格隔开的整数,表示S集合的点编号。 若存在多个最小割可以输出任意一个的解。 #include using namespacestd;#define ...
  • 浮点数表示例题

    2021-06-24 01:28:52
    设 A=–0.101101*2-3,B= 0.101001*2-2,先将A、B表示为规格化的浮点数。...这里有个例题: 我有不明白的地方 中括号内为指数,因为百度这里不能打浮点数的加减法运算完成浮点数加减法的5个步骤:1.对阶操作...
  • 最小距离分类

    千次阅读 2017-01-16 11:43:50
    最小距离分类介绍 作者:liangdas 出处:简单点儿,通俗点儿,机器学习 http://blog.csdn.NET/liangdas/article/details/17039583 前言: 最小距离分类是分类器里面最基本的一种分类方法,它是通过求出未知类别...
  • 【HDU 4162】Shape Number(一阶差分链码+最小表示法) Shape Number Time Limit: 24000/12000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1249 Accepted ...
  • 最小距离分类介绍

    万次阅读 2013-11-30 12:25:25
    下面我们来谈谈最小距离分类的一般步骤,说是最小距离分类器的步骤,其实是我们做监督分类基本的几个步骤。 (1) 确定类别 m ,并提取每一类所对应的已知的样本。 (2) 从样本中提取出一些可以作为区分...
  • 典型例题解析例1设向量问取何值时可由线性表示表示典型例题解析例1 设向量。问取何值时 :(1)可由线性表示,且表示惟一。(2) 可由线性表示,但表示不惟一(3)不可由线性表示。解 本题是利用方程组解的理论解决向量...
  • 线性回归最小二乘法和梯度下降

    万次阅读 2017-04-07 17:25:44
    问题描述首先我们定义问题,线性回归要解决的问题就是根据给出的数据...两列分别表示 索赔要求数量 对所有索赔的总赔付,以千瑞典克朗计 数据前五行108 392,5 19 46,2 13 15,7 124 422,2 40 119,4我们按照这个数据
  • 使用优化的算法计算nextnextnext数组:4.luogu P3375 【模板】KMP字符串匹配5.UVA1328 Period二、字符串的最小表示1.AcWing 137. 雪花雪花雪花 声明: 本系列博客是《算法竞赛进阶指南》+《算法竞赛入门经典》+...
  • 无向图求最小割集

    2021-03-07 10:25:25
    最小割集当然就权和最小的割集。可以用最小切割最大流定理:1.min=MAXINT,确定一个源点2.枚举汇点3.计算最大流,并确定当前源汇的最小割集,若比min小更新min4.转到2直到枚举完毕5.min即为所求输出min不难看出复杂度...
  • 改良梯度下降

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,285
精华内容 4,114
关键字:

最小表示法例题