Liveddd's Blog

愛にできることはまだあるかい

CF1368H2 Breadboard Capacity (hard version)

发表于 更新于 分类于
本文字数： 6.5k 阅读时长 ≈ 14 分钟

有趣的 DP 题，用到模拟网络流的技巧。

首先考虑简单版 CF1368H1 Breadboard Capacity (easy version)。容易发现是个网络流模型：对于边缘，将源点 $S$ 连向所有蓝色点，所有红色点连向汇点 $T$；对于其它点，直接按照四联通连边。那么最大流就是答案。$n,m\le 10^5$，暴力做是不行的，我们不妨转化为求最小割。那么在这种类棋盘状的图上，我们容易想到转化为对偶图来求解。显然我们只用考虑一个方向的答案即可，另一个方向是类似的。下面我们考虑竖直方向的答案。

不过最小割形成的路径显然可以不止一条。我们可以发现，通过一定调整，除了在边界上，其余部分的割形如一条直线。。而边上的贡献是一定会被算的。对割开的的连通块中所有点染成黑色或白色，每一行的颜色是一样的。那么对于每一行进行 DP，不同颜色行之间的转移就需要加上一段割形成的路径，其余贡献只与两边的颜色有关，那么简单 DP 即可求出。时间复杂度 $\mathcal O(n)$。

Easy version
 
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
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e5+10;
int n,m,q;
char L[N],R[N],U[N],D[N];
int f[N][2];
inline int solve(int n,int m,char *L,char *R,char *U,char *D)
{
    f[0][0]=f[0][1]=0;
    for(int i=1;i<=m;i++)f[0][0]+=(U[i]=='R'),f[0][1]+=(U[i]=='B');
    for(int i=1;i<=n;i++)
    {
        f[i][0]=min(f[i-1][0],f[i-1][1]+m)+(L[i]=='R')+(R[i]=='R');
        f[i][1]=min(f[i-1][1],f[i-1][0]+m)+(L[i]=='B')+(R[i]=='B');
    }
    for(int i=1;i<=m;i++)f[n][0]+=(D[i]=='R'),f[n][1]+=(D[i]=='B');
    return min(f[n][0],f[n][1]);
}
int main()
{
    scanf("%d %d %d %s %s %s %s",&n,&m,&q,L+1,R+1,U+1,D+1);
    printf("%d",min(solve(n,m,L,R,U,D),solve(m,n,U,D,L,R)));
    return 0;
}

接着考虑进阶版 CF1368H2 Breadboard Capacity (easy version)。多了修改操作。这个转移显然可以使用矩阵简单表示。那么问题是需要支持区间颜色翻转操作，并且只有一边的。但是我们转移与两边颜色都有关系。所以我们需要额外处理，翻转了某一边的答案，修改时直接交换即可。时间复杂度 $\mathcal O((n+q)\log n)$。

Hard version
 
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
#include<iostream>
#include<cstdio>
using namespace std;
const int N=1e5+10,INF=1e9;
template<class T>
inline void read(T &x)
{
    x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,m,q;
char sL[N],sR[N],sU[N],sD[N];
int L[N],R[N],U[N],D[N];
inline void ckmin(int &x,int y){x=(x<y)?x:y;}
struct Matrix
{
    int a[2][2];
    Matrix(): a{{INF,INF},{INF,INF}}{}
    auto& operator [](int x){return a[x];}
    const Matrix operator*(Matrix &t)const
    {
        Matrix res;
        ckmin(res[0][0],min(a[0][0]+t[0][0],a[0][1]+t[1][0]));
        ckmin(res[0][1],min(a[0][0]+t[0][1],a[0][1]+t[1][1]));
        ckmin(res[1][0],min(a[1][0]+t[0][0],a[1][1]+t[1][0]));
        ckmin(res[1][1],min(a[1][0]+t[0][1],a[1][1]+t[1][1]));
        return res;
    }
    void get(int x,int y){a[1][0]=(a[0][0]=x)+y,a[0][1]=(a[1][1]=2-x)+y;}
};
struct Seg
{
    struct Node
    {
        int l,r;
        Matrix v[4];
        int c1,c2;
        bool tag1,tag2;
    }tr[N<<2];
    void pushup(int x)
    {
        for(int i=0;i<4;i++)tr[x].v[i]=tr[x<<1].v[i]*tr[x<<1|1].v[i];
        tr[x].c1=tr[x<<1].c1+tr[x<<1|1].c1;
        tr[x].c2=tr[x<<1].c2+tr[x<<1|1].c2;
    }
    void update1(int x)
    {
        swap(tr[x].v[0],tr[x].v[1]),swap(tr[x].v[2],tr[x].v[3]);
        tr[x].c1=tr[x].r-tr[x].l+1-tr[x].c1;
        tr[x].tag1^=1;
    }
    void update2(int x)
    {
        swap(tr[x].v[0],tr[x].v[2]),swap(tr[x].v[1],tr[x].v[3]);
        tr[x].c2=tr[x].r-tr[x].l+1-tr[x].c2;
        tr[x].tag2^=1;
    }
    void pushdown(int x)
    {
        if(tr[x].tag1)update1(x<<1),update1(x<<1|1),tr[x].tag1=0;
        if(tr[x].tag2)update2(x<<1),update2(x<<1|1),tr[x].tag2=0;
    }
    void build(int x,int l,int r,int *a,int *b,int m)
    {
        tr[x].l=l,tr[x].r=r,tr[x].tag1=tr[x].tag2=0;
        if(l==r)
        {
            tr[x].c1=a[l],tr[x].c2=b[l];
            tr[x].v[0].get(a[l]+b[l],m),tr[x].v[1].get(!a[l]+b[l],m),
            tr[x].v[2].get(a[l]+!b[l],m),tr[x].v[3].get(!a[l]+!b[l],m);
            return ;
        }
        int mid=l+r>>1;
        build(x<<1,l,mid,a,b,m),build(x<<1|1,mid+1,r,a,b,m);
        pushup(x);
    }
    void flip1(int x,int l,int r)
    {
        if(l<=tr[x].l&&tr[x].r<=r)return update1(x);
        pushdown(x);
        int mid=tr[x].l+tr[x].r>>1;
        if(l<=mid)flip1(x<<1,l,r);
        if(r>mid)flip1(x<<1|1,l,r);
        pushup(x);
    }
    void flip2(int x,int l,int r)
    {
        if(l<=tr[x].l&&tr[x].r<=r)return update2(x);
        pushdown(x);
        int mid=tr[x].l+tr[x].r>>1;
        if(l<=mid)flip2(x<<1,l,r);
        if(r>mid)flip2(x<<1|1,l,r);
        pushup(x);
    }
}t[2];
inline int calc()
{
    int res=INF;
    ckmin(res,t[0].tr[1].v[0][0][0]+t[1].tr[1].c1+t[1].tr[1].c2);
    ckmin(res,t[0].tr[1].v[0][0][1]+t[1].tr[1].c1+(m-t[1].tr[1].c2));
    ckmin(res,t[0].tr[1].v[0][1][0]+(m-t[1].tr[1].c1)+t[1].tr[1].c2);
    ckmin(res,t[0].tr[1].v[0][1][1]+(m-t[1].tr[1].c1)+(m-t[1].tr[1].c2));

    ckmin(res,t[1].tr[1].v[0][0][0]+t[0].tr[1].c1+t[0].tr[1].c2);
    ckmin(res,t[1].tr[1].v[0][0][1]+t[0].tr[1].c1+(n-t[0].tr[1].c2));
    ckmin(res,t[1].tr[1].v[0][1][0]+(n-t[0].tr[1].c1)+t[0].tr[1].c2);
    ckmin(res,t[1].tr[1].v[0][1][1]+(n-t[0].tr[1].c1)+(n-t[0].tr[1].c2));

    return res;
}
int main()
{
    read(n,m,q);
    scanf("%s %s %s %s",sL+1,sR+1,sU+1,sD+1);
    for(int i=1;i<=n;i++)L[i]=(sL[i]=='R');
    for(int i=1;i<=n;i++)R[i]=(sR[i]=='R');
    for(int i=1;i<=m;i++)U[i]=(sU[i]=='R');
    for(int i=1;i<=m;i++)D[i]=(sD[i]=='R');
    t[0].build(1,1,n,L,R,m),t[1].build(1,1,m,U,D,n);
    printf("%d\n",calc());
    while(q--)
    {
        char op[10];
        scanf("%s",op);
        int x,y;
        read(x,y);
        if(op[0]=='L')t[0].flip1(1,x,y);
        else if(op[0]=='R')t[0].flip2(1,x,y);
        else if(op[0]=='U')t[1].flip1(1,x,y);
        else t[1].flip2(1,x,y);
        printf("%d\n",calc());
    }
    return 0;
}