2021 ICPC Asia Shenyang RC 题解

Posted on In ,

比赛链接

B - Bitwise Exclusive-OR Sequence

题意: 构造一个长度为 \(n\) 的序列 \(a_1, a_2, \cdots, a_n\), 满足 \(m\) 条限制, 每条限制形如 \(a_i\oplus a_j=w\). 其中 \(\oplus\) 为异或. 求所有满足条件的数列中数列和最小的一个的和.

数据范围: \(1\le n\le 10^5, 0\le m \le 2\times 10^5, 0\le w<2^{30}\).

展开题解

以 \(n\) 项数列为 \(n\) 个顶点, \(m\) 条限制为 \(m\) 条带权边建图.

不同位间不互相影响, 分开考虑.

考虑图中每个连通块(显然每个连通块之间互不干扰), 进行 \(0/1\) 染色. 对于该位值为 \(0\) 的边, 相邻顶点颜色相同; 值为 \(1\) 的边, 相邻顶点颜色不同. 若染色冲突, 则不存在这样的数列. 否则, 染色值为 \(0\) 和 \(1\) 的节点中有一个该位赋值为 \(0\), 一个赋值为 \(1\), 选择少的那个.

时间复杂度 \(O(B(n+m))\).

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
#include <algorithm>
#include <iostream>
using namespace std;
using ll = long long;
constexpr int MAXN = 1e5 + 5;
constexpr int MAXM = 2e5 + 5;
constexpr int B = 30;
int n, m;
struct Edge {
    int v, nxt, w;
}e[MAXM << 1];
int head[MAXN], cnt;
int fail, siz[2], col[MAXN];
ll ans;

void addedge(int u, int v, int w) {
    e[++cnt] = {v, head[u], w};
    head[u] = cnt;
}

void dfs(int u, int C, int b) {
    col[u] = C;
    siz[C]++;
    for(int i = head[u]; i && !fail; i = e[i].nxt) {
        int v = e[i].v, nc = C ^ ((e[i].w >> b) & 1);
        if(col[v] == -1) {
            dfs(v, nc, b);
        } else {
            if(nc != col[v])
                fail = 1;
        }
    }
}
int calc(int b) {
    for(int i = 1; i <= n; i++)
        col[i] = -1;
    int ret = 0;
    for(int i = 1; i <= n && !fail; i++)
        if(col[i] == -1) {
            siz[0] = siz[1] = 0;
            dfs(i, 0, b);
            ret += min(siz[0], siz[1]);
        }
    return fail ? 0 : ret;
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        addedge(u, v, w);
        addedge(v, u, w);
    }
    fail = 0;
    ans = 0;
    for(int i = 0; i < B && !fail; i++)
        ans += (ll)calc(i) << i;
    if(fail) {
        cout << -1 << '\n';
    } else {
        cout << ans << '\n';
    }
    return 0;
}

D - Cross the Maze

题意: 有一个 \(a\times b\) 个单元格组成的矩形迷宫, 最外围有墙. 里面有 \(n\) 个人, 初始位置分别在 \((s_{xi}, s_{yi})\); 他们要离开的话, 只能从 \(n\) 条绳索离开, 分别在 \((e_{xi}, e_{yi})\). 每个时刻, 每个人可以向四个方向走, 或留在原地. 每个绳索只能使用一次; 在任何时刻, 一个单元格不能停留两个人. 问让所有人离开的最短时间. 保证初始情况不能所有人全部立刻出去.

数据范围: \(1\le n\le 100\), \(1\le a\times b\le 100\).

展开题解

看到各种各样的奇怪的限制, 可以想到网络流.

首先, 对于最终答案, 可以进行二分. 可知最终答案 \(y\) 满足 \(1\le t\le ab\). (这个上界构造: 把迷宫蛇形展开成一行, 一起往一个方向走即可保证). 二分后改判断.

要判断 \(t\) 时间可否完成, 我们网络流建图. 首先, 对于格子, 按照时间建 \(t+1\) 层, 每层还拆成入点和出点. 记 \((t, x, y)\) 表示 \(t\) 时刻的 \((x, y)\) 点的入点, \([t, x, y]\) 为出点. 另外, 对于每根绳子, 我们也拆成入点和出点. 记 \(\langle i \rangle\) 为入点, \(\lbrace i\rbrace\) 为出点. 我们如下建图:

\(S\to (0, s_{xi}, s_{yi})\), 容量为 \(1\). 这意为一开始这里有个冒险者.(流量表示冒险者)

\((t, x, y)\to [t, x, y]\), 容量为 \(1\). 保证任意时刻每个格子只能有一个人在上面走.

\([t, x, y] \to (t+1, u, v)\), 容量为 \(1\), 其中 \((u, v)\) 可由 \((x, y)\) 一步抵达.

\([t, e_{xi}, e_{yi}] \to \langle i \rangle\), 容量为 \(1\), 意为这里有绳索.

\(\langle i\rangle\to \lbrace i \rbrace\), 容量为 \(1\), 保证每个绳索只能用一次.

\(\lbrace i\rbrace\to T\), 容量为 \(1\) 逃出升天.

然后跑最大流即可, 若最大流为 \(n\) 则可行.

构造方案直接沿着流的路径即可.

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
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

constexpr int MAXN = 105;
constexpr int MAXNODE = 30005;
constexpr int MAXEDGE = 150005;
constexpr int INF = 0x3f3f3f3f;
constexpr int dx[5] = {0, 0, 0, 1, -1};
constexpr int dy[5] = {0, 1, -1, 0, 0};
const string dir = "SRLDU";
int N, S, T;
struct Edge {
    int v, nxt, w;
}e[MAXEDGE];
int cur[MAXNODE], head[MAXNODE], cnt = 1;
void addedge(int u, int v, int w) {
    e[++cnt] = {v, head[u], w}; head[u] = cnt;
    e[++cnt] = {u, head[v], 0}; head[v] = cnt;
}

int dep[MAXNODE], que[MAXNODE], hd, tl, max_flow, ans, outnumber;
string way;
bool bfs() {
    for(int i = 0; i < N; i++) {
        dep[i] = 0;
        cur[i] = head[i];
    }
    hd = 1; tl = 0;
    que[++tl] = S;
    dep[S] = 1;
    while(hd <= tl) {
        int u = que[hd++];
        for(int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].v;
            if(e[i].w && !dep[v]) {
                dep[v] = dep[u] + 1;
                que[++tl] = v;
                if(v == T) return 1;
            }
        }
    }
    return 0;
}
int dfs(int u, int flow) {
    if(u == T) return flow;
    int rest = flow;
    for(int &i = cur[u]; i && rest; i = e[i].nxt) {
        int v = e[i].v;
        if(e[i].w && dep[v] == dep[u] + 1) {
            int k = dfs(v, min(rest, e[i].w));
            if(!k) dep[v] = 0;
            e[i].w -= k;
            rest -= k;
            e[i^1].w += k;
        }
    }
    return flow - rest;
}

void dinic() {
    int flow;
    max_flow = 0;
    while(bfs()) {
        while(flow = dfs(S, INF))
            max_flow += flow;
    }
}

int n, a, b, sx[MAXN], sy[MAXN], ex[MAXN], ey[MAXN];

int get_num(int t, int i, int j) {
    return t * a * b + i * b + j;
}
bool legal(int x, int y) {
    return x >= 0 && y >= 0 && x < a && y < b;
}
bool check(int t) {
    N = 2 * (t+1) * a * b + 2 * n + 2;
    S = N-2;
    T = N-1;
    for(int i = 0; i < N; i++)
        head[i] = 0;
    cnt = 1;
    for(int i = 1; i <= n; i++)
        addedge(S, get_num(0, sx[i], sy[i]), 1);
    for(int i = 0; i < (t+1) * a * b; i++)
        addedge(i, i + (t+1) * a * b, 1);
    for(int i = 1; i <= n; i++)
        for(int k = 0; k <= t; k++)
            addedge((t+1) * a * b + get_num(k, ex[i], ey[i]), 2 * (t+1) * a * b + i-1, 1);
    for(int i = 1; i <= n; i++) {
        addedge(2 * (t+1) * a * b + i-1, 2 * (t+1) * a * b + n + i-1, 1);
        addedge(2 * (t+1) * a * b + n + i-1, T, 1);
    }
    for(int k = 0; k < t; k++)
        for(int x = 0; x < a; x++)
            for(int y = 0; y < b; y++)
                for(int d = 0; d < 5; d++) {
                    int nx = x + dx[d], ny = y + dy[d];
                    if(!legal(nx, ny))
                        continue;
                    addedge((t+1) * a * b + get_num(k, x, y), get_num(k+1, nx, ny), 1);
                }
    dinic();
    return max_flow == n;
}

void getway(int x, int y) {
    way.clear();
    outnumber = 0;
    int t = 0;
    while(1) {
        int pos = get_num(t, x, y) + (ans+1) * a * b;
        for(int i = head[pos]; i; i = e[i].nxt)
            if(e[i^1].w == 1) {
                int v = e[i].v;
                if(v < (ans+1) * a * b) {
                    //case 1, next layer
                    int vx = v % (a * b) / b, vy = v % (a * b) % b;
                    for(int k = 0; k < 5; k++)
                        if(vx == x + dx[k] && vy == y + dy[k]) {
                            way += dir[k];
                            x = vx;
                            y = vy;
                            t++;
                            break;
                        }
                } else {
                    //case 2, outside
                    outnumber = v - 2 * (ans+1) * a * b + 1;
                    return ;
                }
            }
    }

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> a >> b;
    for(int i = 1; i <= n; i++) {
        cin >> sx[i] >> sy[i];
        sx[i]--; sy[i]--;
    }
    for(int i = 1; i <= n; i++) {
        cin >> ex[i] >> ey[i];
        ex[i]--; ey[i]--;
    }
    int L = 1, R = a * b;
    ans = -1;
    while(L <= R) {
        int M = (L + R) >> 1;
        if(check(M)) {
            ans = M;
            R = M - 1;
        } else
            L = M + 1;
    }
    check(ans);
    cout << ans << '\n';
    for(int i = 1; i <= n; i++) {
        getway(sx[i], sy[i]);//retrun way, outnumber
        cout << sx[i]+1 << ' ' << sy[i]+1 << ' ' << ex[outnumber]+1 << ' ' << ey[outnumber]+1 << ' ' << way;
        for(int i = way.length(); i < ans; i++)
            cout << 'P';
        cout << '\n';
    }
    return 0;
}

E - Edward Gaming, the Champion

水题, 不写题解了.

展开代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

string s;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> s;
    int cnt = 0;
    for(int i = 0; i < (int)s.length()-4; i++)
        if(s.substr(i, 5) == "edgnb")
            ++cnt;
    cout << cnt << '\n';
    return 0;
}

H - Line Graph Matching

题意: (略加转换)给一个 \(n\) 点 \(m\) 边的无向带权连通简单图, 每次允许的操作是选择共顶点的两条边并删去, 求删去的边权和的最大值.

数据范围: \(3\le n\le 10^5\), \(n-1\le m\le 2\times 10^5\).

展开题解

对于 \(m\) 是偶数的情况, 我们可以把全部边删完. 方案如下: dfs 一棵生成树, 从叶子开始向上删. 如果与点 \(u\) 相邻的边(包括树边和非树边)是偶数, 则把这些边两两一组全部删完. 否则, 留下一条通向父亲的树边, 到父亲处删. 依次类推, 可以全部删完.

对于 \(m\) 是奇数的情况, 则最后一定会剩下一条边(而且容易证明最后剩一条边最优). 枚举留哪条边 \(e\). 如果 \(e\) 是非割边, 则除去它的图仍是连通图, 可以; 如果 \(e\) 是割边, 则要求分成的两个连通块的边数都是偶数. 写个 Tarjan 即可. 时间复杂度 \(O(n+m)\).

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 <iostream>
#include <algorithm>
using namespace std;
using ll = long long;

constexpr int MAXN = 1e5 + 5;
constexpr int MAXM = 4e5 + 5;
constexpr int INF = 0x3f3f3f3f;
int n, m;
struct Graph {
    struct Edge {
        int v, w, nxt;
    }e[MAXM];
    int head[MAXN], cnt = 1;
    void addedge(int u, int v, int w) {
        e[++cnt] = {v, w, head[u]};
        head[u] = cnt;
    }
}G, S;

int dfn[MAXN], low[MAXN], _dfn, cut[MAXM];
int vis[MAXN], bcc[MAXN], _bcc, bcc_val[MAXN], minw, siz[MAXN];
ll totw;

void tarjan(int u, int toe) {
    dfn[u] = low[u] = ++_dfn;
    for(int i = G.head[u]; i; i = G.e[i].nxt) {
        if((i ^ 1) == toe)
            continue;
        int v = G.e[i].v;
        if(!dfn[v]) {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if(low[v] > dfn[u])
                cut[i] = cut[i ^ 1] = 1;
        } else
            low[u] = min(low[u], dfn[v]);
    }
}

void dfs(int u) {
    vis[u] = 1;
    bcc[u] = _bcc;
    for(int i = G.head[u]; i; i = G.e[i].nxt) {
        if(cut[i])
            continue;
        int v = G.e[i].v;
        if(vis[v])
            continue;
        dfs(v);
    }
}


void dfs2(int u, int fa) {
    siz[u] = bcc_val[u];
    for(int i = S.head[u]; i; i = S.e[i].nxt) {
        int v = S.e[i].v, w = S.e[i].w;
        if(v == fa) continue;
        dfs2(v, u);
        if(siz[v] % 2 == 0)
            minw = min(minw, w);
        siz[u] += 1 + siz[v];
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G.addedge(u, v, w);
        G.addedge(v, u, w);
        totw += w;
    }
    if(m % 2 == 0) {
        cout << totw << '\n';
        return 0;
    }
    minw = INF;
    for(int i = 1; i <= n; i++)
        if(!dfn[i]) //connected, so not necessary.
            tarjan(i, 0);
    for(int i = 1; i <= n; i++)
        if(!vis[i]) {
            ++_bcc;
            dfs(i);
        }
    for(int u = 1; u <= n; u++)
        for(int i = G.head[u]; i; i = G.e[i].nxt) {
            if(i & 1)
                continue;
            int v = G.e[i].v, w = G.e[i].w;
            if(bcc[u] == bcc[v]) {
                ++bcc_val[bcc[u]];
                minw = min(minw, w);
            } else {
                S.addedge(bcc[u], bcc[v], w);
                S.addedge(bcc[v], bcc[u], w);
            }
        }
    dfs2(1, 0);
    cout << totw - minw << '\n';
    return 0;
}

I - Linear Fractional Transformation

题意: 给复数域上的函数 \(f(z)=\dfrac{az+b}{cz+d}(a,b,c,d\in\mathbb C, ad-bc\ne 0)\), 其中 \(a,b,c,d\) 未知. 给 \(z_1, z_2, z_3, w_1, w_2, w_3\) 满足 \(f(z_i)=w_i\), 并给 \(z_0\), 求 \(f(z_0)\). 保证解存在且唯一.

展开题解

我们发现这是个分数结构, 故可约去个比例. 分两种情况讨论:

  1. 若 \(c=0\), 则 \(f(z)=\dfrac{az+b}{d}=a'z+b'\), 是个线性函数. 由 \(f(z_1)=w_1, f(z_2)=w_2\) 可求得 \(a', b'\), 再验证 \(f(z_3)=w_3\), 若满足, 则答案就是 \(f(z_0)=a'z_0+b'\).
  2. 若 \(c\ne 0\), 则上下约去 \(c\) 得 \(f(z)=\dfrac{a'z+b'}{z+d'}=w\), 故 \(z_ia'+b'-w_id'=z_iw_i(i=1, 2, 3)\), 高斯消元即可求得 \(a', b', d'\), 代入 \(f(z_0)\) 即可.
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
#include <algorithm>
#include <iostream>
#include <iomanip>
using namespace std;
using db = double;
constexpr db eps = 1e-8;
struct cp {
    db x, y;
    db Mo2()const {return x * x + y * y;}
    cp operator + (const cp &B)const {return {x + B.x, y + B.y};}
    cp operator - (const cp &B)const {return {x - B.x, y - B.y};}
    cp operator * (const cp &B)const {return {x * B.x - y * B.y, x * B.y + y * B.x};}
    cp operator / (const cp &B)const {return {(x * B.x + y * B.y) / B.Mo2(), (y * B.x - x * B.y) / B.Mo2()};}
};
istream& operator >> (istream &in, cp &B) {
    int a, b;
    in >> a >> b;
    B.x = a;
    B.y = b;
    return in;
}
ostream& operator << (ostream &out, const cp& B) {
    out << fixed << setprecision(8) << B.x << ' ' << B.y;
    return out;
}
cp z[4], w[4], a[4][5];
bool check1() {
    cp k = (w[1] - w[2]) / (z[1] - z[2]);
    cp b = w[1] - k * z[1];
    if((k * z[3] + b - w[3]).Mo2() < eps) {
        cout << k * z[0] + b << '\n';
        return 1;
    }
    return 0;
}
void Guass(int n) {
    int r = 1;
    for(int c = 1; c <= n; c++) {
        int num = r;
        for(int i = r+1; i <= n; i++)
            if(a[i][c].Mo2() > a[num][c].Mo2())
                num = i;
        if(num != r)
            for(int i = c; i <= n+1; i++)
                swap(a[r][i], a[num][i]);
        for(int i = r+1; i <= n; i++) {
            cp k = a[i][c] / a[r][c];
            for(int j = c; j <= n+1; j++)
                a[i][j] = a[i][j] - k * a[r][j];
        }
        r++;
    }
    for(int i = n; i >= 1; i--) {
        for(int j = i+1; j <= n; j++)
            a[i][n+1] = a[i][n+1] - a[j][n+1] * a[i][j];
        a[i][n+1] = a[i][n+1] / a[i][i];
    }
}
void work() {
    for(int i = 1; i <= 3; i++)
        cin >> z[i] >> w[i];
    cin >> z[0];
    if(check1())
        return;
    for(int i = 1; i <= 3; i++) {
        a[i][1] = z[i];
        a[i][2] = {1.0, 0.0};
        a[i][3] = {-w[i].x, -w[i].y};
        a[i][4] = w[i] * z[i];
    }
    Guass(3);
    cp A = a[1][4], B = a[2][4], D = a[3][4];
    cout << (A * z[0] + B) / (z[0] + D) << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while(T--)
        work();
    return 0;
}

J - Luggage Lock

题意: 行李箱上的密码 \(a_0a_1a_2a_3\) 转换为 \(b_0b_1b_2b_3\) 至少要几下? 允许的操作是使连续一段同时上移或下移.

愚蠢的原思路(不保证正确)

有个猜想(后面证明不完全正确): 我们可以算出每一位向上移和向下移的次数 \(up_i\) 和 \(down_i\). \(2^4\) 枚举每一位是会往上移还是向下移. 显然我们的操作不会横跨 \(up\) 和 \(down\) 的区间. 于是用和这题类似的做法即可完成.

但是, 这样做是错误的. 一个反例如下:

1
2
1
0000 6405

以我们上面的算法得到的是 \(11\), 但正确答案应该是 \(10\).

过程如下:

1
2
3
4
5
6
7
8
9
10
11
0000
9990
8880
7770
6660
6550
6449
6438
6427
6416
6405

我们发现第三位 \(0\) 绕了一圈! 所以我补上了个补丁, 也就是在上面枚举 \(2^4\) 外, 再 \(2^4\) 地枚举每次是调 \(up_i/down_i\) 还是 \(up_i/down_i+10\).

未证明正确性!

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
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

constexpr int MAXN = 5;
constexpr int INF = 0x3f3f3f3f;
int up[MAXN], down[MAXN];
string a, b;

void work() {
    cin >> a >> b;
    for(int i = 0; i < 4; i++) {
        up[i] = (int(b[i]) - int(a[i]) + 10) % 10;
        down[i] = (int(a[i]) - int(b[i]) + 10) % 10;
    }
    int U = 1 << 4;
    int ans = INF;
    for(int s = 0; s < U; s++) {
        for(int t = 0; t < U; t++) {
            for(int i = 0; i < 4; i++)
                if((t >> i) & 1)
                    up[i] += 10, down[i] += 10;
            int ret = 0;
            for(int i = 0; i < 4; i++) {
                if((s >> i) & 1) {
                    if(i == 0 || (~(s >> (i-1)) & 1))
                        ret += up[i];
                    else
                        ret += max(0, up[i] - up[i-1]);
                } else {
                    if(i == 0 || ((s >> (i-1)) & 1))
                        ret += down[i];
                    else
                        ret += max(0, down[i] - down[i-1]);
                }
            }
            for(int i = 0; i < 4; i++)
                if((t >> i) & 1)
                    up[i] -= 10, down[i] -= 10;
            ans = min(ans, ret);
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while(T--)
        work();
    return 0;
}
一个好做法

我们发现, 如果 \(b_i-a_i\) 全部相同, 则两种情况等价. 所以本质不同的方案只有 \(10000\) 种. 直接预处理 bfs 再 \(O(1)\) 处理询问即可.

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
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;
constexpr int MAXV = 9999;
constexpr int pow10[] = {1, 10, 100, 1000};
int step[MAXV+1];
queue<int> que;
void upbit(int &v, int b) {
    int ori = (v / pow10[b]) % 10;
    int now = (ori == 9 ? 0 : ori + 1);
    v += (now - ori) * pow10[b];
}
void downbit(int &v, int b) {
    int ori = (v / pow10[b]) % 10;
    int now = (ori == 0 ? 9 : ori - 1);
    v += (now - ori) * pow10[b];
}
void init() {
    for(int i = 0; i <= MAXV; i++)
        step[i] = -1;
    que.push(0);
    step[0] = 0;
    while(que.size()) {
        int u = que.front(); que.pop();
        for(int i = 0; i < 4; i++)
            for(int j = i; j < 4; j++) {
                int v = u;
                for(int k = i; k <= j; k++)
                    upbit(v, k);
                if(step[v] == -1) {
                    step[v] = step[u] + 1;
                    que.push(v);
                }
                v = u;
                for(int k = i; k <= j; k++)
                    downbit(v, k);
                if(step[v] == -1) {
                    step[v] = step[u] + 1;
                    que.push(v);
                }
            }
    }
}
string a, b;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int T;
    cin >> T;
    while(T--) {
        cin >> a >> b;
        int x = 0;
        for(int i = 0; i < 4; i++)
            x += ((b[i] - a[i] + 10) % 10) * pow10[i];
        cout << step[x] << '\n';
    }
    return 0;
}