题解：P2250 二面体群

qianyuzhe · 2025-02-19 23:12:06 · 题解

二面体群怎么能没有群论的题解，我来发一篇。

二面体群 D_n，由 2n 个元素构成，是保持平面上正 n(n\ge3) 边形不变的线性变换所成的群。它的凯莱图长这样：

我们设 1 操作为沿着红边移动 1 步，2 操作为沿着蓝边移动 1 步，于是最终状态就可以表示为 k=f^Fr^Y，于是原问题等价于求 D_n 凯莱图上 e 到某一结点的最短路。

直接求最短路肯定是不行的，有什么办法优化吗？

注意到大部分结点其实没必要存储，我们实际上只需存储 4 个结点 e,k,f,fk 和 8 条边 e\rightarrow k,k\rightarrow e,f\rightarrow fk,fk\rightarrow f,e\rightarrow f,k\rightarrow fk,f\rightarrow e,fk\rightarrow k。

然后跑一遍单源最短路即可，代码（这里我用了全源最短路，反正时间差不多）：

#include<bits/stdc++.h> 
using namespace std;
int n,d,r,f,i,j,k;
pair<int,string>w[4][4];//0:e,1:k,2:f,3:fk
char c;
int main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    cin>>n;
    while(cin>>c>>d){//不定项输入 
        if(c=='r')r=((r+(f?-d:d))%n+n)%n;//求R
        else if(d&1)f=!f;//求F
    }
    for(i=0;i<4;i++)for(j=0;j<4;j++)if(i!=j)w[i][j]=make_pair(1e9,"");//初始化 
    w[0][1]=w[3][2]=make_pair(r,r?("r"+to_string(r)+" "):"");//e->k,fk->f 
    w[1][0]=w[2][3]=make_pair(n-r,"r"+to_string(n-r)+" ");//k->e,f->fk
    w[0][2]=w[1][3]=w[2][0]=w[3][1]=make_pair(1,"m1 ");//e->f,k->fk,f->e,fk->k
    for(k=0;k<4;k++)for(i=0;i<4;i++)for(j=0;j<4;j++)if(w[i][j].first>w[i][k].first+w[k][j].first)w[i][j]=make_pair(w[i][k].first+w[k][j].first,w[i][k].second+w[k][j].second);//floyd求最短路 
    cout<<w[0][f?3:1].second;//k在内环则为0->3的最短路,在外环则为0->1的最短路 
}

或者你可以枚举所有路径，代码（其实和其它题解的代码差不多）：

#include<bits/stdc++.h> 
using namespace std;
int n,d,r,f=1;
char c;
int main(){
    cin.tie(0)->ios::sync_with_stdio(false);
    cin>>n;
    while(cin>>c>>d){
        if(c=='r')r=((r+d*f)%n+n)%n;
        else if(d&1)f=-f;
    }
    if(!r)return cout<<(f<0?"m1":""),0;//k=e或k=f 
    if(f==1){//k在外环上 
        if(r<n-r+2)cout<<'r'<<r;
        else cout<<"m1 r"<<n-r<<" m1";
    }else{//k在内环上 
        if(r<n-r)cout<<'r'<<r<<" m1";
        else cout<<"m1 r"<<n-r;
    }
}