一套 Free 题

便宜没好货。

A

给一棵$n$个点带边权$w_i$的树，每次可以把一条路径的权值都异或$x$。问最少多少次操作可以把所有边权变成$0$。

$n\le 10^5,0\le w_i\le 15$。

emmmm

B

给一个$n$个点简单无向图，要求把点集分成$S,T$两部分，使得两个部分都是团，最小化两个团的边数，即$\frac{|S|(|S|-1)+|T|(|T|-1)}{2}$。

$n\le 700$。

二分图，背包。

C

给出$n,k$，求长度为$k$的满足$1\le a_i\le n$，且$a_i|a_{i+1}$的序列的个数。

$n,k\le 10^6$。

差分，插板法。