Wannafly挑战赛1
https://ac.nowcoder.com/acm/contest/15
A
给定一棵n个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。
分析：开始以为是个很复杂的dp 其实只需要将点按照深度分为奇数和偶数即可
设奇数点有a个 偶数点有b个
奇数与奇数 偶数与偶数 路径长度为偶数
即(a-1)×a/2+(b-1)×b/2
B
给定一个长度为n的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为0。n<=1000
分析：很好想到前缀和 开始想着用容斥 发现不太好弄
互不重叠的区间 怎样才能统计出来
这也算个非常经典的问题吧
考虑一个端点i
将区间分成了 [1,i] [i+1,n]两部分 现在问题是要怎么设定统计规则使得不重不漏
设[1,i]为其中所有的区间 [i+1,n]为以i为左端点的所有区间
这样我们顺序枚举i 就可以不重不漏地将所有情况都考虑到
在顺序枚举的时候 会依次跟新[1,i]中的区间
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;
const ll mod = 998244353;
const int DEG = 20;
const double PI = acos(-1.0);
const double eps = 1e-10;
const ll inf = 1e18;
const int N = 1e6 + 5;
int a[N];
int sum[N];
map<int, int> mp;
int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) sum[i] = sum[i - 1] ^ a[i];
ll ans = 0;
for(int i = 1; i <= n; i++){
for(int j = 0; j < i; j++){
mp[sum[i] ^ sum[j]]++;
}
for(int j = i + 1; j <= n; j++){
ans += mp[sum[i] ^ sum[j]];
}
}
cout << ans << "\n";
return 0;
}
C
分析：
求所有点到点集中的距离最大值中的最小值
因为要求最大值中的最小值 所以先排除一些不可能为答案的最大值
将点集看作一个包围的圈 在圈外的点到点集的最大值一定 比 圈内的点到点集里面的最大值要大
综合圈内的点的最大值最小 想到一定是点集中最远的两点的中点！！！！！这个点很重要
问题转化为求点集中的最远两个点
考虑以1为根结点 对每个点赋予深度 此时点集中深度最深的一个点一定是最远的两点的其中一个
然后枚举另一个点 取所有距离最大即可
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=3e5+5;
void solve();
int n;
int fa[maxn][33],dp[maxn];
vector<int>Q[maxn];
void dfs(int,int);
int LCA(int,int);
int len(int,int);
int main(){
solve();
return 0;
}
void solve(){
cin>>n;
for(int i=1;i<n;i++){
int xx,yy;cin>>xx>>yy;
Q[xx].push_back(yy);
Q[yy].push_back(xx);
}
dp[1]=1;
dfs(1,0);
for(int j=1;j<33;j++)
for(int i=1;i<=n;i++)
fa[i][j]=fa[fa[i][j-1]][j-1];
int T;cin>>T;vector<int>G;
while(T--){
int xx;cin>>xx;
int ans=0,maxx=0,id;
G.clear();
for(int i=1;i<=xx;i++){
int uu;cin>>uu;
if(dp[uu]>maxx)maxx=dp[uu],id=uu;
G.push_back(uu);
}
for(int i=0;i<G.size();i++)
ans=max(ans,(len(id,G[i])+1)/2);
cout<<ans<<endl;
}
}
void dfs(int u,int f){
for(int i=0;i<Q[u].size();i++){
int to=Q[u][i];
if(to==f)continue;
dp[to]=dp[u]+1;
fa[to][0]=u;
dfs(to,u);
}
}
int LCA(int u,int v){
if(dp[u]<dp[v])swap(u,v);
for(int i=32;i>=0;i--)
if(dp[fa[u][i]]>=dp[v])u=fa[u][i];
if(u==v)return u;
for(int i=32;i>=0;i--)
if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
int len(int u,int v){
int lca=LCA(u,v);
return dp[u]+dp[v]-2*dp[lca];
}