10-22 训练 T2 plate

10-22 训练 T2 plate

传送门

题目大意

有N个圆盘，每个圆盘的圆周上均匀分布了P个点（可连成正P边形），编号\(P_1\)到 \(P_n\)。这P个点 中有M个关键点，所有关键点都是相同的。给出每个圆盘关键点位置的数据（对应的 \(P_i\)），现在 可以随意转动圆盘，问有多少对圆盘最终可以变成相同的形态。

思路

我们想要对两个序列进行比较，由于编号不一样，很明显想到比较间距。但是间距数列的首项不固定，如果在所有数列的循环同构（把数列首尾接成环，所有的展开而成数列都是循环同构）中暴力比较，复杂度为 \(O(n^2)\) ，不太 \(OK\) 。这时就出现了一个神奇的算法：最小表示。

通过最小表示将序列按间距的字典序最小的方式排列，然后 \(O(n)\) 就可以比较了。

于是重点变成了如何以 \(O(n)\) 处理最小表示。

最小表示法

将数列 \(A\) 复制一份塞在其后来模拟环结构。

定义两个指针 \(i\)，\(j\) （初始为 \(1\) 和 \(2\)）记录两个长度为 \(m\) 的数列的开头，定义 \(k\) 为正在比较的位置距列首的距离。遍历 \(k\)，当比较发现 \(A_{i+k}\) 和 \(A_{j+k}\) 有差别时（这里不妨设是\(A_{i+k}< A_{j+k}\) ），说明\(A_{j},A_{j+1},A_{j+2},\dots,A_{j+k}\) 都不会是最小表示，那么我们将 \(j\) 跳到 \(j+k+1\) ，并且如果 \(j=i\) 时，我们将 \(j\) 再加一以保证比较的是两个不一样的排列。

如过 \(k\) 遍历到了 \(m\)，说明两个排列完全相等，由于我们保证了不对比两个一样的排列，说明这时数列中的元素全部是一样的。这时跳出函数以任意点做起点就行了。

如果 \(i\) 或 \(j\) 有一个超过了 \(m\) 那么所有的排列都被比较完了，那么仍在 \(m\) 范围内的那个指针就作为数列的起点。

Code

#include<cstdio>
#include<algorithm>
using namespace std;

int n,m,p,ans;
int a[501][1001],dis[501][1001];
int st[501],num[501],fa[501];

int findd(int x){
    if(x!=fa[x]) return fa[x]=findd(fa[x]);
    else return fa[x];
}

void add(int x,int y){
    int anx=findd(x),any=findd(y);
    if(anx==any) return ;
    ans+=num[x];
    num[x]+=num[y];
    num[y]=0;
    fa[any]=anx; 
}


int main()
{
    scanf("%d %d %d",&n,&m,&p);
    for(int i=1;i<=n;i++){
        fa[i]=i;
        num[i]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
        }
        sort(a[i]+1,a[i]+1+m);
        for(int j=2;j<=m;j++){
            dis[i][j-1]=a[i][j]-a[i][j-1];
        }
        dis[i][m]=a[i][1]-a[i][m]+p; 
        for(int j=1;j<=m;j++){
            dis[i][m+j]=dis[i][j];
        }
        int x=1,y=2,k=0;
        while(x<=m && y<=m){
            while(k<m && dis[i][x+k]==dis[i][y+k]) k++;
            if(k==m) break;
            if(dis[i][x+k] > dis[i][y+k]){
                x=x+k+1;
                k=0;
                if(x==y) x++;
            }
            else{
                y=y+k+1;
                k=0;
                if(x==y) y++;
            }
        }
        st[i]=min(x,y);
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            int flag=1;
            for(int l=0;l<m;l++){
                if(dis[i][st[i]+l] != dis[j][st[j]+l]){
                    flag=0;
                    break;
                }
            }
            if(flag){
                add(i,j);
            }
        }
    }
    printf("%d",ans);
    return 0;
}

最后统计答案做法很多，读者可以考虑别的做法。

\(\beta y\quad\_thorn\)

10-22 训练 T2 plate

原文：https://www.cnblogs.com/thornblog/p/11723694.html