脚本宝典收集整理的这篇文章主要介绍了【总结】USACO2022FEB，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
对于每一行，从 (i) 向在 (i) 前面的点（包括自己）连边，那么原题转化为将给定有向图划分成若干个简单环的方案数，预处理环后 DP 即可，时间复杂度 (mathcal{O}(n^32^n+3^n))。
很强的期望题，我们定义状态 (f_{i}) 表示 (i) 次询问的期望最优对多少个，显然有 (f_{i} = sumlimits_{j=0}^{T}p_jtimes max{j, f_{i - 1}})。
(p_i) 表示恰好对 (i) 个的概率，求出 ({p}) 的前缀和 ({s})，再预处理期望 (e_{i} = sumlimits_{j = i} ^ T p_jtimes j)，那么转移可以写成 (f_{i} = s_{leftlfloor f_{i - 1}rightrfloor} times f_{i - 1} + e_{leftlfloor f_{i - 1}rightrfloor + 1})。
不难发现转移可以划分成 (mathcal{O}(T)) 个连续段，段内转移都是相同的 (f_{i} = kf_{i - 1} + b)，每次二分端点即可，时间复杂度 (mathcal{O}(T^2 + Tlog k))。
对于每个点，对于每个 (y) 找最近的 (x) 连边，然后跑最小生成树即可。
先用扫描线将矩形变为一次线段加和一次线段减。
每次线段变化时，将修改的区间内，所有的颜色段都新增一个连通块，记录到答案中。
在线段减时，要将两端的颜色段合并掉，在答案中减去。这些都可以用树状数组维护。
但是发现过不去样例二，观察一下发现样例一所有线段连通，而样例二有两个连通图。
所以我们再用 set 维护一下有多少个线段构成的连通图。总时间复杂度 (mathcal{O}(Nlog N))
对 ({a}) 求得前缀和 ({s})，手盘样例得到如果 (q_i | s_n) 则答案为 (n+1+dfrac{s_n}{q_i} - 2times sum)，(sum) 表示 ({s}) 中有多少个 (q_i) 的倍数，否则无解。
直接做是 (mathcal{O}(QN))，实际上还能多过几个点。
考虑优化，由于我们只用考虑 (q_i | s_n) 的情况，所以我们先 pollard-rho 将 (s_n) 分解质因数，最多就 (10^5) 个因数，然后高维前缀和搞一下即可，时间复杂度 (mathcal{O}(omega(sum a)sigma(sum a)))。
非常神的 DP。
我们定义状态 (f_{i}) 表示前 (i) 位的答案。
有三种转移，分别对应划分最后 (1) 位，划分最后 (2) 位和划分最后 (4) 位。
但是这些情况会重复，考虑容斥掉相同的，大力讨论一下。
具体实现了一个 (calc(x,op)) 函数，表示对以 (x) 结尾的最后 (4) 位划分成一段，最后两位不变，倒数三四位交换的方案对 (f_{op}) 的贡献。如果 倒数三四位能够交换就直接返回，否则倒数第 (6) 位到倒数第 (3) 位必须能划分成一段，然后递归到 (calc(x-2,op)) 即可。
其余的细节省略，复杂度感觉是 (mathcal{O}(|s|^2))，实际上跑起来 (100ms) 都不要。
以上是脚本宝典为你收集整理的【总结】USACO2022FEB全部内容，希望文章能够帮你解决【总结】USACO2022FEB所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。