[校内训练20_01_22]ABC

并查集(一)

1.给出序列A,求序列B,使得bi|ai,lcm(b1,b2,…,bn)=lcm(a1,a2,…,an)且字典序最小。

可以发现,对于某个质数p,它有一个最大的次数k将pk放在尽可能靠后且能够整除原数组中的数字的位置上,便是答案。

虽然数字的值域达到1E18,但我们只需要知道每个数1~1E6之间的质因子是什么以及是哪些,剩下来的一定是大于1E6的质因子且最多只有两个。

由于答案中的质数及其次数彼此间相互独立,1E6以下的质因子可以直接统计,而剩下的可以通过两两间求gcd的方法进行比较。在这种情况下,数字ABA在原数组的前面,B在后面)由于质数次数最多为2,令x=gcd(A,B)B除以x后(对于某个质因子)要么次数为0,要么为1,要么为22要特判一下,如果有这种情况,B要更新当且仅当A==B),乘上gcd(x,B除以x)后即可进行更新。复杂度为O(n2*logMAX+MAX0.333)

当然,若不嫌麻烦的话可套用pollard-rho模板。复杂度为O(n*MAX0.25)

博主在考场上采用了后者。

 

[校内训练20_01_22]ABC

 1 #include <cstdio>
 2 #include <sstream>
 3 #include <iostream>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 typedef long long LL;
 9 
10 const int MAXN = 105;
11 
12 LL num[MAXN];
13 LL common[MAXN];
14 int n, cs;
15 
16 LL gcd(LL a, LL b)
17 {
18     LL tmp;
19     while (b) tmp = a, a = b, b = tmp % b;
20     return a;
21 }
22 
23 void solve()
24 {
25     for (int i = 0; i < n; i++){
26         cs = 0;
27         for (int j = 0; j < n; j++)
28             if (i != j)
29                 common[cs ++] = gcd(num[i], num[j]);
30         LL s = 1;
31         for (int j = 0; j < cs; j++){
32             s *= common[j];
33             for (int k = j+1; k < cs; k++)
34                 common[k] /= gcd(common[j], common[k]);
35          }
36          num[i] /= s;
37          while (true){
38             LL x = gcd(num[i], s);
39             if (x == 1)
40                 break;
41             num[i] *= x;
42             s /= x;
43         }
44     }
45 }
46 
47 int main()
48 {
49     freopen("transform.in", "r", stdin);
50     freopen("transform.out", "w", stdout);
51     scanf("%d", &n);
52     for (int i = 0; i < n; i ++)
53         scanf("%lld", &num[i]);
54     solve();
55     for (int i = 0; i < n; i ++)
56         printf("%lld ", num[i]);
57     printf("\n");
58     return 0;
59 }

View Code

 

 

[校内训练20_01_22]ABC

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long int ll;
  4 typedef long double ld;
  5 ll n,a[105],ans[105];
  6 map<ll,ll>cnt,where;
  7 namespace math
  8 {
  9     const int len=10;
 10     ll test[len]={2,3,5,7,11,13,17,19,23,29};
 11     ll size,wait[555];
 12     inline ll mul(ll x,ll y,ll mod)
 13     {
 14         ll d=(ld)x*y/mod;
 15         return ((x*y-d*mod)%mod+mod)%mod;
 16     }
 17     inline ll QPOW(ll x,ll y)
 18     {
 19         ll ans=1;
 20         for(int i=1;i<=y;++i)
 21             ans=ans*x;
 22         return ans;
 23     }
 24     inline ll qpow(ll x,ll y,ll mod)
 25     {
 26         ll ans=1,base=x;
 27         while(y)
 28         {
 29             if(y&1)
 30                 ans=mul(ans,base,mod);
 31             base=mul(base,base,mod);
 32             y>>=1;
 33         }
 34         return ans;
 35     }
 36     inline bool isPrime(ll p)
 37     {
 38         for(int i=0;i<len;++i)
 39         {
 40             if(p<test[i])
 41                 return false;
 42             else if(p==test[i])
 43                 return true;
 44             ll x=qpow(test[i],p-1,p),d=p-1;
 45             if(x!=1)
 46                 return false;
 47             while(x==1&&d%2==0)
 48             {
 49                 d>>=1;
 50                 x=qpow(test[i],d,p);
 51                 if(x!=1&&x!=p-1)
 52                     return false;
 53             }
 54         }
 55         return true;
 56     }
 57     ll gcd(ll x,ll y)
 58     {
 59         if(y==0)
 60             return x;
 61         return x%y==0?y:gcd(y,x%y);
 62     }
 63     inline ll f(ll x,int c,ll mod)
 64     {
 65         return (mul(x,x,mod)+c)%mod;
 66     }
 67     inline ll find(ll n,int step,int c)
 68     {
 69         if(n%2==0)
 70             return 2;
 71         ll x=2,y=2,d=1;
 72         while(true)
 73         {
 74             ll tmpX=x,tmpY=y,d=1;
 75             for(int i=1;i<=step;++i)
 76             {
 77                 x=f(x,c,n);
 78                 y=f(f(y,c,n),c,n);
 79                 d=mul(d,(x%n-y%n+n)%n,n);
 80             }
 81             d=gcd(d,n);
 82             if(d==1)
 83                 continue;
 84             else if(d!=n)
 85                 return d;
 86             x=tmpX,y=tmpY;
 87             for(int i=1;i<=step;++i)
 88             {
 89                 x=f(x,c,n);
 90                 y=f(f(y,c,n),c,n);
 91                 d=gcd(n,(x%n-y%n+n)%n);
 92                 if(d!=1&&d!=n)
 93                     return d;
 94             }
 95             return 0;
 96         }
 97         return -1;
 98     }
 99     void factor(ll x)
100     {
101         if(isPrime(x))
102         {
103             wait[++size]=x;
104             return;
105         }
106         ll step=pow(x,0.1)+1,c=0,now=0;
107         while(!now)
108             now=find(x,step,++c);
109         factor(now),factor(x/now);
110     }
111     void pollard(ll x,int num)
112     {
113         size=0;
114         factor(x);
115         map<ll,ll>G;
116 //        for(int i=1;i<=size;++i)
117 //            cout<<wait[i]<<" ";
118 //        cout<<endl;
119         for(int i=1;i<=size;++i)
120             ++G[wait[i]];
121         for(int i=1;i<=size;++i)
122         {
123             x=wait[i];
124             if(G[x]>=cnt[x])
125             {
126                 ans[where[x]]/=QPOW(x,cnt[x]);
127                 cnt[x]=G[x];
128                 where[x]=num;
129                 ans[num]*=QPOW(x,cnt[x]);
130             }
131         }
132     }
133 }
134 inline bool check(int x)
135 {
136     if(x==1)
137         return false;
138     for(int i=2;i*i<=x;++i)
139         if(x%i==0)
140             return false;
141     return true;
142 }
143 int main()
144 {
145     freopen("transform.in","r",stdin);
146     freopen("transform.out","w",stdout);
147     ios::sync_with_stdio(false);
148     cin>>n;
149     for(int i=1;i<=n;++i)
150     {
151         cin>>a[i];
152         ans[i]=1;
153         math::pollard(a[i],i);
154     }
155     for(int i=1;i<=n;++i)
156         cout<<ans[i]<<" ";
157     cout<<endl;
158     return 0;
159 }

View Code

 

2.有一些机场和航线,航线是形如点A到点B的直线,飞机会准时从t1出发t2到达,期间匀速直线运动。机场和飞机都配备雷达,雷达有固定范围R,你需要保证在任意时间内,任意在飞行中的飞机能够通过雷达直接或间接地与机场相连,求最小的R。

  我们先二分半径r,考虑怎么进行检验。可以发现,不管是飞机关于机场、飞机关于飞机,它们能相互建立连接的可行时间点组成了一个区间,因此一个想法为求出这个区间,对于特定的端点建图进行检查。

对于飞机关于机场的情况是简单的。根据普通的平面向量知识,可以轻松地求出这个向量(飞机的飞行路线)与圆(圆心机场,半径为r)的两个交点(如果存在的话)。再次利用数量积的知识,可以知道这两个点到出发点的距离,与整个路线长度的比值(当然,这是有方向的)。求完后分别取minmax保证时间确实在航班时间范围内即可(比如说起点在圆里面的情况)。

数据分析需要知道的一些概念

飞机关于飞机比较麻烦。首先,我们先使得航线A和航线B的速度相等,这样方便下面求解。具体地讲,A向量的模除以时间A的值,要等于B向量的模除以时间的值。然后以飞机A为参考系,飞机B的航线路线就变为B-A。剩下的操作与“飞机关于机场”的完全一致,只不过要保证时间要在两个航班时间范围内。

还有一点要注意的是,向量可能经过圆心,这需要判断。

总共有O((n+m)2)个区间,单次建边、检查的复杂度是O((n+m)2)的,因此总复杂度为O((n+m)4logn)

 

[校内训练20_01_22]ABC

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long double ld;
  4 const ld eps=1E-9;
  5 const ld inf=1E12;
  6 int n,m;
  7 int A[555],B[555];
  8 ld from[555],to[555],length[555];
  9 struct pt
 10 {
 11     ld x,y;
 12     pt(ld a=0,ld b=0):x(a),y(b){}
 13     pt operator+(const pt&A){return pt(x+A.x,y+A.y);}
 14     pt operator-(const pt&A){return pt(x-A.x,y-A.y);}
 15     pt operator*(const ld&d){return pt(x*d,y*d);}
 16     pt operator/(const ld&d){return pt(x/d,y/d);}
 17     ld operator*(const pt&A){return x*A.y-y*A.x;}
 18     ld operator&(const pt&A){return x*A.x+y*A.y;}
 19     void out()
 20     {
 21         cout<<"("<<x<<","<<y<<")";
 22     }
 23 }p[555];
 24 struct line
 25 {
 26     pt A,B;
 27     line(pt a=pt(),pt b=pt()):A(a),B(b){}
 28 };
 29 struct info
 30 {
 31     ld L,R;
 32     int x,y;
 33     info(ld a=0,ld b=0,int c=0,int d=0):L(a),R(b),x(c),y(d){}
 34 }tmp[555555];
 35 inline ld s(ld x){return x*x;}
 36 inline pt intersection(line a,line b)
 37 {
 38     pt A=b.B-b.A,B=a.B-a.A,C=b.A-a.A;
 39     if(abs(A*B)<=eps)
 40         return pt(inf,inf);
 41     ld d=-(B*C)/(B*A);
 42     return b.A+A*d;
 43 }
 44 inline pt T(pt A)
 45 {
 46     return pt(-A.y,A.x);
 47 }
 48 inline pt perpendicular(pt A,line a)
 49 {
 50     if(abs((A-a.A)*(A-a.B))<=eps)
 51         return A;
 52     pt B=A+T(a.B-a.A);
 53     return intersection(line(A,B),a);
 54 }
 55 inline ld dis(pt A,pt B)
 56 {
 57     return sqrt(s(A.x-B.x)+s(A.y-B.y));
 58 }
 59 namespace graph
 60 {
 61     int size,head[555555];
 62     bool vis[55555];
 63     struct edge
 64     {
 65         int to,next;
 66     }E[555555];
 67     inline void clear()
 68     {
 69         for(int i=1;i<=n+m;++i)
 70             head[i]=0;
 71         for(int i=1;i<=size;++i)
 72             E[i].to=E[i].next=0;
 73         size=0;
 74     }
 75     inline void add(int u,int v)
 76     {
 77         E[++size].to=v;
 78         E[size].next=head[u];
 79         head[u]=size;
 80     }
 81     inline bool ok(ld x)
 82     {
 83         for(int i=1;i<=n+m;++i)
 84             vis[i]=0;
 85         queue<int>Q;
 86         for(int i=1;i<=n;++i)
 87         {
 88             Q.push(i);
 89             vis[i]=1;
 90         }
 91         while(!Q.empty())
 92         {
 93             int u=Q.front();
 94             Q.pop();
 95             for(int i=head[u];i;i=E[i].next)
 96             {
 97                 int v=E[i].to;
 98                 if(vis[v])
 99                     continue;
100                 Q.push(v);
101                 vis[v]=1;
102             }
103         }
104         for(int i=n+1;i<=n+m;++i)
105             if((!vis[i])&&(from[i-n]-eps<=x&&x<=to[i-n]+eps))
106                 return false;
107         return true;
108     }
109 }
110 int tot;
111 inline bool test(ld x)
112 {
113     graph::clear();
114     for(int i=1;i<=tot;++i)
115         if(tmp[i].L-eps<=x&&x<=tmp[i].R+eps)
116         {
117             graph::add(tmp[i].x,tmp[i].y);
118             graph::add(tmp[i].y,tmp[i].x);
119         }
120     return graph::ok(x);
121 }
122 inline bool check(ld r)
123 {
124     tot=0;
125     for(int i=1;i<=n;++i)
126     {
127         pt O=p[i];
128         for(int j=1;j<=m;++j)
129         {
130             line a(p[A[j]],p[B[j]]);
131             pt P=perpendicular(O,a),D,pA,pB;
132             ld d=s(P.x-O.x)+s(P.y-O.y);
133             if(d>r*r-eps)
134                 continue;
135             else if(abs(d)<=eps)
136                 D=(a.B-a.A)*r/dis(a.A,a.B);
137             else
138                 D=T((P-O)*sqrt(r*r/d-1));
139             pA=P+D,pB=P-D;
140             ld t1=((pA-p[A[j]])&(p[B[j]]-p[A[j]]))/length[j]/length[j]*(to[j]-from[j])+from[j];
141             ld t2=((pB-p[A[j]])&(p[B[j]]-p[A[j]]))/length[j]/length[j]*(to[j]-from[j])+from[j];
142             if(t1>t2)
143                 swap(t1,t2);
144             t1=max(from[j],t1);
145             t2=min(to[j],t2);
146             if(t2-t1>=eps)
147                 tmp[++tot]=info(t1,t2,i,n+j);
148         }
149     }
150     for(int i=1;i<=m;++i)
151         for(int j=1;j<=m;++j)
152         {
153             if(from[i]<=from[j])
154                 continue;
155             ld delT=from[i]-from[j];
156             ld g=(ld)(to[i]-from[i])/(ld)(to[j]-from[j]-delT);
157             pt I=p[A[i]]-p[B[i]];
158             pt J=(p[B[j]]-p[A[j]])*delT/(to[j]-from[j]);
159             line a(p[A[j]]+J,p[A[j]]+J+I+(p[B[j]]-(p[A[j]]+J))*g);
160             pt O=p[A[i]];
161             pt P=perpendicular(O,a),D,pA,pB;
162             ld d=s(P.x-O.x)+s(P.y-O.y);
163             if(d>r*r-eps)
164                 continue;
165             else if(abs(d)<=eps)
166                 D=(a.B-a.A)*r/dis(a.A,a.B);
167             else
168                 D=T((P-O)*sqrt(r*r/d-1));
169             pA=P+D,pB=P-D;
170             ld len=dis(a.A,a.B);
171             ld t1=((pA-a.A)&(a.B-a.A))/len/len*(to[i]-from[i])+from[i];
172             ld t2=((pB-a.A)&(a.B-a.A))/len/len*(to[i]-from[i])+from[i];
173             if(t1>t2)
174                 swap(t1,t2);
175             t1=max(max(from[i],from[j]),t1);
176             t2=min(min(to[i],to[j]),t2);
177             if(t2-t1>=eps)
178                 tmp[++tot]=info(t1,t2,n+i,n+j);
179         }
180     for(int i=1;i<=tot;++i)
181     {
182         if((!test(tmp[i].L-2*eps))||(!test(tmp[i].R-2*eps)))
183             return false;
184         if((!test(tmp[i].L+2*eps))||(!test(tmp[i].R+2*eps)))
185             return false;
186     }
187     return true;
188 }
189 int main()
190 {
191     freopen("airline.in","r",stdin);
192     freopen("airline.out","w",stdout);
193     ios::sync_with_stdio(false);
194     cin>>n>>m;
195     for(int i=1;i<=n;++i)
196         cin>>p[i].x>>p[i].y;
197     for(int i=1;i<=m;++i)
198     {
199         cin>>A[i]>>B[i]>>from[i]>>to[i];
200         ++A[i],++B[i];
201     }
202     for(int i=1;i<=m;++i)
203         length[i]=dis(p[A[i]],p[B[i]]);
204     ld L=0,R=0,mid;
205     for(int i=1;i<=n;++i)
206         for(int j=i+1;j<=n;++j)
207             R=max(R,dis(p[i],p[j]));
208     R*=2;
209     while(abs(R-L)>0.000001)
210     {
211         mid=(L+R)/2;
212         if(check(mid))
213             R=mid;
214         else
215             L=mid;
216     }
217     cout<<fixed<<setprecision(4)<<mid<<endl;
218     return 0;
219 }

View Code

 

 

 

 

我们先

二分半径r,考虑怎么进行检验。可以发现,不管是飞机关于机场、飞机关于飞机,它们能相互建立连接的可行时间点组成了一个区间,因此一个想法为求出这个区间,对于特定的端点建图进行检查。

对于飞机关于机场的情况是简单的。根据普通的平面向量知识,可以轻松地求出这个向量(飞机的飞行路线)与圆(圆心机场,半径为r)的两个交点(如果存在的话)。再次利用数量积的知识,可以知道这两个点到出发点的距离,与整个路线长度的比值(当然,这是有方向的)。求完后分别取minmax保证时间确实在航班时间范围内即可(比如说起点在圆里面的情况)。

飞机关于飞机比较麻烦。首先,我们先使得航线A和航线B的速度相等,这样方便下面求解。具体地讲,A向量的模除以时间A的值,要等于B向量的模除以时间的值。然后以飞机A为参考系,飞机B的航线路线就变为B-A。剩下的操作与“飞机关于机场”的完全一致,只不过要保证时间要在两个航班时间范围内。

还有一点要注意的是,向量可能经过圆心,这需要判断。

总共有O((n+m)2)个区间,单次建边、检查的复杂度是O((n+m)2)的,因此总复杂度为O((n+m)4logn)

C#反射与特性(九):全网最全-解析反射

© 版权声明
THE END
喜欢就支持一下吧
点赞0 分享