Solution -「AT 3913」XOR Tree
\(\mathcal{Description}\)
Link.
给定一棵树,边 \((u,v)\) 有边权 \(w(u,v)\)。每次操作可以使一条简单路径上的边权异或任意非负整数。求最少的操作次数使得所有边边权为 \(0\)。
\(n\le10^5\),\(w(u,v)<16\)。
\(\mathcal{Solution}\)
好妙的题 www。
定义一个点的点权 \(val_u\) 为其所有邻接边边权的异或和,即 \(val_u=\bigoplus_{(u,v)\in E}w(u,v)\)。一个至关重要的发现:所有边权为零等价于所有点权为零。
左推右是显然的;右推左,数归,考虑到叶子的边权等于点权,所以去掉所有叶子仍满足,得证。
再考虑一次操作,除路径两端的点,每个点有两条邻接边被异或了同一个数,所以这些点的点权不变!
非常 amazing 啊,这样一来问题就从树上剥离了——给一堆数,每次任选两个数异或同一个非负整数,求把这些数变成 \(0\) 的最小操作次数。
首先,若存在 \(u\not=v,val_u=val_v\),显然应该用一次操作处理掉它们。问题进一步转化——给一个值域在 \([0,16)\) 的集合(无重复元素),求把这些数变成 \(0\) 的最小操作次数。
鉴于 \(16=2^4\),考虑状压。设 \(f(S)\) 为处理集合 \(S\) 的最小操作次数。显然对于 \(S\) 内元素异或和不为 \(0\) 的 \(f(S)\),有 \(f(S)=+\infty\)。接下来想想对于 \(S\not=0\) 的转移:
\]
其中,前一项是暴力两两异或,后者即分别处理两个子集。
设 \(w(u,v)\) 的上限 \(W=2^k,~k\in\mathbb N\),复杂度 \(\mathcal O(3^k+n)\)。
\(\mathcal{Code}\)
#include <cstdio>
#include <cstring>
const int MAXN = 1e5, INF = 0x3f3f3f3f;
int n, val[MAXN + 5], cnt[16], f[1 << 16], xsum[1 << 16];
inline void chkmin ( int& a, const int b ) { if ( b < a ) a = b; }
int main () {
scanf ( "%d", &n );
for ( int i = 1, u, v, w; i < n; ++ i ) {
scanf ( "%d %d %d", &u, &v, &w );
val[u] ^= w, val[v] ^= w;
}
int ans = 0, S = 0;
for ( int i = 0; i < n; ++ i ) ++ cnt[val[i]];
for ( int i = 1; i < 16; ++ i ) {
S |= ( cnt[i] & 1 ) << i >> 1;
ans += cnt[i] >> 1;
}
for ( int i = 1; i < 1 << 15; ++ i ) {
for ( int j = 0; j < 15; ++ j ) {
if ( ( i >> j ) & 1 ) {
++ f[i], xsum[i] ^= j + 1;
}
}
-- f[i];
}
for ( int s = 0; s < 1 << 15; ++ s ) {
if ( xsum[s] ) continue;
for ( int t = s; ; t = ( t - 1 ) & s ) {
if ( ! xsum[t] && ! xsum[s ^ t] ) chkmin ( f[s], f[t] + f[s ^ t] );
if ( ! t ) break;
}
}
printf ( "%d\n", ans + f[S] );
return 0;
}
最新文章
- android输入限制
- 夺命雷公狗-----React---7--组建的状态props和state
- ubuntu搭建svn服务器(转)
- 引入js和css文件的总结
- MongoDB 学习笔记(python操作)
- CodeForces ZeptoLab Code Rush 2015
- 筛选DataTable数据的方法
- CF A and B and Compilation Errors (排序)
- 【python】由一个小例子看出python的灵活性,IF ELSE一例
- 从今天开始学习C#啦
- Web前端相关资源
- DBCP和C3P0使用--未完善
- 实验三《Java面向对象程序设计》实验报告
- 【java集合系列】--- LinkedList
- 用Java开发一个工具类,提供似于js中eval函数功能的eval方法
- kotlin电商学习记录,好久没来逛逛了
- Office Web addin 踩坑计:替换后台网站为MVC框架时遇到的问题
- Java多线程6:Synchronized锁代码块(this和任意对象)
- week06 12 我们准备数据 前端调用rpc 前后端联调一下
- C语言第十二讲,文件操作.
热门文章
- git -remote: Support for password authentication was removed on August 13, 2021
- JDBC 处理sql查询多个不确定参数
- Spark案例练习-打包提交
- vue 使用mock来模拟数据
- UVA 10815 Andy's First Dictionary (C++ STL map && set )
- Oracle update和select 关联
- Mybatis 学习记录
- ClassCastException: java.util.Date cannot be cast to java.sql.Date
- docker镜像制作Dockerfile
- Python Study Note 1