题意：有一排 $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;
其他的就是枚举最后一步决策，按照删当前的还是不删当前的来分就行了。
这题搞砸真的非常难过，非常难过
给一个长度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”
给了 $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”
给定 $N$ 个数字， $Q$ 次询问，每次询问为查询下标在 $[l,r]$ 之间的所有数字中所有可能的子段的 $gcd$ 有多少种。$N,Q < 10^5 , a_i < 10^6$
首先一个重要的结论：以固定点为结尾的子段的 $gcd$ 种数不超过 $max(n,log(max(a_i)))$ 证明：每次往原有的序列里加入一个数字的话， $gcd$ 要么不变，要么至少变为原来的1/2，因此为指数级减小。
有了这个结论，我们可以试着来枚举一个端点考虑本题，不妨枚举每个段的右端点$r_j$ , 假设集合$S$表示以$r_{j-1}$ 为结尾的所有 $gcd$ ，那么要求出以$r_j$为结尾的所有 $gcd$ ，只需遍历S中的每个数字$d_k$，计算其与$a_j$ 的 $gcd$ ，放入新集合$S^{‘}$即可。这样的话我们可以得到一个空间为$O(nlogn)$的结果，表示以每个点为结尾的所有段的 $gcd$ 都是哪些数字。
现在来考虑查询。每次查询的话是要求出来$[l,r]$之间所有可能的 $gcd$ 。直接暴力不可取，由上面的结果可以试着考虑能否转化为前缀问题。可以发现，如果我们对所有的$[l,r]$离线处理，按$r$从小到大排序，并且按照这个顺序来调整已经遇到过的 $gcd$ 的信息的话，每次的查询只需要考虑有多少个 $gcd$ 出现的最右左端点大于等于l，这句话具体的意思是，一个 $gcd$ 可能出现过了很多次，不同的段都可以得到这个 $gcd$ ，但是我们只考虑这些段中左端点l_j最大的那个点$p_j$，这样的话如果$l<=p_j$那么可以确定$[l,r]$中一定有这个 $gcd$ （种类+1），这就就转化成了一个计数问题。 继续阅读“[离线处理][scheduling][数论结论][x] HDU5869 Different GCD Subarray Query”
