2020-2021:teams:farmer_john:差分约束
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
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$ 即可。 | ||
2020-2021/teams/farmer_john/差分约束.1590918940.txt.gz · 最后更改: 2020/05/31 17:55 由 2sozx
