一些订题总结

修建城墙

Z 2494
有 L 和 T 两个部分分。
对于 L 建立二分图求最小点覆盖的方法可能比较典。
一个点是如何输出最小点覆盖的方案对于与 S 相连的取走不到的与 T 相连的取走的到的。
然后是 T 。
首先是建图上要灵活对于 L 更契合的是边的为点对于 T边为点的构图方式显然遇到了一些麻烦于是尝试边为边。
比较重要的一点是转化贡献分析一下可以知道要满足条件每个方格都有一个至少的代价而相邻方格之间可以有公共的代价这重复的代价需要被剪掉那么就要求使这个代价最大化这个代价对应边那么最大流即可。

比赛的时候主要是没有考虑到贡献怎么转化。

1.建图要灵活边为点还是点为边要具体问题具体分析。
2.对于贡献的计算可以考虑最坏情况下的总贡献然后考虑可以尽可能多的减去重复或者不必要的贡献贡献形式就变为一个最大贡献的常数-一个尽可能的大的数可以最大流或者费用流之类的解决。

GCD

Z 2495
一个具有奠基性作用的一点是:把 $gcd(x,y)$ 拆成 ${\sum }_{d|x,y}\varphi (d)$ 这样就由一个 gcd 问题变成了对每个因子计数出现多少次的问题。
由于有区间询问对于数据较小的点容易想到莫队对移动区间时新增加的一个数考虑它对各因子数的贡献。这个东西复杂度是莫队加上每次新加上数时枚举因子的复杂度比较爆炸。
进而受这种思想的启发发现对于一个新加的数的贡献除了每次重新枚举可以对每次加入的数直接更新未来可能加入的数新增的贡献这样当加入一个数时可以直接访问O(1)更新。至于添加一个数对未来添加的数贡献的贡献是可以离线的。
那么其实就是莫队二次离线的思路。
可以把贡献拆成前缀加减的形式一个前缀再减去一个前缀把多余的贡献去掉这样提前处理好每个前缀会对哪些询问有贡献离线的时候在序列上从左到右扫一遍得到前缀的值然后对相应的询问答案加减就可以了。

比赛的时候没有往莫队二离上想。

算是个莫队二次离线的典的应用。
对于一个维护好的区间新加的数的贡献摊到已经维护好的数的贡献这个贡献可以变成两个前缀加减然后就可以直接从左到右扫一般得到前缀值更新相应的答案。

图论科技

Z 2501
一个点是曼哈顿距离与切比雪夫距离的转化。
这里曼哈顿距离不好做换成切比雪夫距离就变成了一个取 max 的问题。

第二个点是对于 max的处理发现贡献是 $\max (|x_i-x_j|,|y_i-y_j|)$ 的形式而题目又求最大值那么可以将每个点 $i$ 的贡献拆成 $x_i,-x_i,y_i,-y_i$四个点的形式由取 max 变成了若干种情况下的简单相加这样就变成了匹配求最大值问题。
可以费用流解决。

第三个点是发现图的模型较为简单考虑模拟费用流。
这里学到了一种新的模拟费用流形式主要对于可以根据人类智慧把图规模缩的比较小的情况下。本质不变——反悔贪心。首先该题的图主要是 S-左部点-x,-x,y,-y的四个贡献点-右部点-T,对于部点对贡献点的边维护时可以直接变为由源汇点向贡献点的边这样图的规模就只有 6 了。用堆和spfa 维护先不考虑反悔边用spfa 贪心跑出一条最大路径那么可以得到一对左右(x,y)的匹配点对于 x 和 y ,把所有原来建的非反悔边删去(这里可以打标记用懒惰删除法处理)然后认为建出反悔边注意反悔贡献的变化。这样对于这道题有 n 对匹配用 spfa 跑 n 次就可以了。