CVBB ACM Team

用户工具

站点工具

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

差别

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

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版 		前一修订版
2020-2021:teams:namespace:牛客多校第二场 [2020/07/16 10:58]
great_designer [B] 		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了，实在无语……
  
-<​hidden>​ +WA的double已经改正了。那么错的就不留了，只留下错的longlong存斜率版本。
-<code C++> +
- +
-#​include<​iostream>​ +
-#​include<​vector>​ +
-#​include<​map>​ +
- +
-using namespace std; +
- +
-#define x first +
-#define y second +
- +
-vector<​pair<​double,double> > points; +
- +
-int maxPoints() +
-{ +
-    int res = 0; +
-    for (int i = 0; i < points.size();​ ++i) +
- { +
-        map<​double,​int>​ m; +
-        int duplicate = 1; +
-        for (int j = i + 1; j < points.size();​ ++j) +
- { +
-            if (points[i].x== points[j].x&&​ points[i].y== points[j].y) +
- { +
-                ++duplicate;​ +
- continue;​ +
-            }  +
-            if(points[j].x*points[i].y==points[i].x*points[j].y) +
-            { +
-            continue;​ +
- } +
-            double dx = points[j].x- points[i].x;​ +
-            double dy = points[j].y- points[i].y;​ +
-            ++m[{dx/​dy}];​ +
-        } +
-        res = max(res, duplicate);​ +
-        map<​double,​int>::​iterator it; +
-        for (it = m.begin(); it != m.end(); ++it) +
- { +
-            res = max(res, it->​second + duplicate);​ +
-        } +
-    } +
-    return res; +
-} +
- +
-int main() +
-{ +
- int n; +
- scanf("​%d",&​n);​ +
- double x,y; +
- while(n--) +
- { +
- cin >> x >> y; +
- double temp=x*x+y*y;​ +
- points.push_back(make_pair(x/​temp,​y/​temp));​ +
- } +
- cout << maxPoints() << endl; +
- return 0 ; +
-} +
- +
- +
-</​code>​ +
-</​hidden>​+
  
 <​hidden>​ <​hidden>​
 <code C++> <code C++>
- 
  
 #​include<​iostream>​ #​include<​iostream>​
行 650: 行 562:
 } }
  
 +</​code>​
 +</​hidden>​
 +
 +我们需要学习**在map中引入自定义运算符**，从而实现map中的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>​ </​code>​
 </​hidden>​ </​hidden>​
  
-我们需要学习在map中引入自定义运算符，从而实现map中的eps控制。+积分算法原来也不难，模拟就好了。反正要求精度不高……
  
 +=====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/牛客多校第二场.1594868331.txt.gz · 最后更改: 2020/07/16 10:58 由 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