A

思路

令 ，则答案必然在 和 之间，两者比较一下谁离 最近,就是答案了。

代码

#include<bits/stdc++.h>
using namespace std;
long long x,ans1,ans2,sq;
int main(){
    scanf("%lld",&x);
    sq=(long long)sqrt(x);
    ans1=sq*sq;
    ans2=(sq+1)*(sq+1);
    if(abs(ans1-x)<abs(ans2-x)) printf("%lld",ans1);
    else printf("%lld",ans2);
    return 0;
}

B

前言

开始没想到异或这么多的性质，于是认为对于每个点，可以和它连边的点的点权 (证明： 即）,于是每次将同一个点权的点放在一起，跑一遍dijkstra，然后超时了……(赛后重新提交，显示case通过率为32.00%）
放一下当初代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10,MAXLIMIT=1048577;
int n,q,a[MAXN],ans,k,x,y;
vector<int> m[MAXLIMIT];
bool vis[MAXN];
int dis[MAXN];
int main(){
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        m[a[i]].push_back(i);
    }
    while(q--){
        scanf("%d %d %d",&k,&x,&y);
        memset(dis,~0xcf,sizeof(dis));
        memset(vis,0,sizeof(vis));
        dis[x]=0;
        vis[x]=1;
        ans=MAXN+10;
        priority_queue <pair<int, int> > q;
        q.push(make_pair(0,x));
        while(!q.empty()&&ans>n){
            int t=q.top().second; q.pop();
            int togo=a[t]^k;
            for(int i=0;i<m[togo].size();i++){
                if(!vis[m[togo][i]]){
                    dis[m[togo][i]]=dis[t]+1;
                    if(m[togo][i]==y){
                        ans=dis[t]+1;
                        break;
                    }
                    vis[m[togo][i]]=1;
                    q.push(make_pair(dis[m[togo][i]],m[togo][i]));
                }
            }
        }
        if(ans<=n) printf("%d\n",ans);
        else printf("-1\n");
    }
    return 0;
}

思路

实际上很简单，答案只有 -1,1,2 三种，我们注意到：对于每个点，和它连边的只有一种点权，假设这种点为 ,则能和 连边的点权为 ,这意味着，对于每两个点 , , 要不是 则答案为1 就是 且存在 使 则答案为 2 （先通过中转到 ,再去 ），否则，答案为-1。

代码

一下子变简单了。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
int n,q,a[MAXN],k,x,y,times[(1<<20)+10];
int main(){
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),times[a[i]]++;//记录每个权值出现次数
    while(q--){
        scanf("%d %d %d",&k,&x,&y);
        if((a[x]^a[y])==0&&times[(a[x]^k)]>0) printf("2\n");//注意，必须要有中转的点才可输出2
        else if((a[x]^a[y]^k)==0) printf("1\n"); //可以直接连边
        else printf("-1\n");//不能到达
    }
    return 0;
}