最近在刷省选题......大致上是按照省份刷的。
不过上面的题目顺序是按照写题的顺序排列的，所以可能会有点乱哈。
最小圆覆盖，随机增量法，期望复杂度\(O(n)\)。
\(\mbox{Kruskal}\)重构树+二维数点。
求\(\sum_{i=1}^n\sum_{j=1}^i\frac ij-\sum_{i=1}^n\sum_{j=1}^i\lfloor\frac ij\rfloor\)。
前半部分随便弄弄就好了。
后半部分，\(\sum_{j=1}^i\lfloor\frac ij\rfloor\)实质上等于\(\sum_{j=1}^id(j)\)。
所以前缀和一下就好了。
求\(\frac{\prod_{i=1}^ni^{\sum_{j=1}^i\lfloor\frac ij\rfloor}}{\prod_{i=1}^n\prod_{j=1}^ij^{\lfloor\frac ij\rfloor}}\)。
上半部分就是\(\sum_{i=1}^ni^{\sum_{j=1}^id(j)}\)。
下半部分，\(\prod_{j=1}^ij^{\lfloor\frac ij\rfloor}\)实质上是\(i\)的各约数的乘积，也就是\(i^{\frac{d(i)}2}\)。
所以前缀积一下就好了。
辛普森积分，虽然是假的。
多项式求\(\ln+\mbox{MTT}\)。谁说莫比乌斯反演的来着？
很显然是要求\(\prod_{i=1}^n\frac{1-x^i}{1-x}\)的\(x^m\)次项系数。
一种做法是求\(\ln\)之后大力开式子，然后可以\(O(n\ln n)\)调和级数求得一多项式然后再\(\exp\)回去。
还有一种做法是拆成前后两部分，\((\frac1{1-x})^n=(\sum_{i=0}^{\infty}x^i)^n\)，相当于\(n\)个盒子每个盒子可以无限放球的生成函数，所以\(x^m\)次项系数是\(\binom{n+m-1}{m}\)。\(\prod_{i=1}^n(1-x^i)\)可以看做一个带符号的\(01\)背包计数，其中第\(i\)个物品的重量恰好为\(i\)。考虑到至多选\(O(\sqrt m)\)个物品，所以可以做\(O(n\sqrt m)\)的\(dp\)。
设\(f_{i,j}\)表示前\(i\)对情侣已经入座，有\(j\)对情侣是挨着的的方案数。考虑插入第\(i+1\)对情侣。
\(f_{i,j}\)可以转移到\(f_{i+1,j-2},f_{i+1,j-1},f_{i+1,j},f_{i+1,j+1}\)，分别表示第\(i+1\)对情侣分别拆散了两对情侣、只拆散了一对情侣、没有拆散情侣以及他俩坐在一起。注意两人分开座时可能会导致某对情侣复合，转移的时候要额外算一下贡献。
线段树合并模板题。树上差分的时候，对\(lca\)与\(fa_{lca}\)打标记而不是做线段树单点插入，即可把空间减小到一半。
坐标离散，横坐标从左往右扫，维护每个纵坐标已存在的点数，组合数算一下，再用树状数组区间求和即可。
矩阵快速幂模板题。
枚举\(n\)维中每一维坐标的极差\(\Delta x_i\)，有
\[\sum_{\Delta x_1=1}^{m_1}\sum_{\Delta x_2=1}^{m_2}...\sum_{\Delta x_n=1}^{m_n}\binom{\gcd(\Delta x_1,\Delta x_2...\Delta x_n)-1}{c-2}\prod_{i=1}^n(m_i-\Delta x_i)\]
枚举\(\gcd(\Delta x_1,\Delta x_2...\Delta x_n)\)，有
\[\sum_{d=1}^{\min(m)}\binom{d-1}{c-2}\sum_{\Delta x_1=1}^{m_1/d}\sum_{\Delta x_2=1}^{m_2/d}...\sum_{\Delta x_n=1}^{m_n/d}[\gcd(\Delta x_1,\Delta x_2...\Delta x_n)=1]\prod_{i=1}^n(m_i-\Delta x_id)\]
反个演
\[\sum_{d=1}^{\min(m)}\binom{d-1}{c-2}\sum_{t=1}^{\min(m)/d}\mu(t)\sum_{\Delta x_1=1}^{m_1/dt}\sum_{\Delta x_2=1}^{m_2/dt}...\sum_{\Delta x_n=1}^{m_n/dt}\prod_{i=1}^n(m_i-\Delta x_idt)\]
换个写法
\[\sum_{d=1}^{\min(m)}\binom{d-1}{c-2}\sum_{t=1}^{\min(m)/d}\mu(t)\prod_{i=1}^n\sum_{\Delta x_i=1}^{m_i/dt}(m_i-\Delta x_idt)\]
令\(T=dt\)，改变枚举顺序
\[\sum_{T=1}^{\min(m)}(\prod_{i=1}^n\sum_{\Delta x_i=1}^{m_i/T}(m_i-\Delta x_iT))\sum_{d|T}\binom{d-1}{c-2}\mu(\frac Td)\]
令\(F(T)=\prod_{i=1}^n\sum_{\Delta x_i=1}^{m_i/T}(m_i-\Delta x_iT)\)，\(G(T)=\sum_{d|T}\binom{d-1}{c-2}\mu(\frac Td)\)。
首先\(G(T)\)在给定\(c\)的前提下可以\(O(n\ln n)\)预处理出来。
观察\(F(T)\)，将其划开
\[F(T)=\prod_{i=1}^nm_i\lfloor\frac{m_i}T\rfloor-\frac{T\lfloor\frac{m_i}T\rfloor(\lfloor\frac{m_i}T\rfloor+1)}2\]
如果\(\lfloor\frac{m_i}T\rfloor\)确定的话，那么\(F(T)\)就是一个关于\(T\)的\(n+1\)次多项式。所以可以预处理\(G(T)T^i\)的前缀和，然后对于每个\(\lfloor\frac{m_i}T\rfloor\)相同的连续段暴力求\(F(T)\)。
总体复杂度\(O(n\ln nc+nmc+Tn^3\sqrt m)\)有点爆炸啊。
直接爆搜质因子，特判最后一个大于根号的质因子即可。
对于前面的相同元素，直接强制从最后一个这种元素转移即可。
先枚举跳跃高度和连跳次数，然后直接记搜转移即可。
正难则反，求三点共线的方案数。枚举相隔较远的两点的横纵坐标之差，然后第三个点就有\(\gcd-1\)种选法。注意特殊处理横纵坐标差为\(0\)。
设\(f_n\)表示\(n\)点二叉树的数量，\(g_n\)表示\(f_n\)棵二叉树的总叶子节点个数。
最近做初赛题发现\(f_n\)就是卡特兰数。
\(g_n\)是啥？考虑\(f_n\)中的一棵\(n\)点二叉树，设其有\(m\)个叶子，那么删掉这\(m\)个叶子后就能得到\(m\)棵不同的\(n-1\)点二叉树；而每棵\(n-1\)点二叉树有\(n\)个位置可以挂叶子，也就是说在上述过程中被计算了\(n\)次。所以\(g_n=nf_{n-1}\)。
\(ans=\frac{g_n}{f_n}=\frac{nf_{n-1}}{f_n}=\frac{n(n+1)}{4n-2}\)。
树剖+线段树两只\(\log\)，用\(\mbox{LCT}\)写可以做到一个\(\log\)。
每个点维护区间最大值，最小值，后面最大值减前面最小值的最大值，前面最大值减后面最小值的最大值。
其实棋子是放在中间那一行的。
所以直接按行\(dp\)就行了。处理一下相邻两行的两个状态是否可以转移，因为转移都是一样的所以可以矩乘优化，复杂度\(O(2^{3m}\log n)\)
据说这玩意儿叫精确覆盖？直接状压完事了。
因为保证\(a\)可以由一个排列得到，所以\(x\)就一定会是排列，否则不更优。贪心，尽量把数值大的放在前面，把数值小的放在后面。对于\(a_i\)值相差为\(1\)的点对建立拓扑关系，然后依次填数，最后统计一遍答案就行了。
正解是动态开点线段树，但是感觉比较难写，就换了一种写法。
开个\(\mbox{std::set}\)维护未放置的区间，平衡树维护已放置的位置集合，支持插入删除，找前驱后继，统计区间点数即可。（如果迭代器支持相减的话就可以直接开两个\(\mbox{std::set}\)做了）
其实只要能够得到最终生成的序列就很好办了。考虑从大到小确定每个数在最终序列里的位置，相当于查找当前的第\(k\)大元素。\(BIT\)可做。
对于所有要出去的小矮人，一定是按照\(a+b\)权值从小到大出去最优。
排序，然后设\(f_i\)表示出去了\(i\)个小矮人时人梯的最高高度。如果\(f_j+b_i\ge h\)就可以用\(f_j-a_i\)更新\(f_{j+1}\)。
黑白染色然后跑最小割。
一条链是考过的原题。
如果是树的话同样可以设\(f_{u,i}\)表示\(u\)点子树内，\(u\)点排在第\(i\)个的方案数，每次转移就是合并两个序列，枚举\(f_{u,i}\)以及在\(u\)的前面放\(j\)个元素，根据大小限制决定是从\(f_{v,1...j}\)转移过来还是从\(f_{v,j+1...sz_v}\)转移过来，同样可以用前缀和优化转移，同时要乘上前后隔板插入的方案数\(\binom{i+j-1}{j}\times\binom{sz_u-i+sz_v-j}{sz_v-j}\)，复杂度\(O(n^2)\)。
上一题弱化版。双倍经验。
预处理多重背包的前后缀\(dp\)，每组询问\(O(m)\)回答。
\(f_u\)表示\(u\)点子树内最少要选多少个叶子才能必胜，如果\(u\)点是自己控制的那么\(f_u=\min\{f_v\}\)，否则\(f_u=\sum f_v\)。找出所有可能是最优转移点的叶子即可。
找到最高和最低的非零系数\(a_m,a_n\)，因为答案是有理数所以一定是\(\frac pq\)的形式，更具体的\(p\)一定是\(a_m\)的约数\(q\)一定是\(a_n\)的约数。所以暴力枚举一下然后\(\mbox{check}\)。\(\mbox{check}\)的话，\(x\)是浮点数不好做，可以选几个大质数做模意义下的运算判断结果是不是\(0\)即可。
原文：https://www.cnblogs.com/zhoushuyu/p/9813323.html