【SSL_2020.10.26】圆盘

本文主要是介绍【SSL_2020.10.26】圆盘，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

圆盘

---

解题思路

这道题是一道 最小表示法 ，两两枚举圆盘并比较后就可以做到优秀的 $O(n{m}^2{\log }_{2}m+n^{2}m)$

code

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;int n,m,p;
int a[1010][1010],b[1010];
int ans,minn[1010];int zxbd(int a[],int n)
{int i=1,j=2,k=0;while(i<=n&&j<=n){k=0;while(a[i+k]==a[j+k]&&k<=n)k++;if(k==n)break;if(a[i+k]<a[j+k]){i+=k+1;if(i==j)i++;}else{j+=k+1;if(i==j)j++;}}return min(i,j);
}int main()
{cin>>n>>m>>p;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)scanf("%d",&b[j]);sort(b+1,b+1+m);for(int j=1;j<m;j++)a[i][j]=b[j+1]-b[j],a[i][j+m]=a[i][j];a[i][m]=b[1]+p-b[m],a[i][m*2]=a[i][m];minn[i]=zxbd(a[i],m*2);}for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){int ok=1;int q=minn[i];int p=minn[j];for(int k=1;k<=m;k++)if(a[i][k+q-1]!=a[j][k+p-1]){ok=0;break;}if(ok)ans++;}}cout<<ans<<endl;
}

这篇关于【SSL_2020.10.26】圆盘的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---