题意：
$n$ 个集合，每个集合最多32个unsigned int范围的整数， $m$ 个询问，每次问下标在 $[l,r]$ 之间的集合能否表示出 $x$ 。数据范围 $1\le n,m\le 50000$，每个数字都在 unsigned int 以内。
题解：
线段树维护线性基即可。学习了一发板子。
继续阅读“[线性基][线段树][模板] 牛客多校第四场 B xor”
[SAM][dp][拓扑排序][模板] 洛谷 P3975 TJOI2015 弦论
题意：
给定一个长度为 n 的字符串，让求出它的第 $k$ 小子串是什么。每次除字符串之外还会给定两个参数 $t $和 $k$ ，$t$ 为 $0$ 则表示不同位置的相同子串算作一个, $t$ 为 $1$ 则表示不同位置的相同子串算作多个。数据范围 $n\le 5*10^5$ $t\in {0,1}$ , $k \le 10^9$.
题解：
后缀自动机板子题。我们知道每一个子串放在sam上跑一定可以走到一个合法节点，反过来说任意一个节点一定代表了一批能走到这儿的子串。那么我们可以想办法把到达每个节点有多少种子串用dag图上dp的方式求出来，然后在t=1的时候，根据sam的性质，给每个dp值再乘以一个 $|endpos|$ 就可以了。学习到的是比我原来板子更快的拓扑排序方式。。。直接用len结果在数组里排序，比起用queue来常数小了很多。另外还纠正了自己的对于sam拓扑序的一个错误认识，他其实无论是slink还是dwag的拓扑序都是一样的，因为无论哪种都一定是从小的子串往大的走。
继续阅读“[SAM][dp][拓扑排序][模板] 洛谷 P3975 TJOI2015 弦论”
[单调性优化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;
其他的就是枚举最后一步决策，按照删当前的还是不删当前的来分就行了。
这题搞砸真的非常难过，非常难过
[线段树][多标记][欧拉降幂] ZOJ 3998 Yet Another Data Structure Problem
题意：
给一个长度1e5的序列，两种操作：操作1 把区间内元素都乘以一个v，操作2：把区间内元素都变为原来的k次方
然后有1e5个询问，问 $[l,r]$ 之间的区间积
题解：
线段树上双标记问题。维护两个 $lazy tag$ ，一个负责次幂一个负责乘，其实相当一个加法和一个乘法然后求区间和。我这里维护的思路是每次都保证维护的点是一个 $k*(a_l a_{l+1}… a_{r} )^w$ 这样一种形式。这样的话每次标记下传的时候，先把w的次幂传下去，注意这时候儿子的k也要变成 $k_{son}^w$ ,然后再把k传下去，即给儿子的 $k_{son}$ 再乘上 $k$ ，这两个顺序搞清楚之后就很好写了。
wa点是，维护$w$次幂对质数取模的时候不能写 $\%mod$ ，而应该用欧拉定理降幂， $\%(mod-1)$ 貌似我因为这个错过很多次了听说用BSGS预处理的话会更快不过我没试过emmm
继续阅读“[线段树][多标记][欧拉降幂] ZOJ 3998 Yet Another Data Structure Problem”
[权值线段树][比赛失误][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”