小苯的最短路

题目链接： https://ac.nowcoder.com/acm/problem/284229
思路：
结论题，首先需要推导的是怎样走最短，是直接从 1 走到 i 呢还是绕路经过某些点到 i 呢。
假设我们通过点 j 到达点 i 吧。那么花费就是 ，由 可得：
所以可知直接从 1 走到 i 最短。所以 。所以

对于前半部分，如果 n 为偶数则为 0，如果 n 为奇数则为 1；对于后半部分，连续整数从 1 到 n 的异或结果有个规律，令 ，

• x=0 时，f (n)=n.
• x=1 时，f (n)=1.
• x=2 时，f (n)=n+1.
• x=3 时，f (n)=0.
  代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
void solve()
{
    int n;
    cin>>n;
    int x=n%2;
    if(n%4==0) cout<<(n^x);
    else if(n%4==1)cout<<(1^x);
    else if(n%4==2)cout<<((n+1)^x);
    else if(n%4==3)cout<<(0^x);
    cout<<endl;
}
signed main(){
    IOS
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
}