2 条题解

  • 0
    @ 2025-10-8 17:02:51
    #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
      @ 2025-10-8 17:02:42
      #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

      「POI2007 R1」对称轴 Axes of Symmetry

      信息

      ID
      2753
      时间
      3500ms
      内存
      64MiB
      难度
      6
      标签
      递交数
      60
      已通过
      20
      上传者