CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 2020/5/11-2020/5/17 ======
===== 团队训练 =====
第一场团队赛：[[https://www.jisuanke.com/contest/9569|Nordic Collegiate Programming Contest 2019]]\\
[[训练记录--比赛记录]]

===== 队伍知识点 =====
[[求01矩阵中最大的全为0或1的矩阵]]\\
[[备用：求01矩阵中最大的全为0或1的矩阵]]

===== 吕双羽 =====
==== 专题 ====
  *还是 [[数据结构专题]]
==== 比赛 ====
  * [[https://codeforces.com/contest/1353]]
  * [[Codeforces Round 642 (Div. 3)]]

===== 吴湛宇 =====
本周只打了例行的ACM模拟赛[手动捂脸]，下次一定

===== 陶虹宇 =====
本周只打了例行的ACM模拟赛[手动捂脸]，下次一定
===== 本周推荐 =====
===== 吕双羽 =====
Codeforces Round 642 (Div. 3) F：[[https://codeforces.com/problemset/problem/1353/F]]

题意：单元格（1，1）中，想进入单元格（n，m）。只能向下（从单元格（i，j）移动到单元格（i+1，j））或向右（从单元格（i，j）移动到单元格（i，j+1））。还有一个附加限制：如果当前单元格的高度为x，则只能移动到高度为x+1的单元格。在第一次移动之前，您可以执行多个操作。在一次操作中，可以将任何单元格的高度减少一个。找到从单元格（1,1）到单元格（n，m）的至少一条合适路径所需执行的最少操作数。答案一定存在。

思路：当(1,1)高度固定时，由于只能向右和向下，从(1,1)到任意(i,j)的距离是唯一的，因此h[i][j]也是确定的，所以使用dp求解。dp[i][j]=min(dp[i-1][j]+dp[i][j-1])+(a[i][j]-a[1][1]-i-j+2)但是如果我们遍历所有可能的高度，我们的解显然会得到超过时间限制的结论。现在我们可以注意到一个重要的事实：在最佳答案中，某些单元格的高度保持不变。因此枚举这些可能的高度即可。时间复杂度O(n^4)

===== 吴湛宇 =====
差分约束：有m个形如\(a_i-a_j \le k\)的限制条件，求\(a_n-a_1\)的最大值\\
解法：\(a_i-a_j \le k\)与最短路中的 \(f_i \le f_j+dis_{i,j}\)类似 因此可以由j向i连一条长度为k的单向边，spfa跑一边最短路即可得到最大值。\\
如果存在负环，则说明无解\\
如果限制条件中存在大于等于，则两边同时乘以-1\\
如果存在等于，则变为大于等于&&小于等于\\
CVBB ACM Team

用户工具

站点工具

页面工具
