4
23
2016
0

[BZOJ2049] [Sdoi2008]Cave 洞穴勘测

LCT

?
bzoj 2049
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<cstdio>
#include<algorithm>
using namespace std;
 
int n,m;
 
struct Node{
int rev;
Node *ch[2],*fa;
Node(Node *fat);
void Pushdown();
}*root[10005],*Null;
 
Node::Node(Node *fat){
fa=fat;
ch[0]=ch[1]=Null;
rev=0;
}
 
void Node::Pushdown(){
if(rev){
    if(ch[0]!=Null)ch[0]->rev^=1;
    if(ch[1]!=Null)ch[1]->rev^=1;
    swap(ch[0],ch[1]);
    rev=0;
}
}
 
int Notroot(Node *x){
return (x->fa->ch[0]==x)||(x->fa->ch[1]==x);
}
 
void Prepare(Node *x){
if(Notroot(x))Prepare(x->fa);
x->Pushdown();
}
 
void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(Notroot(y))z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
}
 
void Splay(Node *x){
Prepare(x);
while(Notroot(x)){
    Node *y=x->fa,*z=y->fa;
    if(!Notroot(y))Rotate(x,y->ch[0]==x);
    else {
        if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
        else if(y->ch[1]==x && z->ch[1]==y){Rotate(y,0);Rotate(x,0);}
        else if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
        else {Rotate(x,0);Rotate(x,1);}
    }
}
}
 
void Access(Node *x){
for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;}
}
 
void Makeroot(Node *x){
Access(x);
Splay(x);
x->rev^=1;
}
 
void Link(Node *u,Node *v){
Makeroot(u);
u->fa=v;
}
 
void Cut(Node *u,Node *v){
Makeroot(u);
Access(v);
Splay(v);
if(v->ch[0]==u){v->ch[0]=Null;u->fa=Null;}
}
 
Node *Find(Node *x){
Access(x);
Splay(x);
while(x->ch[0]!=Null)x=x->ch[0];
return x;
}
 
Node *GetNull(){
Node *p=new Node(Null);
p->ch[0]=p->ch[1]=p->fa=p;
p->rev=0;
return p;
}
 
Node *ToLct(int x){
return root[x];
}
 
int main(){
freopen("2049.in","r",stdin);
freopen("2049.out","w",stdout);
scanf("%d %d",&n,&m);
Null=GetNull();
for(int i=1;i<=n;i++)root[i]=new Node(Null);
for(int i=1;i<=m;i++){
    int u,v;
    char s[10];
    scanf("%s %d %d",s,&u,&v);
    if(s[0]=='C')Link(ToLct(u),ToLct(v));
    if(s[0]=='D')Cut(ToLct(u),ToLct(v));
    if(s[0]=='Q'){
        if(Find(ToLct(u))==Find(ToLct(v)))puts("Yes");
        else puts("No");
    }
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
23
2016
0

[BZOJ2662] [BeiJing wc2012]冻结

水题可以愉悦身心

分层图SPFA

?
bzoj 2662
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
 
int n,m,k,en,h[55],D[55][55],flag[55][55],ans;
 
struct Que{
int a,b;
Que(int sa,int sb){a=sa;b=sb;}
};
 
queue<Que> Q;
 
struct Edge{
int b,v,next;
}e[2005];
 
void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}
 
void SPFA(){
memset(D,127,sizeof(D));
flag[0][1]=1;
D[0][1]=0;
Q.push(Que(0,1));
while(!Q.empty()){
    Que u=Q.front();
    Q.pop();
    flag[u.a][u.b]=0;
    for(int i=h[u.b];i;i=e[i].next){
        int v=e[i].b;
        if(D[u.a][v]>D[u.a][u.b]+e[i].v){
            D[u.a][v]=D[u.a][u.b]+e[i].v;
            if(!flag[u.a][v]){
                flag[u.a][v]=1;
                Q.push(Que(u.a,v));
            }
        }
    }
    if(u.a<k){
        for(int i=h[u.b];i;i=e[i].next){
            int v=e[i].b;
            if(D[u.a+1][v]>D[u.a][u.b]+e[i].v/2){
                D[u.a+1][v]=D[u.a][u.b]+e[i].v/2;
                if(!flag[u.a+1][v]){
                    flag[u.a+1][v]=1;
                    Q.push(Que(u.a+1,v));
                }
            }
        }
    }
}
ans=D[0][n];
for(int i=1;i<=k;i++)ans=min(ans,D[i][n]);
}
 
int main(){
freopen("2662.in","r",stdin);
freopen("2662.out","w",stdout);
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<=m;i++){
    int u,v,w;
    scanf("%d %d %d",&u,&v,&w);
    AddEdge(u,v,w);
    AddEdge(v,u,w);
}
SPFA();
printf("%d\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
23
2016
0

[BZOJ2761] [JLOI2011]不重复数字

行尾有空格会PE

真是日了狗了

?
bzoj 2761
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
 
int n,T;
 
struct Data{
int id,x;
friend bool operator<(Data A,Data B){return A.id<B.id;}
}a[50005];
 
bool cmp(Data A,Data B){return A.x<B.x || (A.x==B.x && A.id<B.id);}
 
int main(){
freopen("2761.in","r",stdin);
freopen("2761.out","w",stdout);
scanf("%d",&T);
while(T--){
    scanf("%d",&n);
    a[n+1].id=99999;
    for(int i=1;i<=n;i++)scanf("%d",&a[i].x),a[i].id=i;
    sort(a+1,a+n+1,cmp);
    for(int i=2;i<=n;i++)if(a[i].x==a[i-1].x)a[i].id=99999;
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){if(a[i+1].id==99999){printf("%d\n",a[i].x);break;}else printf("%d ",a[i].x);}
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
22
2016
0

[BZOJ2763] [JLOI2011]飞行路线

分层图SPFA

最后必须依次比较，因为可能因为边数太少用不到k次

?
bzoj 2763
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
 
int n,m,k,S,T,en,h[10005],D[15][10005],flag[15][10005],ans;
 
struct Que{
int a,b;
Que(int sa,int sb){a=sa;b=sb;}
};
 
queue<Que> Q;
 
struct Edge{
int b,v,next;
}e[100005];
 
void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}
 
void SPFA(){
memset(D,127,sizeof(D));
D[0][S]=0;
flag[0][S]=1;
Q.push(Que(0,S));
while(!Q.empty()){
    Que u=Q.front();
    Q.pop();
    flag[u.a][u.b]=0;
    for(int i=h[u.b];i;i=e[i].next){
        int v=e[i].b;
        if(D[u.a][v]>D[u.a][u.b]+e[i].v){
            D[u.a][v]=D[u.a][u.b]+e[i].v;
            if(!flag[u.a][v]){
                flag[u.a][v]=1;
                Q.push(Que(u.a,v));
            }
        }
    }
    if(u.a<k){
        for(int i=h[u.b];i;i=e[i].next){
            int v=e[i].b;
            if(D[u.a+1][v]>D[u.a][u.b]){
                D[u.a+1][v]=D[u.a][u.b];
                if(!flag[u.a+1][v]){
                    flag[u.a+1][v]=1;
                    Q.push(Que(u.a+1,v));
                }
            }
        }
    }
}
ans=D[0][T];
for(int i=1;i<=k;i++){ans=min(ans,D[i][T]);}
}
 
int main(){
freopen("2763.in","r",stdin);
freopen("2763.out","w",stdout);
scanf("%d %d %d %d %d",&n,&m,&k,&S,&T);
for(int i=1;i<=m;i++){
    int u,v,w;
    scanf("%d %d %d",&u,&v,&w);
    AddEdge(u,v,w);
    AddEdge(v,u,w);
}
SPFA();
printf("%d\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
21
2016
0

[BZOJ2759] 一个动态树好题

的确是好题。。。

根本不会，然后copy了PoPoQQQ大爷的代码

反正就是LCT乱搞

题解

?
bzoj 2759
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int Mod=10007,N=30005;
 
int n,m,vis[N],cnt,fa[N];
 
struct Line{
int k,b;
Line(){}
Line(int ks,int bs){k=ks;b=bs;}
friend Line operator+(Line A,Line B){return Line(A.k*B.k%Mod,(B.k*A.b+B.b)%Mod);}
int F(int x){return (k*x+b)%Mod;}
};
 
struct Node{
Line v,sum;
Node *ch[2],*fa,*spc;
Node(int k,int b);
void Pushup();
}*root[N],*Null;
 
Node::Node(int k,int b){ch[0]=ch[1]=fa=spc=Null;v=sum=Line(k,b);}
void Node::Pushup(){sum=ch[0]->sum+v+ch[1]->sum;}
bool Notroot(Node *x){return x->fa->ch[0]==x || x->fa->ch[1]==x;}
Node *GetNull(){Node *p=new Node(1,0);p->ch[0]=p->ch[1]=p->fa=p;return p;}
 
void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(Notroot(y))z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}
 
void Splay(Node *x){
while(Notroot(x)){
    Node *y=x->fa,*z=y->fa;
    if(!Notroot(y))Rotate(x,y->ch[0]==x);
    else {
        if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
        else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
        else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
        else {Rotate(y,0);Rotate(x,0);}
    }
}
}
 
void Access(Node *x){for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;x->Pushup();}}
Node *Findroot(Node *x){Access(x);Splay(x);while(x->ch[0]!=Null)x=x->ch[0];return x;}
pair<int,int>exgcd(int a,int b){if(!b)return make_pair(1,0);pair<int,int>P=exgcd(b,a%b);return make_pair(P.second,P.first-a/b*P.second);}
int Inv(int x){int P=exgcd((x+Mod)%Mod,Mod).first;return (P%Mod+Mod)%Mod;}
void DFS(int u){vis[u]=cnt;if(vis[fa[u]]==cnt){root[u]->spc=root[fa[u]];return;}root[u]->fa=root[fa[u]];if(!vis[fa[u]])DFS(fa[u]);}
 
int Query(Node *x){
Node *rt=Findroot(x);
Access(rt->spc);
Splay(rt->spc);
int k=rt->spc->sum.k,b=rt->spc->sum.b;
if(k==1 && !(b==0 && x->sum.k==0))return b?-1:-2;
Access(x);
Splay(x);
return x->sum.F((Mod-b)*Inv(k-1)%Mod);
}
 
void Modify(Node *x,int k,Node *f,int b){
Node *rt=Findroot(x);
x->v.k=k;x->v.b=b;x->Pushup();
if(x==rt)x->spc=Null;
else {
    Access(x);
    Splay(x);
    x->ch[0]->fa=Null;
    x->ch[0]=Null;
    x->Pushup();
    if(Findroot(rt->spc)!=rt){
        Access(rt);
        Splay(rt);
        rt->fa=rt->spc;
        rt->spc=Null;
    }
}
Access(x);
Splay(x);
if(Findroot(f)==x){x->spc=f;}
else x->fa=f;
}
 
int main(){
freopen("2759.in","r",stdin);
freopen("2759.out","w",stdout);
scanf("%d",&n);
Null=GetNull();
for(int i=1;i<=n;i++){
    int k,f,b;
    scanf("%d %d %d",&k,&f,&b);
    fa[i]=f;
    root[i]=new Node(k,b);
}
for(int i=1;i<=n;i++){if(!vis[i]){cnt++;DFS(i);}}
scanf("%d",&m);
for(int i=1;i<=m;i++){
    char s[10];
    int x,k,p,b;
    scanf("%s",s);
    if(s[0]=='A'){scanf("%d",&x);printf("%d\n",Query(root[x]));}
    if(s[0]=='C'){scanf("%d %d %d %d",&x,&k,&p,&b);Modify(root[x],k,root[p],b);}
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
20
2016
0

[BZOJ1069] [SCOI2007]最大土地面积

旋转卡壳模版题

首先搞出凸包，然后在凸包上面扫描，用两个指针维护单调性

?
bzoj 1069
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cstring>
#include<algorithm>
using namespace std;
 
int n,St_size,St[2005];
double ans;
 
struct Point{
double x,y;
Point(){}
Point(int sa,int sb){x=sa;y=sb;}
friend Point operator+(Point A,Point B){return Point(A.x+B.x,A.y+B.y);}
friend Point operator-(Point A,Point B){return Point(A.x-B.x,A.y-B.y);}
friend double operator*(Point A,Point B){return A.x*B.y-A.y*B.x;}
friend bool operator<(Point A,Point B){return A.y<B.y || A.y==B.y && A.x<B.x;}
}poi[2005];
 
double Abs(double x){return x>0?x:-x;}
double Dist(Point A,Point B){return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);}
 
bool cmp(Point A,Point B){
int Mul=(int)((A-poi[1])*(B-poi[1]));
return (Mul>0)||(Mul==0 && Dist(A,poi[1])<Dist(B,poi[1]));
}
 
void Graham(){
if(n==1){St[1]=1;St_size=1;return;}
St[1]=1;
St[2]=2;
St_size=2;
for(int i=3;i<=n;i++){
    while(St_size>1 && (poi[St[St_size]]-poi[St[St_size-1]])*(poi[i]-poi[St[St_size-1]])<=0)St_size--;
    St[++St_size]=i;
}
}
 
void Prepare(){
int pos=1;
for(int i=2;i<=n;i++)if(poi[i]<poi[pos])pos=i;
swap(poi[pos],poi[1]);
sort(poi+2,poi+n+1,cmp);
}
 
void RC(){
St[St_size+1]=1;
for(int i=1;i<=St_size;i++){
    int poix=i%St_size+1,poiy=(i+2)%St_size+1;
    for(int j=i+2;j<=St_size;j++){
        while(poix%St_size+1!=j && Abs((poi[St[j]]-poi[St[i]])*(poi[St[poix+1]]-poi[St[i]]))>Abs((poi[St[j]]-poi[St[i]])*(poi[St[poix]]-poi[St[i]])))poix=poix%St_size+1;
        while(poiy%St_size+1!=i && Abs((poi[St[poiy+1]]-poi[St[i]])*(poi[St[j]]-poi[St[i]]))>Abs((poi[St[poiy]]-poi[St[i]])*(poi[St[j]]-poi[St[i]])))poiy=poiy%St_size+1;
        ans=max(ans,Abs((poi[St[j]]-poi[St[i]])*(poi[St[poix]]-poi[St[i]]))+Abs((poi[St[poiy]]-poi[St[i]])*(poi[St[j]]-poi[St[i]])));
    }
}
}
 
int main(){
freopen("1069.in","r",stdin);
freopen("1069.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){scanf("%lf %lf",&poi[i].x,&poi[i].y);}
Prepare();
Graham();
RC();
printf("%.3lf\n",ans/2);
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
19
2016
0

Hello,AHOI2017

AHOI2016挂的很惨。。。

lyz lyf都开始停课搞OI了，马上就要拿到Au走上人生巅峰了

我因为没进省队回家种仙人掌去了很悲伤

所以，我在此立下FLAG:

我不停课，但我的OI也不会停的！

同时预祝两位大爷今年NOI能拿到Au为学校争光~

AHOI2017,我会翻盘的！

UPD2016.08.17

lyz确实拿到Au了……lyf是Cu

Category: 随笔 | Tags: 随笔 弱
4
19
2016
0

[BZOJ1085] [SCOI2005]骑士精神

双向BFS

怎么写着写着就5kb+了呢……其他人为什么跑得那么快……

?
bzoj 1085
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
 
const int Smod=9973;
const pair<int,int> tab[]={make_pair(-1,-2),make_pair(-2,-1),make_pair(-1,2),make_pair(-2,1),make_pair(1,-2),make_pair(2,-1),make_pair(1,2),make_pair(2,1)};
const long long Lmod1=233333333333333ll,Lmod2=666666666666667ll;
 
int T,hn1,hn2,mat[10][10],h1[10005],h2[10005];
char mt[10][10];
 
struct Hash{
int next,step;
long long L1,L2;
}ha1[1000005],ha2[1000005];
 
void AddHash1(int s,long long l1,long long l2,int step){
ha1[++hn1].L1=l1;
ha1[hn1].L2=l2;
ha1[hn1].step=step;
ha1[hn1].next=h1[s];
h1[s]=hn1;
}
 
int FindHash1(int s,long long l1,long long l2){
for(int i=h1[s];i;i=ha1[i].next){
    if(ha1[i].L1==l1 && ha1[i].L2==l2)return i;
}
return 0;
}
 
void AddHash2(int s,long long l1,long long l2,int step){
ha2[++hn2].L1=l1;
ha2[hn2].L2=l2;
ha2[hn2].step=step;
ha2[hn2].next=h2[s];
h2[s]=hn2;
}
 
int FindHash2(int s,long long l1,long long l2){
for(int i=h2[s];i;i=ha2[i].next){
    if(ha2[i].L1==l1 && ha2[i].L2==l2)return i;
}
return 0;
}
 
struct Matrix{
int mt[6][6],now;
friend bool operator==(Matrix A,Matrix B){
for(int i=1;i<=5;i++){
    for(int j=1;j<=5;j++)if(A.mt[i][j]!=B.mt[i][j])return 0;
}
return 1;
}
}Template;
 
pair<int,pair<long long,long long> > GetHash(Matrix M){
int s=0;
long long l1=0,l2=0;
for(int i=1;i<=5;i++){
    for(int j=1;j<=5;j++){
        s=(s*127+M.mt[i][j])%Smod;
        l1=(l1*233+M.mt[i][j])%Lmod1;
        l2=(l2*667+M.mt[i][j])%Lmod2;
    }
}
return make_pair(s,make_pair(l1,l2));
}
 
queue<Matrix> Q1,Q2;
 
void OutMatrix(Matrix M){
puts("This is Mt:");
for(int i=1;i<=5;i++){
    for(int j=1;j<=5;j++){
        printf("%d",M.mt[i][j]);
    }
    putchar('\n');
}
puts("-------------");
}
 
void BFS(int mode,int st){
if(st>8){puts("-1");return;}
if(mode){
    while(Q1.front().now==st){
        Matrix u=Q1.front();
        //OutMatrix(u);
        Q1.pop();
        int x,y;
        for(x=1;x<=5;x++){for(y=1;y<=5;y++){if(!u.mt[x][y])break;}if(!u.mt[x][y] && y<6)break;}
        //printf("XY:%d %d\n",x,y);
        for(int i=0;i<8;i++){
            int px=x+tab[i].first,py=y+tab[i].second,tc;
            if(px<1 || py<1 || px>5 || py>5)continue;
            swap(u.mt[x][y],u.mt[px][py]);u.now++;
            pair<int,pair<long long,long long> >Pt=GetHash(u);
            tc=FindHash2(Pt.first,Pt.second.first,Pt.second.second);
            if(tc){printf("%d\n",u.now+ha2[tc].step<=15?u.now+ha2[tc].step:-1);return;}
            tc=FindHash1(Pt.first,Pt.second.first,Pt.second.second);
            if(!tc){AddHash1(Pt.first,Pt.second.first,Pt.second.second,u.now);Q1.push(u);}
            swap(u.mt[x][y],u.mt[px][py]);u.now--;
        }
    }
    BFS(mode^1,st);
    return;
}
else {
    while(Q2.front().now==st){
        Matrix u=Q2.front();
        //OutMatrix(u);
        Q2.pop();
        int x,y;
        for(x=1;x<=5;x++){for(y=1;y<=5;y++){if(!u.mt[x][y])break;}if(!u.mt[x][y] && y<6)break;}
        //printf("XY:%d %d\n",x,y);
        for(int i=0;i<8;i++){
            int px=x+tab[i].first,py=y+tab[i].second,tc;
            if(px<1 || py<1 || px>5 || py>5)continue;
            swap(u.mt[x][y],u.mt[px][py]);u.now++;
            pair<int,pair<long long,long long> >Pt=GetHash(u);
            tc=FindHash1(Pt.first,Pt.second.first,Pt.second.second);
            if(tc){printf("%d\n",u.now+ha1[tc].step<=15?u.now+ha1[tc].step:-1);return;}
            tc=FindHash2(Pt.first,Pt.second.first,Pt.second.second);
            if(!tc){AddHash2(Pt.first,Pt.second.first,Pt.second.second,u.now);Q2.push(u);}
            swap(u.mt[x][y],u.mt[px][py]);u.now--;
        }
    }
    BFS(mode^1,st+1);
    return;
}
}
 
void MakeMt(Matrix &x){
for(int i=1;i<=5;i++){
    for(int j=1;j<=5;j++){
        x.mt[i][j]=mat[i][j];
    }
}
x.now=0;
}
 
void Prepare(){
mat[1][1]=2;mat[1][2]=2;mat[1][3]=2;mat[1][4]=2;mat[1][5]=2;
mat[2][1]=1;mat[2][2]=2;mat[2][3]=2;mat[2][4]=2;mat[2][5]=2;
mat[3][1]=1;mat[3][2]=1;mat[3][3]=0;mat[3][4]=2;mat[3][5]=2;
mat[4][1]=1;mat[4][2]=1;mat[4][3]=1;mat[4][4]=1;mat[4][5]=2;
mat[5][1]=1;mat[5][2]=1;mat[5][3]=1;mat[5][4]=1;mat[5][5]=1;
}
 
void First(){
while(!Q1.empty())Q1.pop();
while(!Q2.empty())Q2.pop();
memset(h1,0,sizeof(h1));
memset(h2,0,sizeof(h2));
hn1=0;hn2=0;
}
 
int main(){
freopen("1085.in","r",stdin);
freopen("1085.out","w",stdout);
scanf("%d",&T);
Prepare();
MakeMt(Template);
while(T--){
    First();
    scanf("%s %s %s %s %s",mt[1]+1,mt[2]+1,mt[3]+1,mt[4]+1,mt[5]+1);
    for(int i=1;i<=5;i++){
        for(int j=1;j<=5;j++){
            if(mt[i][j]=='0')mat[i][j]=1;
            else if(mt[i][j]=='1')mat[i][j]=2;
            else mat[i][j]=0;
        }
    }
    Matrix Tp;
    pair<int,pair<long long,long long> > Pr;
    MakeMt(Tp);
    if(Tp==Template){puts("0");continue;}
    Q1.push(Tp);
    Q2.push(Template);
    Pr=GetHash(Tp);
    AddHash1(Pr.first,Pr.second.first,Pr.second.second,0);
    Pr=GetHash(Template);
    AddHash2(Pr.first,Pr.second.first,Pr.second.second,0);
    BFS(1,0);
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
19
2016
0

[BZOJ3218] a + b Problem

这是一个卡内存的悲伤故事

我把UOJ爆了一通才卡完内存，然后又发现在BZOJ上MLE了

然后又是乱卡一通，终于A掉了

题解(PoPoQQQ)

?
bzoj 3218
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
 
const int INF=2100000000,N=900005;
 
int n,en,S,T,level[N],h[N],cur[N],his[5005],cnt,flow_cnt,ans;
queue<int> Q;
 
struct Edge{
int b,f,back,next;
}e[N];
 
void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].f=sc;
e[en].back=en+1;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].back=en-1;
e[en].next=h[sa];
h[sa]=en;
}
 
int BFS(){
memset(level,0,sizeof(level));
level[S]=1;
Q.push(S);
while(!Q.empty()){
    int u=Q.front();
    Q.pop();
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].b;
        if(!e[i].f || level[v])continue;
        level[v]=level[u]+1;
        Q.push(v);
    }
}
return level[T];
}
 
int DFS(int u,int flow){
if(u==T)return flow;
int f=flow;
for(int &i=cur[u];i;i=e[i].next){
    int v=e[i].b,fl;
    if(e[i].f && level[v]==level[u]+1 && (fl=DFS(v,min(f,e[i].f)))){
        e[i].f-=fl;
        e[e[i].back].f+=fl;
        f-=fl;
        if(f==0)return flow;
    }
}
return flow-f;
}
 
int Dinic(){
int ans=0;
while(BFS()){for(int i=1;i<=flow_cnt;i++)cur[i]=h[i];ans+=DFS(S,2100000000);}
return ans;
}
 
struct SegTree{
int nl,nr,v,pos;
}tree[N];
 
void Newnode(int &rt,int lastrt){
rt=++cnt;
tree[rt].nl=tree[lastrt].nl;
tree[rt].nr=tree[lastrt].nr;
tree[rt].pos=++flow_cnt;
}
 
void Update(int &rt,int lastrt,int l,int r,int pos,int val){
Newnode(rt,lastrt);
int mid=l+r>>1;
AddEdge(val,tree[rt].pos,INF);
if(lastrt)AddEdge(tree[lastrt].pos,tree[rt].pos,INF);
if(l==r)return;
if(pos<=mid)Update(tree[rt].nl,tree[lastrt].nl,l,mid,pos,val);
if(pos>mid)Update(tree[rt].nr,tree[lastrt].nr,mid+1,r,pos,val);
}
 
void Query(int rt,int l,int r,int x,int y,int point){
if(!rt)return;
if(x<=l && r<=y){AddEdge(tree[rt].pos,point,INF);return;}
int mid=l+r>>1;
if(x<=mid)Query(tree[rt].nl,l,mid,x,y,point);
if(y>mid)Query(tree[rt].nr,mid+1,r,x,y,point);
}
 
int main(){
freopen("3218.in","r",stdin);
freopen("3218.out","w",stdout);
scanf("%d",&n);
S=n*2+1;T=n*2+2;flow_cnt=n*2+2;
for(int i=1;i<=n;i++){
    int a,b,w,l,r,p;
    scanf("%d %d %d %d %d %d",&a,&b,&w,&l,&r,&p);
    ans+=b+w;
    AddEdge(S,i+n,w);AddEdge(i+n,T,b);
    AddEdge(i,i+n,p);
    Update(his[i],his[i-1],0,1000000000,a,i+n);
    Query(his[i-1],0,1000000000,l,r,i);
}
printf("%d\n",ans-Dinic());
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
19
2016
0

[BZOJ1483] [HNOI2009]梦幻布丁

链表启发式合并

每次将元素少的并到多的上面

注意维护一下每个链表维护的真实颜色就好了

?
bzoj 1483
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int N=1500005;
 
int n,m,a[N],siz[N],f[N],ans;
 
struct Line{
int pos;
Line *next;
Line(){}
Line(int x,Line *y){pos=x;next=y;}
}*color[N];
 
void Add(int x,int pos){Line *tp=new Line(pos,color[x]);color[x]=tp;}
 
void Merge(int x,int y){
if(x==y)return;
if(siz[f[x]]>siz[f[y]])swap(f[x],f[y]);
x=f[x];y=f[y];
if(!color[x])return;
for(Line *i=color[x];i;i=i->next){if(a[i->pos-1]==y)ans--;if(a[i->pos+1]==y)ans--;}
for(Line *i=color[x];i;i=i->next)a[i->pos]=y;
Line *Tp;
for(Tp=color[x];Tp->next;Tp=Tp->next);
Tp->next=color[y];color[y]=color[x];color[x]=NULL;
siz[y]+=siz[x];siz[x]=0;
}
 
int main(){
freopen("1483.in","r",stdin);
freopen("1483.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){scanf("%d",&a[i]);f[a[i]]=a[i];siz[a[i]]++;Add(a[i],i);if(a[i]!=a[i-1])ans++;}
for(int i=1;i<=m;i++){
    int opt,x,y;
    scanf("%d",&opt);
    if(opt==1){scanf("%d %d",&x,&y);Merge(x,y);}
    if(opt==2)printf("%d\n",ans);
}
return 0;
}
Category: BZOJ | Tags: OI bzoj

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com