POJ 3321.md

题意:
给一棵nn个节点的树,每个节点开始有一个苹果,mm次操作
1.将某个结点的苹果数异或 11
2.查询一棵子树内的苹果数

树上的修改查询要转化成线性的话,用的方法就是DFS序

cf1042F.md

题意:给定一棵树,将叶子节点分为尽量少个集合使集合里任一点对的距离不超过k。求最少集合数。

题解:很妙的一道题。我们可以先考虑一个点xx, 考虑它的两个儿子aa,bb。考虑贪心的思维,我们要尽可能的将叶子合在一起。题目要求最少集合数,那么我们试着将他们aa,bb两个集合合在一起。如何合在一起?

cf1152C.md

题目链接:https://codeforces.com/contest/1152/problem/C

题解:不妨设a<ba < b 那么$$lcm(a + k, b + k) = \frac {(a + k)\times (b + k)} {gcd(a + k, b + k)} $$
可推

lcm(a+k,b+k)=(a+k)×(b+k)gcd(a+k,ba)lcm(a + k, b + k)= \frac {(a+k) \times (b + k)} {gcd(a + k, b - a)}

不妨令
$$ t = a + k$$
$$ d = b - a$$

luogu3080.md

题目链接:https://www.luogu.org/problemnew/show/P3080

题解:不妨定义dp[i][j][0/1]dp[i][j][0/1]表示[i,j][i, j]区间已经完成并且此时站在左边或者右边
那么直接一个区间dp的转移即可,具体转移代码参见代码