打表观察数学性质 | #小苯的最短路#

数据范围可以视为 $+\infty$ , 因此任何计算的算法都无法解决, 先打表找找规律

打表代码

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e5 + 10;

vector<PII> g[N];

int dijkstra(int n) {
    static int d[N];
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    static bool st[N];
    memset(st, 0, sizeof st);
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, 1});

    while (q.size()) {
        auto [dis, u] = q.top();
        q.pop();

        if (st[u]) continue;
        st[u] = true;

        for (auto [w, v] : g[u]) {
            if (d[u] + w < d[v]) {
                d[v] = d[u] + w;
                q.push({d[v], v});
            }
        }
    }

    int ans = 0;
    for (int i = 2; i <= n; ++i) ans ^= d[i];
    return ans;
}

void solve(int cnt) {
    for (int i = 1; i <= cnt; ++i) g[i].clear();
    for (int i = 1; i <= cnt; ++i) {
        for (int j = 1; j <= cnt; ++j) {
            g[i].push_back({i ^ j, j});
        }
    }

    printf("%d->%d\n", cnt, dijkstra(cnt));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    for (int i = 1; i <= 1000; ++i) solve(i);

    return 0;
}

不难发现分为以下几种情况

$n \mod 4 = 0$ , 这种直接输出 $n$
$n \mod 4 = 1$ , 输出 $0$
$n \mod 4 = 2$ , 输出 $n + 1$
否则输出 $1$

AC代码

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

void solve() {
    int n;
    cin >> n;
    if (n % 4 == 0) {
        cout << n << '\n';
    }
    else if (n % 4 == 1) {
        cout << 0 << '\n';
    }
    else if (n % 4 == 2) {
        cout << n + 1 << '\n';
    }
    else cout << 1 << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;
    while (T--) solve();

    return 0;
}