Xiaruize's Blog

[USACO11DEC]Simplifying the Farm G By xiaruize 题面 求一张竞赛图中最小生成树的方案数 思路 Kruskal求最小生成树，记录每个长度的边被选择几次 重新跑Kruskal,对于长度一样的边，dfs检查有多少选法，使结果仍然是最小生成树，乘法原理求结果 例如，在这张图中，对于长度为1的边，本来选定2条，所以只有一种方案 对于长度为2的边，本来选定1条，dfs检查其它长度为2的边，均可以，答案 ×3\times 3×3 Code

三分-abc279d By xiaruize 前置知识 三分 俗话说:二分不行就三分 那么，三分是什么？ 如果你不会二分,请点击链接跳转 二分需要一个序列满足单调性，那么，如果是一个单峰函数，如何求极值呢？ 设 f(x)f(x)f(x) 在 x=ax=ax=a 时取到 maxmaxmax 为 bbb 取 l,rl,rl,r 表示当前的两端，l<a,r>al<a,r>al<a,r>a 取区间 [l,r][l,r][l,r] 的三等分点 lmid,rmidlmid,rmidlmid,rmid 令l′=f(lmid),r′=f(rmid)l'=f(lmid),r'=f(rmid)l′=f(lmid),r′=f(rmid) 若 l′<r′l'<r'l′<r′, lmid<almid < almid<a 若 l′>r′l'>r'l′>r′, rmid>armid > armid>a 对应的收缩区间 abc279_d 显 ...

菱形求和 Method 1 考虑每次中心由 (x,y)⇒(x,y+1)(x,y) \rArr (x,y+1)(x,y)⇒(x,y+1) 的变化情况 如图1-1中所示 所以可以考虑用前缀和维护斜向的格子，O(1)O(1)O(1) 的进行转移 (x,y)⇒(x+1,y)(x,y) \rArr (x+1,y)(x,y)⇒(x+1,y) 同理 Method 2 前置知识 切比雪夫距离 考虑点 (x,y)(x,y)(x,y)，将所有的点 (x,y)⇒(x+y,x−y)(x,y)\rArr (x+y,x-y)(x,y)⇒(x+y,x−y) 表示 此时，原来两点 (x1,y1),(x2,y2)(x_1,y_1),(x_2,y_2)(x1​,y1​),(x2​,y2​) 之间的曼哈顿距离 ∣x1−x2∣+∣y1−y2∣|x_1-x_2|+|y_1-y_2|∣x1​−x2​∣+∣y1​−y2​∣ 转化为 max⁡(∣x1−x2∣,∣y1−y2∣)\max(|x_1-x_2|,|y_1-y_2|)max(∣x1​−x2​∣,∣y1​−y2​∣) 思路 然后就是板子 ...