Description 众所周知，Zjr506是算法之神，因此Ztxz16经常向他请教算法。这一天，Zjr506在教导了Ztxz16关于图论方面的一些算法后，给他出了一道图论题作为家庭作业： 给定N个点，M条无向边，Q个询问，每个询问给定L, R，问连上第L~R条边后，图中有多少联通块（询问之间互不影响）。 Ztxz16智商太低，百思不得其解，只好向你请教这个问题。 Input 第一行输

题目大意 给定n,k，求多少个n的排列在经过以下计算后得到k： n≤1000000 且为奇数 分析 直接算不好算，可以转化成：结果是大于等于k的减大于等于k+1的。 然后把大于等于k的数看成1，小于k的看成0。继续挖掘有什么性质。 把每一层看成去掉第一、最后的位置，在草稿纸上手玩一下，可以发现： 1. 如果原序列中间的数是1，且两边有一个1，那么答案一定是1 2. 如果原序列中

题目大意 对于一棵树，q个操作可以新增节点或改变一个点的权值，或询问整棵树的带权重心，强制在线 1≤q≤3×105 1\le q\le 3\times 10^5 题解 考虑如何找带权重心，显然是每次往最大权的子树走，条件是这个子树的权×2大于整棵树的权值和。 那么就很明显了，我们要做的是维护以每个点为根的子树的权值和，以及每个点的儿子中的最大权。 由于一条链上的信息更改会影响很多点，

题目大意 给出n个数a[i]，将x改为y的代价为|x-y|，求将a变成xor和为零的最小代价。 1≤n≤15,0≤a[i]≤109 1\le n\le 15,0\le a[i]\le 10^9 题解 考虑动态规划，按二进制从高到低，用 3n 3^n的状态表示每个数是在k位之前是增加/不变/减少，设f[k][i][S][0/1]表示当前做到第k位，当前考虑第i位，S为每个数的状态，然后转移