一些题(二)

[ICPC2014 WF] Surveillance

断环,然后复制一倍转化为序列问题,可以倍增。

https://www.luogu.com.cn/record/60927918

[CERC2013] Captain Obvious and the Rabbit-Man

构造多项式 \(A(x)=\prod(x-F_i)\),考虑等式 \(\sum a_iF_iA(F_i)=0\) 的左边,展开它就做完了。

https://www.luogu.com.cn/record/60939504

[CERC2014] Virus synthesis

当 \(S\) 有偶回文子串时,可以先构造它的一半然后用操作 2 补全另一半再用操作 1 补全剩下的。于是在回文自动机上转移 dp 即可。

https://www.luogu.com.cn/record/60953431

[NEERC2015] Landscape Improved

枚举最高点在哪里,然后二分它可以搭多高,判断时可以用倍增求出他左右两边第一个不需要垫的位置。

https://www.luogu.com.cn/record/60979650

[CERC2015] Greenhouse Growth

发现一段连续的相等的 \(h\) 会一起变,可以考虑维护这些连续段。对于两个相邻的连续段,可以快速地计算出它们合并的时间。于是按照时间顺序依次合并即可,每次合并两段时注意重新计算它与相邻段的合并时间。

https://www.luogu.com.cn/record/60988923

[ICPC2015 WF]Qanat

相邻两个排土口中点左边的土都从左出,右边同理。列出式子来后拉格朗日乘子就好了。

https://www.luogu.com.cn/record/60979549

[ICPC2016 WF] Longest Rivers

计算一个节点时,肯定将它到根的链上的边都给为它,计它此时的长度为 \(l\)。对于不在这条链上的节点,贪心地考虑它到它父亲的这条边:如果存在一个儿子流向它的长度已经 \(>l\),就给这个儿子;否则给最短的一个。

考虑计算 \(f_u\) 表示分配完 \(u\) 子树内以及到父亲的边时 \(u\) 子树内的最大长度的最小值。将 \(f_u>l\) 的点都染成黑色,那么该点答案就为黑点连通块的不在那条链上的叶子个数 +1。

于是按照每个叶子的 \(l\) 降序排序,顺次将一些点染黑,用树状数组维护下叶子个数即可。

https://www.luogu.com.cn/record/61048238

[CERC2017] Embedding Enumeration

计 \(f_u\) 表示将 \(u\) 的子树铺在网格中且 \(u\) 在左上角的方案数,转移的话想清楚就不难了。

https://www.luogu.com.cn/record/61053190

[NEERC2015] Binary vs Decimal

发现如果一个数合法,那么它的后缀也合法,于是可以每次往前加一个 0/1 进行 bfs。答案可以有 160+ 位,需要高精度。

https://www.luogu.com.cn/record/61057069

CF1599F Mars

可以通过区间的和、长度、公差来确定整个等差数列。比较两个集合大小是否相等可以比较它们 \(k\) 次方和,而一个等差数列的 \(k\) 次方和容易 \(O(k)\) 计算。

https://codeforces.com/contest/1599/submission/133306282

CF1599A Weights

对于一个升序数组,如果将它左右交替放那么每放一个天平都会切换。于是设 \(S\) 有 \(k\) 个切换的位置,那么第一个就放第 \(k+1\) 大的砝码,接下来每切换一次就放一个更大的在另一边。不切换时就将较小的 \(n-k\) 个砝码从大到小,第一个放在第 \(S\) 的第一个字符的另一边,每放一个就换一边。容易证明这样是合法的。

https://codeforces.com/contest/1599/submission/133307766

【集训队作业2018】购物

对每个特殊区域,计算从左/上进和右/下出的方案数,相邻两个区域和自己区域内部的转移都可以 FFT,而起点和终点的方案是经典组合数求和问题。

https://uoj.ac/submission/513360

上一篇:【已解决】解决高德地图key鉴权失败的问题。


下一篇:【luogu P6178】【模板】Matrix-Tree 定理(行列式)(数学)(树)