这里会显示出您选择的修订版和当前版本之间的差别。
两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
2020-2021:teams:farmer_john:差分约束 [2020/05/31 17:55] 2sozx [[FJOI2018]所罗门王的宝藏] |
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$,问是否有可行解。 | * 题意:有 $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$ 建边判负环即可。 | * 题解:将 $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$ | * 题意:给定 $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$ 即可。 | * 题解:考虑前缀和 $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$ 即可。 |