思路

题意是找[l,r]范围中转换成二进制后0的数量大于1的数（前导零不算）。做了几道数位dp的题后发现数位dp的大致思路大概有两种。一种是在最开始通过init打出所有情况再进行dp，另外一种就是这道题使用的dfs。对于数位dp中的dfs，我们大致使用类似如下的模板：

1
2
3
4
5
6
7
8
9
10
11
12
13

int dfs(int pos,状态(这道题是0，1的个数，是否是第一位),int limit(判断前一位是否到上限，到了现在这位就要用digit[pos])){
    if(pos==-1)return -1;//显然当pos等于-1的时候说明我们搜索到了合法数的边界，返回1
    if(!limit&&!lead&&dp[pos][状态]!=-1)return dp[pos][状态];//使用记忆化减少计算量
    int ans=0;
    int up=limit?digit[pos]:9;//如前所说，limit==true该位就同样有了限制
    for(int i=0;i<up;i++){
        if()...
        else if()...
        //状态转移：ans+=dfs(pos-1,status,lead&&i==0,limit&&i==digit[pos]);最后两个参数必须这样写，因为前导零需要之前的lead也为true同时limit也是如此
    }
    if(!limit&&!lead)dp[pos][状态]=ans;
    return ans;
}

参考博客：数位dp总结 之 从入门到模板

思路
现在发现自己的dp实在是烂，决定把kuangbin专题下的dp都刷一遍。

思路：
数位dp的入门题，主要是为了对数位dp有一个初步的认识。我一开始认为数位dp是对左右区间进行dp，不过在看了几篇博客后认识到了应当对当前位以i为第一位的数作为状态来dp。递推式还是比较简单的。

思路：
AC自动机模板题。AC自动机是在一个字符串中查找多个特征串的算法。其中使用了一个next数组和Trie树，与kmp的next数组相类似。思想就是当指向的节点不匹配时，退回上一个匹配的节点，然后在其fail节点中继续查找这个串。（可以理解为两个特征串相同的前后缀然后直接跳转）构造fail指针的时候，需要查找其父节点的fail然后查其儿子节点。利用BFS完成。在扫描的时候，需要对已经扫过的节点标记为-1，避免重复计算。

POJ – 1061 青蛙的约会

思路：
不能直接暴力，看网上的题解说这道题卡了使用mod的运行时间。所以要使用extgcd。方程由mt+x=kl+nt+y推出得到(m-n)t-k*l=y-x计算这个方程即可

思路：
树链剖分模板题，TLE11次结果发现是自己细节上蠢了。。
树链剖分的原理

树链剖分是对一棵树进行轻重链划分，然后使用数据结构来维护每条链的一种算法。通常是为了解决树上点到点（也可以是点到边）值的更新与查询。在树链剖分中，核心的算法是两次dfs。第一次dfs我们对每个节点都确定其儿子节点中最“重”的节点（也就是size最大的节点），并记录一些关键信息，如深度，父亲节点等。第二次中我们对树上节点重新编号（因为优先对重儿子赋值，使得其id在线段树上连续，使得更新更加方便），同时确定其祖先节点。重儿子的祖先是其父亲的祖先，轻儿子的祖先是自己。在查询的过程中，如果两个节点的祖先节点相同，那么我们显然可以直接在线段树上查询，而不同的话我们就先更新其到其祖先节点的val，然后用之前记录的父亲节点爬到另一根链上（这里要注意，要优先用depth较深的节点进行更新）。这样交替进行直到成为我们之前碰到的两个点在一条链上，最后完成查询。

本题思路

本题与常规提不同，查询的是边的权值。碰到这种情况我们通常把边权值赋到较低的节点上，转换成点的问题。本题还闲得蛋疼卡string和cin，需要注意。

思路：
最短路的裸题，不过想尝试一下以前没用过的Dijkstra的堆优化。Dijkstra的思路简单的说就是找目前没有扫描过的，且到出发点最近的点。标记其为使用过后再更新其周围的点的最短路径。常规时间复杂度为O(|V|^2)。在算法中我们可以使用一个小顶堆维护当前的离出发点最近的点，避免了多余的扫描，使得复杂度变为O(|E|log|V|)。这题一眼扫过去是个裸题就直接做了，没看到题目说可以有重边。。

思路：
说来惭愧，看到这道题的第一反应是一个二维的树状数组（因为题没读完）。在读二维树状数组的资料时恰好看到了别人的资料，发现读入数据是按照y坐标的递增序读入的。那么对于y的考虑显然是不必要的，所以只需要一维就能够完成这道题。这道题使用y递增序化二维问题为一维问题似乎是个不错的解题思路？然后由于是第一次手写BIT的板子，在这里稍微做一些笔记吧。

在白书上对于树状数组提供的功能有两个：
1.给定位置，计算前缀和

通过上图的二进制我们能够发现为了求到n的区间和，我们可以通过不断去掉末尾的1（即lowbit）然后对BIT[n]求和的方法来计算前缀和。那么怎么理解这个过程？我的理解是在建立树状数组的时候我们可以把每个部分看成一个小的树状数组。很显然应该能够理解类似100这样的二进制数在维护一个大区间，然后对于后面的两个0位，我们通过添加一个1（对于两个0位每添加一个1就是一个新区间，不能添加两个，不然就跑到7去了，可以对照着图理解）构成了一个小的树状数组的空间（101，110），通过这样不断递归的定义最终完成了整个树状数组。所以在回过头去求的时候我们就要去掉末尾的1返回到前面那个区间。
2.给定位置的变化量，更新维护的前缀和
根据上面的介绍，不难理解对于形如1xxx（x为0或者1）的数都处于一个类似小树状数组的空间中，通过左移1可以在同一个树状数组中逐层向上，所以而1xxx又处在10000（即多一位）的区间中，所以显然是可以这样更新的。

树状数组通常用来求解逆序对以及前缀和询问。

思路：
一道典型的树状数组求逆序对题，不详细写了，主要就是练习一下离散化.

思路：
区间上的动态规划，计算区间上的失配数。如果外围区间上()[]已经配好，dp值为dp[l+1][r-1]很显然我们要做的就是把失配的括号边上添一个括号。