• 创建了本周训练周报
• 创建了暑期自己第二次加训界面

The 2015 ACM-ICPC Asia Beijing Regional Contest

fyh:
题目大意：一个序列，你可以每次把这个序列前五个重排，然后如果重排后前三个数相同得一分，无论得不得分都会把这三个数删掉，特殊的是如果最后剩下三个数还相同的话也得一分，求最大得分
tag:DP，DP优化
做法:首先如果当前位置三个都相同我们一定要得上这一分（根据荒谬的方法可以证明（误））

设$dp[i][x][y]$表示当前在第i轮，这两个数是x,y的最大得分。

分几种转移，一种是三个数都相同的，那么对于$dp[i-1][][]$的所有合法状态都应该+1

第二种是有两个数相同的，设相同的数为p，另外一个为q，那么$dp[i][q][k]$可以从$dp[i-1][k][p]$（或者反过来）转移过来。

第三种是很随意的，设那三个数分别为p,q,r 那么$dp[i][q][r]$可以从$dp[i-1][p][p]$转移过来。

以上三种都是会使得答案增加的，当然我们必须得把其余剩下的所有换数情况考虑进来，比如直接把这三个数扔掉；扔掉其中两个数与自己手中的一个数；还有把自己手中的数全扔了，选两个加进来。

这看似是$O(n^3)$的，但是实则每次从$dp[i-1][][]$转移到$dp[i][][]$的最多是$O(n)$的，所以时间上得到了保证，至于空间上的优化，我们可以直接把第一维压掉，直接覆盖即可（有些当然不能直接覆盖，分析会发现，需要进行转移的信息只有$O(n)$个，所以转移前也需要维护这些信息。）（当然写起来有亿点恶心）
comment:当时想到了$O(n^3)$做法，觉得绝对没前途于是放弃，实际上把所有转移方程写出来是可以优化到$O(n^2)$的

wxg:
题目大意 给了一个长度为 $2^n$ 的数列，让你进行单点修改，翻转每一个 $2^k$ 的区间，交换每个相邻的 $2^k$ 的区间，和区间求和。
tag: 线段树
做法: 我们发现，操作2就是将线段树中所有区间长度小于等于 $2^k$ 的节点的左右儿子交换一下。操作3就是将线段树中所有区间长度等于 $2^{k+1}$ 的节点的左右儿子交换一下。我们用线段树的懒标记维护即可
comment: 本题巧妙的把区间翻转和区间交换用线段树来维护。

hxm:
题目大意： 给了一个$n*m$的棋盘的初态和终态，每次可以交换相邻两个棋子，每对位置之间交换次数有一个上限，求最小交换次数使得初态变为终态
tag: 费用流
做法: 容易想到由$S$向初始的黑点连边，由终态的黑点向$T$连边，然后相邻的点间连边 但是这样满足不了交换次数的限制，也无法计算答案

考虑如何满足一个点的交换次数限制 当然是拆点 但是一个位置被经过时会被交换两次，而终点和起点都只交换了一次 那么我们就拆成三个点$left$，$mid$，$right$，分别管理入，中介，出 它们之间顺次两边，费用为$1$ 流量将限制$lim$拆开，当$lim$为奇数时要考虑给哪一边： 如果该点一开始是黑点，终态是白点，那么这个点出边一定比入边多 如果一开始是白点，终态是黑点，那么一定要入边多一点 否则一样多

有一些要注意的地方： ①要判黑白起始是否相同 ②相邻不止是四个方向

comment: 费用流模型的建立

比赛：cfglobal#10(ABCDE),abc176(ABCDE)口糊了abc176的F
补了训练赛的K题，回忆并总结了数位DP。
整理了几种特殊网络流的板子

比赛：CF 665div2

小学期
将所有模板整理到一个文档中