CVBB ACM Team

用户工具

站点工具

您在这里: front_page » 2020-2021 » teams » namespace » 牛客多校第二场
2020-2021:teams:namespace:牛客多校第二场

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版 		前一修订版
2020-2021:teams:namespace:牛客多校第二场 [2020/07/16 10:27]
great_designer [C] 		2020-2021:teams:namespace:牛客多校第二场 [2020/07/17 12:24] (当前版本)
great_designer [E]
行 5: 行 5:
 =====D===== =====D=====
  
-唯一一道水题。+唯一一道过了的水题。
  
 <​hidden>​ <​hidden>​
行 34: 行 34:
  
 =====F===== =====F=====
 +
 +以下是补题。
  
 这个题TLE掉了。原因是单调队列不熟练，还需要一个记忆化的小技巧。 这个题TLE掉了。原因是单调队列不熟练，还需要一个记忆化的小技巧。
  
-记忆化技巧代码： +记忆化技巧代码加单调队列：
- +
-<​hidden>​ +
-<code C> +
- +
-int i;  +
-for(i=1;​i<​=n;​i++) +
-{ +
- int j; +
- for(j=1;​j<​=m;​j++) +
- { +
- if(!Gcd[i][j]) +
- { +
- int k; +
- for(k=1;​k*i<​=n&&​k*j<​=m;​k++) +
- { +
- Gcd[k*i][k*j]=k;​ +
- A[k*i][k*j]=i*j*k;​ +
- } +
- } +
- } +
-} +
- +
-</​code>​ +
-</​hidden>​ +
- +
-单调队列：+
  
 <​hidden>​ <​hidden>​
行 70: 行 46:
 #​include<​stdio.h>​ #​include<​stdio.h>​
  
-int a[5010][5010],​b[5010][5010];​ +short Gcd[5010][5010];​ 
-int head,​tail,​q[50100];+short head,​tail,​q[5010];
  
-int gcd(int a,int b) +int A[5010][5010],b[5010][5010];
-{ +
- return b?​gcd(b,​a%b):​a;​ +
-} +
- +
-int lcm(int a,int b) +
-{ +
- return a*b/​gcd(a,​b); +
-}+
  
 int main() int main()
行 88: 行 56:
     scanf("​%d%d%d",&​n,&​m,&​k);​     scanf("​%d%d%d",&​n,&​m,&​k);​
     long long res=0;     long long res=0;
-    int i;+    int i; 
     for(i=1;​i<​=n;​i++)     for(i=1;​i<​=n;​i++)
     {     {
行 95: 行 63:
         for(j=1;​j<​=m;​j++)         for(j=1;​j<​=m;​j++)
         {         {
-            a[i][j]=lcm(i,j);+        if(!Gcd[i][j]) 
 + { 
 + int h; 
 + for(h=1;h*i<​=n&&​h*j<=m;h++) 
 + { 
 + Gcd[h*i][h*j]=h;​ 
 + A[h*i][h*j]=i*j*h; 
 + } 
 + }
             while(tail>​=head&&​j-q[head]>​=k)             while(tail>​=head&&​j-q[head]>​=k)
  {  {
  head++;  head++;
  }  }
-            while(tail>​=head&&​a[i][j]>a[i][q[tail]])+            while(tail>​=head&&​A[i][j]>A[i][q[tail]])
  {  {
  tail--;  tail--;
行 107: 行 83:
             if(j>=k)             if(j>=k)
  {  {
- b[i][j-k+1]=a[i][q[head]];​+ b[i][j-k+1]=A[i][q[head]];​
  }  }
         }         }
行 139: 行 115:
 </​hidden>​ </​hidden>​
  
-如果能把两者结合起来就好了。+注意，样例在5000范围，5000乘5000的gcd数组不用short的话会爆内存。
  
 =====C===== =====C=====
行 433: 行 409:
 </​hidden>​ </​hidden>​
  
-======B======+=====B=====
  
 储存斜率用了两种做法。开longlong那个TLE掉了，double那个WA了，实在无语…… 储存斜率用了两种做法。开longlong那个TLE掉了，double那个WA了，实在无语……
 +
 +WA的double已经改正了。那么错的就不留了，只留下错的longlong存斜率版本。
  
 <​hidden>​ <​hidden>​
行 446: 行 424:
 using namespace std; using namespace std;
  
-#define x first +vector<​pair<​long long,long long> > points;
-#define y second+
  
-vector<​pair<​double,double> > points;+long long gcd(long long a,long long b) 
 +{ 
 +    return (b == 0) ? a : gcd(b, a % b); 
 +}
  
 int maxPoints() int maxPoints()
行 456: 行 436:
     for (int i = 0; i < points.size();​ ++i)     for (int i = 0; i < points.size();​ ++i)
  {  {
-        map<double,int> m;+        map<pair<​int,​ int>, int> m;
         int duplicate = 1;         int duplicate = 1;
         for (int j = i + 1; j < points.size();​ ++j)         for (int j = i + 1; j < points.size();​ ++j)
  {  {
-            if (points[i].x== points[j].x&& points[i].y== points[j].y)+            if (points[i].first== points[j].first&& points[i].second== points[j].second)
  {  {
                 ++duplicate;​                 ++duplicate;​
  continue;​  continue;​
-            }  +            } 
-            ​if(points[j].x*points[i].y==points[i].x*points[j].y)+            ​long long x1=points[i].first; 
 +            long long x2=points[j].first; 
 +            long long y1=points[i].second; 
 +            long long y2=points[j].second; 
 +            if(x1*y2==y1*x2)
             {             {
             continue;             continue;
  }  }
-            ​double ​dx = points[j].x- points[i].x; +            ​long long dx =x2*(x1*x1+y1*y1)-x1*(x2*x2+y2*y2); 
-            ​double ​dy = points[j].y- points[i].y; +            ​long long dy =y2*(x1*x1+y1*y1)-y1*(x2*x2+y2*y2);​ 
-            ++m[{dx/​dy}];​+            long long d = gcd(dx, dy); 
 +            ++m[{dx / d, dy / d}];
         }         }
         res = max(res, duplicate);         res = max(res, duplicate);
-        map<double,​int>::​iterator it; +        map<pair<​int,​int>​,​int>::​iterator it; 
-        for (it = m.begin(); it != m.end(); ++it)+        for(it = m.begin(); it != m.end(); ++it)
  {  {
             res = max(res, it->​second + duplicate);             res = max(res, it->​second + duplicate);
行 487: 行 472:
  int n;  int n;
  scanf("​%d",&​n);​  scanf("​%d",&​n);​
- double ​x,y;+ long long x,y;
  while(n--)  while(n--)
  {  {
  cin >> x >> y;  cin >> x >> y;
- double temp=x*x+y*y;​ + points.push_back(make_pair(x,​y));​
- points.push_back(make_pair(x/temp,y/temp));+
  }  }
  cout << maxPoints() << endl;  cout << maxPoints() << endl;
  return 0 ;  return 0 ;
 } }
- 
  
 </​code>​ </​code>​
 </​hidden>​ </​hidden>​
 +
 +后记：这种采用了反演的写法要考虑eps——
 +
 +事实证明，没有通过就是eps的问题。唉，太悲伤了……
 +
 +以下是修改后的通关代码：
  
 <​hidden>​ <​hidden>​
 <code C++> <code C++>
  
 +#​include<​stdio.h>​
  
-#​include<​iostream>​ 
 #​include<​vector>​ #​include<​vector>​
 #​include<​map>​ #​include<​map>​
行 512: 行 501:
 using namespace std; using namespace std;
  
-vector<​pair<​long long,long long> > points;+#define eps 1e-12
  
-long long gcd(long long a,long long b)+struct compare
 { {
-    return ​(b == 0) ? a : gcd(b, a % b); + bool operator()(const double &key1,const double &key2) 
-}+ { 
 + if(key1-key2<​(-eps)||key1-key2>​eps) 
 + { 
 + return key1<​key2; 
 + } 
 + else 
 + { 
 + return 0; 
 + } 
 + } 
 +}; 
 + 
 +vector<​pair<​double,​double>​ > points;
  
 int maxPoints() int maxPoints()
 { {
-    int res = 0; +    int res=1; 
-    for (int i = 0; i < points.size();​ ++i)+    int i; 
 +    for(i=0;​i<​points.size();​++i)
  {  {
-        map<pair<int, int>, int> m; +        map<double,int,compare> m; 
-        int duplicate = 1; +        int j;  
-        for (int j = i + 1; j < points.size();​ ++j)+        for(j=i+1;​j<​points.size();​++j)
  {  {
-            if (points[i].first== ​points[j].first&& ​points[i].second== points[j].second) +            if(points[j].first*points[i].second==points[i].first*points[j].second)
- { +
-                ++duplicate;​ +
- continue;​ +
-            } +
-            long long x1=points[i].first; +
-            long long x2=points[j].first; +
-            long long y1=points[i].second; +
-            long long y2=points[j].second;​ +
-            if(x1*y2==y1*x2)+
             {             {
             continue;             continue;
  }  }
-            ​long long dx =x2*(x1*x1+y1*y1)-x1*(x2*x2+y2*y2); +            ​double ​dx=points[j].first-points[i].first; 
-            ​long long dy =y2*(x1*x1+y1*y1)-y1*(x2*x2+y2*y2);​ +            ​double ​dy=points[j].second-points[i].second; 
-            long long d = gcd(dx, dy); +            ++m[dx/dy];
-            ++m[{dx / d, dy / d}];+
         }         }
-        ​res = max(res, duplicate);​ +        map<double,​int>::​iterator it; 
-        ​map<pair<​int,​int>​,​int>::​iterator it; +        for(it=m.begin();​it!=m.end();​++it)
-        for(it = m.begin(); it != m.end(); ++it)+
  {  {
-            res = max(res, it->​second + duplicate);+            res=max(res,​it->​second+1);
         }         }
     }     }
行 560: 行 551:
  int n;  int n;
  scanf("​%d",&​n);​  scanf("​%d",&​n);​
- long long x,y;+ double ​x,y;
  while(n--)  while(n--)
  {  {
- cin >> ​x >> ​y; + scanf("​%lf%lf",&​x,&y); 
- points.push_back(make_pair(x,​y));​+ double temp=x*x+y*y; 
 + points.push_back(make_pair(x/temp,y/temp));
  }  }
- cout << ​maxPoints() ​<< endl; + printf("​%d\n",​maxPoints()); 
- return 0 ;+ return 0;
 } }
  
行 573: 行 565:
 </​hidden>​ </​hidden>​
  
-后记：这种采用了反演的写法要考虑eps——+我们需要学习**在map中引入自定义运算符**，从而实现map中的eps控制。
  
-事实证明，没有通过就是eps的问题。唉，太悲伤了+=====K=====
  
 +我一开始想手算积分，结果发现这个多元积分上下限有绝对值判定，换句话说积不出来。那么就只能使用积分算法了。
  
 +<​hidden>​
 +<code C>
 +
 +#​include<​stdio.h>​
 +#​include<​math.h>​
 +
 +const double pi=acos(-1.0);​
 +
 +double r1,r2,r3;
 +
 +double sqr(double x)
 +{
 + return x*x;
 +}
 +
 +double f(double j)
 +{
 + double EG=sqrt(sqr(r1)+sqr(r2)-2*cos(j)*r1*r2);​
 + double AGE=acos((sqr(r1)+sqr(EG)-sqr(r2))/​2/​r1/​EG);​
 + double alp=asin(r1*sin(AGE)/​r3);​
 + return r3*(alp*sin(alp)+cos(alp))*EG/​pi;​
 +}
 +
 +double swap(double *p1,double *p2)
 +{
 + double temp;
 + temp=(*p1);​
 + (*p1)=(*p2);​
 + (*p2)=temp;​
 +}
 +
 +int main()
 +{
 + int t;
 + scanf("​%d",&​t);​
 + while(t--)
 + {
 + scanf("​%lf%lf%lf",&​r1,&​r2,&​r3);​
 + if(r1>​r2)
 + {
 + swap(&​r1,&​r2);​
 + }
 + if(r2>​r3)
 + {
 + swap(&​r2,&​r3);​
 + }
 + if(r1>​r2)
 + {
 + swap(&​r1,&​r2);​
 + }
 + double res=0,​j=pi/​10000.0;​
 + int i;
 + for(i=0;​i<​5000;​i++,​j+=pi/​5000.0)
 + {
 + res+=f(j);​
 + }
 + printf("​%.1lf\n",​res/​5000);​
 + }
 +    return 0;
 +}
 +
 +</​code>​
 +</​hidden>​
 +
 +积分算法原来也不难，模拟就好了。反正要求精度不高……
 +
 +=====E=====
 +
 +集合中可重复取数，求异或的最大值，集合大小很大。
 +
 +有一个与FFT、NTT非常相似的东西叫FWT，比前两者简单，用于解决数组异或（不进位加法）卷积的问题。
 +
 +FWT和它的逆，将数组异或（不进位加法）的卷积变为了乘法。
 +
 +<​hidden>​
 +<code C>
 +
 +#​include<​stdio.h>​
 +
 +int n,​nans[1<<​18],​one[1<<​18],​ans[200005];​
 + 
 +void FWT(int *src,int t)
 +{
 + int sz; 
 +    for(sz = 2;sz <= 1<<​18;​sz<<​=1)
 + {
 +        int step = sz >> 1;
 +        int i;
 +        for(i = 0;i< 1<<​18;​i+=sz)
 + {
 + int j;
 +            for(j = i;j < i+step;j++)
 + {
 +                int a = src[j];
 + int b = src[j+step];​
 +                src[j] = a+b;
 +                src[j+step] = a-b;
 +                if(t==-1)
 +                {
 +                src[j]>>​=1;​
 +                src[j+step]>>​=1;​
 + }
 +            }
 +        }
 +    }
 +}
 +
 +int main()
 +{
 +    scanf("​%d",&​n);​
 +    int x;
 +    int i;
 +    for(i = 1;i<= n;i++)
 + {
 +        scanf("​%d",&​x);​
 +        one[x]=1;
 +        nans[x]=1;
 +        if (x > ans[1])
 + {
 + ans[1] = x;
 + }
 +    }
 +    FWT(one,1);
 +    for(i = 2;i<= 20;i++)
 + {
 +        FWT(nans,​1);​
 +        int j;
 +        for(j = 0;j < 1<<​18;​j++)
 +        {
 +        nans[j] = nans[j]*one[j];​
 + }
 +        FWT(nans,​-1);​
 +        for(j = 0;j < 1<<​18;​j++)
 +        {
 +        if (nans[j])
 +        {
 +        nans[j] = 1;
 + }
 + }
 +        for(j=(1<<​18)-1;​j>​=0;​j--)
 +        {
 +        if (nans[j])
 + {
 +                ans[i] = j;
 +                break;
 +            }
 + }
 +    }
 +    for(i = 21;i<= n;i++)
 +    {
 +    ans[i] = ans[i-2];
 + }
 +    for(i = 1;i<= n;i++)
 +    {
 +    printf("​%d ",​ans[i]);​
 + }
 +}
 +
 +</​code>​
 +</​hidden>​
 +
 +=====J=====
 +
 +对给定置换A开k次方，k是个大素数。
 +
 +由群论知，对大素数k，k次方运算是一一映射，所以实质是个求数论倒数的运算。
 +
 +由于模不是素数，用费马欧拉定理不方便，只能改用一次不定方程的扩展来求逆。
 +
 +<​hidden>​
 +<code C++>
 +
 +#​include<​stdio.h>​
 +
 +#​include<​vector>​
 +
 +using namespace std;
 +
 +long long extgcd(long long a,long long b,long long& u,long long& v)
 +{
 +    long long d;
 +    if(b==0)
 + {
 +        d = a;
 +        u=1,v=0;
 +    }
 + else
 + {
 +        d = extgcd(b,​a%b,​v,​u);​
 +        v -= a/b*u;
 +    }
 + return d;
 +}
 +
 +int n,​k,​vis[100005];​
 +int P[100005],​ans[100005],​a[100005],​tmp[100005],​ttt[100005];​
 +
 +int main()
 +{
 +    scanf("​%d%d",&​n,&​k);​
 +    int i;
 +    for(i=1;​i<​=n;​i++)
 + {
 + scanf("​%d",&​a[i]);​
 + }
 +    for(i=1;​i<​=n;​i++)
 +    {
 +     if(!vis[i])
 + {
 +         vis[i] = 1;
 +         vector<​int>​ pos;
 +         int u = a[i],len = 1;​pos.push_back(i);​
 +         while(u!=i)
 + {
 +             len++;
 +             vis[u] = 1;​pos.push_back(u);​
 +             u = a[u];
 +         }
 +         long long x,y;
 +         extgcd(k,​len,​x,​y);​
 +         x = (x%len+len)%len;​
 +         int j;
 +         for(j=1;​j<​=len;​j++)
 + {
 +             ans[pos[j-1]] = pos[(j-1+x)%len];​
 +         }
 +     }
 + }
 +    for(i=1;​i<​=n;​i++)
 + {
 + printf("​%d ",​ans[i]);​
 + }
 +    return 0;
 +}
 +
 +</​code>​
 +</​hidden>​
  
2020-2021/teams/namespace/牛客多校第二场.1594866464.txt.gz · 最后更改: 2020/07/16 10:27 由 great_designer

页面工具

除额外注明的地方外，本维基上的内容按下列许可协议发布： CC Attribution-Share Alike 4.0 International
CC Attribution-Share Alike 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki
京ICP备20018844号-3