wxwoo's blog

原题目链接

首先树剖边权转点权，把每一条边的权值下放到子节点上

在修改的时候注意最后要避开两个点的LCA，因为LCA的点权所代表的边权不在两个点的路径上

然后看见区间推平就想到了ODT

原题目链接

此题显然为有向图判负权环板子题

没做过请先右转模板【负环】

此题关键点：

小明和小红的生活中，有N个关键的节点。有M个事件，记为一个三元组（Si，Ti，Wi），表示从节点Si有一个事件可以转移到Ti，事件的效果就是使他们之间的距离减少Wi。

所以建边时，要把权值变为相反数

然后以1为源点进行SPFA求负环，就AC了

……吗？

原题目链接

先无视租机器，明显的最大权闭合子图

最大权闭合子图：

给定一个有向图，点有点权，选择一个子图，满足子图上如果选择了一个点就必须选择它后继的所有点。最大化点权和。

我们将机器和任务都看成一个点

如果这题没有租机器，这题的建边方式就应该是这样：

1. 源点向订单连流量为利润的边

2. 机器向汇点连流量为购买价格的边

3. 每个订单向需要的机器连流量为inf的边

可以发现，源点连的边都是订单的利润，汇点连的边都是机器的成本，只有机器和订单之间的边是$inf$

对于每个订单需要的相同机器，租用的价格也不一样

所以我们考虑把$inf$换成租机器的费用

原题目链接

明显的最大权闭合子图

最大权闭合子图：

给定一个有向图，点有点权，选择一个子图，满足子图上如果选择了一个点就必须选择它后继的所有点。最大化点权和。

经典的网络流问题，具体使用最小割求解

我们将顾客和通讯站都看成一个点，然后如下建边：

1. 源点向顾客连流量为利润的边

2. 通讯站向汇点连流量为成本的边

3. 每个顾客向需要的通讯站连流量为inf的边

原题目链接

前置知识：不带修区间最大子段和

没做过请先右转GSS1

这题比GSS1多了一个对左右端点的区间限制，GSS1的做法不再适用

这时我们就要分两种情况讨论

原题目链接

树上链最值查询

做法很多，LCT，树上倍增，树剖都可以

但由于LCT常数过大，树上倍增比树剖常数大，这里使用树链剖分

边权转点权是树剖常用套路，将边权转成深度较大的点的点权，查询时注意避开两点的LCA的权值

由于不带修改，树剖后用ST表维护，时间复杂度$\mathcal{O}(n\log n)$，比用线段树维护$\mathcal{O}(n\log ^2n)$还少一个log

原题目链接

PS：

这题比赛时当场出锅……

std被hack……

整场比赛最后unrated……

对于每两个相邻的图形，交点数是固定的

也就是说我们可以打表

1
2
3
4
5

     1   2   3
   
1    /   3   4
2    3   /  inf
3    4  inf  /

但是！直接打表是错误的！std就是这样被hack的！

原题目链接

首先想到$\Theta(n^4)$的暴力枚举，但$n\le 4000$显然不行。

考虑先预处理出c数组和d数组的和，再暴力计算答案。

由于c数组和d数组的和可能会有重复，排序后使用二分来降低时间复杂度

最终时间复杂度$\Theta (n^2\log n)$

原题目链接

选人有利润，选了要付出代价：明显的最小割模型

我们将每个人看成一个点，然后如下建边：

1. 源点向每个人连流量为其总收益的边（即$\sum\limits_{j=1}^n E_{i,j}$）

2. 每个人向汇点连流量为其花费的边

3. $i$向$j$连流量为$E_{i,j} \times 2$的边

原题目链接

每张合影可选可不选，选了必须带一些特定人：明显的最大权闭合子图

最大权闭合子图：

给定一个有向图，点有点权，选择一个子图，满足子图上如果选择了一个点就必须选择它后继的所有点。最大化点权和。

经典的网络流问题，具体使用最小割求解。