2
27
2016
0

[BZOJ1087] [SCOI2005]互不侵犯King

状压DP

f[i][j][k]表示当前在第i行，包括第i行一共放了j个国王，而且这一行状态为k的方案数

那么f[i][j][k]=Sigma(f[i-1][j-cnt[l]][l],其中l为一种可行方案且不和k状态冲突)

然后搞个ans加一下就没了

?
bzoj 1087
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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
 
long long n,K,cnt[1<<10],f[15][105][1<<10],rule[1<<10],ed,ans;
 
int Cnt(int s){
int ans=0;
while(s){
    ans+=s&1;
    s>>=1;
}
return ans;
}
 
int CheckNot(int s,int l){
return (s&l)||(s&(l>>1))||(s&(l<<1));
}
 
int CheckGood(int s){
int flg=0;
while(s){
    if(s&1 && flg)return 0;
    flg=s&1;
    s>>=1;
}
return 1;
}
 
void Get(){
for(int i=0;i<=ed;i++){cnt[i]=Cnt(i);rule[i]=CheckGood(i);}
}
 
int main(){
freopen("1087.in","r",stdin);
freopen("1087.out","w",stdout);
scanf("%lld %lld",&n,&K);
ed=(1<<n)-1;
Get();
for(int i=0;i<=ed;i++)if(rule[i])f[1][cnt[i]][i]=1;
for(int i=2;i<=n;i++){
    for(int j=0;j<=ed;j++){
        if(!rule[j])continue;
        for(int k=0;k<=ed;k++){
            if(!rule[k] || CheckNot(j,k))continue;
            for(int l=cnt[k];l+cnt[j]<=K;l++)f[i][l+cnt[j]][j]+=f[i-1][l][k];
        }
    }
}
for(int i=0;i<=ed;i++)ans+=f[n][K][i];
printf("%lld\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj
2
26
2016
0

[BZOJ1084] [SCOI2005]最大子矩阵

m<=2。。。

所以直接DP

m=1时

f[i][1][k]表示这一列前i个数选了k个子矩阵(中间的1没有用处)

那么转移就很像最大子段和:f[i][1][k]=max(f[i-1][1][k],f[j][1][k-1]+sum[i]-sum[j]);

前面表示不选择，后面表示选择j-i这一段所能带来的当前情况下的最大得分

m=2时复杂一些

f[i][j][k]表示第一列前i个数第二列前j个数选了k个子矩阵

那么转移分4种情况

1:f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k]);表示继承上一个状态的结果，不选择i或者j

2:f[i][j][k]=max(f[i][j][k],f[ix][j][k-1]+sum[i][1]-sum[ix][1]);表示选择ix-i这一段所能带来的当前情况下的最大得分

3:f[i][j][k]=max(f[i][j][k],f[i][jx][k-1]+sum[j][2]-sum[jx][2]);表示选择jx-j这一段所能带来的当前情况下的最大得分

4:if(i==j)f[i][j][k]=max(f[i][j][k],f[x][x][k-1]+sum[i][1]-sum[x][1]+sum[j][2]-sum[x][2]);表示同时选择两排所能带来的最大得分

最后输出f[n][n][k]就可以了，表示第一列和第二列都选完了，一共选择了k个子矩阵

难得写一次详细的题解……主要是因为我在狂补DP,DP渣到连前几年的普及组题目都写不出来……

去年NOIP D2T2居然不会写

这都坚定了我要补DP的决心……

?
bzoj 1084
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
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
 
int sum[105][5],f[105][105][15],a[105][5],n,m,K;
 
int main(){
freopen("1084.in","r",stdin);
freopen("1084.out","w",stdout);
scanf("%d %d %d",&n,&m,&K);
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        scanf("%d",&a[i][j]);
        sum[i][j]=sum[i-1][j]+a[i][j];
    }
}
memset(f,-127,sizeof(f));
if(m==1){
    for(int i=0;i<=n;i++)f[i][1][0]=0;
    for(int i=1;i<=n;i++){
        for(int k=1;k<=K;k++){
            f[i][1][k]=f[i-1][1][k];
            for(int j=0;j<i;j++){
                f[i][1][k]=max(f[i][1][k],f[j][1][k-1]+sum[i][1]-sum[j][1]);
            }
        }
    }
    printf("%d\n",f[n][1][K]);
}
else if(m==2){
    for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)f[i][j][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=K;k++){
                f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k]);
                for(int ix=0;ix<i;ix++)f[i][j][k]=max(f[i][j][k],f[ix][j][k-1]+sum[i][1]-sum[ix][1]);
                for(int jx=0;jx<j;jx++)f[i][j][k]=max(f[i][j][k],f[i][jx][k-1]+sum[j][2]-sum[jx][2]);
                if(i==j)for(int x=0;x<i;x++)f[i][j][k]=max(f[i][j][k],f[x][x][k-1]+sum[i][1]-sum[x][1]+sum[j][2]-sum[x][2]);
            }
        }
    }
    printf("%d\n",f[n][n][K]);
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
2
25
2016
1

[BZOJ2631] tree

又做了一道叫"tree"的题目。。

这题要开unsigned int!!!!

开int会WA!开int会WA!开int会WA!重要的事说三遍

?
bzoj 2631
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
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
#include<cstdio>
#include<algorithm>
using namespace std;
 
unsigned int n,q;
 
struct Node{
unsigned int v,sum,add,rev,mul,siz;
Node *ch[2],*fa;
Node(unsigned int val,Node *fat);
void Pushdown();
void Pushup();
}*root[100005],*Null;
 
Node::Node(unsigned int val,Node *fat){
v=sum=val;
mul=siz=1;
add=rev=0;
ch[0]=ch[1]=Null;
fa=fat;
}
 
void Node::Pushdown(){
if(rev){
    rev=0;
    if(ch[0]!=Null)ch[0]->rev^=1;
    if(ch[1]!=Null)ch[1]->rev^=1;
    swap(ch[0]->ch[0],ch[0]->ch[1]);
    swap(ch[1]->ch[0],ch[1]->ch[1]);
}
if(mul!=1){
    if(ch[0]!=Null){
        ch[0]->mul=(ch[0]->mul*mul)%51061;
        ch[0]->add=(ch[0]->add*mul)%51061;
        ch[0]->sum=(ch[0]->sum*mul)%51061;
        ch[0]->v=(ch[0]->v*mul)%51061;
    }
    if(ch[1]!=Null){
        ch[1]->mul=(ch[1]->mul*mul)%51061;
        ch[1]->add=(ch[1]->add*mul)%51061;
        ch[1]->sum=(ch[1]->sum*mul)%51061;
        ch[1]->v=(ch[1]->v*mul)%51061;
    }
    mul=1;
}
if(add){
    if(ch[0]!=Null){
        ch[0]->add=(ch[0]->add+add)%51061;
        ch[0]->sum=(ch[0]->sum+ch[0]->siz%51061*add)%51061;
        ch[0]->v=(ch[0]->v+add)%51061;
    }
    if(ch[1]!=Null){
        ch[1]->add=(ch[1]->add+add)%51061;
        ch[1]->sum=(ch[1]->sum+ch[1]->siz%51061*add)%51061;
        ch[1]->v=(ch[1]->v+add)%51061;
    }
    add=0;
}
}
 
void Node::Pushup(){
siz=1;
sum=v;
if(ch[0]!=Null){siz+=ch[0]->siz;sum=(sum+ch[0]->sum)%51061;}
if(ch[1]!=Null){siz+=ch[1]->siz;sum=(sum+ch[1]->sum)%51061;}
}
 
int Notroot(Node *p){
return (p->fa->ch[0]==p)||(p->fa->ch[1]==p);
}
 
void Prepare(Node *p){
if(Notroot(p))Prepare(p->fa);
p->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;
y->Pushup();
x->Pushup();
}
 
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[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();}
}
 
void Makeroot(Node *x){
Access(x);
Splay(x);
x->rev^=1;
swap(x->ch[0],x->ch[1]);
}
 
void Link(Node *x,Node *y){
Makeroot(x);
x->fa=y;
}
 
void Cut(Node *x,Node *y){
Makeroot(x);
Access(y);
Splay(y);
if(y->ch[0]==x){x->fa=Null;y->ch[0]=Null;}
}
 
Node *Find(Node *x){
Access(x);
Splay(x);
while(x->ch[0]!=Null)x=x->ch[0];
return x;
}
 
Node *ToLct(int x){
return root[x];
}
 
Node *GetNull(){
Node *p=new Node(0,Null);
p->ch[0]=p->ch[1]=p->fa=p;
p->siz=0;
return p;
}
 
void Add(int x,int y,int z){
Node *p=ToLct(x),*q=ToLct(y);
Makeroot(p);
Access(q);
Splay(q);
q->add=(q->add+z)%51061;
q->v=(q->v+z)%51061;
q->Pushup();
}
 
void Mul(int x,int y,int z){
Node *p=ToLct(x),*q=ToLct(y);
Makeroot(p);
Access(q);
Splay(q);
q->mul=(q->mul*z)%51061;
q->v=(q->v*z)%51061;
q->Pushup();
}
 
unsigned int Div(int x,int y){
Node *p=ToLct(x),*q=ToLct(y);
Makeroot(p);
Access(q);
Splay(q);
return q->sum;
}
 
int main(){
freopen("2631.in","r",stdin);
freopen("2631.out","w",stdout);
scanf("%d %d",&n,&q);
Null=GetNull();
for(int i=1;i<=n;i++)root[i]=new Node(1,Null);
for(int i=1;i<n;i++){
    int u,v;
    scanf("%d %d",&u,&v);
    Link(ToLct(u),ToLct(v));
}
for(int i=1;i<=q;i++){
    char s[3];
    scanf("%s",s);
    if(s[0]=='+'){
        int u,v,c;
        scanf("%d %d %d",&u,&v,&c);
        Add(u,v,c);
    }
    if(s[0]=='-'){
        int u1,v1,u2,v2;
        scanf("%d %d %d %d",&u1,&v1,&u2,&v2);
        Cut(ToLct(u1),ToLct(v1));
        Link(ToLct(u2),ToLct(v2));
    }
    if(s[0]=='*'){
        int u,v,c;
        scanf("%d %d %d",&u,&v,&c);
        Mul(u,v,c);
    }
    if(s[0]=='/'){
        int u,v;
        scanf("%d %d",&u,&v);
        printf("%d\n",Div(u,v));
    }
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
2
24
2016
0

[BZOJ2654] tree

怎么说呢……神奇的二分

每次把白色边加上一个二分的权值，再做最小生成树

如果大于need条边就说明加上的权值太小了需要增大

反之亦然(因为题目保证有解，所以必然会存在这样的一个权值)

注意排序时权值相等时白色边放在前面

?
bzoj 2654
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
#include<cstdio>
#include<algorithm>
using namespace std;
 
int V,E,need,f[100005],test=0,ne=0;
 
struct Edge{
int a,b,v,co;
friend bool operator<(Edge a,Edge b){
return a.v==b.v?a.co<b.co:a.v<b.v;
}
}e[100005];
 
int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
void Union(int sa,int sb){
if(sa<sb)f[sb]=sa;
else f[sa]=sb;
}
 
int Check(int ans){
test=ne=0;
for(int i=1;i<=V;i++)f[i]=i;
for(int i=1;i<=E;i++){
    if(!e[i].co)e[i].v+=ans;
}
sort(e+1,e+E+1);
for(int i=1;i<=E;i++){
    if(Find(e[i].a)!=Find(e[i].b)){
        Union(Find(e[i].a),Find(e[i].b));
        test+=e[i].v;
        if(!e[i].co)ne++;
    }
}
for(int i=1;i<=E;i++){
    if(!e[i].co)e[i].v-=ans;
}
return ne>=need;
}
 
int main(){
freopen("2654.in","r",stdin);
freopen("2654.out","w",stdout);
scanf("%d %d %d",&V,&E,&need);
for(int i=1;i<=E;i++){
    scanf("%d %d %d %d",&e[i].a,&e[i].b,&e[i].v,&e[i].co);
    e[i].a++;
    e[i].b++;
}
int l=-105,r=105,ans;
while(l<=r){
    int mid=l+r>>1;
    if(Check(mid)){ans=test-need*mid;l=mid+1;}
    else r=mid-1;
}
printf("%d\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj
2
23
2016
0

[BZOJ1305] [CQOI2009]dance跳舞

最大流

拆点，男孩和女孩各拆成2个点ix,iy,jx,jy，互相喜欢ix->jx:1 不互相喜欢iy->jy:1

然后ix->iy=k,jy->jx=k,S->ix=ans,jy->T=ans

枚举ans跑最大流，不满流答案就是ans-1

?
bzoj 1305
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
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
  
int en,n,k,level[1005],S,T,cur[1005],POINT_N,h[1005];
char s[55][55];
  
struct Edge{
int b,f,back,next;
}e[1000005];
  
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(){
queue<int> Q;
Q.push(S);
memset(level,0,sizeof(level));
level[S]=1;
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(level[v] || !e[i].f)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(level[v]==level[u]+1 && e[i].f && (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<=POINT_N;i++)cur[i]=h[i];
    ans+=DFS(S,2100000000);
}
return ans;
}
  
int main(){
freopen("1305.in","r",stdin);
freopen("1305.out","w",stdout);
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
S=4*n+1;
T=4*n+2;
POINT_N=4*n+2;
int ans=1;
while(ans<=1000){
    memset(h,0,sizeof(h));
    for(int i=1;i<=n;i++){
        AddEdge(i,i+n,k);
        AddEdge(i+3*n,i+2*n,k);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(s[i][j]=='Y'){
                AddEdge(i,j+2*n,1);
            }
            else {
                AddEdge(i+n,j+3*n,1);
            }
        }
    }
    for(int i=1;i<=n;i++){
        AddEdge(S,i,ans);
        AddEdge(i+2*n,T,ans);
    }
    int an=Dinic();
    //printf("%d\n",ans);
    if(an<ans*n){printf("%d\n",ans-1);return 0;}
    ans++;
}
return 0;
}

Category: BZOJ | Tags: OI bzoj
2
23
2016
0

[BZOJ1266] [AHOI2006]上学路线route

这题有2问

第一问SPFA

第二问先从1->n 求一遍最短路，再从n->1求一遍最短路，然后判定每条边是否可能在最短路上

即D[e[i].a]+Di[e[i].b]+e[i].t==ans

注意每条边的反向边也需要判断一下

然后跑一遍最大流就行了（最小割=最大流）

?
bzoj 1266
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
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
 
int h[505],n,m,en,en1,D[505],Di[505],flag[505],S,T,cur[505];
 
struct Es{
int a,b,t,c;
}E[200005];
 
struct Edge1{
int b,v,next;
}e1[300005];
 
struct Edge{
int b,f,next,back;
}e[300005];
 
void AddEdge1(int sa,int sb,int sc){
e1[++en1].b=sb;
e1[en1].v=sc;
e1[en1].next=h[sa];
h[sa]=en1;
}
 
void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].f=sc;
e[en].next=h[sa];
e[en].back=en+1;
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].next=h[sa];
e[en].back=en-1;
h[sa]=en;
}
 
int Spfa(int S,int T){
queue<int> Q;
memset(D,127,sizeof(D));
memset(flag,0,sizeof(flag));
Q.push(S);
D[S]=0;
flag[S]=1;
while(!Q.empty()){
    int u=Q.front();
    Q.pop();
    flag[u]=0;
    for(int i=h[u];i;i=e1[i].next){
        int v=e1[i].b;
        if(D[u]+e1[i].v<D[v]){
            D[v]=D[u]+e1[i].v;
            if(!flag[v]){
                Q.push(v);
                flag[v]=1;
            }
        }
    }
}
return D[T];
}
 
int Spfa2(int S,int T){
queue<int> Q;
memset(Di,127,sizeof(Di));
memset(flag,0,sizeof(flag));
Q.push(S);
Di[S]=0;
flag[S]=1;
while(!Q.empty()){
    int u=Q.front();
    Q.pop();
    flag[u]=0;
    for(int i=h[u];i;i=e1[i].next){
        int v=e1[i].b;
        if(Di[u]+e1[i].v<Di[v]){
            Di[v]=Di[u]+e1[i].v;
            if(!flag[v]){
                Q.push(v);
                flag[v]=1;
            }
        }
    }
}
return Di[T];
}
 
int Bfs(){
queue<int> Q;
Q.push(S);
memset(flag,0,sizeof(flag));
flag[S]=1;
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(flag[v] || !e[i].f)continue;
        flag[v]=flag[u]+1;
        Q.push(v);
    }
}
return flag[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(flag[v]==flag[u]+1 && e[i].f && (fl=Dfs(v,min(f,e[i].f)))){
        f-=fl;
        e[i].f-=fl;
        e[e[i].back].f+=fl;
        if(f==0)return flow;
    }
}
return flow-f;
}
 
int Dinic(){
int ans=0;
while(Bfs()){
    for(int i=1;i<=n;i++)cur[i]=h[i];
    ans+=Dfs(S,2100000000);
}
return ans;
}
 
int main(){
freopen("1266.in","r",stdin);
freopen("1266.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
    scanf("%d %d %d %d",&E[i].a,&E[i].b,&E[i].t,&E[i].c);
    AddEdge1(E[i].a,E[i].b,E[i].t);
    AddEdge1(E[i].b,E[i].a,E[i].t);
}
int ans1=Spfa(1,n),ans2=Spfa2(n,1);
memset(h,0,sizeof(h));
printf("%d\n",ans1);
for(int i=1;i<=m;i++){
    if(D[E[i].a]+Di[E[i].b]+E[i].t==ans1){AddEdge(E[i].a,E[i].b,E[i].c);}
    if(Di[E[i].a]+D[E[i].b]+E[i].t==ans1){AddEdge(E[i].b,E[i].a,E[i].c);}
}
S=1;T=n;
ans2=Dinic();
printf("%d\n",ans2);
return 0;
}
Category: BZOJ | Tags: OI bzoj
2
22
2016
0

[BZOJ1269] [AHOI2006]文本编辑器editor

这题写了我1.5h……

以后写题目必须认真、仔细！

Pushdown居然写错了……调试了半天

所以以后必须仔细想好细节再写，这样才能节省时间。

?
bzoj 1296
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
191
192
193
#include<cstdio>
#include<algorithm>
using namespace std;
 
int n,move_to=0;
char s[2000005];
 
struct Node{
char v;
int rev,siz;
Node *ch[2],*fa;
Node(char ch,Node *fat);
void Pushdown();
void Pushup();
}*root,*Null;
 
Node::Node(char c,Node *fat=Null){
ch[0]=ch[1]=Null;
fa=fat;
siz=1;
rev=0;
v=c;
}
 
void Node::Pushdown(){
if(rev){
    rev=0;
    if(ch[0]!=Null)ch[0]->rev^=1;
    if(ch[1]!=Null)ch[1]->rev^=1;
    swap(ch[0]->ch[0],ch[0]->ch[1]);
    swap(ch[1]->ch[0],ch[1]->ch[1]);
}
}
 
void Node::Pushup(){
siz=1;
if(ch[0]!=Null)siz+=ch[0]->siz;
if(ch[1]!=Null)siz+=ch[1]->siz;
}
 
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(z!=Null)z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}
 
void Splay(Node *x,Node *place){
while(x->fa!=place){
    Node *y=x->fa,*z=y->fa;
    if(z==Null || z==place)Rotate(x,y->ch[0]==x);
    else {
        if(y->ch[1]==x && z->ch[1]==y){Rotate(y,0);Rotate(x,0);}
        else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
        else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
        else {Rotate(y,1);Rotate(x,1);}
    }
}
if(place==Null)root=x;
}
 
Node *Find(Node *splay,int k){
splay->Pushdown();
if(k==splay->ch[0]->siz+1)return splay;
if(k<=splay->ch[0]->siz)return Find(splay->ch[0],k);
return Find(splay->ch[1],k-1-splay->ch[0]->siz);
}
 
Node *Split(int pos,int tot){
Node *x=Find(root,pos),*y=Find(root,pos+tot+1);
Splay(x,Null);
Splay(y,root);
return y->ch[0];
}
 
Node *Build(int l,int r){
if(l>r)return Null;
int mid=l+r>>1;
Node *splay=new Node(s[mid],Null);
splay->ch[0]=Build(l,mid-1);
if(splay->ch[0]!=Null)splay->ch[0]->fa=splay;
splay->ch[1]=Build(mid+1,r);
if(splay->ch[1]!=Null)splay->ch[1]->fa=splay;
splay->Pushup();
return splay;
}
 
void Del_Tree(Node *splay){
if(splay==Null)return;
splay->Pushdown();
Del_Tree(splay->ch[0]);
Del_Tree(splay->ch[1]);
if(splay->ch[0]!=Null)delete splay->ch[0];
if(splay->ch[1]!=Null)delete splay->ch[1];
splay->ch[0]=Null;
splay->ch[1]=Null;
splay->Pushup();
}
 
Node *GetNull(){
Node *p=new Node('#',Null);
p->ch[0]=p->ch[1]=p->fa=p;
p->siz=p->rev=0;
}
 
void Build_First(){
Null=GetNull();
s[1]='H';
s[2]='i';
root=Build(1,2);
}
 
void Insert(int pos,int tot){
Node *x=Find(root,pos+1),*y=Find(root,pos+2);
Splay(x,Null);Splay(y,root);
y->ch[0]=Build(1,tot);
if(y->ch[0]!=Null)y->ch[0]->fa=y;
y->Pushup();
x->Pushup();
}
 
void Delete(int pos,int tot){
Node *seq=Split(pos,tot),*fat=seq->fa;
Del_Tree(seq);
if(seq!=Null)delete seq;
fat->ch[0]=Null;
fat->Pushup();
fat->fa->Pushup();
}
 
void Reverse(int pos,int tot){
Node *seq=Split(pos,tot),*fat=seq->fa;
seq->rev^=1;
swap(seq->ch[0],seq->ch[1]);
fat->Pushup();
fat->fa->Pushup();
}
 
char GetKey(int pos){
Node *u=Split(pos,1);
return u->v;
}
 
void GetString(int len){
char ch;
while((ch=getchar())=='\n');
s[1]=ch;
for(int i=2;i<=len;i++){s[i]=getchar();}
s[len+1]='\0';
}
 
int main(){
freopen("1269.in","r",stdin);
freopen("1269.out","w",stdout);
scanf("%d",&n);
Build_First();
for(int i=1;i<=n;i++){
    char opt[10];
    scanf("%s",opt);
    if(opt[0]=='M'){
        int k;
        scanf("%d",&k);
        move_to=k;
    }
    if(opt[0]=='I'){
        int tot;
        scanf("%d",&tot);
        GetString(tot);
        Insert(move_to,tot);
    }
    if(opt[0]=='D'){
        int tot;
        scanf("%d",&tot);
        Delete(move_to+1,tot);
    }
    if(opt[0]=='R'){
        int tot;
        scanf("%d",&tot);
        Reverse(move_to+1,tot);
    }
    if(opt[0]=='G'){
        printf("%c\n",GetKey(move_to+1));
    }
    if(opt[0]=='P')move_to--;
    if(opt[0]=='N')move_to++;
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
2
22
2016
0

[BZOJ3673&3674] 可持久化并查集 by zky & 可持久化并查集加强版

两个都是可持久化线段树，相当于复习一下算法。。

第一个程序我没加路径压缩，第二个加了

第二个读入的操作编号不要异或lastans……在这里卡了一下

?
bzoj 3673
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
#include<cstdio>
#include<algorithm>
using namespace std;
 
struct SegTree{
int l,r,ls,rs,v;
}tree[2000005];
 
int root[20005],cnt,deep[200005],n,m;
 
void Build(int &rt,int l,int r){
if(!rt)rt=++cnt;
if(l==r){tree[rt].v=l;return;}
int mid=l+r>>1;
tree[rt].l=l;
tree[rt].r=r;
Build(tree[rt].ls,l,mid);
Build(tree[rt].rs,mid+1,r);
}
 
void Change(int x,int &y,int pos,int val){
y=++cnt;
tree[y].l=tree[x].l;
tree[y].r=tree[x].r;
if(tree[x].l==tree[x].r){tree[y].v=val;deep[y]=deep[x];return;}
tree[y].ls=tree[x].ls;
tree[y].rs=tree[x].rs;
int mid=tree[x].l+tree[x].r>>1;
if(pos<=mid)Change(tree[x].ls,tree[y].ls,pos,val);
if(pos>mid)Change(tree[x].rs,tree[y].rs,pos,val);
}
 
int Query(int rt,int pos){
if(tree[rt].l==tree[rt].r)return rt;
int mid=tree[rt].l+tree[rt].r>>1;
if(pos<=mid)return Query(tree[rt].ls,pos);
if(pos>mid)return Query(tree[rt].rs,pos);
}
 
void Add(int rt,int pos){
if(tree[rt].l==tree[rt].r){deep[rt]++;return;}
int mid=tree[rt].l+tree[rt].r>>1;
if(pos<=mid)Add(tree[rt].ls,pos);
if(pos>mid)Add(tree[rt].rs,pos);
}
 
int Find(int rt,int x){
int tp=Query(rt,x);
if(x==tree[tp].v)return tp;
return Find(rt,tree[tp].v);
}
 
int main(){
freopen("3673.in","r",stdin);
freopen("3673.out","w",stdout);
scanf("%d %d",&n,&m);
Build(root[0],1,n);
for(int i=1;i<=m;i++){
    int opt;
    scanf("%d",&opt);
    if(opt==1){
        int x,y,px,py;
        scanf("%d %d",&x,&y);
        root[i]=root[i-1];
        px=Find(root[i],x);py=Find(root[i],y);
        if(tree[px].v==tree[py].v)continue;
        if(deep[px]>deep[py])swap(px,py);
        Change(root[i-1],root[i],tree[px].v,tree[py].v);
        if(deep[px]==deep[py])Add(root[i],tree[py].v);
    }
    if(opt==2){
        int k;
        scanf("%d",&k);
        root[i]=root[k];
    }
    if(opt==3){
        int x,y;
        root[i]=root[i-1];
        scanf("%d %d",&x,&y);
        if(tree[Find(root[i],x)].v!=tree[Find(root[i],y)].v)puts("0");
        else puts("1");
    }
}
return 0;
}
?
bzoj 3674
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
#include<cstdio>
#include<algorithm>
using namespace std;
 
int n,m,cnt,lastans=0,deep[10000005],root[200005];
 
struct SegTree{
int l,r,ls,rs,v;
}tree[10000005];
 
void Build(int &rt,int l,int r){
if(!rt)rt=++cnt;
tree[rt].l=l;
tree[rt].r=r;
if(l==r){tree[rt].v=l;return;}
int mid=l+r>>1;
Build(tree[rt].ls,l,mid);
Build(tree[rt].rs,mid+1,r);
}
 
void Change(int x,int &y,int pos,int val){
y=++cnt;
tree[y].l=tree[x].l;
tree[y].r=tree[x].r;
if(tree[x].l==tree[x].r){tree[y].v=val;deep[y]=deep[x];return;}
tree[y].ls=tree[x].ls;
tree[y].rs=tree[x].rs;
int mid=tree[x].l+tree[x].r>>1;
if(pos<=mid)Change(tree[x].ls,tree[y].ls,pos,val);
if(pos>mid)Change(tree[x].rs,tree[y].rs,pos,val);
}
 
void Add(int rt,int pos){
if(tree[rt].l==tree[rt].r){deep[rt]++;return;}
int mid=tree[rt].l+tree[rt].r>>1;
if(pos<=mid)Add(tree[rt].ls,pos);
if(pos>mid)Add(tree[rt].rs,pos);
}
 
int Query(int rt,int pos){
if(tree[rt].l==tree[rt].r){return rt;}
int mid=tree[rt].l+tree[rt].r>>1;
if(pos<=mid)return Query(tree[rt].ls,pos);
if(pos>mid)return Query(tree[rt].rs,pos);
}
 
int Find(int rt,int x){
int p=Query(rt,x);
if(x==tree[p].v){return p;}
int tp=Find(rt,tree[p].v);
Change(rt,rt,tree[p].v,tp);
return tp;
}
 
int main(){
freopen("3674.in","r",stdin);
freopen("3674.out","w",stdout);
scanf("%d %d",&n,&m);
Build(root[0],1,n);
for(int i=1;i<=m;i++){
    int opt;
    scanf("%d",&opt);
    if(opt==1){
        int x,y,p,q;
        scanf("%d %d",&x,&y);
        x^=lastans;y^=lastans;
        root[i]=root[i-1];
        p=Find(root[i],x);
        q=Find(root[i],y);
        if(tree[p].v==tree[q].v)continue;
        if(deep[p]>deep[q])swap(p,q);
        Change(root[i-1],root[i],tree[p].v,tree[q].v);
        if(deep[p]==deep[q])Add(root[i],tree[q].v);
    }
    if(opt==2){
        int k;
        scanf("%d",&k);
        k^=lastans;
        root[i]=root[k];
    }
    if(opt==3){
        int x,y;
        scanf("%d %d",&x,&y);
        x^=lastans;y^=lastans;
        root[i]=root[i-1];
        if(tree[Find(root[i],x)].v==tree[Find(root[i],y)].v){puts("1");lastans=1;}
        else {puts("0");lastans=0;}
    }
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
2
21
2016
0

[BZOJ1500] [NOI2005]维修数列

Splay模版题

调试两天总算A啦！

2016/2/21 *1

2016/3/20 *1

?
bzoj 1500
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
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
#include<cstdio>
#include<algorithm>
using namespace std;
 
int n,a[1000005],m;
 
struct Node{
int v,mx,sum,lx,rx,siz,tag,rev;
Node *ch[2],*fa;
Node(int val,Node *fat);
void Pushdown();
void Pushup();
}*root,*Null;
 
Node::Node(int val=0,Node *fat=Null){
ch[0]=ch[1]=Null;
fa=fat;
v=sum=mx=val;
tag=rev=0;
siz=1;
if(v>=0)lx=rx=v;
else lx=rx=0;
}
 
void Node::Pushdown(){
if(tag){
    tag=rev=0;
    if(ch[0]!=Null){ch[0]->tag=1;ch[0]->sum=ch[0]->siz*v;ch[0]->v=v;}
    if(ch[1]!=Null){ch[1]->tag=1;ch[1]->sum=ch[1]->siz*v;ch[1]->v=v;}
    if(v>=0){
        if(ch[0]!=Null){ch[0]->lx=ch[0]->mx=ch[0]->rx=v*ch[0]->siz;}
        if(ch[1]!=Null){ch[1]->lx=ch[1]->mx=ch[1]->rx=v*ch[1]->siz;}
    }
    else {
        if(ch[0]!=Null){ch[0]->mx=v;ch[0]->lx=ch[0]->rx=0;}
        if(ch[1]!=Null){ch[1]->mx=v;ch[1]->lx=ch[1]->rx=0;}
    }
}
if(rev){
    rev=0;
    if(ch[0]!=Null)ch[0]->rev^=1;
    if(ch[1]!=Null)ch[1]->rev^=1;
    swap(ch[0]->ch[0],ch[0]->ch[1]);
    swap(ch[1]->ch[0],ch[1]->ch[1]);
    swap(ch[0]->lx,ch[0]->rx);
    swap(ch[1]->lx,ch[1]->rx);
}
}
 
void Node::Pushup(){
siz=ch[0]->siz+ch[1]->siz+1;
sum=ch[0]->sum+ch[1]->sum+v;
mx=max(ch[0]->mx,ch[1]->mx);
mx=max(mx,ch[0]->rx+v+ch[1]->lx);
lx=max(ch[0]->lx,ch[0]->sum+v+ch[1]->lx);
rx=max(ch[1]->rx,ch[1]->sum+v+ch[0]->rx);
}
 
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(z!=Null)z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}
 
void Splay(Node *x,Node *place){
while(x->fa!=place){
    Node *y=x->fa,*z=y->fa;
    if(z==Null || z==place)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);}
    }
}
if(place==Null)root=x;
}
 
Node *Find(Node *splay,int k){
splay->Pushdown();
if(splay->ch[0]->siz+1==k)return splay;
if(splay->ch[0]->siz>=k)return Find(splay->ch[0],k);
return Find(splay->ch[1],k-1-splay->ch[0]->siz);
}
 
Node *Split(int pos,int tot){
Node *x=Find(root,pos);
Splay(x,Null);
Node *y=Find(root,pos+tot+1);
Splay(y,root);
return y->ch[0];
}
 
Node *Build(int l,int r){
if(l>r)return Null;
int mid=l+r>>1;
Node *splay=new Node(a[mid],Null);
splay->ch[0]=Build(l,mid-1);
if(splay->ch[0]!=Null)splay->ch[0]->fa=splay;
splay->ch[1]=Build(mid+1,r);
if(splay->ch[1]!=Null)splay->ch[1]->fa=splay;
splay->Pushup();
return splay;
}
 
void Insert(int pos,int tot){
Node *x=Find(root,pos+1),*y=Find(root,pos+2);
Splay(x,Null);Splay(y,root);
y->ch[0]=Build(1,tot);
if(y->ch[0]!=Null)y->ch[0]->fa=y;
y->Pushup();
x->Pushup();
}
 
Node *GetNull(){
Node *p=new Node(0,Null);
p->fa=p->ch[0]=p->ch[1]=p;
p->mx=p->v=-1000000000;
p->rev=p->tag=p->siz=p->sum=p->lx=p->rx=0;
return p;
}
 
void Build_First(){
Null=GetNull();
a[1]=-1000000000;
a[n+2]=-1000000000;
root=Build(1,n+2);
}
 
void Del_Tree(Node *splay){
if(splay==Null)return;
splay->Pushdown();
Del_Tree(splay->ch[0]);
Del_Tree(splay->ch[1]);
if(splay->ch[0]!=Null)delete splay->ch[0];
if(splay->ch[1]!=Null)delete splay->ch[1];
splay->ch[0]=Null;
splay->ch[1]=Null;
splay->Pushup();
}
 
void Delete(int pos,int val){
Node *seq=Split(pos,val),*fat=seq->fa;
Del_Tree(seq);
if(seq!=Null)delete seq;
fat->ch[0]=Null;
fat->Pushup();
fat->fa->Pushup();
}
 
void MakeSame(int pos,int tot,int val){
Node *seq=Split(pos,tot),*fat=seq->fa;
seq->tag=1;
seq->sum=seq->siz*val;
seq->v=val;
if(val>=0)seq->lx=seq->rx=seq->mx=seq->siz*val;
else seq->lx=seq->rx=0,seq->mx=val;
fat->Pushup();
fat->fa->Pushup();
}
 
void Reverse(int pos,int tot){
Node *seq=Split(pos,tot),*fat=seq->fa;
if(!seq->tag){
    seq->rev^=1;
    swap(seq->ch[0],seq->ch[1]);
    swap(seq->lx,seq->rx);
    fat->Pushup();
    fat->fa->Pushup();
}
}
 
int GetSum(int pos,int tot){
Node *seq=Split(pos,tot);
return seq->sum;
}
 
int main(){
freopen("1500.in","r",stdin);
freopen("1500.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=2;i<=n+1;i++)scanf("%d",&a[i]);
Build_First();
for(int i=1;i<=m;i++){
    char s[10];
    scanf("%s",s);
    if(s[0]=='I'){
        int pos,tot;
        scanf("%d %d",&pos,&tot);
        for(int i=1;i<=tot;i++)scanf("%d",&a[i]);
        Insert(pos,tot);
    }
    if(s[0]=='D'){
        int pos,tot;
        scanf("%d %d",&pos,&tot);
        Delete(pos,tot);
    }
    if(s[0]=='M' && s[2]=='K'){
        int pos,tot,val;
        scanf("%d %d %d",&pos,&tot,&val);
        MakeSame(pos,tot,val);
    }
    if(s[0]=='M' && s[2]=='X'){
        printf("%d\n",root->mx);
    }
    if(s[0]=='R'){
        int pos,tot;
        scanf("%d %d",&pos,&tot);
        Reverse(pos,tot);
    }
    if(s[0]=='G'){
        int pos,tot;
        scanf("%d %d",&pos,&tot);
        printf("%d\n",GetSum(pos,tot));
    }
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
2
20
2016
0

我的几个ID

嗯……这些ID都是我的

Lvat2000

Lvat_s

A_Star

Lvat_Violet

DreamPublisher

SkyChecker

OI_Endless

SnowSword

Initialize

好像就这些了……也许我自己忘了一些ID……

Category: 随笔 | Tags: 随笔

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