逐渐摸索套路中

Expogo

起始点为$(0,0)$，目标点为$(x,y)$，第$i$次移动可以向上下左右任意一个方向移动$2^(i-1)$格，问最少移动次数到达目标点的操作序列。

首先设 $x+y$ 二进制下最高位为$i$，那么在 $i$ 步内一定能移动到终点，如果更多次数的话，意味着需要反向移动抵消一些步。
对于 $x+y$ 的二进制表示，如果从低到高每位都为$1$，那么意味着 $x\&y=0$，只需要分别把二进制位分别填入 $x,y$ 即可。
如果有若干位为$0$的话，首先想到对于 $2^{i+1}-1$，如果减去 $2^x, (x\in [1,i])$，那么 $x+y - x|y = 2\times 2^x$，因此计算 $x+y- x|y$，再除$2$，此时为$1$的位就是与$x,y$异号的位。
那么现在知道了哪些需要正向跳，哪些需要反向跳。从$0$到$i$枚举，如果某一位在$x$中为$1$，将其根据正负号赋$W or E$，并改变$x$的值；如果在$y$中为$1$，做同样的操作；如果$x,y$中都为$1$，此时无法满足要求，不可行。
$O(n)$

Expogo.cpp
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int T;
    cin >> T;
    for (int cas = 1; cas <= T; ++cas) {
        int x, y, fx = 0, fy = 0;
        cin >> x >> y;
        if (x < 0) fx = 1, x = -x;
        if (y < 0) fy = 1, y = -y;
        ll tot = 1;
        int lim = 0;
        while (tot <= x + y) tot <<= 1, ++lim;
        tot -= 1;
        int sp = tot ^ (x + y);
        sp >>= 1;
        string ans;
        for (int i = 0; i < lim; ++i) {
            if (x >> i & 1) {
                if (y >> i & 1) {
                    ans = "IMPOSSIBLE";
                    break;
                }
                if (sp >> i & 1) {
                    x += 1 << i;
                    if (fx) ans.push_back('E');
                    else ans.push_back('W');
                } else {
                    if (fx) ans.push_back('W');
                    else ans.push_back('E');
                }
            } else if (y >> i & 1) {
                if (sp >> i & 1) {
                    y += 1 << i;
                    if (fy) ans.push_back('N');
                    else ans.push_back('S');
                } else {
                    if (fy) ans.push_back('S');
                    else ans.push_back('N');
                }
            } else {
                ans = "IMPOSSIBLE";
                break;
            }
        }
        printf("Case #%d: %s\n", cas, ans.c_str());
    }
    return 0;
}

Blindfolded Bullseye

有一个左上角右下角为$(-1e9,1e9)$和$(1e9,-1e9)$的大正方形，有一个半径为$R$，圆心为$(x,y)$的圆形，每次询问一个点，告诉这个点在圆内（包括边界），在圆外或是在圆心，要求在 $300$ 次内询问到圆心坐标。

因为$\frac {10^9}{2} \leq R$，因此每隔$\frac {10^9}{2}$的距离就询问一下，一定能问到一个点在圆上。
当询问到一个点在圆上后，我们就可以通过$4$次二分询问到相互垂直的两条弦$(x1,y),(x2,y),(x,y1),(x,y2)$，那么圆心就应当位于$(\frac {x1+x2}{2},\frac {y1+y2}{2})$。但是由于上面问到的点只能是整数，圆心可能不太精确，因此以上面的答案为中心，询问一个小范围即可。
$O(\log n)$

Blindfolded Bullseye.cpp
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
#include <bits/stdc++.h>
using namespace std;

int main() {
    auto sd = [&](int x, int y) {
        cout << x << ' ' << y << endl;
        os << x << ' ' << y << endl;
        string s;
        cin >> s;
        if (s == "CENTER")
            return 1;
        if (s == "HIT")
            return 2;
        return 0;
    };

    int T, a, b;
    cin >> T >> a >> b;
    for (int cas = 1; cas <= T; ++cas) {
        int x, y, f = 0;
        string s;
        for (x = -1e9 + 1e9 / 2; x < 1e9; x += 1e9 / 2) {
            for (y = -1e9 + 1e9 / 2; y < 1e9; y += 1e9 / 2) {
                cout << x << ' ' << y << endl;
                cin >> s;
                if (s == "CENTER") goto nex;
                if (s == "HIT") {
                    f = 2;
                    break;
                }
            }
            if (f) break;
        }
        if (f == 2) {
            int l = -1e9, r = x, x1, x2, y1, y2, mid, res;
            while (l <= r) {
                mid = (l + r) / 2;
                if (res = sd(mid, y)) {
                    if (res == 1) goto nex;
                    r = mid - 1;
                    x1 = mid;
                } else
                    l = mid + 1;
            }
            l = x, r = 1e9;
            while (l <= r) {
                mid = (l + r) / 2;
                if (res = sd(mid, y)) {
                    if (res == 1) goto nex;
                    l = mid + 1;
                    x2 = mid;
                } else
                    r = mid - 1;
            }
            l = -1e9, r = y;
            while (l <= r) {
                mid = (l + r) / 2;
                if (res = sd(x, mid)) {
                    if (res == 1) goto nex;
                    r = mid - 1;
                    y1 = mid;
                } else
                    l = mid + 1;
            }
            l = y, r = 1e9;
            while (l <= r) {
                mid = (l + r) / 2;
                if (res = sd(x, mid)) {
                    if (res == 1) goto nex;
                    l = mid + 1;
                    y2 = mid;
                } else
                    r = mid - 1;
            }
            x = (x1 + x2) / 2;
            y = (y1 + y2) / 2;
        } else
            return 3;
        for (int i = -2; i <= 2; ++i) {
            for (int j = -2; j <= 2; ++j) {
                cout << x + i << ' ' << y + j << endl;
                cin >> s;
                if (s == "CENTER") goto nex;
            }
        }
        nex:;
    }
    return 0;
}

Join the Rank

有一个序列是 $1,2,3…R,1,2,3…R,…….1,2,3…R$，每次操作可以把序列分为$a,b,c$三段，然后组合成$bac$，问最少几次使序列被从小到大排好序，和操作的序列。

可以发现如果把相同的一段数字看成一个数字的话，每次最多合并两个数字，那么做法就是 $12 | 34561 | 23…..$这样切，每次都能合并两个数。特殊的是合并成 $512345$ 这种情况，只需要 $5 | 1234 | 5$这样再操作一次即可。
由于$r,c$都很小，直接暴力做就可以了，$O(\sum_{i = 1}^{RC} {i})$（不太确定）。

Join the Rank.cpp
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
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

int main() {
    int T;
    cin >> T;
    for (int cas = 1; cas <= T; ++cas) {
        int r, c, f = 0;
        cin >> r >> c;

        string s;
        for (int i = 0; i < c; ++i) {
            for (int j = 0; j < r; ++j) {
                s.push_back(j);
            }
        }
        vector<pii> ans;
        while (1) {
            vector<char> p;
            int i, a, b = -1;
            p.emplace_back(s[0]);
            for (i = 1; i < r * c; ++i) {
                if (s[i] != s[i - 1]) {
                    if (p.size() == 2) {
                        a = i;
                        break;
                    }
                    p.emplace_back(s[i]);
                }
            }
            for (; i < r * c; ++i) {
                if (s[i - 1] == p[0] && s[i] == p[1]) {
                    b = i;
                    break;
                }
            }
            if (b == -1) break;
            ans.emplace_back(a, b);
            s = s.substr(a, b - a) + s.substr(0, a) + s.substr(b);
        }
        if (!is_sorted(s.begin(), s.end())) {
            ans.emplace_back(c - 1, r * c - 1);
        }
        printf("Case #%d: %d\n", cas, ans.size());
        for (auto &i : ans)
            printf("%d %d\n", i.first, i.second - i.first);
    }
    return 0;
}