每日一水第46弹(12-world-final-keys)

https://icpcarchive.ecs.baylor.edu/external/60/6031.pdf

题意:有一些钥匙环和钥匙构成的一坨东西,每把钥匙都会存在于一个钥匙环内,钥匙环跟钥匙环有可能会相互连接构成一棵树。当然也可能会是森林,钥匙和环最多都只有26种(A-Z,a-z)。拿下一把钥匙,插入一把钥匙,断开两个环之间的连接,连接两个环,这四种操作的代价都是1。现在要求将两种钥匙(A-M, N-Z)分开到两个连通块里面。求最少的钥匙操作的代价,以及最少的环操作的代价。先满足钥匙操作最少,再满足环操作最少。

这题现场赛过的很少,难点在于很容易推出一些错误的贪心性质,还有一些比较tricky的数据。

 

首先,可以观察出,有矛盾的环最多只有13个,那这些矛盾的环里面肯定会有一种钥匙出来,再到别的环里面去。

所以基本的想法就是暴力枚举每个矛盾环里面哪种钥匙出来,然后再枚举取出来的两种钥匙分别放到哪两个环里面。

有一个问题是,如果枚举放到的环里面跟要放的钥匙矛盾,是不是就不用考虑这种方案了,答案是否定的。因为要是整个连通块只有每个环里面都有某一种钥匙(0颜色),其中一个环多了一种钥匙,而且多的钥匙(1颜色)的数量小于另一种,显然,我们要将1颜色的钥匙拿出来,然而这个时候其他环都是0颜色,所以显然有一个环里面的钥匙要先拿出来。

上面的暴力解决了第一个最小的钥匙操作的问题,第二个最小的环操作则可以通过一次树dp维护跟当前根联通的集合的颜色来搞。

 

其实像这种数据规模小的题,有些地方能暴力即暴力,一开始以为只有一种钥匙的环不会取出里面的钥匙,实在是容易被坑到。

 

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
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define mp std::make_pair
const int INF = (int)1e7;
const int N = 30;
bool tree[N][N];
bool key[N][N];
int dp[N][3];
bool ring[N];
int tot; //有矛盾的环的数量
int conflict[13];
bool is_conflict[N];
int color[N];
int n;
int v[N];
int  num[N][2];
int has_color;
int sum_of_color[2];
std::vector<int> edge[N];
pii ret;
bool flag;
bool used[N];
bool operator < (const pii &a, const pii &b)
{
    return a.first < b.first ¦¦ a.first == b.first && a.second < b.second;
}
void init()
{
    for(int i = 0; i < 26; i++) {
        edge[i].clear();
    }
    tot = 0; 
    memset(used, false, sizeof(used));
    memset(num, 0, sizeof(num));
    memset(tree, 0, sizeof(tree));
    memset(ring, false, sizeof(ring));
    memset(is_conflict, false, sizeof(is_conflict));
    memset(sum_of_color, 0, sizeof(sum_of_color));
    memset(key, false, sizeof(key));
}
void add_ring_edge(char a, char b)
{
    tree[a-'a'][b-'a']=tree[b-'a'][a-'a']=1;
}
void add_ring(char a)
{
    ring[a-'a'] = true;
}
void connect(char a, char b)
{
    if(islower(a)) {
        add_ring(a);
    }
    if(islower(b)) {
        add_ring(b);
    }
    if(islower(a) && islower(b)) {
        add_ring_edge(a, b);
    } else if(islower(a) && isupper(b)) {
        key[a-'a'][b-'A']=true;
        sum_of_color[b >= 'N'] ++;
    } else if(isupper(a) && islower(b)){
        key[b-'a'][a-'A']=true;
        sum_of_color[a >= 'N']++;
    } else {
        while(1);
    }
}
//暴力枚举怎么把钥匙拆开
//最多只有13个环上有不同的钥匙
//拆粗来之后枚举放在哪两个钥匙环上
//然后就跟钥匙无关了 可以进行一次树形DP
//dp[u][i]表示u子树内跟u联通的块是i颜色,没颜色也是一种颜色 dp值表示满足条件的最小代价
void dfs(int u, int fa)
{
    used[u] = true;
    has_color ¦= (color[u] != 2);
    dp[u][color[u]] = 0;
    if(color[u] == 2) {
        dp[u][0] = dp[u][1] = 0;
    }
    for(auto v: edge[u]) {
        if(v == fa) {
            continue;
        }
        dfs(v, u);
        int cut = INF;
        for(int i = 0; i < 3; i++) {
            cut = std::min(cut, dp[v][i] + 1);
        }
        for(int i = 0; i < 3; i++) {
            dp[u][i] += std::min(cut, std::min(dp[v][i], dp[v][2]));
        }
    }
}
pii gao(int A, int B)
{
    pii ret = mp(INF, INF);
  //  printf("tot=%d\n",tot);
    for(int i = 0; i < (1 << tot); i++) {
        memset(color, -1, sizeof(color));
        for(int j = 0; j < tot; j++) {
            color[conflict[j]] = (i >> j & 1);
        }
        //不能和状态压缩枚举的状态产生矛盾
        if(color[A] == 1 ¦¦ color[B] == 0) {
            continue;
        }
        color[A] = 0; color[B] = 1;
        for(int j = 0; j < n; j++) {
            if(color[j] == -1) {
                color[j] = 2;
            }
        }
        int pre = 0;
        //钥匙的操作要提前算,分成两部分
        //1:从矛盾的钥匙环里面取出放入到别的环
        //2:假如一些钥匙放到一个不矛盾的环(A,B)里面产生了新的矛盾,则要将原有的钥匙先拿出来再放到别的环里
        //神坑啊!!!
        for(int j = 0; j < n; j++) {
            if(color[j] != 2) {
                pre += num[j][!color[j]] * 2;
            }
            if(color[j] == 2 && (num[j][0]+num[j][1])) {
                color[j] = num[j][1] > 0;
            } 
        }
        /*
        for(int j = 0; j < n; j++) {
            printf("color[%d]=%d\n",j,color[j]);
        }
        */
        if(pre > ret.first) {
            continue;
        }
        for(int j = 0; j < n; j++) {
            for(int k = 0; k < 3; k++) {
                dp[j][k] = INF;
            }
        }
        memset(used, false, sizeof(used));
        int second = 0, block = 0;
        for(int j = 0; j < n; j++) {
            if(!used[j]) {
                has_color = 0;
                dfs(j, -1);
                if(has_color) {
                    int mi = INF;
                    for(int k = 0; k < 3; k++) {
                        mi = std::min(mi, dp[j][k]);
                    }
                    //   切了mi次 差生了mi+1个联通块
                    second += mi;
                    block += mi + 1;
                }
            }
        }
        // block 个联通块合并成两个联通块
        second += block - 2;
        ret = std::min(ret, mp(pre, second));
    }
    return ret;
}
void prepare()
{
    bool tmp[N][N];
    memset(tmp, false, sizeof(tmp));
    int cnt = 0;
    int a[N];
    for(int i = 0; i < 26; i++) {
        if(ring[i]) {
            for(int j = 0; j < 26; j++) {
                tmp[cnt][j] = key[i][j];
            }
            a[cnt] = i;
            cnt++;
        }
    }
    n = cnt;
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) if(tree[a[i]][a[j]]){
                      //  printf("i=%d j=%d %d %d\n", i, j,a[i],a[j]);
            edge[i].push_back(j);
            edge[j].push_back(i);
        }
    }
    memcpy(key, tmp, sizeof(tmp));
    memset(v, -1, sizeof(v));
    flag = false;
    for(int i = 0; i < n; i++) {
        bool flag1 = false, flag2 = false;
        for(int j = 0; j < 13; j++) {
            if(key[i][j]) {
                num[i][0]++;
                flag1=true;
            }
        }
        for(int j = 13; j < 26; j++) {
            if(key[i][j]) {
                num[i][1]++;
                flag2=true;
            }
        }
        if(flag1 && flag2) {
            conflict[tot++] = i;
            is_conflict[i] = true;
            flag = true;
        } else if(flag1) {
            v[i] = 0;
        } else if(flag2) {
            v[i] = 1;
        }
    }
    /*
        for(int i = 0; i < n; i++) {
            printf("i=%d %d %d\n", i, num[i][0], num[i][1]);
        }
        */
}
void solve() // 分别放到A和B
{
    if(flag && n < 2) {
        printf("impossible\n");
        return ;
    }
    pii ret = mp(INF, INF);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) if(i != j) {
           // if(!(i == 1 && j == 3)) continue;
            pii tmp = gao(i, j);
            if(tmp < ret) {
                ret = tmp;
            }
        }
    }
    printf("%d %d\n", ret.first, ret.second);
}
void go(int u)
{
    used[u] = true;
    for(int v : edge[u]) {
        if(!used[v]) {
            go(v);
        }
    }
}
int main()
{
    //freopen("F.in","r",stdin);
    //   freopen("F.out","w",stdout);
    char s[10];
    int ca = 1;
    init();
    while(scanf("%s", s) == 1) {
        if(s[0] == '0') {
            printf("Case %d: ", ca++);
            prepare();
            if(!sum_of_color[0] && !sum_of_color[1]) {
                printf("0 0\n");
                init();
                continue;
            }
            if(!sum_of_color[0] ¦¦ !sum_of_color[1]) {
                memset(used, false, sizeof(used));
                int sum = 0, cnt = 0;
                for(int i = 0; i < n; i++) {
                    if(num[i][0] + num[i][1] && !used[i]) {
                        cnt++;
                        go(i);
                    }
                }
                printf("0 %d\n", cnt-1);
                init();
                continue;
            }
            solve();
            init();
        } else {
            connect(s[0], s[1]);
        }
    }
    return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注