2 条题解
-
0
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ULL; template<typename T>void qr(T& x) { x=0;int f=1;char c=getchar(); for( ;!isdigit(c);c=getchar())if(c=='-')f=-1; for( ; isdigit(c);c=getchar())x=x*10+c-48; x=x*f; } const int N=4e5+10; const ULL B=131; ULL f1[N],f2[N],d[N],s[N]; struct point{int x, y;}P[N]; bool check(int l, int r) { ULL h1=f1[r]-f1[l-1]*d[r-l+1]; ULL h2=f2[l]-f2[r+1]*d[r-l+1]; return h1==h2; // 正反哈希值相等说明回文 } int main() { d[0]=1;for(int i=1;i<N;i++)d[i]=d[i-1]*B; int T;qr(T); while(T--) { int n;qr(n);for(int i=1;i<=n;i++)qr(P[i].x),qr(P[i].y); for(int i=1;i<=n;i++) { int a=i, b=i+1, c=i+2;b-=(b>n)*n;c-=(c>n)*n; s[i*2-1]=(P[a].x-P[b].x)*(P[a].x-P[b].x)+ (P[a].y - P[b].y)*(P[a].y - P[b].y); ULL x1,y1,x2,y2; x1=P[b].x-P[a].x; y1=P[b].y-P[a].y; x2=P[c].x-P[b].x; y2=P[c].y-P[b].y; s[i*2]=x1*y2-y1*x2; } for(int i=1; i<=n*2;i++) s[i+n*2]=s[i]; // 断环成链 f1[0]=0; for(int i=1; i<=n*4;i++) f1[i]=f1[i-1]*B+s[i]; // 正向哈希 f2[n*4+1]=0;for(int i=n*4;i>=1;i--) f2[i]=f2[i+1]*B+s[i]; // 反向哈希 int ans=0;for(int i=1; i<=n*2;i++) ans += check(i,i+n*2); // 判断回文 printf("%d\n",ans/2); // 答案除二 } return 0; } -
0
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ULL; template<typename T>void qr(T& x) { x=0;int f=1;char c=getchar(); for( ;!isdigit(c);c=getchar())if(c=='-')f=-1; for( ; isdigit(c);c=getchar())x=x*10+c-48; x=x*f; } const int N=4e5+10; const ULL B=131; ULL f1[N],f2[N],d[N],s[N]; struct point{int x, y;}P[N]; bool check(int l, int r) { ULL h1=f1[r]-f1[l-1]*d[r-l+1]; ULL h2=f2[l]-f2[r+1]*d[r-l+1]; return h1==h2; // 正反哈希值相等说明回文 } int main() { d[0]=1;for(int i=1;i<N;i++)d[i]=d[i-1]*B; int T;qr(T); while(T--) { int n;qr(n);for(int i=1;i<=n;i++)qr(P[i].x),qr(P[i].y); for(int i=1;i<=n;i++) { int a=i, b=i+1, c=i+2;b-=(b>n)*n,c-=(c>n)*n; s[i*2-1]=(P[a].x-P[ b ].x)*(P[a].x-P[ b ].x)+ (P[a].y - P[ b ].y)*(P[a].y - P[ b ].y); ULL x1,y1,x2,y2; x1=P[ b ].x-P[a].x; y1=P[ b ].y-P[a].y; x2=P[c].x-P[ b ].x; y2=P[c].y-P[ b ].y; s[i*2 ]=x1*y2-y1*x2; } for(int i=1; i<=n*2;i++) s[i+n*2]=s[i]; // 断环成链 f1[0]=0; for(int i=1; i<=n*4;i++) f1[i]=f1[i-1]*B+s[i]; // 正向哈希 f2[n*4+1]=0;for(int i=n*4;i>=1;i--) f2[i]=f2[i+1]*B+s[i]; // 反向哈希 int ans=0;for(int i=1; i<=n*2;i++) ans += check(i,i+n*2); // 判断回文 printf("%d\n",ans/2); // 答案除二 } return 0; }
- 1
信息
- ID
- 2753
- 时间
- 3500ms
- 内存
- 64MiB
- 难度
- 6
- 标签
- 递交数
- 60
- 已通过
- 20
- 上传者