头像

lsz_

$\href{https://www.acwing.com/blog/content/16850/}{{个人主页}}$




离线:8小时前


最近来访(1240)
用户头像
dp菜苟
用户头像
忘打周赛
用户头像
顾声武
用户头像
故事丶还未结束_5
用户头像
邹成功
用户头像
迎风飘扬
用户头像
种花家的兔兔
用户头像
辣鸡号航母
用户头像
ret.
用户头像
人间过客_追梦人
用户头像
AcWing2AK
用户头像
封禁用户
用户头像
huangweiliang
用户头像
海亮hutianshuo
用户头像
周赛
用户头像
一之为逸
用户头像
Snow_raw
用户头像
xunyu
用户头像
不减到170不改名
用户头像
gangan

活动打卡代码 AcWing 188. 武士风度的牛

lsz_
4天前
#include<bits/stdc++.h>
using namespace std;
int n,m,i,j,k,a[200][200],step,xx,yy;
const int dx[]={2,2,1,1,-1,-1,-2,-2},dy[]={-1,1,-2,2,-2,2,-1,1};
char c;
int main()
{
    cin>>n>>m;
    for(i=2;i<=m+1;i++)
    {
        for(j=2;j<=n+1;j++)
        {
            if(i<2||j<2||i>m+1||j>n+1)  a[i][j]=-1;
            else
            {
                cin>>c;
                if(c=='.')  a[i][j]=0x3f3f3f;
                else if(c=='*') a[i][j]=-1;
                else if(c=='H') a[i][j]=114514;
                else    a[i][j]=0;
            }
        }
    }
    while(++step)
    {
        for(i=2;i<=m+1;i++)
        {
            for(j=2;j<=n+1;j++)
            {
                if(a[i][j]>=0&&a[i][j]<step)
                {
                    for(k=0;k<8;k++)
                    {
                        xx=i+dx[k];
                        yy=j+dy[k];
                        if(a[xx][yy]>0)
                        {
                            if(a[xx][yy]==114514)
                            {
                                cout<<step;
                                return 0;
                            }
                            a[xx][yy]=min(a[xx][yy],step);
                        }
                    }
                }
            }
        }
    }
    return 0;
} 



lsz_
8天前

//感谢lsz_(臭不要脸,确信)菜鸡提出的错误

题目描述

给定一张$N\times M$的地图,地图中有$1$个男孩,$1$个女孩和$2$个鬼。

字符.表示道路,字符X表示墙,字符M表示男孩的位置,字符G表示女孩的位置,字符Z表示鬼的位置。

男孩每秒可以移动$3$个单位距离,女孩每秒可以移动$1$个单位距离,男孩和女孩只能朝上下左右四个方向移动。

每个鬼占据的区域每秒可以向四周扩张$2$个单位距离,并且无视墙的阻挡,也就是在第$k$秒后所有与鬼的曼哈顿距离不超过$2k$的位置都会被鬼占领。

注意: 每一秒鬼会先扩展,扩展完毕后男孩和女孩才可以移动。

求在不进入鬼的占领区的前提下,男孩和女孩能否会合,若能会合,求出最短会合时间。

输入格式

第一行包含整数$T$,表示共有$T$组测试用例。

每组测试用例第一行包含两个整数$N$和$M$,表示地图的尺寸。

接下来$N$行每行$M$个字符,用来描绘整张地图的状况。(注意:地图中一定有且仅有$1$个男孩,$1$个女孩和$2$个鬼)

输出格式

每个测试用例输出一个整数$S$,表示最短会合时间。

如果无法会合则输出$−1$。

每个结果占一行。

数据范围

$1<n,m<800$

输入样例:

3
5 6
XXXXXX
XZ..ZX
XXXXXX
M.G...
......
5 6
XXXXXX
XZZ..X
XXXXXX
M.....
..G...
10 10
..........
..X.......
..M.X...X.
X.........
.X..X.X.X.
.........X
..XX....X.
X....G...X
...ZX.X...
...Z..X..X

输出样例:

1
1
-1

算法$1~(BFS)~O(Tnm)$

首先先找到男孩和女孩的位置,存入不同的队列中,依次枚举每个点,每次行动先判断队列内点是否可行(不可行的接下来肯定不行),接下来再枚举枚举每个能到的点,先看是否可行(不可行的接下来肯定不行),在存入队列中,标一下点。一旦有重合点,return结果

C++ 代码

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
int n,m,test,mp[810][810];
const int bfsx[4]={1,-1,0,0},bfsy[4]={0,0,1,-1};
char a[810][810];
pii by,grl,ghst[3];
int distance(int x,int y,int xx,int yy)
{
    return abs(x-xx)+abs(y-yy);//距离
}
bool check(int x,int y,int t)
{
    if((a[x][y]=='X'||x>n||x<1||y<1||y>n)||(distance(x,y,ghst[1].first,ghst[1].second)<=2*t)||(distance(x,y,ghst[2].first,ghst[2].second)<=2*t))    return 0;//边界判断,距离判断
    return 1;
}
int bfs()
{
    int temp=0,step=0,sz,x,y,xx,yy;
    queue<pii> boy,girl;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]=='M')
            {
                by.first=i;
                by.second=j;
            }
            if(a[i][j]=='G')
            {
                grl.first=i;
                grl.second=j;
            }
            if(a[i][j]=='Z')
            {
                temp++;
                ghst[temp].first=i;
                ghst[temp].second=j;
            }
            //记录
        }
    }
    boy.push(by);
    girl.push(grl);//存队列
    while(boy.size()||girl.size())//直到没有点
    {
        step++;//次数
        for(int i=1;i<=3;i++)
        {
            sz=boy.size();
            for(int j=1;j<=sz;j++)//不要写成for(int j=1;j<=boy.size();j++),会死循环
            {
                x=boy.front().first;
                y=boy.front().second;//存储
                boy.pop();//弹出
                if(!check(x,y,step))    continue;//判断是否可行
                for(int k=0;k<4;k++)
                {
                    xx=x+bfsx[k];
                    yy=y+bfsy[k];//枚举
                    if((mp[xx][yy]==1)||(!check(xx,yy,step)))   continue;//判重,可行
                    if(mp[xx][yy]==2)   return step;//return
                    mp[xx][yy]=1;//标点
                    boy.push(make_pair(xx,yy));//存入队列内
                }
            }
        }
        sz=girl.size();
        for(int i=1;i<=sz;i++)
        {
            x=girl.front().first;
            y=girl.front().second;
            girl.pop();
            if(!check(x,y,step))    continue;
            for(int j=0;j<4;j++)
            {
                xx=x+bfsx[j];
                yy=y+bfsy[j];
                if((mp[xx][yy]==2)||(!check(xx,yy,step)))   continue;
                if(mp[xx][yy]==1)   return step;
                mp[xx][yy]=2;
                girl.push(make_pair(xx,yy));
            }
        }//同理哒
    }
    return -1;
}
int main()
{
    cin>>test;
    while(test--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)   for(int j=1;j<=m;j++)   cin>>a[i][j];
        memset(mp,0,sizeof(mp));
        cout<<bfs()<<endl;
    }//看不懂就说不过去了哦
    return 0;
}


活动打卡代码 AcWing 177. 噩梦

lsz_
8天前
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
int n,m,test,mp[810][810];
const int bfsx[4]={1,-1,0,0},bfsy[4]={0,0,1,-1};
char a[810][810];
pii by,grl,ghst[3];
int distance(int x,int y,int xx,int yy)
{
    return abs(x-xx)+abs(y-yy);
}
bool check(int x,int y,int t)
{
    if((a[x][y]=='X'||x>n||x<1||y<1||y>n)||(distance(x,y,ghst[1].first,ghst[1].second)<=2*t)||(distance(x,y,ghst[2].first,ghst[2].second)<=2*t))    return 0;
    return 1;
}
int bfs()
{
    int temp=0,step=0,sz,x,y,xx,yy;
    queue<pii> boy,girl;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]=='M')
            {
                by.first=i;
                by.second=j;
            }
            if(a[i][j]=='G')
            {
                grl.first=i;
                grl.second=j;
            }
            if(a[i][j]=='Z')
            {
                temp++;
                ghst[temp].first=i;
                ghst[temp].second=j;
            }
        }
    }
    boy.push(by);
    girl.push(grl);
    while(boy.size()||girl.size())
    {
        step++;
        for(int i=1;i<=3;i++)
        {
            sz=boy.size();
            for(int j=1;j<=sz;j++)
            {
                x=boy.front().first;
                y=boy.front().second;
                boy.pop();
                if(!check(x,y,step))    continue;
                for(int k=0;k<4;k++)
                {
                    xx=x+bfsx[k];
                    yy=y+bfsy[k];
                    if((mp[xx][yy]==1)||(!check(xx,yy,step)))   continue;
                    if(mp[xx][yy]==2)   return step;
                    mp[xx][yy]=1;
                    boy.push(make_pair(xx,yy));
                }
            }
        }
        sz=girl.size();
        for(int i=1;i<=sz;i++)
        {
            x=girl.front().first;
            y=girl.front().second;
            girl.pop();
            if(!check(x,y,step))    continue;
            for(int j=0;j<4;j++)
            {
                xx=x+bfsx[j];
                yy=y+bfsy[j];
                if((mp[xx][yy]==2)||(!check(xx,yy,step)))   continue;
                if(mp[xx][yy]==1)   return step;
                mp[xx][yy]=2;
                girl.push(make_pair(xx,yy));
            }
        }
    }
    return -1;
}
int main()
{
    cin>>test;
    while(test--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)   for(int j=1;j<=m;j++)   cin>>a[i][j];
        memset(mp,0,sizeof(mp));
        cout<<bfs()<<endl;
    }
    return 0;
}



lsz_
17天前

题目描述

农民约翰一直努力让他的草地充满鲜美多汁而又健康的牧草。

可惜天不从人愿,他在植物大战人类中败下阵来。

邪恶的乳草已经在他的农场的西北部份占领了一片立足之地。

草地像往常一样,被分割成一个高度为$Y$,宽度为$X$的直角网格。

$(1,1)$是左下角的格(也就是说坐标排布跟一般的$X,Y$坐标相同)。

乳草一开始占领了格$(M_x,M_y)$。

每个星期,乳草传播到已被乳草占领的格子四面八方的每一个没有很多石头的格(包括垂直与水平相邻的和对角线上相邻的格)内。

$1$周之后,这些新占领的格又可以把乳草传播到更多的格里面了。

达达想要在草地被乳草完全占领之前尽可能的享用所有的牧草。

她很好奇到底乳草要多久才能占领整个草地。

如果乳草在$0$时刻处于格$(M_x,M_y)$,那么几个星期以后它们可以完全占领入侵整片草地呢(对给定的数据总是会发生)?

在草地地图中,.表示草,而*表示大石。

比如这个$X=4,Y=3$的例子。

....
..*.
.**.

如果乳草一开始在左下角(第$1$排,第$1$列),那么草地的地图将会以如下态势发展:

      ....  ....  MMM.  MMMM  MMMM  
      ..*.  MM*.  MM*.  MM*M  MM*M  
      M**.  M**.  M**.  M**.  M**M  
星期数  0     1     2     3     4

乳草会在$4$星期后占领整片土地。

输入格式

第$1$行: 四个由空格隔开的整数:$X, Y, M_x, M_y$

第$2$到第$Y+1$行: 每行包含一个由$X$个字符(.表示草地* 表示大石)构成的字符串,共同描绘了草地的完整地图。

输出格式

输出一个整数,表示乳草完全占领草地所需要的星期数。

数据范围

$1\leq X,Y\leq 100$

输入样例:

4 3 1 1
....
..*.
.**.

输出样例:

4

算法1 (BFS)

这题输入有毒,直接模拟。

思路:

先把每一株被传染的草标记为“$N$”,再每一周结束后换为“$O$”(避免这周生长的还能传播),重复到所有的都感染为止

然后呢?你在期待什么?没辣!

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int x,y,i,j,milkweedx,milkweedy,ans;
bool t;
char a[110][110];
int main()
{
    cin>>x>>y>>milkweedx>>milkweedy;
    for(i=1;i<=y;i++)   for(j=1;j<=x;j++)   cin>>a[i][j];
    a[y-milkweedy+1][milkweedx]='O';
    while(t!=1)
    {
        t=1;
        for(i=1;i<=y;i++)
        {
            for(j=1;j<=x;j++)
            {
                if(a[i][j]=='O')
                {
                    if(a[i-1][j-1]=='.')    a[i-1][j-1]='N';
                    if(a[i-1][j]=='.')  a[i-1][j]='N';
                    if(a[i-1][j+1]=='.')    a[i-1][j+1]='N';
                    if(a[i][j-1]=='.')  a[i][j-1]='N';
                    if(a[i][j+1]=='.')  a[i][j+1]='N';
                    if(a[i+1][j-1]=='.')    a[i+1][j-1]='N';
                    if(a[i+1][j]=='.')  a[i+1][j]='N';
                    if(a[i+1][j+1]=='.')    a[i+1][j+1]='N';
                }
            }
        }
        ans++;
        for(i=1;i<=y;i++)
        {
            for(j=1;j<=x;j++)
            {
                if(a[i][j]=='N')    a[i][j]='O';
                if(a[i][j]=='.')    t=0;
            }
        }
    }
    cout<<ans;
    return 0;
}



lsz_
18天前

题目描述

$7$月$17$日是$Mr.W$的生日,$ACM-THU$为此要制作一个体积为$Nπ$的 $M$层生日蛋糕,每层都是一个圆柱体。

设从下往上数第$i$层蛋糕是半径为$R_i$,高度为$H_i$的圆柱。

当$M>i$时,要求$R_i>R_i+1$且$Hi>Hi+1$。

由于要在蛋糕上抹奶油,为尽可能节约经费,我们希望蛋糕外表面(最下一层的下底面除外)的面积$Q$最小。

令$Q=Sπ$,请编程对给出的$N$和 $M$,找出蛋糕的制作方案(适当的$R_i$和$H_i$的值),使 $S$最小。

除$Q$外,以上所有数据皆为正整数。

输入格式

输入包含两行,第一行为整数$N$,表示待制作的蛋糕的体积为$Nπ$。

第二行为整数$M$,表示蛋糕的层数为$M$。

输出格式

输出仅一行,是一个正整数$S$(若无解则$S=0$)。

数据范围

$1\leq N\leq 10000$
$1\leq M\leq 20$

输入样例:

100
2

输出样例:

68

算法1(DFS+剪枝)

这个蛋糕可作为参考,在讲解思路的时候可以用:
11145145.png

这题不难发现,$M$的值在很小的范围内,易联想到$DFS$。

有$DFS$就有剪枝,,这一题的剪枝如下:

1.顺序问题
不难发现,这上一层的蛋糕大小是由下一层决定的,所以要从下到上
而在同一层里,要先枚举半径再枚举高,因为半径对体积的影响比较大,还要从大到小枚举。

2.表面积剪枝
如果当前的表面积为$S$,则现在的表面积加预计最小的表面积(可以用预处理解决)的表面积不能大于目前最优解,即$S+min\sum\limits_{i-1}^1<ans$

3.体积剪枝
有表面积剪枝就有体积剪枝(bushi),先预处理前$uflr$层蛋糕的最小体积$min\sum\limits_{i=1}^{u-1}S_i$,可发现现在占有的体积加预计最小体积不能超过目前最优答案,即$min\sum\limits_{i=1}^{u-1}S_i<ans$

4.范围剪枝
易发现,第$uflr$层的半径最小是$uflr$,最大由$uflr+1$层的半径减$1$和第$uflr$层体积的最大值除第$uflr$层高度的最小值$uflr$定的,即
$u\leq R_u\leq min\lbrace R_{u+1}-1,\sqrt{\frac {n-min\sum\limits_{i=1}^{u-1}V_i-V}{u}}\rbrace$
高度也是类似,即
$u\leq H_u\leq min\lbrace H_{u+1}-1,\frac {n-min\sum\limits_{i=1}^{u-1}V_i-V}{R_u^2}\rbrace$

5.关系剪枝
第$1$层至第$uflr$层的表面积有(不考虑$π$)
$S_u=2\sum\limits_{i-1}^uR_iH_i=\frac {2}{R_{u+1}}\sum\limits_{i-1}^uR_{u+1}R_iH_i>\frac {2}{R_{u+1}}\sum\limits_{i-1}^uR_i^2H_i$
第$1$层至第$uflr$层的体积有
$n-V=\sum\limits^u_{i=1}R_i^2H_i$
得$S_{1-u}>\frac {2(n−V)}{R_{u+1}}$
得$S_总=S+S{1-u}\geq S_{ans}$,即$S+\frac {2(n−V)}{R_{u+1}}\geq S_{ans}$可剪枝

C++ 代码

#include<bits/stdc++.h>
#define INF 1e9
using namespace std;
int n,m,ans=INF,mns[50],mnv[50],r[50],h[50];
void i_want_to_kill_Mr_W(int v,int s,int uflr)
{
    if(n<v+mnv[uflr])   return ;
    if(ans<=s+mns[uflr])    return ;
    if(ans<=s+2*(n-v)/r[uflr+1])    return ;
    if(!uflr)
    {
        if(v==n)    ans=min(ans,s);
        return ;
    }
    for(int r1=min(r[uflr+1]-1,(int)sqrt((n-v-mnv[uflr-1])/uflr));r1>=uflr;r1--)
    {
        for(int h1=min(h[uflr+1]-1,(n-v-mnv[uflr-1])/r1/r1);h1>=uflr;h1--)
        {
            h[uflr]=h1;
            r[uflr]=r1;
            if(uflr==m) i_want_to_kill_Mr_W(v+r1*r1*h1,s+2*r1*h1+r1*r1,uflr-1);
            else    i_want_to_kill_Mr_W(v+r1*r1*h1,s+2*r1*h1,uflr-1);
        }
    }
    return ;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        mns[i]=mns[i-1]+2*i*i;
        mnv[i]=mnv[i-1]+i*i*i;
    }
    h[m+1]=r[m+1]=INF;
    i_want_to_kill_Mr_W(0,0,m);
    if(ans==INF)    ans=0;
    cout<<ans;
    return 0;
}


活动打卡代码 AcWing 168. 生日蛋糕

lsz_
22天前
#include<bits/stdc++.h>
#define INF 1e9
using namespace std;
int n,m,ans=INF,mns[50],mnv[50],r[50],h[50];
void i_want_to_kill_Mr_W(int v,int s,int uflr)
{
    if(n<v+mnv[uflr])   return ;
    if(ans<=s+mns[uflr])    return ;
    if(ans<=s+2*(n-v)/r[uflr+1])    return ;
    if(!uflr)
    {
        if(v==n)    ans=min(ans,s);
        return ;
    }
    for(int r1=min(r[uflr+1]-1,(int)sqrt((n-v-mnv[uflr-1])/uflr));r1>=uflr;r1--)
    {
        for(int h1=min(h[uflr+1]-1,(n-v-mnv[uflr-1])/r1/r1);h1>=uflr;h1--)
        {
            h[uflr]=h1;
            r[uflr]=r1;
            if(uflr==m) i_want_to_kill_Mr_W(v+r1*r1*h1,s+2*r1*h1+r1*r1,uflr-1);
            else    i_want_to_kill_Mr_W(v+r1*r1*h1,s+2*r1*h1,uflr-1);
        }
    }
    return ;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        mns[i]=mns[i-1]+2*i*i;
        mnv[i]=mnv[i-1]+i*i*i;
    }
    h[m+1]=r[m+1]=INF;
    i_want_to_kill_Mr_W(0,0,m);
    if(ans==INF)    ans=0;
    cout<<ans;
    return 0;
}



lsz_
22天前

草稿
未命名.png

初稿
未命名1.png

废搞
未命名2.png

最终稿
未命名3.png




lsz_
23天前



lsz_
23天前

题目描述

有一天,达达捡了一条价值连城的宝石项链,但是,一个严重的问题是,他并不知道项链的主人是谁!

在得知此事后,很多人向达达发来了很多邮件,都说项链是自己的,要求他归还(显然其中最多只有一个人说了真话)。

达达要求每个人都写了一段关于自己项链的描述: 项链上的宝石用数字$0$至$9$来标示。

一个对于项链的表示就是从项链的某个宝石开始,顺指针绕一圈,沿途记下经过的宝石,比如项链:$0−1−2−3$,它的可能的四种表示是$0123、1230、2301、3012$。

达达现在心急如焚,于是他找到了你,希望你能够编写一个程序,判断两个给定的描述是否代表同一个项链(注意,项链是不会翻转的)。

也就是说给定两个项链的表示,判断他们是否可能是一条项链。

输入格式

输入文件只有两行,每行一个由字符$0$至$9$构成的字符串,描述一个项链的表示(保证项链的长度是相等的)。

输出格式

如果两个对项链的描述不可能代表同一个项链,那么输出 No,否则的话,第一行输出一个 Yes,第二行输出该项链的字典序最小的表示。

数据范围

设项链的长度为$L,1\leq L\leq 1000000$

输入样例:

2234342423
2423223434

输出样例:

Yes
2234342423

算法1 (最小表示法) $O(n)$

前置姿势:(最小表示法)诶嘿是我写的

通过第二问,我们容易知道最终要输出最小表示法这是一个提示。判断是否相等时,也可以利用最小表示法。

所以思路就是比较两条字符串的最小表示法,判断一下,很好懂的。

时间复杂度 $O(n)$

C++ 代码

#include<bits/stdc++.h>
using namespace std;
char a[2000010],b[2000010];
int mn(char s[])
{
    int n=strlen(s+1);
    for(int i=1;i<=n;i++)   s[n+i]=s[i];
    int i=1,j=2,k;
    while(i<=n&&j<=n)
    {
        for(k=0;k<n&&s[i+k]==s[j+k];k++);
        if(k==n)    break;
        if(s[i+k]>s[j+k])
        {
            i+=k+1;
            if(i==j)    i++;
        }
        else
        {
            j+=k+1;
            if(i==j)    j++;
        }
    }
    return min(i,j);
}
int main()
{
    int x,y,lena,lenb;
    scanf("%s",a+1);
    lena=strlen(a+1);
    x=mn(a);
    scanf("%s",b+1);
    lenb=strlen(b+1);
    y=mn(b);
    a[x+lena]=b[y+lenb]=0;
    if(lena==lenb&&(!strcmp(a+x,b+y)))
    {
        cout<<"Yes"<<endl;
        puts(a+x);
    }
    else    cout<<"No"<<endl;
    return 0;
}



lsz_
23天前

前言

$\color{white}{看不见我}$这个我是讲解$LYD$大佬所在书上讲解的内容,有书者可读第$75$到$77$页(河南电子音像出版社)大佬讲的详细作者我讲的不详细,没书者可继续阅读。

基础概念

$\color{white}{看不见我}$给你一个字符串(设它为$“S[N]”$),如果我们不断把最后一个字符放在开头,最终会得到$N$个字符串,我们称这几个字符串是循环同构的。在这些字符串里,字典序最的一个,即是$S$的最小表示

$\color{white}{看不见我}$例如某一个字符串是$“fxtnb”$,则它的$5$个循环同构的字符串等于$“fxtnb”、“bfxtn”、“nbfxt”、“tnbfx”、“xtnbf”$,显然,它的最小表示是$“bfxtn”$。我们定义$B[i]$来表示从$i$开始的循环同构字符串,即$S[i\sim n]+S[1\sim i-1]$

$\color{white}{看不见我}$如何快速求出一个字符串的最小表示?事实上,可以使用$O(n)$的效率求出。我们首先复制一个字符串$S$放到字符串$S$的后面,形成字符串$SS$。显然,$B[i]=SS[i\sim i+n+1]$。

$\color{white}{看不见我}$我们观察以下的比较过程:

$S=”bacacabc”,i=2,j=4,k=3$
未命名.jpg

$\color{white}{看不见我}$如果在$i+k$和$j+k$处不相等,假设$SS[i+k]>SS[j+k]$,可得知$B[i]$不是$S$的最小表示{存在一个更小的循环同构串$B[j]$)。除此之外,我们还可得知$B[i+1],B[i+1],…,B[i+k]$也都不是$S$的最小表示。因为这是对于$1\leq p\leq k$,存在一个比$B[i+k]$更小的循环同构串$B[j+p]$(从$i+p$与$j+p$开始向后扫描,同样会发现$p=k$时不相等,并且$SS[i+k]>SS[j+k]$)。

未命名1.jpg

$\color{white}{看不见我}$这个算法通过两个指针$(i,j)$不断向后移动的形式,尝试比较每两个循环同构串的大小。利用上面的性质,可及时排除掉不同的选项。当其中一个指针移到结尾时,既考虑过所有情况(二元组$(B[i],B[j])$),即可得到了最小表示。

$\color{white}{看不见我}$最后附上$LYD$大佬的代码:

int n = strlen(s + 1);
for (int i = 1; i <= n; i++) s[n+i] = s[i];
int i = 1, j = 2, k;
while (i <= n && j <= n) {
    for (k = 0; k < n && s[i+k] == s[j+k]; k++);
    if (k == n) break;
    if (s[i+k] > s[j+k]) {
        i = i + k + 1;
        if (i == j) i++;
    } else {
        j = j + k + 1;
        if (i == j) j++;
    }
}
ans = min(i, j);