2024.1.18 杭州电子科技大学2023华为杯编程竞赛
解题思路
首先可以知道,我们任意选一点为根 root 往下递归异或就可以得到 f [ i ](root 到 i 的路径异或值 ),那么 l 到 r 的路劲异或值可以由 f [ l ] ^ f [ r ]得出
那么如何计算答案呢,就是用 f [ l ]~f [ r ] 分别异或f [ x ] 相加即可,但是1e5级别的询问显然时间复杂度不可以接受,然后我们就行有什么可以快速算出 l ~ r 的贡献呢,这里可以想到用前缀和;
(当然不是异或前缀和,异或不满足分配律,比如 (2^3+2^3+4^3)!=8^3
所以是另一种 :计算1~n , f [ i ] 2进制的每一位1和0的前缀和,
那么答案就是,对f [ x ] 的每一位的贡献计算,比如f [ x ] 第2位是0,那么根据异或1异或0才有贡献, 贡献就是 pow( 2 , i (第几位) *( sum1[ r ][ i ]-sum1[ l-1 ][ i ] );
复杂度位1e5*30,显然可以接受
(这道题我一开始把所有变量换成longlongTLE了,只换ans其他部分用1ll处理就过了,longlong效率比int低,注意,如果看表面复杂度过了但TLE了可能就是这个问题)
代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
using namespace std;
#define ll long long
const int N=100005;
vector<pair<int,int>> e[N];
int f[N],pre1[N][32],pre0[N][32];
int n;
void solve(int x,int fa)
{
for(auto ed:e[x])
{
if(ed.first==fa)continue;
f[ed.first]=f[x]^ed.second;//f存储每个点到根的路径异或和
solve(ed.first,x);
}
}
inline void init()
{
for(int i=1;i<=n;i++)
{
e[i].clear();
f[i]=0;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin>>T;
while(T--)
{
cin>>n;
init();
for(int i=1;i<n;i++)
{
int u,v,w;
cin>>u>>v>>w;
e[u].push_back({v,w});
e[v].push_back({u,w});
}
solve(1,-1);
for(int i=1;i<=n;i++)
{
for(int j=0;j<30;j++)
{
int x=((f[i]>>j)&1);//提取每一位数字
pre1[i][j]=pre1[i-1][j]+(x>0);//pre1用来存储前i个点中有多少路径异或和的第j位能在x的第j位为0时做出贡献的
pre0[i][j]=pre0[i-1][j]+(x==0);//pre0用来存储前i个点中有多少路径异或和的第j位能在x的第j位为1时做出贡献的
}
}
int q;
cin>>q;
while(q--)
{
int l,r,x;
cin>>l>>r>>x;
ll ans=0;//要开long long
for(int i=0;i<30;i++)
{
int t=((f[x]>>i)&1);
if(t) ans+=1ll*(1ll<<i)*(pre0[r][i]-pre0[l-1][i]);//算式里也要注意long long
else ans+=1ll*(1ll<<i)*(pre1[r][i]-pre1[l-1][i]);
}
cout<<ans<<'\n';
}
}
return 0;
}
标签:前缀,int,ed,异或,include,pre1,刷题
From: https://www.cnblogs.com/modemingzi-csy/p/17972356