题解 | #小苯的最短路#

更好的阅读体验可看CSDN

思路

用dijkstra写一个打表，打表代码

#include <bits/stdc++.h>
#define maxOf(a) *max_element(a.begin(),a.end())
#define minOf(a) *min_element(a.begin(),a.end())
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N=100;
vector<pii> G[N];
int n;
bool bl[N];
ll dis[N];
void dijkstra()
{
    memset(bl,0,sizeof(bl));
    memset(dis,0x3f,sizeof(dis));
    priority_queue<pii,vector<pii>,greater<pii>> q;
    q.push({0,1});
    dis[1]=0;
    while(!q.empty())
    {
//        printf("%d %d\n",q.top().first,q.top().second);//debug
        int u=q.top().second;
        q.pop();
        if(bl[u])
        {
            continue;
        }
        bl[u]=true;
        for(auto [v,w]:G[u])
        {
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                q.push({dis[v],v});
            }
        }
    }
}

void solve()
{
    printf("%d -> ",n);
    for(int i=1;i<=n;i++)
    {
        G[i].clear();
    }
//    printf("building graph:\n");
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i!=j)
                G[i].push_back({j,i^j});
//            printf("%d ",i^j);
        }
//        printf("\n");
    }
//    printf("dijkstra:\n");
    dijkstra();
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
//        printf("%lld ",dis[i]);
        if(i==1)
            ans=dis[i];
        else
            ans^=dis[i];
    }
    printf("%lld\n",ans);
}

int main()
{
    for(n=1;n<=99;n++)
    {
        solve();
    }
    return 0;
}

输出的结果是

1 -> 0
2 -> 3
3 -> 1
4 -> 4
5 -> 0
6 -> 7
7 -> 1
8 -> 8
9 -> 0
10 -> 11
11 -> 1
12 -> 12
13 -> 0
14 -> 15
15 -> 1
16 -> 16
17 -> 0
18 -> 19
19 -> 1
20 -> 20
......

所以规律显然意见，每四个数是0,i+1,1,i，直接输出就行

代码

#include <bits/stdc++.h>
#define maxOf(a) *max_element(a.begin(),a.end())
#define minOf(a) *min_element(a.begin(),a.end())
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void solve()
{
    ll n;
    scanf("%lld",&n);
    if(n%4==0)
    {
        printf("%lld\n",n);
    }
    else if(n%4==1)
    {
        printf("0\n");
    }
    else if(n%4==2)
    {
        printf("%lld\n",n+1);
    }
    else
    {
        printf("1\n");
    }
}

int main()
{
    int T=1;
    scanf("%d",&T);
    while(T--)
    {
        solve();
    }
    return 0;
}