2020-2021:teams:die_java:weeksummary12

差别

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

到此差别页面的链接

--- 2020-2021:teams:die_java:weeksummary12 [2020/08/28 16:56]
fyhssgss [黄旭民]
+++ 2020-2021:teams:die_java:weeksummary12 [2020/08/28 21:18] (当前版本)
mychael
@@ 行 30: / 行 30: @@
 **wxg: **
-\\ **题目大意**
+\\ **题目大意** 给了一个长度为 $2^n$ 的数列，让你进行单点修改，翻转每一个 $2^k$ 的区间，交换每个相邻的 $2^k$ 的区间，和区间求和。
-\\ **tag: **
+\\ **tag: **  线段树
-\\ **做法:**
+\\ **做法:**  我们发现，操作2就是将线段树中所有区间长度小于等于 $2^k$ 的节点的左右儿子交换一下。操作3就是将线段树中所有区间长度等于 $2^{k+1}$ 的节点的左右儿子交换一下。我们用线段树的懒标记维护即可
-\\ **comment: **
+\\ **comment: **  本题巧妙的把区间翻转和区间交换用线段树来维护。
 **hxm:**
-\\ **题目大意：**
+\\ **题目大意：** 给了一个$n*m$的棋盘的初态和终态，每次可以交换相邻两个棋子，每对位置之间交换次数有一个上限，求最小交换次数使得初态变为终态
-\\ **tag:**
+\\ **tag:** 费用流
-\\ **做法:**
+\\ **做法:** 容易想到由$S$向初始的黑点连边，由终态的黑点向$T$连边，然后相邻的点间连边
+但是这样满足不了交换次数的限制，也无法计算答案
-\\ **comment:**
+考虑如何满足一个点的交换次数限制
+当然是拆点
+但是一个位置被经过时会被交换两次，而终点和起点都只交换了一次
+那么我们就拆成三个点$left$，$mid$，$right$，分别管理入，中介，出
+它们之间顺次两边，费用为$1$
+流量将限制$lim$拆开，当$lim$为奇数时要考虑给哪一边：
+如果该点一开始是黑点，终态是白点，那么这个点出边一定比入边多
+如果一开始是白点，终态是黑点，那么一定要入边多一点
+否则一样多
+有一些要注意的地方：
+①要判黑白起始是否相同
+②相邻不止是四个方向
+\\ **comment:** 费用流模型的建立
 ----
@@ 行 53: / 行 68: @@
 ====== 王兴罡 ======
+比赛：CF 665div2
 ----
 ====== 黄旭民 ======
+小学期
-\\
+\\ 将所有模板整理到一个文档中

2020-2021/teams/die_java/weeksummary12.1598605017.txt.gz · 最后更改: 2020/08/28 16:56 由 fyhssgss