10.13 校内模拟赛教主系列

题目及数据：http://pan.baidu.com/s/18hm3s

第一题。。一眼题不多说。。

第二题。。我的做法比较挫：

在左边从下往上依次连边，

每个点最多连4个边，最少连3个边：

即，每个点的上下两个点，以及右边比他小的最大点和比他大的最小点（设为j，当rj<Li+1时连）

那么如此建出来的图数量级是O(n)的，按此图做kruscal，效率O(nlogn)；

遗憾的是在学校没能过掉全部点，不过如此大的数据量居然是1s。。

求神解...

 1 #include<set>
 2 #include<queue>
 3 #include<cstdio>
 4 #include<cstdlib>
 5 #include<cstring>
 6 #include<iostream>
 7 #include<algorithm>
 8 using namespace std;
 9 const int N = 65540;
10 #define For(i,n) for(int i=1;i<=n;i++)
11 #define Rep(i,l,r) for(int i=l;i<=r;i++)
12 #define Down(i,r,l) for(int i=r;i>=l;i--)
13 
14 int n,A[N],H[N];
15 
16 void Make(int l,int r,int fa){
17     if(l>=r) return;
18     int Mid=(l+r+1)>>1;
19     H[fa<<1]=A[Mid];
20     Make(Mid+1,r,fa<<1);
21     H[(fa<<1)+1]=A[l];
22     Make(l+1,Mid-1,(fa<<1)+1);
23 }
24 
25 int main(){
26     freopen("lazy.in","r",stdin);
27     freopen("lazy.out","w",stdout);
28     scanf("%d",&n);
29     For(i,n) scanf("%d",&A[i]);
30     sort(A+1,A+n+1);
31     H[1]=A[1];
32     Make(2,n,1);
33     For(i,n-1) printf("%d ",H[i]);
34     printf("%d
",H[n]);
35     return 0;
36 }

Lazy T1

 1 #include<set>
 2 #include<cmath>
 3 #include<queue>
 4 #include<cstdio>
 5 #include<cstdlib>
 6 #include<cstring>
 7 #include<iostream>
 8 #include<algorithm>
 9 using namespace std;
10 const int N = 600010;
11 #define For(i,n) for(int i=1;i<=n;i++)
12 #define Rep(i,l,r) for(int i=l;i<=r;i++)
13 #define Down(i,r,l) for(int i=r;i>=l;i--)
14 
15 double ans,tans;
16 int fa[N*2],n,m,x1,x2,cnt;
17 long long R[N*2],L[N*2];
18 
19 double sqr(double A){ return A*A;}
20 
21 struct edge{
22     int x,y;
23     double v;
24 }E[N*4];
25 
26 void init(){
27     freopen("cable.in","r",stdin);
28     freopen("cable.out","w",stdout);
29     scanf("%d%d%d%d",&n,&m,&x1,&x2);
30     tans=sqr(x2-x1);
31     For(i,n) {
32         scanf("%I64d",&L[i]);
33         if(i>1){
34             E[++cnt].x=i;E[cnt].y=i-1;E[cnt].v=L[i];
35         }
36         L[i]+=L[i-1];
37     }
38     For(i,m){
39         scanf("%I64d",&R[i]);
40         if(i>1){
41             E[++cnt].x=i+n;E[cnt].y=i+n-1;E[cnt].v=R[i];
42         }
43         R[i]+=R[i-1];
44     }
45 }
46 
47 bool cmp(edge A,edge B){
48     return A.v<B.v;
49 }
50 
51 void Clean(){
52     int j=1;
53     For(i,n){
54         while(j<m&&R[j+1]<L[i]) j++;
55         E[++cnt].x=i;E[cnt].y=j+n;E[cnt].v=sqrt(tans+sqr(L[i]-R[j]));
56         if(i==n||(R[j+1]<=L[i+1])){
57             j++;
58             E[++cnt].x=i;E[cnt].y=j+n;E[cnt].v=sqrt(tans+sqr(L[i]-R[j]));
59             j--;
60         }
61     }
62 }
63 
64 int find(int i){
65     if(fa[i]!=i) return fa[i]=find(fa[i]);
66     else         return i;
67 }
68 
69 void Kruscal(){
70     sort(E+1,E+cnt+1,cmp);
71     For(i,n+m) fa[i]=i;
72     int tot=0;
73     For(i,cnt){
74         int fx=find(E[i].x),fy=find(E[i].y);
75         if(fx!=fy){
76             ++tot;ans+=E[i].v;
77             fa[fx]=fy;
78         }
79         if(tot==n+m-1) break;
80     }
81     printf("%.2lf
",ans);
82 }
83 
84 int main(){
85     init();
86     Clean();
87     Kruscal();
88     return 0;
89 }

Cable T2

10.13 校内模拟赛 教主系列

10.13 校内模拟赛教主系列