格雷码
这题比那个SCOI的炒鸡格雷码好多了,甚至告诉你构造方法,所以...
void wk(uLL kk)
{
int j=0;
for(uLL i=n-1;~i;--i)
{
if(kk>>i&1) printf("%d",j^1),j^=j==0;
else printf("%d",j),j^=j==1;
}
}括号树
考虑朴素做法,即dfs整棵树,然后记录到根的括号序列,每个点的贡献为祖先贡献+以自己这个位置为右端点的合法括号序列数量,可以\(O(n^2)\)
考虑优化,我们要统计的括号序列是一段后缀,所以把\()\)看做\(1\),\((\)看做\(-1\),那么一个后缀为合法括号序列当且仅当这一段的权值和为0,且这个后缀没有包含一段和\(<0\)的后缀(也就是有一些\((\)一定匹配不上),那么线段树每个位置维护对应后缀的和,以及再维护区间权值0个数(就是维护区间最小值以及其个数),每次进入一个点先对所有后缀\(+1/-1\),然后线段树上二分找出权值\(<0\)的最靠右位置\(p\),那么以这个点为最右端的合法括号序列个数就是\([p+1,dep_x]\)内权值0个数
.
树上的数
不会,咕...
Emiya 家今天的饭
这里的方案计算只有某一列被选次数不超过\(\lfloor\frac{k}{2}\rfloor\)这个限制不太好直接做,所以考虑容斥,即总方案-不合法方案.总方案为\(\prod_{i=1}^{n}(1+\sum_{j=1}^{m}a_{i,j})\)
如果有一列被选次数\(>\lfloor\frac{k}{2}\rfloor\),那么有且仅有这一列会超出限制,所以不合法方案只有一列不满足限制,那就枚举超出限制的为哪一列,然后设\(f_{i,j,k}\)表示考虑前\(i\)行,选了\(j\)次,指定的不合法列选\(k\)次的方案,转移背包转移即可,那么这一列的贡献为\(\sum_{j=1}^{n}\sum_{k=\lfloor\frac{j}{2}\rfloor+1}^{j} f_{n,j,k}\),复杂度\(O(n^3m)\)
考虑优化,如果我们把上述状态的\(j-k\)和\(k\)做差,那么一个不合法方案,它的这个差一定\(<0\),所以上述状态改为\(f_{i,j}\)表示前\(i\)行,其他列出现次数-指定列出现次数为\(j\)的方案,然后转移完后用\(j<0\)的统计,即可做到\(O(n^2m)\).实现时注意负下标的处理
划分
先考虑朴素dp,设\(f_{i,j}\)表示上一次选择的段为\([j,i]\)的最小值,复杂度\(O(n^3)\),然后注意到一个\(f_{i,j}\),从前面一个位置\(k\)转移过来\((k=j-1)\),那么\(f_k\)的合法第二维一定是在\([x,k]\)之间,其中\(x\)为最大的能转移到\(f_{i,j}\)的位置,那么记一下\(f_{i,j}\)关于\(j\)的后缀最小值,即可做到\(O(n^2)\)
然后先丢一个证明链接,再不加证明的给出两个引理
- 一个\(f_{i,j}\)往后转移时,一定是用合法的\(j\)最大的\(f_{i,j}\)的转移到后面,后面记这个最大的\(j\)为\(p_i\)
- 对于一个\(i\),记能从前面转移过来的位置集合为\({x}\),那么最优的转移位置一定是集合最大值\(k\),即用\(f_{k,p_k}\)转移到\(f_{i,k+1}\)
这样对于每个\(i\),二分出它最先可以贡献的后面的位置(即最小的\(a\)满足\(sum_a-sum_i\ge sum_i-sum_{p_i-1}\)),把\(i\)丢进对应的决策集合,然后在做到某个位置时用这个位置的决策更新最优决策,可以做到\(O(nlogn)\)
但这个二分是可以去掉的,我们维护一个单调队列,维护还没加入的决策\(i\),这些\(i\)以对应的\(sum_i-sum_{p_i-1}\)为关键字,每次加入一个决策进队列就把队尾的一定比这个决策差的决策弹掉(设队尾对应元素为\(t\)即\(sum_i-sum_{p_i-1}<=sum_t-sum_{p_t-1}-(sum_i-sum_t)\)时弹队尾),然后压进队尾,每次用队首能加入的决策更新当前决策
同时你还需要实现一个高精,所以请注意常数问题.我这里用的是4个\(\text{int}\)表示\(32\)位整数
树的重心
考虑朴素做法,枚举鸽的是哪条边,然后对于剩下两个子树分别求重心,具体操作是分别以两个点为根,然后从根出发,走到第一个点满足最大的儿子子树大小\(\le \lfloor\frac{size}{2}\rfloor\).如果有两个重心,则说明当前走到的点最大的儿子子树大小\(=\lfloor\frac{size}{2}\rfloor\),那么另一个重心为对应子树大小最大的儿子
如果套用以上做法,然后随便设一个点为根,那么可以统计出鸽掉每条边后,靠下面的点(记为\(y\))的子树的重心贡献,在往儿子走的时候加一个倍增优化即可.然后还有被鸽边上面那个点(记为\(x\))的贡献,那么可以看做是把\(x\)作为根,然后不考虑\(y\)的子树,然后往儿子走的过程,所以可以考虑换根dfs,因为在dfs到某个点的时候,只有这个点到根路径上的点的父子关系变化了,所以每次枚举这个点的儿子\(y\)时,\(x\)为根时的儿子实际上是\(x\)在原树中的其他儿子和\(x\)的父亲,那么倍增数组只要用这些\(x\)为根时的儿子预处理就好了.具体实现的时候,如果\(y\)为子树大小最大的儿子,那么\(x\)下一步走的是父亲或者子树大小次大儿子,否则是父亲或者子树大小最大儿子