248
- cf#377c 就是考虑第哪一餐之间到和哪一餐之后走。
- cf#377a
- cf#377b
- cf90a
- cf90b
- cf90c
- hdu4007
- cf724A
- cf724B
- bnu52308 set+模拟
- hdu5918 kmp
- hdu5914 找规律，1 2 3 5 8 13 21
- bnu52306 暴力
- bun52307 搜索，预处理守卫到每个点最小的时间
- bun52309 找规律
- hdu5907 长度为n的连续字符串对答案的贡献是
(1+n)*/2。 - hdu5908 预处理所有的约数，然后o(n)去检测分成的区间是否符合要求。、
- 2016弱校联盟十一专场10.2A
- 2016弱校联盟十一专场10.2E 找规律
- hdu5792 先预处理四个数组，然后容斥搞一下，枚举(a,b)情况，乘以(c,d)的个数，其中a和d不会相等，但是b和d有可能相当，所以需要减去重复的情况。
- cf719e 矩阵快速幂+线段树，线段树去维护快速幂的第一个矩阵，然后相加就相当与乘上这个矩阵。
- hdu3294 manecher算法，输出的时候要想一下。
- hdu5781 概率dp
- hdu5787 数位dp，记录的有点多
- hdu5791 简单容斥，设dp[i][j]为第一个长度为i第二个长度为j时的答案，如果a[i]==b[j],那么dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+1,否则dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]-dp[i-1][j-1]。
- hdu5886 树形dp，首先预处理出一条树上的直径，然后以直径的两个端点为起点进行dfs，依次处理出以第i个点为根的子树的最大直径。最后考虑删去每一条边，如果这条边不为直径上的边，对答案的贡献还是直径，否则取分别以这两个端点为直径的子树的直径的最大值。
- hdu5903 根据题目的特性，只需要考虑n/2的长度就可以了。从n/2开始dp，dp[i][j]表示当字符串从n/2到i时，距离为j能否满足。如果存在答案，那么从正序开始构造答案，尽量让前面的字典序最小。
- hdu5904 离散化，离散化当中要去除数组中重复的数字，还有可能3和5不是相邻的，离散化之后可能相邻，所有在中间要插入一个多余的数字4，才能保证离散化的正确性。最后数列的长度要在1e5左右才能memset。
- hdu5828 线段树，没有开方操作的话，都是最基础的线段树，然后1e5开不了几次就会到1了。维护区间最大最小和区间和，开方时，如果一个区间内数都相同，那么就相当于减去一个数，直接标记一下就可以了。如果区间内最大和最小相差大于1，暴力更新下去。如果最大和最小差为1，对最大和最小值开方，如果值相同，那么再用一个标记符号，表示区间内的数都相同，否则相当于原来的最大最小值减去一个相等的数。
- hiho1383 模拟
- hiho1385 模拟
- cf#373a
- cf#373c 找到离小数点最近且数值大于等于5的开始处理，从后先前判断能不能再进位。
- hdu5823 首先通过枚举处理出来所有的点独立集（即点集中的点都没有边相邻），然后再dp计算每个点集的最小值。
- cf#373b 枚举第一位放r或者b，然后每种情况统计一下不符合的颜色数量，再取一下最小的。
- hdu5893 树链剖分+线段树，线段树合并区间内有多少段时，前一段右端点和下一段左端点比较一下，另外要注意的是在树上分段查询的时候要，要保存每一个端点的前一段，因为这里也要去除重复。最后自己写的时候，线段树的更新写错了。
- hdu5887 贪心+搜索，将物品按体积从大到小排列，然后维护一个后缀，如果搜索时发现可以将一个后缀上的全部都装完，直接更新。
- hdu3911 线段树，区间取反操作，延迟更新，向上更新和向下更新，还有注意查询。
- hdu5881 贪心，前两次取l+2,之后每次只能取2个，然后特判掉一些答案。
- hdu5884 二分答案，用两个队列验证。
- cf#372a
- cf#372b 注意题意
- cf#372c 最简单的解法应该是第i次时，当前的值为i*(i-1)，假设下一步时值为(i+1) * i,然后应该加 (i+1) * (i+1) * i-i-1次。自己的想法是假设当前为m，那么要能开方且复合题意的话，要得到的值最小应该为mi=(i+1) * k，其中要满足(mi * mi -now)%i==0，k可以通过二分来找到，还要注意一点计算过程中会超过long long 的范围，所以要避免4个数连乘，先求与除数的公约数，之后再乘。
- hdu5895 数位dp
- hdu5898 区间dp
- hdu5889 先求最短路，然后在最短路边上求网络流。
- hdu5883 先判断欧拉路径，如果存在，那么每个顶点的值都要贡献(in/2+1),其中in为这个顶点的度。如果所有点的度都为偶数，那么要枚举一下哪个点为起点，那么这个点要多贡献一次。
- hdu5882 符合题意的游戏要求你选择什么东西的胜率都要为0.5，如果每个选择看成一个点，连出去的边和连进来的边都要一样多。当n为奇数时符合题意。
- hdu5879 当n很大时，这个表达式的上界是pi*pi/6,n很小的时候直接计算。
- hdu5878 暴力打表得出所有的组合，然后对于每一个输入直接lower_bound查找答案。
- hdu2439 贪心
- hdu5812 d(x,y)=f(x/gcd(x,y))+f(y/gcd(x,y))，f(x)为x所包含的质因子的个数。首先预处理出来全部的f(x)，对于每个x，枚举所有的约数y，计算计算一下x和y的d值为s，用c[y][s]记录一下一共有多少个，由于s很小，所以再用d[y]状态压缩把记录一下s=i有没有出现。查询的时候也用类似的方法。
- cf#371a 考虑两个区间的关系
- cf#371b 判断一下一共有多少个不同的数字，然后考虑关系。
- cf#371c 记录一下某个数字有没有出现过，如果没有出现过那么把它按题意转化为01组成的串并放在一个map中储存，然后查询时直接输出。
- hdu5964 计算一个发现第i个字符串的字符数为2^i-1个，所以对多只需要计算到60左右就可以了，然后利用观察一下相邻两个字符的关系，利用容斥计算一下就可以了。
- hdu5811 拓扑排序+最长上升子序列，首先分别检查一下所要求的两个序列是否符合题意，这里用拓扑排序就可以了，如果有环就说明一个序列不符合要求，然后拓扑序就是一个符合条件的解。之后对于每个t2中的数，在t1中找到一个合适的位置，并记录下来，再在记录下来的序列中求最长上升序列就是解了。
- hdu5700 将所有区间按l升序排列，枚举左端点，依次将区间插入线段树，每次只需要将r点+1即可，然后在线段树查找大于k的最远端。
- hdu5691 状态压缩dp，dp[i][j]，i中的每一位代表点是否有使用了，j代表得到当前集合中最后一个选择的点，那么指定某个数放在那里就是第几步只能选用那个数字。
- patA1112 出错的字母，在原字符串中出现的次数一定可以整除k，所以预处理出哪几个字母出错了就可以了。
- patA1116 按题意输出即可
- patA1117 排序，然后对于每个ai，看一下后面是否有ai-1个数，如果有的话，就是一个符合条件的答案， 最后取ai-1最大。
- patA1118 并查集应用
- patA1119 已知前序和后序遍历，求一种中序遍历，这里只要递归建树就可以了，然后中序遍历不唯一的情况是有一个结点只有一个子结点，特判一下就可以了。
- hdu5869 将查询区间按r升序排列，计算(l,r)中的不同gcd的数量转化为计算(1,r)和(1,l)中的不同gcd的数量，然后做减法得到答案。用一个mp维护每个gcd出现最靠右的位置，用树状数组记录每个位置上是否有gcd贡献。
- hdu3333 想法更上一题类似。
- hdu5875 对于每一个a[i]，记录下第一个j使的a[j]<=a[i]。
- cf#370c 刚开始想从(x,x,x)进过一些方法得到(y,y,y)，但是想了好多方法都不行。后来发现反过来想比较简单从(y,y,y)开始，按照三角形的要求得到下一个为(2*y-1,y,y)，然后一直这样做下去。最后当三角形边最小的长度大于x时，就可以结束了。
- cf#370a
- cf#370b 每一个走一个u必须要再走一个d，走一个l必须要再走一个r，反之也成立，所以统计一下就可以了。
- hdu5874 找规律
- hdu5877 dfs+离散化+树状数组，树状数组维护不同的值有多少个，访问某一个点先计算，然后再将这个点的值加进去，回溯是减去。
- hdu5876 维护两个set，一个表示补图已经与s直接或间接连接了的点集合，另一个表示还没有连接的，所以每一次从第一个集合中取出一个点，然后与第二个集合中没有原来链接的点，都可以在补图中连一条边，一直重复这样的操作不断减少第二个集合点的数量，-1的情况是某个点原来和剩下的其他点都有边相连。
- hdu5873
- hdu5876 bfs+set
- patA1048 对于输入x<=m,看一下前面时候出现过m-x，如果有那么有解。在标记一下x出现了。
- cf#338a
- cf#338b 找一条上升的链，美丽值为链的长度乘以序号最大的点连的边数量。所以反过来想，找出每一点可以组成的最长下降的链的长度，然后比较一下。
- cf#339c 贪心，预处理a[i][j]为t从i开始和s从j开始最多匹配多少个字母，同理处理出来s翻转之后的值，之后就是贪心，遍历每一个t中的字母，一直从已经匹配的里面加上去。
- patA1019 计算出d进制下n的值，然后判定一下是否是回文数。
- patA1021 并查集+树形dp，用并查集判断一下是否是树，然后dfs以1为根计算出最大的深度，第i个点的答案一定是与它相连的父结点那块的最大深度或者是自己的子树的最大深度+1，然后如果是最大肯定有一个是0的，所以也可以用树的直径去做。
- patA1014 模拟，有几个窗口就开几个队列，然后考虑一下每次处理完成任务时间最早的那一个，如果还有排队的就加到这个队列去。最后注意，只要某个人在17点之前被服务到，都不用输出Sorry。
- patA1015 先将n转化为d进制下的数x，然后获得相反的数y，将y转化为10进制下的数m，最后看一下n和m是否为素数。
- poj3367 线段树，每个结点维护从左开始最大有多少个连续的0、从右开始最大有多少个连续的0，两个子树合并时中间有多少个连续的0。根据维护的信息查询即可。
- patA1012 对每一门课程分别排序，最后比较输出。
- patA1013 对于每一个被询问的城市，删除与其相连的边，再进行dfs搜索，统计出有多少连通块，答案为连通块数量减一。
- patA1010
- patA1011
- poj2484
- poj3111 01分数规划
- poj3414 搜索
- poj1118 枚举
- poj1952 nlogn求最长下降子序列，对于每个数字遍历之间大小大于它的并且可以放置在它前一个位置的，累计答案，不能用树状数组之类的保存。
- cf#363a
- cf#363b 随便取一个点，枚举全部n+m的点为放置炸弹的点，检查一下。
- cf#363c dp
- cf#346f 将所有点按从大到小排序，然后用并查集维护相邻并不小于a的，如果有某个并查集内的最小值乘以点的个数大于k，并且k能整除a，就用bfs找到一组合适的解输出。
- cf#369d 图比较特殊，找出图中有多少个环就可以了，每一个环对答案的贡献为乘上2^n-2，其中n为环中顶点的个数，最后乘上2^m，m为不在任何一个环上的点的数。
- poj2774 后缀数组
- poj1035 暴力
- poj2231 计算任意点之间的距离和
- hdu3466 排序之后01背包
- cf#346b 排序
- cf#346c 暴力+二分
- cf#346d 找出四种会掉入水里的情况
- cf#346e 贪心，从某一没有访问过的点出发，如果找到一个环，那么出发的点也可以访问到。
- cf#349a
- cf#349b 计算出要填的数字，然后在验证一下是不是幻方。
- cf#349c dp，n^4，dp[i][j][k]，i代表第i棵树，j代表涂的颜色，k代表前i个分成的段数。
- AIM Tech Round 3e 树形DP，对于一个点u，如果没有一个子树的大小大于n/2，那么这个点就是重心。另外最多只有一个子树v的大小大于n/2，这时候要考虑在v中删除最大的一个节点数不超过n/2的子树，如果删去后子树v的节点数还是大于n/2，那么u不可能成为重心。维护两个数组，down和up，down代表以u为根的树里面的子树节点数不超过n/2的最大值，up代表u的搜索过程中不包含u为根的树中子树节点数不超过n/2的最大值。up值计算需要注意一下。
- cf#364a
- cf#364b 简单容斥,维护一下每行每列有没有放置过，已经放了几个，然后容斥计算一下。
- cf#364c two points，题意就是找一个包含全面出现过的字符的最短子串长度，维护左右端点取一下就好了。
- cf#364d 贪心加二分验证，将n分成每组最多k个人的小组来考虑，问题中要求的就是最后一组什么时候到达，然后可以想到的一点是，汽车最好在所有的时间里面都在运行，所以我们枚举第一组坐车多少米，之后他们就是步行到终点，计算一下这样的时间，并且假设这个是答案，在去验证剩下的小组能不能在这个时间内达到终点。
- cf#365e 两次dfs，从1开始搜索，son[x]记为以x为根的子树里有多少所大学，然后找到第一个son[x]>=m的做为下一次dfs的起点。第二次dfs以x为起点，计算到每一所大学的距离，然后在累加一下。另一种做法就是考虑每一条边取左右最小的大学数作为对答案的贡献。
- hdu5772 最大权闭合子图，注意一下建图。
- AIM Tech Round 3a 模拟
- AIM Tech Round 3b 分别考虑第1个点不走或者第n个点不走，那一段路走两遍，还要考虑起点是在这些点的中间、左边还是右边。
- AIM Tech Round 3c 改变从左到右遇到的第一个可以改变的字符串，特别注意一下如果给定的串全部由a组成要改变最后一个a。
- AIM Tech Round 3d 00和11的个数可以推测出0和1的个数，设00为n个，0为m个，有n=(m-1)*m/2。如果00和11的个数为0的话，如果有10和01的，那么0和1的个数为1。假设0为x个，1为y个，那么10和01的个数必要符合等于x * y。最后构造答案，假设有一个x个0的字符串，那么我们去构造10的这种组合，只需要在字符串中插入1，然后统计一下这个1后面有几个0，如果刚好有符合题目个10组合，那么把1全部放在最后一个0的后面。这样子01会自动符合条件的。
- poj1835 每一个状态维护face、head、right分别是哪边
- poj3087 模拟
- poj3254 状态压缩dp
- poj3083 第三问的答案直接bfs即可。前两问本质相同，对于到达每一个点维护一个方向，先走左边的就是从左边的开始顺时针走，另外一种情况从右边的开始逆时针走。
- hdu4911 数列如果有逆序对，那么肯定存在交换一对相邻的减少一个逆序对。所以只需要求出所有逆序对的个数，与k比较大小就可以了。求逆序对可以先用离散化或者排序，之后在用树状数组来统计。排序的时候要采用稳定排序stable_sort()。
- hdu4907
- cf#366b n为奇数2胜利，为偶数1胜利，每一个都这样考虑，再考虑如何合并即可。
- cf#366c queue模拟，注意是前t个生成的信息而不是前t个操作。
- cf#366d 贪心，最后形成的链一定是s为起点，t为终点，对于每一个i遍历前面已经生成的链找一个最优点插进去，一直这样操作找到的一定是最优的。
- cf#368d bitset+dfs,构建一棵树来，每一个输入与前一个相连结，对于操作四与第k个链接，注意搜索的时候回溯。
- cf#edu16a
- cf#edu16b 找中间的一个数
- cf#edu16c 最中间一行全部放奇数，之后向上向下每一行减少放两个奇数，最后剩下的位置放偶数。
- cf#edu16e dp，n的范围在1e7以内，所以可以保留全部答案，也可以从n开始往下搜索。
- cf#368e 二维树状数组+暴力更新。
- cf#365d 自己只想到莫队算法，但是这次居然数据范围有1e6个，所以毫无疑问的超时。根据这道题目的特点，当加入某一个数字时，第一次出现不用统计，第二次出现才要统计。所以将所有查询离线，然后对查询区间按r排序，之后对于比较当前查询的r与已经求的的r的关系，如果小了，将前一个出现这个数的位子上异或上对应的这个数字。然后再查询l开始的值。可以放在树状数组上维护。
- cf#368a
- cf#368b 找出一条两端点分别可以建仓库和建面包店的权值最小的边即可
- cf#368c 根据勾股定理，aa=(c-b)(c+b),如果输入的n为奇数，那么把它当成a带入到式子中，把c-b当成1解出b和c，如果输入n能整除4，那么用3、4、5构造出一个解来，最后剩下的可以整除2的先除以2剩下的一定是一个奇数，按第一种构造就可以了。特判1和2为不可能。
- cf#365c 如果按照题意思考，很难搞清楚情况。所以把问题转换一下，假设只有人在走，水平方向速度为v，竖直方向速度为u。根据物理知识，人在问题中的停止可以当场先在x轴上走一段距离，然后再同时朝上和朝右运动。又由于u和v已知，所以同时运动时的运动轨迹是确定的，而且是一条直线，假设这个斜率是a，又假设现在x轴上走了b米，那么运动方程是y=ax-ab。最后要求的就是一个最小的b满足y[i]>=ax[i]-ab，即所有点都在直线上方。另外特殊考虑b=0时是否所有点都在直线下方，如果是那么这个是最优解。
- cf#366a
- hdu5862 线段树/树状数组+离散化，题目比较特殊，首先对x坐标进行离散化，然后将平行于y轴的线段拆分成两个点，按y坐标分。再按y坐标大小排序，遇到平行于x轴的查询区间x1到x2的大小即为交点数，遇到平行y轴的线段，如果是某条线段y坐标小的点，线段树上x1点+1，否则x1点-1。自己写的时候，离散化的数组忘记排序以及线段树的大小考虑错了导致超时。
- ACdream1028 树形DP，需要在树上找出长度为奇数和长度为偶数的最大链，记长度为ans[0]和ans[1]，输入查询后和对应的答案比较一下即可。dp[i][0]和dp[i][1]分别代表以i为根的子树上面最长奇数长度的链的长度和偶数长度链的长度，然后注意一下转移方程就可以了。
- hdu5861 线段树，根据题意，每一条公路只能开一次。所以对于每一条公路，第一开了之后，只有当最后一次使用完成之后才可以关闭。所以，我们要预处理出每条公路第一次使用和最后一次使用的时间。这里我直接用线段树维护每一条公路的最迟和最早使用时间。之后，本来自己想的是在以天数建一棵线段树，把每一条公路的最早和最迟使用区间内的每一点都更新值，最后在查询得出答案。看了人家的博客后，发现可以在原来的树上直接做，将得到的时间排序，然后最早时间线段树对应点加上费用，最迟时间之后线段树上对应点点减去费用。每一天的答案都在sum[1]上。
- hdu5857 考虑三种区间情况，分离，相交和包含。然后统计两个一共有多少数字，按照前面的情况讨论一下中位数在那里就可以了。
- hdu5858 数学题，发现这个图像放大缩小，阴影部分面积与正方形面积的比例不会改变。所以只需要考虑长度为1时的情况就可以了。然后，解微积分明显不靠谱，所以在里面多连几条辅助线，用三角函数关系可以得出来。刚开始用matlab求了一下交点，也许可以将图形用matlab画出来，然后用抛针法来逼近那个比例。
- hdu5867 注意一下特殊的英文单词就可以了。
- ACdream1015 树形DP，第一个儿子选择点u之后，第二个儿子最优的选择肯定是一个与u有路相连的点v，接下来就是讨论一下v是u的父结点或者是子节点，取最优的作为第二个儿子的选择，然后计算一下第一个儿子可以得到多少城市，最大值就是答案。
- ACdream1020 约瑟夫环问题，
f[i]=(f[i-1]+2)%i,f[1]=1。根据递推公式可以发现i为2的幂时，f[i]=1,之后为1、3、5……所以只要找出2^x>i，x的最小值，答案为2*(n-2^(x-1))。 - ACdream1063 字典树，同前一天写的cf#357d。
- ACdream1064 数位DP
- ACdream1069 移位加密的移位值和费伯纳西数列有关
- fzu1627 刚好走k部的方案数，矩阵快速幂
- ACdream1083 DP，先将输入的边反向，进行拓扑排序，得到一个拓扑序列。然后按照拓扑序列考虑点u，u可以走到v，费用为w。定义dp[u]为删边后从u到终点的最短路，dis[u]为不删边从u到终点的最短路。根据拓扑序列的性质，计算点u时，肯定所有的子节点都计算过了。所以dis[u]=min(dis[u]+w)。然后考虑删除一条边，分成两类讨论。第一种是删除与u相连的一条边，那么GG可以选择走(dis[v]+w)中次小的一条(min(dis[v]+w)被删除了)。第二种删除v到终点中的一条，那么选择走min(dp[v]+w)中最小的一条。最后，由于军队有主动权，dp[u]为两种方案中较大的一个值。
- cf#365a
- cf#365b 找规律，容斥原理
- cf#357a
- cf#357b 前缀和
- cf#357c dp，看清楚题目
- cf#357d 字典树，要注意到最多只有30层，所以对于每一输入的数字转化成30位的二进制，然后如果不是有new的，要注意数组开大一点，防止re。
- hdu5855 最大权闭合子图，二分时间t，之后商店的利润和s连边，工厂花费和t连边，商店和对应的工厂连边流量为无穷。累加所有有用的商店的利润并且减除最大流即为答案。
- hdu5834 树形dp，两次dfs。第一次dfs计算出dp[0][u]从u出发遍历子树最后回到u的值，dp[1][u]从u出发遍历子树最后不回到u点即在某一子树结束寻找的最大值，dp[2][u]与dp[1][U]类似，从u出发遍历子树最后不回到u点即在某一子树结束寻找的次大值。第二次dfs统计答案，每次dfs维护两个值sum1，sum2，sum1是从u结点出发，走父结点的方向并回到u点的最大值，sum2是从u结点出发，走父结点的方向不回到u点的最大值。
ans[u]=max(sum1+dp[2][u],sum2+dp[1][u])。然后重新计算向子结点传递的sum1，sum2。 - hdu5839 计算几何，求一个特殊的四面体（所有棱长度相同或者4条棱长度相同，剩下的两条不相同的棱不相邻）。首先暴力枚举剩下两条棱中的一条，然后遍历所有其他点，保存到这条棱两端点相同的点，再在上一步中的点中枚举符合条件的点（去掉4点共面情况）。最后统计答案的时候去除重复。
- hdu5832 注意N范围
- hdu5833 输入的每一个ai进行质数分解，之后得到一个01矩阵，最后利用高斯消元得出自由变量。
- hdu5835 贪心
- hdu5842 跟lis无关，只要找出有多少种字母就可以了。
- hdu4381 背包变形，比赛的最后写的有几分背包的样子，但是没有往这方面想过去，所以没有写出来。首先将两种操作分开来看，发现本质是一样的。以第一种为例，可以构建出
dp[i]=min(dp[i],dp[i-xi]+1),0<=i<=ai。第二种也转化为覆盖0-ai的情况就和第一种一样了。最后枚举答案，如果为k，那么假设覆盖了第一种中的1到i，那么第二种就覆盖了剩下从n开始的k-i个。第二问答案就是两个dp值相加取最小的。 - hdu5543 背包,dp[3][2*L],dp[0]代表没有挂在外面的，dp[1]代表一个挂在外面，dp[2]代表两端都有一个挂在外面。将输入的长度都放大两倍即可，之后就是背包了，注意一下不同dp[i]之间的转移就可以了。不知道为什么数组越界在g++下会报出超时。
- cf#edu15c two points
- cf#edu15d 数学问题，然后跟时间相关函数的函数肯定是单调的，可以去找规律，也可以用二分去逼近。
- cf#edu15b 暴力枚举
- cf#edu15a dp
- fzu1759 欧拉函数降幂+快速幂，A^x = A^(x % Phi(C) + Phi(C)) (mod C)。
- hdu5816 状态压缩做法，n+m<=20，所以可以状态压缩，但是写的时候要仔细一点，很容易超时。牌堆总共的方案数是(n+m)!，然后通过状态压缩枚举出前几张为什么组合时可以打死对手，之后再乘以剩余卡牌的全排列就可以了。用s表示牌的状态，即第i位为1表示集合中有第i张牌，为0反之。用dp[s]代表当前的方案数，统计s中A和B的个数，s可以转移要满足
2*A-(A+B)-1>0。最后再统计一下就可以了。 - fzu2195 累加全部权值，然后减去从根到叶权值最大的一条链的权值即可。
- cf#691d 并查集
- hdu4786 求出最小成树和最大生成树的值，然后看看两个值之间有没有一个费伯纳西数
- hdu5695 贪心+拓扑排序
- poj3255 次短路，考虑清楚转移即可。
- hdu5804 根据题目超过所有商品价值总和的账单是不对的
- hdu5805 数学期望，考虑删除第i个数，取前i-1个数差的最大值、后i+1到n数差的最大值和i-1和i+1的差中间最大的，即得到删除i的贡献。对于前面两个数可以维护两个数列。
- hdu5806 自己用的是二分，首先预处理到第i个数为止前面有多少个大于m的数字，然后枚举左端点，二分查找
到左端点为止大于m的个数+k的值，再统计一下就可以了。官方题解是two points，也就是说第二步二分查找是没有必要的，右端点一定是一直增大的。 - hdu5807 最朴素的想法是设f[i][j][k]分别带表i、j、k三个人所在的位置，然后由于是有向无环图且u<v，可以搜索或者dp得到转移方程。但是这样写的复杂度为
O(N^6)。考虑优化，设f[i][j][k][now]，新增加一维代表当前考虑第几个人走，转移方向为k->j->i。将复杂度降到`O(n^4)。 - hdu5738 把题目里的公式化解一下会发现就是要求共线的点，首先对输入的点进行(x,y)的双关键字排序，然后枚举每一个点，计算出与他后面的点的极角值，再进行一次极角排序，统计出重点为num1，对于每一条线段上的点为ai(包括重点，不包括开始枚举的点)，一共有d条线段。然后考虑计算公式，如果没有重点的话一共有2^ai-1种可能（即在ai个点里面取1、2、......ai个点的组合数）。然后考虑有重点的重复统计情况，一共多统计了d-1条线段的情况，每一条线段多统计的为2^num1-1种，即答案要减去
(d-1)*(2^num1-1)。
- poj3417 lca+dfs,注意用vector会超时。题目中首先给出是一棵树，然后考虑一下，如果加入新边后，某一条原来就存在的边是桥的话，对结果贡献是m。如果旧的边只在一个环中那么对于答案的贡献是1。对于每一条新的边，相当于将这两个点到最近 公共祖先部分中的边覆盖一次。所以只要统计每一条旧边被覆盖几次就可以了。
- hdu5745 bitset+dp。bitset直接进行位运算时可以将复杂度降低到O(N/8)。用dp[i][j][k]代表s串第i个字符，p串第j个字符，k=0，1，2分别代表与前一个字符进行交换，不交换，与后一个字符进行交换。
dp[i][j][1]=(s[i]=p[j])&(dp[i-1][j-1][0]|dp[i-1][j-1][1])考虑优化， 用bitset表示第一维，用滚动数组表示第二维。再用另外一个bitset预处理26个字符的情况，可以化解得到dp[cur][1]=w[p[j]-'a']&((dp[cur^1][0]|dp[cur^1][1])<<1)，另外两种情况可以同理处理。
- poj3420 找出递推规律，假设f(n)最后n-i行连在一起，当i=1时，结果为1f(n-1),当i=2时，4f(n-2)，之后i为奇数时，2f(n-i),i为偶数时，3f(n-i)。最后可以找到递推公式为f(n)=f(n-1)+5*f(n-2)+f(n-3)-f(n-4)。之后，再用矩阵快速幂计算，由于有负数，取模过程中先加一个模。
- poj3419 求[l,r]区间内没有重复数字的子串的最长长度。先预处理，每一个位置开始最远可以到达的位置为bi，然后可以得出以i开始的长度为a[i]=b[i]-i+1。然后用lower_bound找出区间内最小的j满足b[j]>r，[j,r]的答案是r-j+1，[l,r-1]的答案为a[i]的最大值，可以用rmq处理出来。
- hdu4355 三分搜索
- fzu1502 最长公共子序列
- hdu3410 暴力
- hdu1562
- hdu5783
- hdu5777 贪心
- hdu5778 暴力枚举，y的所有因子出现两次可以转换为y=z*z,只需要枚举z，z只需要找到一个使y大于x和一个使y小于x，另外z的因子在logn以内。
- hdu5776
- hdu5748
- hdu5747
- hdu5720
- hdu3392 dp,想的仔细一点
- hdu5722 矩形面积并，先对元素进行大小位置排序，然后得到取值范围。
- hdu5753 考虑每一位对结果的贡献
- hdu5754 王需要打表，车为巴什博弈，后为威佐夫博弈，马先预处理最大的情况。
- hdu5762 Manhattan距离，注意的是根据鸽巢原理会在O(M）的时间内退出循环。
- hdu2177 威佐夫博弈
- hdu1542 矩形面积求并，离散化之后用扫描线+线段树做，注意一下每次更新端点的值
- hdu4539 状压dp，poj1185的变形，考虑曼哈顿距离即可
- hdu2188 博弈
- hdu1527 威佐夫博弈
- hdu5719
- poj1185 状压DP，从二维到三维的建立模型，以及通过分析降低复杂度。
- hdu5729 dp，转换成二分匹配问题
- hdu5718
- hdu5726 一个整数n的约数个数在logn以内，所以先对输入的数列建立rmq，又有所有的gcd值是递减的，然后预处理所有(l,r)值，存放在map中，具体是固定l，二分下界，统计个数。对与所有的输入直接查询就可以了。
- hdu5727 全排列+二分图匹配，枚举阴宝石的位置，一个有(n-1)!种可能，对于每一种可能如果不会影响阳宝石，建边，然后去跑二分图。
- L2-016. 愿天下有情人都是失散多年的兄妹 对长辈进行性别标注
- L2-013. 红色警报 字母写错了……
- L2-014. 列车调度 导弹拦截问题中的本质是求一个序列的最长上升子序列（nlogn），只有这样才会新开导弹组。也就是本问题中的铁轨。
- hdu5724 sg函数，注意计算方法
- hdu5723 最小生成树，边的权值不同保证最小生成树唯一。求数学期望时，用dfs找出规律，但是10w个点中，5w乘以5w也会爆int
- poj2296 2sat
- hdu1816 poj2723升级版，poj的题目可以把一组钥匙看做2-sat值，这道题目可以考虑值为选用某把钥匙，和不选用某把钥匙，从而来限制关系
- hdu4115 2sat，建边的关键不是通过已知的信息连接，而是连限制的边。第一次建边时，将相同情况连了边，而没有考虑相同情况时导致的限制条件
- poj2723 2sat，二分门的数量，然后判断
- poj3905
- cf#362A
- uvalive3713 2sat
- poj3648 2sat,强连通+拓扑排序
- poj3678 2sat,强连通，注意建边关系即可：
- A,B不能同时取 < A,B' >< B,A' >
- A,B不能都不取 < A',B >< B',A >
- A,B必须都取或者都不取 < A,B > < B,A >< A',B' >< B',A' >
- 必须取A <A',A>
- poj2749 2sat+二分，两个点之间的距离超过二分值，连接不同的点
- patA1058
- poj3683 2-sat
- cf#357C 用优先队列模拟堆，cout效率很低，会超时
- poj3207 2-sat，注意建边，这里和之前题目不同的之处在于，不选择的点也不能冲突。
- hdu3622 2sat，注意建边
- cf#edu13D 矩阵优化
- cf#edu13E 状压DP，反过来想这个问题，假设dp[i][j]代表存活的人的状态为i，擂台上的人是j时，主人公获胜的概率。dp[i][j]=max(dp[i][j],p[j][k]*dp[i^(1<<k)][j]+p[k][j]*dp[i^(1<<j)][k]);
- cf#edu13C 容斥原理
- cf#361D rmq+二分搜索
- cf#57A 异或运算
- cf#57B 字符串处理
- cf#57D 贪心
- hdu1861
- poj1102
- poj1573
- poj2251
- poj3140 树形dp
- hdu1426 搜索
- hdu1814 2-sat输出字典序最小的方案，注意建边的顺序
- cf#361B 搜索
- cf#361C 二分+验证
- UVALive3211 2-sat问题入门
- hdu5636 最短路floyd
- cf#361A
- hdu1732 搜索
- cf#358C dfs，树形dp
- hdu2821 搜索
- cf#358D dp
- patA1006
- cf#360D 数论
- patA1027
- hdu1254 搜索
- cf#360A
- cf#360B
- cf#360C 黑白染色问题
- hdu2822 优先队列
- hdu1372 搜索
- poj3107 树的重心
- cf#359D 子树的重心
- cf#359B 冒泡排序变形题
- cf#359C 题目较难理解，搜索
- poj1655 树的重心