[SCOI2016]幸运数字 线性基
2024-08-29 10:48:59
题面
题解
题面意思非常明确:求树上一条链的最大异或和。
我们用倍增的思想。
将这条链分成2部分:x ---> lca , lca ---> y
分别求出这2个部分的线性基,然后合并,再求最大异或和。
所以我们现在只需要考虑如何在树上求一条无需拐弯的链的最大线性基。
考虑倍增。
我们预处理出f[i][j]表示从点i开始向上走\(2^j\)构成的链的线性基。至于只有点\(i\)一个点的线性基,我们可以在运算的时候特判一下处理。
暴力预处理后,我们就可以最多 合并3次 + 求LCA的复杂度 求出任意询问的答案了!
如果我们还是跟普通倍增一样暴力向上跳的话,是单次询问\(logn * 60 * 60\),所有询问的总复杂度\(q * logn * 60 * 60\),差不多都到百亿级别了!不知道为什么很多人用这种方法都过了。
所以我们考虑跟RMQ类似的思想,因为在线性基中插入重复串不会有什么影响,因此对于树上任意一条不带拐弯的链,我们完全可以拆分成2段长度至少为一半的链,然后合并即可。
虽然可能会有重复的部分,但是不会有影响。
所以就可以做到单次复杂度\(60 * 60 * 3\)啦,忽略3这个常数复杂度大概是7亿左右,时限6s基本还是可以勉强接受的范围。(这里的60其实是对一个longlong大小的数取log,因为比较大,所以不能忽略)
#include<bits/stdc++.h>
using namespace std;
#define R register int
#define LL long long
#define AC 21000
#define ac 40100
int n, m;
int Head[AC], Next[ac], date[ac], tot;
int dep[AC], fa[AC][15];
LL s[AC], ans;
inline LL read()
{
LL x = 0;char c = getchar();
while(c > '9' || c < '0') c = getchar();
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x;
}
inline void add(int f, int w)
{
date[++ tot] = w, Next[tot] = Head[f], Head[f] = tot;
date[++ tot] = f, Next[tot] = Head[w], Head[w] = tot;
}
struct basis{
LL f[61];
inline void clear() {memset(f, 0, sizeof(f));}
inline void ins(LL x)
{
LL maxn = 1LL << 60;
for(R i = 60; ~i; i --, maxn >>= 1)
{
if(!(x & maxn)) continue;
if(!f[i]) {f[i] = x; break;}
else x ^= f[i];
}
}
inline void merge(basis x){for(R i = 0; i <= 60; i ++) ins(x.f[i]);}
}f[AC][15], a, b;
void dfs(int x)
{
f[x][0].ins(s[x]), f[x][0].ins(s[fa[x][0]]);//直接按常规方法处理,使用的时候特判掉
for(R i = 1; i <= 14; i ++)
{
fa[x][i] = fa[fa[x][i - 1]][i - 1];
f[x][i] = f[x][i - 1], f[x][i].merge(f[fa[x][i - 1]][i - 1]);
}
for(R i = Head[x]; i; i = Next[i])
{
int now = date[i];
if(now == fa[x][0]) continue;
fa[now][0] = x, dep[now] = dep[x] + 1, dfs(now);
}
}
inline int LCA(int x, int y)
{
if(dep[x] < dep[y]) swap(x, y);
for(R i = 14; i >= 0; i --)
if(dep[fa[x][i]] >= dep[y]) x = fa[x][i];
for(R i = 14; i >= 0; i --)
if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
if(x == y) return x;
else return fa[x][0];
}
inline int kth(int x, int k)
{
int lim = dep[x] - k;
for(R i = 14; i >= 0; i --)
if(dep[fa[x][i]] >= lim) x = fa[x][i];
return x;
}
void cal(int x, int y)
{
int lca = LCA(x, y), len1 = dep[x] - dep[lca], len2 = dep[y] - dep[lca];
a.clear(), b.clear();
if(!len1) a.ins(s[x]);
else
{
LL tmp = 1, cnt = 0;
for(R i = 0; i <= 60; i ++, tmp <<= 1, ++ cnt) if((tmp << 1) > len1) break;
a = f[x][cnt], a.merge(f[kth(x, len1 - tmp)][cnt]);
}
if(!len2) b.ins(s[y]);
else
{
LL tmp = 1, cnt = 0;
for(R i = 0; i <= 60; i ++, tmp <<= 1, ++ cnt) if((tmp << 1) > len2) break;
b = f[y][cnt], b.merge(f[kth(y, len2 - tmp)][cnt]);
}
a.merge(b);
}
void pre()
{
n = read(), m = read(), fa[1][0] = dep[1] = 1;
for(R i = 1; i <= n; i ++) s[i] = read();
for(R i = 1; i < n; i ++) add(read(), read());
}
void work()
{
for(R i = 1; i <= m; i ++)
{
cal(read(), read()), ans = 0;
for(R j = 60; ~j; j --)
if((ans ^ a.f[j]) > ans) ans ^= a.f[j];
printf("%lld\n", ans);
}
}
int main()
{
// freopen("in.in", "r", stdin);
pre();
dfs(1);//建倍增数组
work();
// fclose(stdin);
return 0;
}
最新文章
- 了解JavaScript 数组对象及其方法
- virturalbox 本地win8 虚拟机为Linux-- 网络设置
- attr和prop
- 函数mem_pool_create
- JavaScript 现状:方言篇
- 【转】Session与Cookie的比较
- ci 笔记
- 让rdlc报表在ReportViewer中水平居中的方法
- 3D空间中射线与三角形的交叉检測算法
- 第13章 Swing程序设计----JFrame窗体
- vue视频学习笔记06
- jsp中button按钮单击莫名提交两次或刷新页面问题
- 小强的HTML5移动开发之路(13)——HTML5中的全局属性
- 21 re正则模块 垃圾回收机制
- 阿里___MQTT中协议QoS的实现
- Zip文件和RAR文件解压
- Linux服务器---安装mysql
- 浅析HttpCient
- Day 15 内置函数 , 匿名函数.
- Web前端开发最佳实践(12):JavaScript代码中有大量写死的配置数据?这些数据难以维护,你需要合理组织这些数据
热门文章
- jaron插件的用法
- 数据库路由中间件MyCat - 源代码篇(15)
- HIS系统患者实体OO设计的一点思考
- WPF DrawingContext Pen
- Python接口测试实战5(下) - RESTful、Web Service及Mock Server
- CentOS7.2 部署Haproxy 1.7.2
- Numpy入门笔记第二天
- Hyperledger_Fabric_Model
- [leetcode-914-X of a Kind in a Deck of Cards]
- 2016-2017 ACM-ICPC, NEERC, Moscow Subregional Contest Problem L. Lazy Coordinator