用户工具

站点工具


2020-2021:teams:farmer_john:差分约束

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版
前一修订版
2020-2021:teams:farmer_john:差分约束 [2020/05/31 11:51]
jjleo [建边方法]
2020-2021:teams:farmer_john:差分约束 [2020/05/31 18:51] (当前版本)
2sozx [倍杀测量者]
行 28: 行 28:
      * 于是用$floyd$跑一遍确定一下上下界,然后枚举两个砝码就行了      * 于是用$floyd$跑一遍确定一下上下界,然后枚举两个砝码就行了
 ====[FJOI2018]所罗门王的宝藏==== ====[FJOI2018]所罗门王的宝藏====
-[[https://​www.luogu.com.cn/​problem/​P4578]|传送门]]+[[https://​www.luogu.com.cn/​problem/​P4578|传送门]] 
 +  * 题意:有 $n+m$ 个变量,给定 $k$ 组限制,每次告诉你 $x_r+y_c=k$,问是否有可行解。 
 +  * 题解:将 $x_r+y_c=k$ 转变为两个不等式 $x_r-(-y_c)\le k,​x_r-(-y_c)\ge k$ 建边判负环即可。
 ====倍杀测量者==== ====倍杀测量者====
 [[https://​www.luogu.com.cn/​problem/​P4926|传送门]] [[https://​www.luogu.com.cn/​problem/​P4926|传送门]]
 +  * 题意:已知某些位置的 $S_i$ ,​求最大的 $T$ 使得存在一个序列 $S$ 满足 $m$ 个形如 $S_a>​S_b\times (k_i-T),​S_a>​S_b\times \frac{1}{k_j+T}$ 的限制。如果不存在则输出 $-1$。序列长度 $n\le 1000$,限制个数 $m\le 1000$
 +  * 题解:将限制取对数,然后对于 $T$ 二分。建图的时候要将已经确定的 $S_i$ 可以建立两个形如 $S_0-S_i\le -S_i,​S_i-S_0\le S_i$ 的限制即可,然后就可以判断是否有解。
 ====[HNOI2005]狡猾的商人==== ====[HNOI2005]狡猾的商人====
 [[https://​www.luogu.com.cn/​problem/​P2294|传送门]] [[https://​www.luogu.com.cn/​problem/​P2294|传送门]]
 +  * 题意:给定 $m (m\le 1000)$ 个限定,每个限定为 $\sum_{i=s}^t a_i=v_j$,问是否存在这样一个序列 $a$。 序列长度 $n\le 100$
 +  * 题解:考虑前缀和 $sum_i=\sum_{j=1}^i a_j$ ,限定转化为 $sum_t-sum_{s-1}=v_j$ ,将等式转化为两个不等式 $sum_t-sum_{s-1}\ge v_j,​sum_t-sum_{s-1}\le v_j$ 即可。
2020-2021/teams/farmer_john/差分约束.1590897113.txt.gz · 最后更改: 2020/05/31 11:51 由 jjleo