题解 | #小苯的最短路#

凡是相关的问题，都优先考虑能不能打表

打个dijkstra的表

发现 于是问题转化成

如果 是奇数，

打一个 前缀和表

不难发现 如果 是奇数，并且形如xxxx 11，即有多于 2 位的 1，res = 0 如果仅有 1 位 1，xxxx 0 1，res = 1

如果 是偶数，并且形如xxxx 00，对称的，那么res = n本身 否则，只有xxxx 10，只有 1 个 0，res = n+1

void dijkstra(int s, vector<ll> &f) {
    vector<int> vis(maxn, 0);
    priority_queue<PLL, vector<PLL>, greater<PLL> > heap;
    f[s] = 0;
    heap.push(PLL{f[s], s});

    while (heap.size()) {
        auto x = heap.top().second;
        heap.pop();

        if (vis[x]) continue;
        vis[x] = true;

        for (auto [y, w] : G[x]) {
            if (f[y] > f[x] + w) {
                f[y] = f[x] + w, heap.push(PLL{f[y], y});
            }
        }
    }
}

void solve() {
    int n;
    cin >> n;

    // for (int i = 1; i <= n; i++) {
    //     for (int j = i+1; j <= n; j++) {
    //         auto w = i ^ j;
    //         G[i].push_back({j, w}), G[j].push_back({i, w});
    //     }
    // }

    // vector<ll> f(maxn, inf);
    // dijkstra(1, f);

    // for (int i = 1; i <= n; i++) {
    //     // printf("1->%d:  ", i);
    //     // printf("%lld\n", f[i]);
    //     assert(f[i] == (1 ^ i));
    // }

    // ll ans = 0;
    // for (int i = 1; i <= n; i++) ans ^= i, printf("->%d:   %lld\n", i, ans);
    // puts("");

    // printf("->%d:  %lld\n", n, ans);

    if (n == 1) {
        puts("0");
        return;
    }

    int ans = 0;
    auto h = 31 - __builtin_clz(n);

    if (n % 2 == 0) {
        auto tail = 1;
        if (((n >> 1) & 1) == 0) tail += 1;

        if (tail >= 2) ans = n;
        else ans = n + 1;
    }
    else {
        if (n == (1<<(h+1)) - 1) ans = 0;
        else {
            auto tail = 1;
            if ( ((n >> 1) & 1) == 1 ) tail += 1;

            if (tail >= 2) ans = 0;
            else ans = 1;
        }
    }

    if (n % 2) ans ^= 1;

    printf("%d\n", ans);


    // int ans = 0;
    // auto hi = n, lo = (1<<h);
    // auto cnt = hi - lo + 1;
    // if (cnt % 2) ans |= (1<<h);

    // for (int p = h-1; p >= 1; p--) {
    //     hi = (1<<(p+1)) - 1;
    //     lo = (1<<p);

    //     auto cnt = hi - lo + 1;
    //     if (cnt % 2) ans |= (1<<p);
    // }

    // if (n % 2) ans ^= 1;
    // printf("->%d:  %d\n", n, ans);
}

int main() {
    freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false), cin.tie(0);
    int cas;
    cin >> cas;
    while (cas--) {
        solve();
    }
}

/*

->1:  1
->2:  3
->4:  4
->5:  1
->15:  0
->32:  32




->1:   1
->2:   3
->3:   0
->4:   4
->5:   1
->6:   7
->7:   0
->8:   8
->9:   1
->10:   11
->11:   0
->12:   12
->13:   1
->14:   15
->15:   0
->16:   16
->17:   1
->18:   19
->19:   0
->20:   20
->21:   1
->22:   23
->23:   0
->24:   24
->25:   1
->26:   27
->27:   0
->28:   28
->29:   1
->30:   31


*/