A median
如果保证每个数互不相同，直接统计每个序列中小于 \(x\) 和大于 \(x\) 的数量就好。
但是有重复的数，答案会算重，考虑给每一个数一个独一无二的特征，保证满足大小关系，直接给所有数排个序后，记录排序后的位置即可。时间复杂度 \(\mathcal{O}(n\log n)\)。
B travel
当 \(k\to\infty\) 时，而 \(f(x,y)\) 不为常量，则一定有环，两种情况：存在二元及以上的环，或者存在一条有两个自环的路径。拓扑可以同时处理这两个东西。
C game
首先如果只有一个数是必胜，考虑加进来一个数。
如果有两个 \(1\) 是必败，如果不是两个 \(1\)，可以理解为谁在两个 \(1\) 的局面时成为先手，谁就必败，可以将两个数同时减去 \(1\),同理，之后的局面也能减去 \(1\)，故可以直接减去较小数，剩下另一个。得出两个数的结论：当且仅当两数相等时，是先手必败局面。
考虑三个数的情况，根据差分的和小于最大值，先手可以对最大值进行操作，使得剩下两个数相等，所以三个数的时候是先手必胜。
推广到四个数：与两个数同理，谁在两个 \(1\) 的局面时成为先手，谁就必败，四个数同时减去最小值，如果剩三个，先手必胜，如果剩两个，此时最小值有两个，考虑剩下两个是否相等，如果剩一个，先手必胜，不剩也是先手必胜，所以我们得到四个数的结论：当且仅当相同的数两两配对时，先手必败。
后面的推广也类似，所以得出结论：当且仅当 \(n\) 为偶数且相同的数两两配对时，先手必败。
考虑严谨的证明：
- 由必败状态操作后，一定会对数做出更改，无法回到必败状态。
- 当前是必胜状态，如果 \(n\) 为奇数，根据差分的和小于最大值，先手可以对最大值进行操作，可以让所有数两两相等配对，剩下偶数个数。
- 当前是必胜状态，如果 \(n\) 为偶数，根据差分的和小于最大值，先手可以对最大值进行操作，可以让 \(n-2\) 个数两两相等配对，剩下一个最小的数，而最大数经过操作之后一定可以等于这个最小数，这个直接考虑把数画成柱状图证明。
D counter
像最短路，考虑中转点，假设由 \(l\) 到 \(r\)，由于每次最多移动 \(9\)，所以一定会经过 \([mid-4,mid+4]\) 中的某些点，然后就可以二合并，考虑猫树分治即可，路径一定不会超出目标过远，差不多三十左右的距离。当距离不远时，查询效率极其低下，这时直接暴力即可。
#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define fo(i,s,t) for(int i=s;i<=t;++i)
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=1e5+300,LEN=1e5+30,inf=1e9;
int n,to[20][10][N],re[20][10][N],lastans,dis[N];
std::vector<int> in[N],out[N];
inline void build(int p,int l,int r){
if(r-l<=30)return ;
if(l==r)return;
int fal=std::max(0,l-30),far=r+30;
int mid=l+r>>1;
int L=std::max(l,mid-4),R=std::min(r,mid+4);
for(int s=L;s<=R;++s){
std::fill(dis+fal,dis+far+1,-1);
std::queue<std::pair<int,int>> q;
q.push({s,0});
while(!q.empty()){
auto it=q.front();q.pop();
if(dis[it.fi]>=0)continue;
dis[it.fi]=it.se;
for(int v:out[it.fi])if((dis[v]==-1)&&(v>=fal)&&(v<=far))q.push({v,it.se+1});
}
for(int i=l;i<=r;++i)to[p][s-L+1][i]=dis[i];
std::fill(dis+fal,dis+far+1,-1);
q.push({s,0});
while(!q.empty()){
auto it=q.front();q.pop();
if(dis[it.fi]>=0)continue;
dis[it.fi]=it.se;
for(int v:in[it.fi])if((dis[v]==-1)&&(v>=fal)&&(v<=far))q.push({v,it.se+1});
}
for(int i=l;i<=r;++i)re[p][s-L+1][i]=dis[i];
}
build(p+1,l,mid);build(p+1,mid+1,r);
}
inline int query(int p,int l,int r,int x,int y){
if(x==y)return 0;
if(std::abs(x-y)<=30){
int fal=std::max(0,std::min(x,y)-30),far=std::max(x,y)+30;
std::fill(dis+fal,dis+far+1,-1);
std::queue<std::pair<int,int>> q;
q.push({x,0});
while(!q.empty()){
auto it=q.front();q.pop();
if(dis[it.fi]>=0)continue;
dis[it.fi]=it.se;
if(it.fi==y)break;
for(int v:out[it.fi])if((dis[v]==-1)&&(v>=fal)&&(v<=far))q.push({v,it.se+1});
}
return dis[y];
}
int mid=l+r>>1;
if((x<=mid&&y>mid)||(x>mid&&y<=mid)){
int L=std::max(l,mid-4),R=std::min(r,mid+4);
int min=inf;
for(int i=L;i<=R;++i)if(re[p][i-L+1][x]>=0&&to[p][i-L+1][y]>=0){
min=std::min(min,re[p][i-L+1][x]+to[p][i-L+1][y]);
}
return min==inf?-1:min;
}
if(y<=mid&&x<=mid)return query(p+1,l,mid,x,y);
else return query(p+1,mid+1,r,x,y);
}
signed main(){
freopen("counter.in","r",stdin);freopen("counter.out","w",stdout);
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
for(int i=1;i<=LEN+30;++i){
int zc=i;
bool mp[10]={0};
while(zc){
int w=zc%10;
zc/=10;
if(!w||mp[w])continue;
mp[w]=1;
out[i].eb(i-w);in[i-w].eb(i);
out[i].eb(i+w);in[i+w].eb(i);
}
}
build(0,0,LEN);
int T=read();
while(T--){
int x=read()^(lastans+1),y=read()^(lastans+1);
std::cout<<(lastans=query(0,0,LEN,x,y))<<'\n';
}
}
总结
咋一点博弈论都不会啊，这场有效时间没超过两个小时，后面就在坐牢，感觉已经对计数和博弈产生了畏难情绪，感觉比较寄。
以后静下心来慢慢找规律，学过的东西要运用起来。