浴谷夏令营2017.8.3数据结构的整理

P1196 银河英雄传说

加权并查集

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 #define MAXN 30005
 7 #define pii pair<int,int>
 8 using namespace std;
 9 int p[MAXN];
10 int f[MAXN];
11 int r[MAXN];
12 int t;
13 pii find(int x){
14     if(x!=p[x]){
15         pii t=find(p[x]);
16         p[x]=t.first;
17         f[x]+=t.second;
18         return make_pair(p[x],f[x]);
19     }
20     else{
21         return make_pair(x,0);
22     }
23 }
24 void lik(int x,int y){
25     pii temp;
26     temp=find(x); x=temp.first;
27     temp=find(y); y=temp.first;
28     if(x!=y){
29         p[x]=y;
30         f[x]=r[y]+1;
31         r[y]+=(r[x]+1);
32     }
33 }
34 bool same(int x,int y){
35     pii tempx,tempy;
36     tempx=find(x);
37     tempy=find(y);
38     return (tempx.first==tempy.first);
39 }
40 int main()
41 {
42 //    freopen("data.in","r",stdin);
43     for(int i=1;i<MAXN;i++){
44         p[i]=i;
45     }
46     scanf("%d",&t);
47     for(int i=1;i<=t;i++){
48         char c[2]={0};
49         int x,y;
50         scanf("%s%d%d",c,&x,&y);
51         if(c[0]=='M'){
52             lik(x,y);
53         }
54         else{
55             if(same(x,y)){
56                 printf("%d
",abs(f[x]-f[y])-1);
57             }
58             else{
59                 printf("-1
");
60             }
61         }
62     }
63     return 0;
64 }

View Code

P2344 奶牛抗议

dp+树状数组

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<map>
 7 #include<set>
 8 #include<queue>
 9 #define INF 0x7f7f7f7f
10 #define pii pair<ll,int>
11 #define ll long long
12 #define MAXN 100005
13 #define MOD 1000000009
14 using namespace std;
15 int n;
16 ll a[MAXN];
17 ll s[MAXN],N;
18 pii c[MAXN];
19 ll dat[MAXN];
20 ll f[MAXN];
21 ll sum(int k){
22     ll ret=0;
23     while(k>=1){
24         ret=(ret+dat[k])%MOD;
25         k-=(k&-k);
26     }
27     return ret;
28 }
29 void add(int k,ll x){
30     while(k<=N){
31         dat[k]=(dat[k]+x)%MOD;
32         k+=(k&-k);
33     }
34 }
35 ll read(){
36     ll x=0,f=1;char ch=getchar();
37     while(ch<'0'||ch>'9'){if('-'==ch)f=-1;ch=getchar();}
38     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
39     return x*f;
40 }
41 
42 int main()
43 {
44 //    freopen("data.in","r",stdin);
45     n=read();
46     for(int i=1;i<=n;i++){
47         a[i]=read();
48         c[i].first=c[i-1].first+a[i];
49         c[i].second=i;
50     }
51     c[n+1].first=0,c[n+1].second=0;
52     sort(c+1,c+n+2);
53     N=0;
54     for(int i=1;i<=n+1;i++){
55         if(1==i||c[i].first!=c[i-1].first){
56             N++;
57         }
58         s[c[i].second]=N;
59     }
60     add(s[0],1);
61     for(int i=1;i<=n;i++){
62         f[i]=sum(s[i]);
63         add(s[i],f[i]);
64     }
65     printf("%lld
",f[n]);
66     return 0;
67 }

View Code

P3144 [USACO16OPEN]关闭农场Closing the Farm_Silver

倒序并查集

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<vector>
 6 #define MAXN 100005
 7 #define pii pair<int,int>
 8 #define ll long long
 9 using namespace std;
10 int n,m;
11 int f[MAXN];
12 int b[MAXN];
13 int X[MAXN],Y[MAXN];
14 vector<int> p;
15 vector<pii > G[MAXN];
16 vector<int> ans;
17 int find(int x){return ((x==f[x])?x:f[x]=find(f[x]));}
18 void lik(int x,int y){
19     x=find(x),y=find(y);
20     if(f[x]!=y){
21         f[x]=y;
22     }
23 }
24 int main()
25 {
26     scanf("%d%d",&n,&m);
27     for(int i=1;i<=n;i++){
28         f[i]=i;
29     }
30     for(int i=1;i<=m;i++){
31         int x,y;
32         scanf("%d%d",&x,&y);
33         G[x].push_back(make_pair(x,y));
34         G[y].push_back(make_pair(x,y));
35     }
36     for(int i=1;i<=n;i++){
37         int t;scanf("%d",&t);
38         p.push_back(t);
39     }
40     for(int i=n-1;i>=0;i--){
41         int x=p[i];
42         b[x]=1;
43         for(int j=0;j<G[x].size();j++){
44             int s=G[x][j].first,t=G[x][j].second;
45             if(b[s]&&b[t]){
46                 lik(s,t);
47             }
48         }
49         int t=find(x),ok=1;
50         for(int i=1;i<=n;i++){
51             if(b[i]){
52                 if(find(i)!=t){
53                     ans.push_back(0);
54                     ok=0;
55                     break;
56                 }
57             }
58         }
59         if(ok)
60         ans.push_back(1);
61     }
62     for(int i=ans.size()-1;i>=0;i--){
63         if(ans[i]){
64             printf("YES
");
65         }
66         else{
67             printf("NO
");
68         }
69     }
70     return 0;
71 }

View Code

P1223 排队接水

贪心

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<map>
 7 #include<set>
 8 #include<queue>
 9 #define INF 0x7f7f7f7f
10 #define pii pair<int,int>
11 #define MAXN 1005
12 #define ll long long
13 using namespace std;
14 pii a[MAXN];
15 int n;
16 int main()
17 {
18 //    freopen("data.in","r",stdin);
19     scanf("%d",&n);
20     for(int i=1;i<=n;i++){
21         scanf("%d",&a[i].first);
22         a[i].second=i;
23     }
24     sort(a+1,a+n+1);
25     ll ans=0;
26     for(int i=1;i<=n;i++){
27         printf("%d ",a[i].second);
28         ans+=1LL*a[i].first*(n-i);
29     }
30     printf("
");
31     printf("%.2f
",(double)ans/n);
32     return 0;
33 }

View Code

P1168 中位数

维护两个堆

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<map>
 7 #include<set>
 8 #include<queue>
 9 #define INF 0x7f7f7f7f
10 #define pii pair<int,int>
11 #define MAXN 100005
12 #define ll long long
13 using namespace std;
14 priority_queue<int> s;
15 priority_queue<int,vector<int>,greater<int> >t;
16 int a[MAXN];
17 int n;
18 int main()
19 {
20 //    freopen("data.in","r",stdin);
21     scanf("%d",&n);
22     for(int i=1;i<=n;i++){
23         scanf("%d",&a[i]);
24     }
25     printf("%d
",a[1]);
26     t.push(a[1]);
27     for(int i=3;i<=n;i+=2){
28         int k=i/2+1;
29         s.push(a[i-1]),t.push(a[i]);
30         while(s.top()>t.top()){
31             int x=s.top(),y=t.top();
32             s.pop();t.pop();
33             s.push(y);t.push(x);
34         }
35         printf("%d
",t.top());
36     }
37     return 0;
38 }

View Code

P2345 奶牛集会

逆序对

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<map>
 7 #include<set>
 8 #include<queue>
 9 #define INF 0x7f7f7f7f
10 #define pii pair<int,int>
11 #define MAXN 20005
12 #define ll long long
13 using namespace std;
14 int d1[MAXN],d2[MAXN];
15 int t1[MAXN],t2[MAXN];
16 //qian
17 void add1(int k,int x){
18     while(k<MAXN){
19         d1[k]+=x;
20         t1[k]+=1;
21         k+=(k&-k);
22     }
23 }
24 ll sum1(int k,int &t){
25     ll ret=0;
26     t=0;
27     while(k>=1){
28         ret+=d1[k];
29         t+=t1[k];
30         k-=(k&-k);
31     }
32     return ret;
33 }
34 //hou
35 void add2(int k,int x){
36     while(k>=1){
37         d2[k]+=x;
38         t2[k]+=1;
39         k-=(k&-k);
40     }
41 }
42 ll sum2(int k,int &t){
43     ll ret=0;
44     t=0;
45     while(k<MAXN){
46         ret+=d2[k];
47         t+=t2[k];
48         k+=(k&-k);
49     }
50     return ret;
51 }
52 int n;
53 pii a[MAXN];
54 ll ans;
55 int main()
56 {
57 //    freopen("data.in","r",stdin);
58     scanf("%d",&n);
59     for(int i=1;i<=n;i++){
60         scanf("%d%d",&a[i].first,&a[i].second);
61     }
62     sort(a+1,a+n+1);
63     for(int i=1;i<=n;i++){
64         int x=a[i].second;
65         int cnt1,cnt2;
66         ll p=sum1(x-1,cnt1),q=sum2(x+1,cnt2);
67         ans+=(ll)a[i].first*((ll)cnt1*x-p+q-(ll)cnt2*x);
68         add1(x,x),add2(x,x);
69     }
70     printf("%lld
",ans);
71     return 0;
72 }

View Code

P2826 [USACO08NOV]光开关Light Switching

线段树

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<map>
 7 #include<set>
 8 #include<queue>
 9 #define INF 0x7f7f7f7f
10 #define pii pair<int,int>
11 #define MAXN 100005
12 #define ll long long
13 using namespace std;
14 int dat[MAXN*4];
15 int tag[MAXN*4];
16 int n;
17 
18 int read(){
19     int x=0;char ch=getchar();
20     while(ch<'0'||ch>'9'){ch=getchar();}
21     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
22     return x;
23 }
24 void pushdown(int k,int L,int R){
25     int lc=(k<<1),rc=(k<<1|1);
26     int mid=(L+R)/2;
27     int ls=mid-L,rs=R-mid;
28     dat[lc]=(ls-dat[lc]);
29     dat[rc]=(rs-dat[rc]);
30     tag[lc]=(!tag[lc]);
31     tag[rc]=(!tag[rc]);
32     tag[k]=0;
33 }
34 int query(int a,int b,int k,int L,int R){
35     if(b<=L||R<=a){
36         return 0;
37     }
38     else if(a<=L&&R<=b){
39         return dat[k];
40     }
41     else{
42         if(tag[k]){
43             pushdown(k,L,R);
44         }
45         int lc=query(a,b,k<<1,L,(L+R)>>1);
46         int rc=query(a,b,k<<1|1,(L+R)>>1,R);
47         return (lc+rc);
48     }
49 }
50 void update(int a,int b,int k,int L,int R){
51     if(b<=L||R<=a){
52         return ;
53     }
54     else if(a<=L&&R<=b){
55         tag[k]=(!tag[k]);
56         dat[k]=R-L-dat[k];
57     }
58     else{
59         if(tag[k]){
60             pushdown(k,L,R);
61         }
62         update(a,b,k<<1,L,(L+R)>>1);
63         update(a,b,k<<1|1,(L+R)>>1,R);
64         dat[k]=dat[k<<1]+dat[k<<1|1];
65     }
66 }
67 int main()
68 {
69 //    freopen("data.in","r",stdin);
70     n=read();
71     int T=read();
72     for(int i=1;i<=T;i++){
73         int p=read(),a=read(),b=read();
74         if(1==p){
75             printf("%d
",query(a,b+1,1,1,n+1));
76         }
77         else{
78             update(a,b+1,1,1,n+1);
79         }
80 //        for(int j=1;j<=n;j++){
81 //            printf("%d",query(j,j+1,1,1,n+1));
82 //        }
83 //        printf("
");
84     }
85     return 0;
86 }

View Code

P2894 [USACO08FEB]酒店Hotel

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<map>
  7 #include<set>
  8 #include<queue>
  9 #define INF 0x7f7f7f7f
 10 #define pii pair<int,int>
 11 #define MAXN 50005
 12 #define ll long long
 13 using namespace std;
 14 int dat[MAXN*4],datL[MAXN*4],datR[MAXN*4];
 15 int tag[MAXN*4];
 16 int n;
 17 
 18 int read(){
 19     int x=0;char ch=getchar();
 20     while(ch<'0'||ch>'9'){ch=getchar();}
 21     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 22     return x;
 23 }
 24 void build(int k,int L,int R){
 25     if(L+1==R){
 26         dat[k]=datL[k]=datR[k]=R-L;
 27         return;
 28     }
 29     build(k<<1,L,(L+R)>>1);
 30     build(k<<1|1,(L+R)>>1,R);
 31     datL[k]=datR[k]=dat[k]=dat[k<<1]+dat[k<<1|1];
 32 }
 33 void pushdown(int k,int L,int R){
 34     int lc=(k<<1),rc=(k<<1|1);
 35     int mid=(L+R)/2;
 36     int lsize=mid-L,rsize=R-mid;
 37     datL[lc]=datR[lc]=dat[lc]=((1==tag[k])?lsize:0);
 38     datL[rc]=datR[rc]=dat[rc]=((1==tag[k])?rsize:0);
 39     tag[lc]=tag[rc]=tag[k];
 40     tag[k]=0;
 41 }
 42 void update(int a,int b,int k,int L,int R,int x){
 43     if(b<=L||R<=a){
 44         return ;
 45     }
 46     else if(a<=L&&R<=b){
 47         dat[k]=datL[k]=datR[k]=((1==x)?R-L:0);
 48         tag[k]=x;
 49     }
 50     else{
 51         if(tag[k]){
 52             pushdown(k,L,R);
 53         }
 54         int mid=(L+R)/2;
 55         int lsize=mid-L,rsize=R-mid;
 56         update(a,b,k<<1,L,mid,x);
 57         update(a,b,k<<1|1,mid,R,x);
 58         dat[k]=max(dat[k<<1],dat[k<<1|1]);
 59         dat[k]=max(dat[k],datR[k<<1]+datL[k<<1|1]);
 60         if(datL[k<<1]==lsize){
 61             datL[k]=datL[k<<1]+datL[k<<1|1];
 62         }
 63         else{
 64             datL[k]=datL[k<<1];
 65         }
 66         if(datR[k<<1|1]==rsize){
 67             datR[k]=datR[k<<1|1]+datR[k<<1];
 68         }
 69         else{
 70             datR[k]=datR[k<<1|1];            
 71         }
 72         dat[k]=max(dat[k],max(datL[k],datR[k]));
 73     }
 74 }
 75 int query(int s,int k,int L,int R){
 76     if(tag[k]){
 77         pushdown(k,L,R);
 78     }
 79     if(datL[k]>=s){
 80         return L;
 81     }
 82     if(dat[k<<1]>=s){
 83         return query(s,k<<1,L,(L+R)>>1);
 84     }
 85     else if(datR[k<<1]+datL[k<<1|1]>=s){
 86         return (L+R)/2-datR[k<<1];
 87     }
 88     else{
 89         return query(s,k<<1|1,(L+R)>>1,R);
 90     }
 91 }
 92 void debug(int k,int L,int R){
 93     if(L+1==R){
 94         printf("%d ",dat[k]);
 95         return ;
 96     }
 97     if(tag[k]){
 98         pushdown(k,L,R);
 99     }
100     debug(k<<1,L,(L+R)>>1);
101     debug(k<<1|1,(L+R)>>1,R);
102 }
103 int main()
104 {
105 //    freopen("data.in","r",stdin);
106 //    freopen("my.out","w",stdout);
107     n=read();
108     int T=read();
109     build(1,1,n+1);
110     for(int i=1;i<=T;i++){
111         int p=read(),x=read();
112         if(1==p){
113             if(dat[1]<x){
114                 printf("0
");
115                 continue;
116             }
117             int p=query(x,1,1,n+1);
118             printf("%d
",p);
119             update(p,p+x,1,1,n+1,2);
120         }
121         else{
122             int y=read();
123             update(x,x+y,1,1,n+1,1);
124         }
125 //        debug(1,1,n+1);
126 //        printf("
");
127     }
128     return 0;
129 }

View Code