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”
要求给一片文章排版，要求每行 $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”
题意：有一排 $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了。
类似上一题，给定一个长度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”
给一个长为1e5的串，问至少去掉多少个字符后该串中不包含hard这个子序列。
连续两场有类似的这样的题目搞砸了，心情复杂。
这个是比较简单的版本，当时真的怎么就没想到用有限状态机来表示呢。。。还是naive，太菜了。。。
用 dp[i][j] 表示到第 i 个位置为止，使得前缀为j长度的hard的子串不出现至少需要删除多少个字符。状态转移很简单，当为char==h&&j==0的时候dp[i][j]=dp[i-1][j]+1;
其他的就是枚举最后一步决策，按照删当前的还是不删当前的来分就行了。
这题搞砸真的非常难过，非常难过
给了 $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”
比赛时候：第一眼这不就DP吗，第二眼欸这东西怎么转移啊。。gg
当时迷了一直在想以AB和BA的数目为下标推，但是这样会有很多去重的问题。。。于是就没整出来，后来滚去推高数题了
看了叉姐的一句话题解大概懂了，推的时候直接用x和y的数目做下标，这样首先可以避免重复的问题。也就是设dp[i][j]为i个A，j个B时可用的前缀有多少种。这里面最重要的就是这个“可用的”怎么确定。这里的判断写出来很简单(i-j<=n&&j-i<=m).为什么是这样的呢？现在来考虑一个前缀，什么时候我们可以判断这个前缀一定不能作为最终答案中的某一个方案的前缀（也就是对最终答案没有任何贡献）？首先考虑凑AB，要用这个前缀的话，最终的结果是在他后面再补上(n+m-i)个A和(n+m-j)个B，注意这里的后面的排列并没有确定，也就是说我为了用到这个前缀（使答案+=它这种情况），可以尽力的去想办法摆布后面的A和B使得满足要求。那么有一个结论是在i-j>n的时候无论后面如何摆都满足不了要求：这个前缀至少可以配成j-1个AB或者BA，在加一个AB或者BA，然后如果i比j多了n个以上，那么意味着这多出来的i-j个A跟后面的配对只能配AB了，这样的话AB的总数就超过了n，由于AB和BA的总数确定的，这时候就一定不满足要求了；反之如果i-j<=n，则一定可以通过后面的调整来满足n个AB，m个BA的要求，可以自己试试看，只要注意到AB和BA的互换就行了。比如ABAB可以看出俩AB也可以看出一个AB一个BA（中间的）。。
然后dp边界是dp[i<=n][0]=1,dp[0][j<=m]=1，这个很好理解，全是A或者全是B就只有一种情况的。。。
这题还有点卡常，dp每次不要都memset，否则会tle 继续阅读“[比赛补题][DP][递推计数][思维] 牛客2019多校 第一场 E ABBA”
这个题一开始想歪了一直在想polya。。。带了半天队友节奏最后俩人都没整出来。
其实一开始就不该被给出的示意图带着走的，当时已经想到了剩下的是n-m段，但是关键在于没有想到怎么处理排列的去重。。。试了下用母函数分配出入度后来发现无法去除已经有圈的情况于是放弃。。其实这时候该想想能不能换个方向用母函数，哎，总的来说还是太菜，做组合数学还是不行。
后来想了下，可以先完全去掉所有的标号，也就是说把所有的点当成同一种点，然后去解决把这n个点分为n-m条链的分法，最后把标号还原回去只需要乘以一个n!的全排列系数就好了。
这时候问题转化为n个相同的点，分为n-m个链条（单个节点自身也是一个链条）的分法，而且这种分法要考虑到空间对称（参考样例）。我们可以设普通型母函数\[F(x)=a_0+a_1x+a_2x^2+…+a_nx^n\]来表示一条链的情况，幂次等于这条链条有多少个节点。由于不认为0个节点是一个链，所以\[a_0=0\], 然后当节点数多于1的时候由于空间对称要除以2，所以除了\[a_1\]之外所有的a都是1/2，也就是说对于一条链其母函数就是\[F(x)=x+1/2 x^2+1/2 x^3+1/2 x^4+….+1/2 x^n\]
得到了一条链的F(x)，由母函数的性质可以得到k条链\[(k=m-n)\]的情况就是\[F(x)^k\]的结果中\[x^n\]的系数，只不过还要乘以一个\[n!\]的系数（因为我们之前把所有球都当作一样了所以要乘以一个全排列）再除以一个\[(n-m)!\]（因为每次算出来的是所有可能的组合情况，但是这k条链条是不用排序的）
现在的话就是如何计算\[F(x)^k\]的结果中\[x^n\]的系数了，直接暴力肯定超时，考虑把\[F(x)\]的函数变换成更简单的形式。由级数的知识可以知道|x|<1时，\[ F(x)=（x-1/2 x^2)/1-x\] , 那么\[F(x)^k=x^k(1-1/2 x)^k/(1-x)^k \],\[x^k\]好处理，这说明只需要求剩下的部分的\[x^(n-k)\]的系数就行了。看剩下的部分，这里的分母看上去很难操作，但是可以再用级数的方式变换一下 \[1/(1-x)=(1+x+x^2+x^3+x^4+…+x^n)\], 也就是说要求的部分变成了 \[(1-1/2 k)^k (1+x+x^2+x^3+x^4+…+x^n)^k\], 后面的这一坨\[1+x+x^2+x^3+x^4+…+x^n\]可以认为是一次一次乘到前面的。前面的\[(1-1/2 x)^k\]可以用二项式展开，每一项为\[C_k^{i} (-1/2 )^ix^i\] 。这时候考虑计算“二项式展开中第i项对于最终结果的第j项的贡献度(i<=j)”，可以想象一下i变成j是因为加了j-i个1次幂，而总共后面乘的是k个多项式，那么所有的情况也就是中学常学的“把j-i个物品分成k份允许有空集的分法”组合问题了，答案是\[C(j-i+k-1,k-1)\]，当时高中数学老师管这叫插隔板法还是什么来着emmmmm。这时候就容易计算了，在算贡献的时候再带上（-1/2）的i次幂就行了。。。
确实是不好想，尤其是在现场赛的环境下，感觉自己还是得更多的做难一点的题目。
继续阅读“[数学][组合数学][母函数][比赛补题][×] ZOJ 4069(2018 青岛现场赛 L) Sub-cycle Graph”
昨晚肝这一场是真的赔了，傻不拉几的C低级失误wa了一发，出完发现大家都会F然后跑去看了20min没头绪，折回去搞这个D，到最后也没过。。。感觉复杂度没错却一直tle，一直弄到两点受不了了睡觉去了，今早上课困得一批。
下午睡醒之后一直tle on test 27，给跪了好吧，疯狂卡常数真的有意思？最后把multiset改成priority_queue过了，真的服了，到目前为止52组数据吧，最狠的一组达到了2979ms，差21ms超时呵呵呵呵呵呵。。。
继续阅读“[CF][二分check][贪心][×] codeforces 1132D Stressful Training”
http://codeforces.com/contest/1061/problem/D
嗯。。。又是这种一维的区间最优化策略问题了。。。似乎已经感觉到了套路。。。（赛场上贪心有感觉就直接上了
这种题一般是先排序（以左端点或者右端点）搞出来一个顺序，然后在这个顺序的基础上逐个考虑。考察到某一段时候一般需要做决策，然后这时候可以根据具体题目来看是贪心决策还是dp，如果直觉是贪心（毕竟真正证明有时候确实不好弄），那一般决策都跟满足条件的极端值有关，比如在这里就是如果存在能合并的点（如果连最基本的两段合并后小于各买一台电视机都不满足那一定不能合并），那么一定是和这段左边最靠近他的一个点合并。具体证明可以分情况讨论，一般真的证明的时候就是得考虑，如果不这么合并，计算出来的结果和原来的结果对比，一般要考虑之后的seg的影响，在考虑的时候可以分情况讨论（反正我一般有直觉就上233
然后在实现的时候，有时候没有头绪可以想想STL！（想起了ccpc网络赛被set支配的恐惧），这个东西有时候真的有妙用，它既保持了单调的性质（可以用来贪心）又有着动态维护的特性（贪心的动态调整）。
wa点又是精度，嗯万年精度，这次竟然LL也炸了，而且是因为add的两个参数本身可以达到LL，然后一加给爆了。。。。我去
