codeforces 1325 E
题意：给定一个长度1e5的数组$a$， $1 \le a_i \le 10^6$ ，满足 $a_i$的因子数量不超过7. 求 $a$ 的最短的满足所有元素相乘结果为完全平方数的子序列的长度。
这个题目做的时候。。一直在想怎么dp。。。完全没往图的方向想。太久没做题了就是这样，丢掉了很多东西，sigh
继续阅读“[数论][图论][思维] codeforces 1325 E Ehab’s REAL Number Theory Problem”
[DP][后效性处理] codeforces 1247 E Rock Is Push
题意：
给定一个 $n*m$ 的棋盘，每次你只能向右走或者向下走，要求从左上角 $(1,1)$ 走到右下角 $(n,m)$ ，问有多少种走法。
有一个限制因素是棋盘的格子里可能有石头，然后走到一个地方就会把这里的石头按照来的方向推出去，如果有多个石头就会连带着一起推过去。
数据范围 $1\le n,m\le 2000$ ，答案对 $10^9+7$ 取模。
题解：
直接DP会有后效性的问题，我们可以给状态加上约束：令 $D_{i,j} R_{i,j}$ 分别表示一个点改变原方向后向下走/向右走有多少种走法。
这样的话dp转移可以写成类似于 $D_{i,j}=\sum_{i=1}^{n-k-i}R_{i+t,j}$ 的形式，然后这样可以得到一个复杂度 $\mathcal{O}(n^3)$ 的算法，
观察这个式子发现他是线性的，当一个维度发生变化是等式右边只有一到两项会发生变化，就把复杂度降到了 $\mathcal{O}(n^2)$ ,就可以通过本题了。
继续阅读“[DP][后效性处理] codeforces 1247 E Rock Is Push”
[KM][二分图带权匹配][优秀模板][比赛补题] codeforces gym 101635 G Cordon Bleu
题意：
题解：
KM最大权二分图匹配。然后权值的话，左侧原来的 m 个点代表送货员的家，与右侧表示红酒地点的 n 个点之间连边，权值为送货员的家 ni 与红酒处 mi 之间的距离与 mi 到 饭店之间距离的和，选中这条边的话表示这个人直接从家里到红酒处然后把酒送到了饭店。之后在左侧新建 n-1 个点表示走到店里又出来的送货员，其与右侧n个点的权值设为2倍红酒到饭店的距离，因为回到店里之后所有的送货员就没差别了，而且一个人可以被重复利用，没有什么先后的时间限制。n-1 是因为最多就只有 n-1 瓶红酒会被从店里又出来的人送到（至少有 1 个人是直接从家里到红酒处的）。这样直接跑KM就可以了，但是有个问题是原来的KM板子太慢了，到UOJ#80找了个新的板子，能1s跑2000个点的KM。。。
继续阅读“[KM][二分图带权匹配][优秀模板][比赛补题] codeforces gym 101635 G Cordon Bleu”
[单调性优化DP][二分][比赛补题][×][思维] codeforces gym 101412 I Beautiful Spacing
题意：
要求给一片文章排版，要求每行 $W$ 个格子，每一行的要求是首单词必须顶格，除了最后一行之外的尾单词也必须顶格，然后单词之间至少有 $1$ 个空格，单词内部不能有空格，也不能改变单词之间的顺序。现在问在排版方案满足这些要求的条件下，单词之间的最大空格最小是多少。数据量: 每一行的格子数： $3\le W \le 80,000$， 总共的单词数：$2\le N\le 50,000$ 每个单词的长度 $x_i$ 满足 $1\le x_i \le \frac{W-1}{2}$
继续阅读“[单调性优化DP][二分][比赛补题][×][思维] codeforces gym 101412 I Beautiful Spacing”
[高斯消元][模拟][比赛补题][×] codeforces gym 101412 B Stylish
题意：
给定一段代码，让模仿出来他的代码缩进风格。缩进风格由三个数字 $R C S$ 确定，分别代表到当前位置有多少个未封闭的圆括号/花括号/方括号 ，然后每多一个 $R/C/S$ 的话，多出来的缩进数是确定的。现在要求用学习到的代码风格对新的一段没有缩进的代码进行缩进，输出每行缩进的空格数。数据范围行数 $N\le 80$ , 每行最多80个字符。
题解：
显然难点在于能不能用已经学到的经验来推断出来现在该缩进多少。把所有 $(r,c,s)$ 的三元组看成一组向量，等于说新的向量能不能被之前出现过的表示出来，也就是是否线性相关。那么我们只需要用高斯消元去解就行了，如果有唯一解那么一定是可以被表示出来的，这是后这个就能解出来了，如果不是的话就把这个新的向量插进去作为一个新的基。
这个题当时的问题就在于没有一个好的高斯消元板子。。。于是很正经的去找了一个好的板子TAT
wa点：没注意到题目说RCS最多只有20个最少至少有1个。。。这个限制导致了在某些情况下方程解不出来但是仍然可以确定RCS的数值。
[比赛补题][线段树][连通分量][二分图] codeforces gym 102055 B Balance of the Force (CCPC 2018 Final)
题意：
给定 $N$ 个人，每个人可以选择加入黑暗 $Dark$ 或者光明 $Light$ 两种阵营，他们加入不同的阵营之后获得的力量值是不同的，即 $D_i$ 和 $L_i$ 。然后有些人之间有矛盾，是不能加入同一阵营的，矛盾的对数共有 $M$ 对，现在给出所有的矛盾和所有的 $L_i D_i$，问在所有可能存在的最终阵营分配情况中，力量值最大的人和力量值最小的人之间的差最小可能是多少？如果说不可能分配的话输出$IMPOSSIBLE$。其中 $1\le N\le 2*10^5$, $0\le M\le 2*10^5$, $1\le L_i D_i \le 10^9$ ,共20组test，时限4S
题解：
一个非常有意思的，看上去像是图论其实是数据结构的题目。。其实以前做过类似的？应该是今年西安邀请赛时候，区别在于那个题目应该是一种背包的性质，一个联通分量要么选，要么不选，而这个题是每个连通分量都得选，但是要从两套孪生方案中选择一种，每一种都会有一个最大值和一个最小值。
把两两不能在一起的人之家连一条无向边，那么一堆互相有关系的人就形成了一个连通分量，不在同一个分量里的人互相是完全没有影响的，无论这个人是选择D还是L都跟我的选择没关系。而在同一个联通分量里的情况的话，可以发现只要有一个人的状态确定了就可以用二分染色的方法确定连通分量里其他所有人的状态。因此我们首先用染色法对每个连通分量判定，如果能染色成功那么就说明有可行解存在，否则输出$IMPOSSIBLE$，另外，在dfs的过程中还要顺便把每个连通分量的两种方案的最大值最小值总共四个数分别求出来（这里我当时就写假了emmm）。之后考虑如何让差值最小化，一般让某个东西最小化很容易想到二分，但是这个题目的条件下，如果要二分就必须再 $O(n)$ 枚举一个下界，乘上 $O(n)$ 的check的话就n方了，显然无法接受。这时候观察这个题目，此时的每个元素(连通分量)正好有两个属性，发现我们可以用一个常用的套路来尝试，那就是按照其中一个属性排序然后对另一个属性套某种log的数据结构。。对这个题来说，回想我们刚才考虑的二分，他必须有一个操作就是枚举出一个下界or上界，那么如果我们就着这个操作进行下去会怎么样？如果我们能一边枚举一边很快的计算出来当当前枚举到的最小值是最小值的时候最大值最小是多少，那么这个问题就可以解决了。
继续阅读“[比赛补题][线段树][连通分量][二分图] codeforces gym 102055 B Balance of the Force (CCPC 2018 Final)”
[比赛补题][2SAT][x] codeforces gym 101987 K TV Show Game
题意：
题意：有一排 $n$ 个灯，可以是红色或者蓝色，然后k个人投票，每个人投的票会写上他猜测的某三盏灯的颜色。然后现在问是否有一种红蓝灯的安排方式使得每个人投的票至少有2个猜测是对的。
题解：
$2-SAT$ 板子题，但是比赛时候忘记了（主要这东西在中国真的很少考emm）相当于求让每个人的条件都为真的一组二进制向量。那么现在的问题就是怎么把每个人的约束条件转化为 $2-SAT$ 的子句的形式。
首先用 $x_1$ $x_2$ $x_3$ 表示一个人的三个选择，那么代表这个人的子句用文字表达来说就是 $x_1 x_2 x_3$ 中有2个或者3个为真。用条件的知识可以推出来这个说法等价于 $(x_1\lor x_2 )\land(x_1\lor x_3)\land(x_2\lor x_3)$ ,这样就把每个人的条件写成 $2-SAT$ 的形式了，接下来按板子连通分量+拓扑排序求解就OK了。
[比赛补题][线段树+][动态维护矩阵乘法][动态dp][区间lr问题] codeforces 750E New Year and Old Subsequence
题意：
类似上一题，给定一个长度2e5的字符串，2e5个询问，每次问从区间 [l,r] 里面最少删去多少而可以使得结果中存在2017但是不存在2016。这个是比较好的一道题，之前我从没来遇到过动态维护动态规划的。。。这叫什么，动态动态规划？（雾）
题解：
首先考虑简单版的问题，如果不考虑查询，单次做问整个序列最少去掉多少该怎么做？我当时是考虑了很多，但是如果按照正常的考虑方式的话就会越想越复杂，不知道该维护什么样的一个状态。该以什么作为状态呢？如果按照状压的思路会发现无法转移，因为他这个2016和2017都是有顺序的啊，不能状压搞，但是也不能把前面的所有情况搞出来，复杂度会爆炸。看了题解发现有人提正则表达式和有限状态机才明白了。。。之前做的那个题简单是因为他很好转移，是不包含当前前缀时最少需要删除多少，而这个题目的状态需要定义为包含当前状态机节点对应的前缀且不包含严格包含当前状态机节点对应的前缀最少需要删除多少个字符。。。意思就是20的时候不能有201和2017的时候的需要删除的最少字符。。
然后考虑状态的转移，这个有限状态机可以匹配出来2017，但是匹配出来之后呢？我们应该拒绝掉所有的2016，注意这时候，从状态2017和201都可以转移到2016，所以我们当前如果已经匹配完且达到2017/201的时候，转移回到本身都需要多删掉一个字符，也就是本身。。。其他情况是如果要往下一个节点走的时候，回到自身的代价是1，往下走的代价是0.。。其实也就是一个选择，选择当前的这个字符留还是不留，，，，跟谁匹配的话比较好。。
然后他很妙的一点就是这个转移可以写成矩阵的形式，当然这不是一个矩阵乘法，是一个很怪的操作，类似Floyd最短路的方法，然后这个矩阵操作是满足结合律的（我也不知道为什么满足结合律）。。。。就可以用线段树维护了。。。
甚至说这个题甚至可以改成带修的。。
继续阅读“[比赛补题][线段树+][动态维护矩阵乘法][动态dp][区间lr问题] codeforces 750E New Year and Old Subsequence”
[DP][子序列][有限状态机][正则表达式] codeforces 1096D Easy Problem
题意：
给一个长为1e5的串，问至少去掉多少个字符后该串中不包含hard这个子序列。
题解：
连续两场有类似的这样的题目搞砸了，心情复杂。
这个是比较简单的版本，当时真的怎么就没想到用有限状态机来表示呢。。。还是naive，太菜了。。。
用 dp[i][j] 表示到第 i 个位置为止，使得前缀为j长度的hard的子串不出现至少需要删除多少个字符。状态转移很简单，当为char==h&&j==0的时候dp[i][j]=dp[i-1][j]+1;
其他的就是枚举最后一步决策，按照删当前的还是不删当前的来分就行了。
这题搞砸真的非常难过，非常难过
[权值线段树][比赛失误][x] HDU 6609 Find the answer
题意：
给了 $N$ 个数 $W_k$ , 对于每个 $1 \le i \le n$, 在 $i$ 以前不包括 $i$ 的所有 $W$ 里选取最少的一些 $W$ 将其变为 $0$ ， 使得 从 $1$ 到 $i$ 的和不大于 $m$ 。要求对于每个 $i$ 输出最小的数目。
题解：
做的时候傻了，一直用set乱搞，搞来搞去总是tle，主要是用set维护真的会被卡。。用平衡树板子又有点大材小用，于是就米勒很久。
所以说遇到一个简单题很久没出的话，可能就得考虑全盘否定直接从来了。。。
如果一开始就没有被赵老师带着想set，而是直奔线段树去的话，就很好搞了，直接把问题转化为在前 i-1 个数里找出最少的数字使得之和大于 $pre[i]-m$ ，其中 $pre[i]$ 是前缀和。这样的话直接用权值线段树来做，每个节点存两个域，一个是数字的个数，一个是数字的和。。然后query的时候利用线段树天然的二分性质来搞就行了。。。
这题其实动机真的不难，就是因为不用数据结构的话每次要排序，然后权值线段树天生有排序的特性在里面。。。所以遇事不决还是先考虑线段树。。。不能一开始就想骚操作emmmmm
继续阅读“[权值线段树][比赛失误][x] HDU 6609 Find the answer”