Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"lypl","updateTime":1554003297000,"title":"整理一哈","dislikeCnt":0,"content":"***所以是简述题目让做什么求什么,然后从不同角度挖掘所给模型的性质;某些角度刁钻需要积累……***\n\n样例:1 2 4 8 16 32 64\n[problem:CodeForces - 614A] while里break跳出写在前后有区别,因为当前可能是合法的,写在前面会漏解 ;大数乘可能越界,所以用除法判,不用乘法\n\n**图论**\n最短路 \n[problem:CodeForces - 20C] 大数据,不可使用Dijkstra邻接矩阵和邻接表,都卡空间和时间,直接上堆优化的最短路模板\n[problem:HDU - 2544 ][problem:POJ - 3613 ] floyd算法 多源最短路 (+倍增)\n[problem:HDU - 2066 ] [problem:CodeForces - 601A ] dijkstra算法 单源最短路 数据小 不能处理负权边和负权环\n[problem:POJ - 3255 ]次短路 spfa cnt\u003en-1时即为圈\n[problem:POJ-3463]最短路计数\n[submission:17219060]最短路计数+节点有权值求最大+dijkstra \n[problem:CodeForces - 500B] 矩阵可以往图 上考虑,Floyd可以算出每个位置能放的数有哪些,因为交换是一种**传递闭包**(ps:如果交换是不关乎位置且可为任意次的,可由floyd做 [submission:18156862] )\n[problem:CodeForces - 8B ] 给一个LRUD字符串,判断当前点是否是前一步走的最短的路到达的,用g[x][y]和它上下左右的点的走过的个数和是否\u003e1\n[problem:CodeForces - 689B ]用bfs更新邻接点,因为数据大不能用floyd,图也不好存,且每个点的邻接点只有3个\n[problem:CodeForces - 986A ]对物品进行bfs,不是对点,如果对点,每次要判断当前点可以满足其他哪些点,复杂度太高,不能对每个节点都bfs一次;因为k很小,所以可以对每个物品暴力,对物品i bfs,更新每个小镇j获得每个物品i的最短距离,最后取到这个节点花费小的s个物品。(再整理一次思路)\n[problem:CodeForces - 954D ] 因为最短路可能不止一条,如果最短路之间连边可能改变最短路长度,因此不能用n*(n-1)/2 -m -( 最短路上的点数*(最短路上的点数-1)/2-最短路长度)计算,而是枚举每条边看能否作为答案,判断是否可行即判断加入这条边后最短路是否发生变化,*(加了一条边,就新增了两条路,两条路都要判)*用**起点、终点两次bfs [submission:18249937]或者dijkstra来判断**(针对点边数少的情况(1e3)两次bfs可以求出每个点分别距起点、终点的最短距离,dijkstra和spfa相同作用)\n[submission:18251806 ] 最短路记录路径lst数组\n\n**用bfs求最短路和dijkstra求最短路的区别及条件(dijkstra是bfs的升级版):**bfs可以求最短路的路径具体是由哪些构成的,\n\n最小生成树\n[problem:HDU - 1875 ] [problem: HDU 1102 ]prim算法 与dijkstra思想一样 往集合里加点\n[problem:51Nod - 1212 ]kruscal算法 并查集\n[problem:CodeForces - 939D] 用最少的字母对,使得两个字符串相等。字母对之间的字母可以相互转换。 给每对字母建边求最小生成树 ,因为转换是可以通过链式的,所以所有字母对是没有环的(或并查集做法)\n[problem:CodeForces - 916C ]构造一个图,要求最小生成树是素数,则用一个大一点的素数如 9999991 构造根为1的最小生成树(见代码),剩下的边用1e9保证不在最小生成树里 \n\n\n二分图匹配\n[problem:HDU - 2444 ][problem:51Nod - 2006 ] 二分图染色+匈牙利算法 完全匹配\n[problem:HDU - 2255 ]KM算法 最优(大)匹配\n[problem:HDU - 3488 ] KM算法 拆点 最小匹配\n[problem:HDU - 1068 ]二分图最大独立集\n[problem:HDU - 1150 ]二分图的最小顶点覆盖数\u003d最大匹配数\n[problem:HDU - 1054 ]无向图的最大二分匹配数/2\u003d\u003d最小顶点覆盖\n[problem:HDU - 1151 ]最小路径覆盖(最小边覆盖)\n[problem:HDU - 1507 ]奇偶匹配\n[problem:HDU - 3360 ]行列匹配\n[problem:POJ - 1321 ][problem:HDU - 1281 ]象棋放车\n\n稳定婚姻\n[problem: HDU - 1435 ]\n\n拓扑排序\n[problem:HDU - 2094 ] [problem:POJ - 2367 ] 板子\n[problem:CodeForces - 510C ]判环\n[problem:HDU - 4857 ]\n[problem:HDU - 5813 ](贪心也可解)\n[problem:HDU - 1811 ]拓扑排序+并查集\n\n欧拉通路\n[problem:HihoCoder - 1181 ][problem:HihoCoder - 1182 ]\n\n强连通分量\n[problem:CodeForces - 427C ][problem:HDU - 1269 ]tarjan 板子\n\n01分数规划\n[problem:POJ - 2728 ]最优比率生成树\n[problem:HDU - 3621 ]最优比率生成环\n\n环\n[problem:CodeForces - 761B ] 环上偏移量,**找到不变量**因为各障碍物之间的距离是不变的,所以求出的两个间隔队列比较一下,注意这里的比较不要忘记位移比较,因为是个圈。所以如果在某个位移位置存在重合,那么就是相等的,否则就是不相等。\n[problem:CodeForces - 24A ]顺时针逆时针计算环的代价(待整理)\n[problem:CodeForces - 574B ]3个点的环可以直接枚举三个点,优化可直接枚举边,并注意不要枚举到自己\n**并查集找环、bfs找环、dfs找环的区别:(待更新)**并查集只能判断有没有环,有几个环([problem:CodeForces - 977E ] )(单圈环,根据点的度来判断),不能判断环上有什么点;bfs能找唯一环,根据每个点的度数类似拓扑排序([problem:CodeForces - 131D\t ]);dfs更适于求点到点的距离,只有环没有其他点的时候,可以用dfs遍历;小环直接枚举点(边优化 574B)\n\n**胡搞**\n[problem:CodeForces - 437C ] n个点由m条线连(可重边),删去一个的花费是它连着点的权重和(相当于每条边都删去),问删完所有点的最少花费。 每次将剩余点中点权最大的点揪出,这样可以保证每条边都是会选择相对小的点权被消耗掉。所以直接选择边连接的较小权值的点\n[problem:CodeForces - 548B ] 如何处理每行的连续的1的个数的最大值\n[problem:CodeForces - 962C ] 问最少去掉几个数字使剩下的数字是个完全平方数 ,可以用2进制枚举,最多10位,从1\u003c\u003c(len)-1开始,len是整数的位数,一直到0就可以遍历出每一种情况(这个数的删除位数的所有情况),二进制的1表示改为保留,0表示去掉,然后每个判断一下没有前导零,是平方数就行\n[problem:CodeForces - \t893B ] 什么情况可以打表,每次所用的值或所给的结论都是固定的,就把这些值打出来\n[problem:CodeForces - \t546B ] 给一些数字,要让每个数字都不一样最少需要增加几\n[problem:CodeForces - \t908B ] [submission: 18451749] next_permutation()的用法,且固定以某个下标0,1,2,3表示上下左右,通过改变排列来确定题目给的0,1,2,3代表哪个方向;不用dfs搜(再整理)\n\n[problem:CodeForces - \t740A ] 可以再买\u003e4本使满足题意\n[problem:CodeForces - \t842A ] 不能只考虑k*x~k*y长度小于a~b的情况,还有大于的情况,且因为点是离散的,还是要从x到y一个一个比\n[problem:CodeForces - \t919C ] 特别考虑k\u003d1 \n[problem:CodeForces - \t611B ] 打表法,二进制表示只有一个0的数字,如何打表\n[problem:CodeForces - \t940A ] 问最少删除几个数字,使得剩余数字的 最大值 - 最小值 \u003c \u003d m。逆向,求符合题意的最多数字 ,注意i,j的表示,j从i开始,不是从i+1开始\n[problem:CodeForces - \t334B ]给出3个原子的化学价,求出1-2 2-3 1-3 号原子之间有几条键,分别用ta tb tc 表示(ta是a(1号)的对边,tb,tc同理), 用数学的方法表示出来的话就是a \u003d tc + tb; b \u003d ta+tc; c \u003d ta + tb,枚举\n[problem:CodeForces - \t298B ] 定义四种操作,给一个字符串代表操作的顺序,可以选择不去执行其中的某些操作。问你最终可否到达destination。\n只有当顺着风的方向可以使当前位置到目的地距离减小时才顺风走,否则就不动,\n如果在中间某一时刻到目的地了就输出当时的秒数,如果到最后都没到就是到不了了\n[problem:CodeForces - \t304A ] 注意不要重复取数\n[problem:CodeForces - \t416B ] (再整理,什么思想,如何维护的pre和t)有n个画家,有m幅画需要完成,画家们采用流水线的方式作业,给出每幅画经过每个画家的所需要的时间,问说每幅画被完成的时间\n记录每个画家完成上一个画得时间。然后当每幅画到达一个画家手里时,选取t值和到达时间中最长的作为起始时间,完成则加上该画家完成该画得工作时间\n[problem:CodeForces - \t48B ] 在一个长方形里遍历一个小长方形的方法 \n[problem:CodeForces - \t514B ] 枚举斜率k \n[problem:CodeForces - \t1117A ] 求一个序列的最大均值的最大子段长度,其实是求最大值的最长连续个数,要注意加上哨兵,哨兵应该是没有定义的,设为-1;此外统计的时候也要注意内层循环\n[problem:CodeForces - \t1007A ] vector erase()用法,用iterator \n**!!!**[problem:CodeForces - \t999D ] **动态思想,挨个考察每一个数**将n个数分为m组,每组n/m个数,每组的数%m相等,每个数都可以+无限多个1,要求每组个数相同,问最少加多少个1. 对0~m-1每一个组,用set维护该组里当前的个数,从0~n扫一遍每个数对应的组,如果该组没填满,则填到该组;若填满了,则找到最小的能加数的组加进去(用set的lowerbound()若找不到就是用set的第一个组即可);如果某个组已经达到n/m个数了,就从set里删除这个组\n[problem:Gym - 101853K ] string读一行:getline(cin,s); istringstream 的用法,ios::sync_with_stdio(false); 关同步\n[problem:CodeForces - \t997A ] 有一个长度为n的只包含0 1 的字符串,现在有两种操作,一种是把这个字符串的某一个连续的子串倒置,花费是x,第二种是,把某一个连续的子串逐位取反(即0变成1 1变成0),花费是y。问你把这个字符串变成全 1 串的最小花费。 因为花费与长度无关,所以可以缩成一个1/0,例如:000 1000 10000 100 100这个串,因为上面操作的花费与段的长度无关,所以我们可以把相邻的1合成一个1,相邻的0合成一个0。所以原串就可以转化成 0 10 10 10 10。因为我们是要把目标串变成全1串,所以开头的1(和结尾的1)我们可以不去管它。\n\n第一种方法,我们可以选择第二段 10 ,对其进行倒置操作,所以整个串就变成了 0 01 10 10 10。然后再次合并相邻的1 和相邻的 0 ,原串变成了 0 10 10 10。然后在进行一次相同的操作,就变成了 0 10 10.以此类推,最后将变成 0 10,再倒置一次,变成 00 1,然后再对00 进行一次操作二即可。这种方法的花费为 (num-1)*x+y。\n\n第二种方法,我们直接对每一段0实施操作二,使得其变为全1串,这样的花费是num*y。\n\n所以显然,当x\u003c\u003dy时,我们选择第一种方案,当x\u003ey时,我们选择第二中方案,统计0的段数,直接输出结果即可。\n\n\n\n**搜索**\n[problem:CodeForces - \t1105D] 多源bfs\n[problem:CodeForces - \t977D] 用cnt数组代替vis,因为每个数特别大 \n[problem:CodeForces - \t441C] 构造法很巧妙\n[problem:CodeForces - \t445A] bool dfs与void dfs区别\n[problem:CodeForces - \t771A] 判断每个连通块里的各个点是否都有边,即判断所有连通块的点的导出子图是不是完全图,也就是每个联通块的点数n和边数m要满足关系m\u003dn*(n-1)/2,求连通块用并查集或dfs,**递归找比while快**\n[problem:CodeForces - 687A ] [problem:CodeForces - \t862B]二分图染色板子\n[problem:CodeForces - 60B ] 简单三维dfs\n[problem:CodeForces - 475B ] 不需要建图,因为(0,1)-\u003e(0,2)不易用图表示\n[problem:CodeForces - 839C ] dfs维护长度及概率\n[problem:CodeForces - 782C ] dfs染色 某节点的颜色和他的相邻节点颜色不能相同,且对于每个父亲,它所有儿子的颜色都不能相同,问你最少需要多少颜色,用color记录当前染色的个数\n[problem:CodeForces - 1006E ] dfs序 \n[problem:CodeForces - 320B ] 不建图也可以搜索,区间这种抽象的点可以直接搜\n[problem:CodeForces - 1093D\t ] 二分图染色+计数 ,注意只考虑**奇偶性**,1和3是等价的。如果将每条边连接的两个点染成黑点和白点,个数分别为wi和vi,如果黑点是2,那么个数就是2^vi。如果白点是2,那么个数是2^wi。 不能用mm(col),会TLE\n[problem:CodeForces - 131D\t ]n个点n条边,保证图连通,并且有且只有有一个环,求出每个点距离环的距离。**这种n个点 n条边/n-1条边的题都是套路了,要仔细考虑图特性:点的度(出度,入度),怎么搜(顺着搜,倒着搜,BFS好写还是DFS好写)但是一旦确定思路,要多举反例,谨防入坑!!**找唯一环的话,用类似拓扑排序的方法,由于环上点的度\u003e\u003d2,所以bfs后未能遍历的点必在环上,然后就用dfs跟新距离就行了。\n[problem:CodeForces - 793B\t ] 转弯题,三维vis数组,多一维记录到达每个点的转弯次数 bfs[submission:18251276] [submission:18251336 ] dfs[submission:18251387] \n[problem:CodeForces - 653B\t ] 字符串搜索\n[problem:CodeForces - 999E\t ] (待整理)给你一张有向图,需要使得给定的点可以到达图中任意的一个节点位置,问至少有在图中修多少条路。,遍历1到n个点,把到达过的位置做一个标记,并将每个点可以到达的位置保存到堆栈中。然后标记清零,bfs定点s可以到达的节点,做标记。堆栈中未被标记的位置便是需要建立通路的位置。\n[problem:Gym - 101889E ] vis【】【】记忆化一下\n[problem:HDU - 1401 ] 双向宽搜\n[problem:HDU - 2234 ]迭代加深搜索\n[problem:HDU - 1043 ] A*启发式搜索,康拓展开\n[problem:HDU - 1667 ] IDA*\n[problem:POJ - 2420 ] 模拟退火\n[problem:HDU - 2614 ] dfs()多一维参数记录一条链的长度\n[problem:HDU - 1312 ] 求一个联通块的大小 \n[problem:POJ - 3035 ] dfs,序列可以用一个int型的数表示\n[problem:CodeForces - 9C ] 统计1~n之间有多少数字只由0,1构成 。dfs求解 \n\n**乘法逆元**\n[problem:Gym - 101864E ]费马小定理求逆元\n[problem:51Nod - 1256 ]拓展欧几里得求逆元\n\n**莫队算法(处理区间询问,能o1的得到l-1,r+1,l+1,r-1的结果)**\n[problem:CodeForces - 617E ] 连续子段满足异或和等于 k \u003c\u003d\u003e pre[i]^pre[j]\u003d\u003dk(pre[i]\u003da1^……^ai),(因为a^a\u003d\u003d0)即询问区间内有多少对i,j满足pre[i]^pre[j]\u003d\u003dk\n\n**模拟**\n[problem:Gym - 101864F ] STL set 自动排序\n[problem:HDU - 2689]归并排序\n[problem:CodeForces - 670E ] 数组模拟双向链表 \n\n**二分**\n[problem:CodeForces - 676C ] 给你一个字符串,字符串中不是\u0027a\u0027就是\u0027b\u0027,我们可以修改最多k个位置。问能够得到的最长相同字符的序列。 暴力枚举长度和起点超时,因为前缀和是递增的,所以可以考虑**对每个起点二分终点**,对每个起点来讲,前半段可行,后半段不可行,找到最大的可行的终点,注意mid\u003d(l+r+1)\u003e\u003e1;特判一下n\u003d1的情况\n[problem:Gym - 101257D ] 二分,前一半都不可行,后一半都可行,O(1)judge答案,用二分搜索找最大值最小/最小值最大\n[problem:CodeForces - 702B ] 位运算判断是不是2^n 的方法:x-x\u0026(-x)\u003d\u003d0 x为2的次幂 (会超时) 二分找 二分可以将 n^2降为nlogn 二分找对应的值 \n\n**数学**\n[problem:Gym 101864A ]约瑟夫环\n[problem:CodeForces - \t1064B] 异或性质 集合表示异或\n[submission:16587473 ] 素数线性筛\n[problem:51Nod - 1130 ][problem:HDU - 1060 ]求阶乘 斯特林公式\n[problem:HDU - 5701 ]中位数 处理方法,比他大的置1,小的置-1,等于的置0,统计区间和为0的区间个数\n[problem:POJ - 3784 ]动态维护中位数 对顶堆算法\n[problem:POJ - 3641 ]米勒罗宾大素数判定+快速幂\n[problem:POJ - 3070 ]矩阵快速幂求斐波那契数列\n[problem:HihoCoder - 1505 ]容斥原理\n[submission:17421515 ][problem:LightOJ - 1341 ]唯一分解定理+因子个数+因子和\n[problem:LightOJ - 1370 ]欧拉函数打表\n[problem:LightOJ - 1213 ]循环次数+推导公式\n[problem:HYSBZ - 1477 ]拓展欧几里得 https://blog.csdn.net/sky_zdk/article/details/71023325\n[problem:CodeForces - \t787A]给定两个等差数列,求两个数列最小公共项 拓展欧几里得\n[problem:CodeForces - \t1104D] 余数性质 交互题\n[problem:CodeForces - \t893E] 组合数c的写法(乘法逆元),质因数分解(先用线性筛求出素数,再枚举素数分解质因数),组合数学结论:∑ C(n,偶数) \u003d ∑ C(n,奇数) \u003d 2^(n-1)。一个长度为y,乘积为x的数列可以看做,将x的所有∑ p[i]个质因子,分配到了y个位置上。因此用隔板法(在n个元素间插入(b-1)个板,即把n个元素分成b组的方法),C(y-1+t,y-1) \n1. *ps:隔板法:分两种,允许有些组为空 和 每组至少一个 2种\n1. 1:将20个大小形状完全相同的小球放入3个不同的盒子,允许有盒子为空,但球必须放完,有多少种不同的方法 分析:问题等价于将小球分成三组,允许有若干组无元素,用隔板法。将20个小球分成三组需要两块隔板,因为允许有盒子为空,不符合隔板法的原理,那就人为的再加上3个小球,保证每个盒子都至少分到一个小球,那就符合隔板法的要求了(分完后,再在每组中各去掉一个小球,即满足了题设的要求)。然后就变成待分小球总数为23个,球中间有22个空档,需要在这22个空档里加入2个隔板来分隔为3份,共有C(22,2)\u003d231种不同的方法.\n1. 对n件相同物品(或名额)分给m个人(或位置),允许若干个人(或位置)为空的问题,可以看成将这n件物品分成m组,Cn+m-1 m-1种排法\n1. 2:例如:将20个优秀学生名额分给18个班,每班至少1个名额,有多少种不同的分配方法 分析:将20个相同的小球分成18组,需要17块隔板,先将20个小球排成一排,因小球相同,故小球之间无顺序,是组合,只有1种排法,再在20个小球之间的19个空档中,选取17个位置放隔板,因隔板无差别,故隔板之间无序,是组合问题,故隔板有C(19, 17)种不同的放法,根据分步计数原理,共有C(19 ,17)种不同的方法,因17块隔板将20个小球分成18组,从左到右可以看成每班所得的名额数,每一种隔板与小球的排法对应于一种分法,故有C(n-1, m-1)种分法.*\n\n[problem:CodeForces - \t1114E ] (交互题)二分求出最大值,然后随机数(rand最大值32767,更大的随机数用 mt19937)去查询第x个,求出gcd即可能为公差d,多问几次就是答案 **公因数,公差一类可以考虑gcd**\n[problem:CodeForces - \t476B ] 概率 计算C(n,m)的另一种方法和2^x\u003d1\u003c\u003cx\n[problem:CodeForces - \t633B ]找阶乘因子中5的个数\n[problem:Gym - 101853G ] 离散对数 bsgs算法\n[problem:Gym - 101889J ] 枚举gcd,详见代码注释\n[problem:Gym - 101257G ]求期望\n\n**dp**\n**阶段(子问题的规模,从小问题到大问题的,如区间dp的区间长度)、状态(现在子问题都是什么,如区间dp左、右端点)、决策(往哪里转移,如选该物品还是不选)、附加维度(描述状态的)**\n[problem:HDU - 1466]画递归树\n[problem:HDU - 1003 ]最长子段和\n[problem:HDU - 1058 ]wa vector去重 \n[problem:HDU - 1069 ]最长有序子序列\n[problem:HDU - 1074 ][problem:POJ - 2411 ]状压dp\n[problem:HDU - 1087 ]最长上升子序列 [problem:HDU - 1025 ]nlogn算法\n[problem:HDU - 1159 ]最长公共子序列\n[problem:HDU - 1081 ]最大子矩阵和\n[problem:POJ - 1958 ]4柱汉诺塔\n**背包即明确:容量、体积、价值**\n[problem:HDU - 1114 ]完全背包\n[problem:HDU - 2602 ]01背包\n[problem:CodeForces - 189A] 要求把丝带切成给定长度a、b、c中的0种、一种或多种,问最多能切成几条(等价于 分硬币)一个需要刚好装满的完全背包问题,只有三种商品a, b, c,能取无限件物品,每件物品价值是1,求最大价值(dp/bf 暴力枚举长度为a、b的木棒数量)\n[problem:CodeForces - 474D]统计数字的分解种类\n[problem:POJ - 2411 ]骨牌覆盖\n[problem:CodeForces - 1105C]和为3的n个数方案 考虑余数\n[problem:CodeForces - 1102F]状压dp\n[problem:CodeForces - 615B] 给出一个n个点m条边的无向无环图(不一定全联通),求一条递增链长度与尾节点个数乘积(长度*最后一个点的边数)的最大值。!!!注意该转移方程,与图论结合\n[problem:CodeForces - 557B ] 鸽巢原理,求被m整除则转化为余数处理 \n[problem:Gym - 101982D ] 数位dp\n\n**博弈**\n\n**差分系统** \nhttps://blog.csdn.net/qq_39670434/article/details/78454033\n\n**技巧**\n[problem:CodeForces - 670C ]离散化\n[problem:HihoCoder - 1384 ]倍增\n[problem:CodeForces - 722C ]一般删除都可以逆向考虑,变成添加\n[problem:CodeForces - 1005C ]2的30次方~\u003d1e9,但可以不打表,用i\u003c\u003c30表示\n写二分要找两个相邻的数模拟一下,看mid取(l+r)\u003e\u003e1 (求\u003e\u003dx中最小的) 还是(l+r+1)\u003e\u003e1(求\u003c\u003dx中最大的 )\n[problem:CodeForces - 181B ] 结构体的构造函数,重载运算符\n[problem:CodeForces - 279B ] (待整理,曲尺有什么特点)曲尺法,假设从i位置开始读可以读到j位置,所花分钟数为s(\u003c\u003dm),那么从i+1位置开始一定也可以读到j而且j位置且目前化为为s-a[i],这样递推下去取每个位置的max就可以了\n[problem:CodeForces - 289B ] vector去重\n[problem:CodeForces - 701C ]首先,取得满足条件的最小序列,然后依次将i向右移动,若i向左移动的过程中序列仍然满足条件,则j不移动,否则将j也向右移动。在移动的过程中记录j-i的最小值。\n[problem:Gym - 101606A ] 环形的,一天24小时这种用余数即可\n[problem:Gym - 101606G ] **随机函数**的应用,两人同时进行模拟,6个方向,两人各选择一个,走即可。如果能找到比现在还有更优(更近)的解(应用**估价函数best**),那就朝那个方向移动。至此这就是最普通的题 。但是题目说如果找不到最优解,那么随便走。所以我们要模拟“随便走”,如果没有最优解,那么rank随机数出两个方向走即可。 \n[problem:CodeForces - 550B ] 从n个数中选出 m个 数 要求这m个数的和大于等于 l ,并且小于等于 r , 而且这m个数中 最大值 和最小值的差 不小于x,求有多少种选法。因为n\u003c\u003d15,所以用二进制状态压缩枚举选每一位的情况,具体选了哪几位则用\u0026该位是1的数\n\n**二分**(模型特点(待整理),排序后单调……)\n[problem:CodeForces - 181B ] 排序,枚举两端点,二分中点,可以用set,注意结构体中要重载运算符\u003d\u003d\n\n**并查集**(有向边一般不用并查集)\n[problem:POJ - 1182 ][problem:HDU - 3038 ]带权并查集\n[problem:HDU - 1829 ][problem:POJ - 2492 ]种类并查集(**种类并查集不能用普通并查集判环来代替,因为偶环的话满足不同种类的两点相互连接但是他们在一个环里,所以仍需另一个记录种类**)\n*种类并查集的向量偏移:路径压缩的时候,i 和其祖先节点的关系通过其直接父亲和祖先的关系与i与其直接父亲的关系来确定;Rank表示了相较其父亲的偏移量,Rank[faX] \u003d (Rank[y] - Rank[x] + 1) % 2; //这里可以用向量的方式思考,(-Rank[x]表示x的父亲和x的关系,和之前相反了, +1 是x 相较于 y的关系,Rank[y]是 y 相较 y的父亲的关系 fx-\u003ex-\u003ey-\u003efy\u003dfx-\u003efy\u003drank[fx],因为f[fx]\u003dfy)*\n\n[problem:HDU - 1272 ]并查集判环\n[problem:HDU - 1232 ]普通并查集\n[problem:CodeForces - 977E ] 并查集找单圈环,判断一个集合里的每个点的度是不是2\n[problem:CodeForces - 731C ]该写法可将每个集合的元素放进去\n[problem:CodeForces - 722C ]给定 n 个数,然后每次破坏一个位置的数,那么剩下的连通块的和最大是多少。 用并查集来做,从后往前推,一开始什么也没有,如果破坏一个,那么我们就加上一个,然后判断它左右两侧是不是存在,如果存在,那么就合并起来,然后不断最大值,因为这个最大值肯定是不递减,所以我们一直更新就好。\n[problem:CodeForces - 659E ]在合并过程中,u,v,求得的fu不是最终的集合代表,因此要最后找到集合代表标记一下\n[problem:CodeForces - 103B ]判断图是否只有一个环和所有点连通,边数\u003d\u003d顶点数 \u0026\u0026 连通图\n[problem:CodeForces - 691D ]并查集思路和floyd不太一样\n待整理:[problem:CodeForces - 843A ][problem:CodeForces - 490B ]\n[problem:CodeForces - 744A ]完全图:边\u003d点*(点-1)/2;并查集的标记\n[problem:CodeForces - 698B ] 有向图的并查集,f[ ]、 flag[ ]表示不同。 给出 n 个结点的父亲,问至少修改多少个结点的父亲,能使整张图变成一棵树(根的父亲为自己),要求输出任一方案。 \n[problem:CodeForces - 1131F ] 并查集维护一行,用 lf[i] 表示一个集合区间的左端点,rt[ i]表示一个集合区间的右端点,to维护两个并查集的连接情况;因为是一行要输出每个数,所以用to数组。合并时,每次都把左边的合并到右边来,然后更新当前整个集合的情况:lf、rt、to\n\n\n**贪心**\n[problem:Gym 101864L] [problem:POJ - 1328 ] 区间贪心\n[problem:CodeForces - 1064C ][problem:CodeForces - 1038C ]随便贪\n[problem:HYSBZ - 4198 ]哈夫曼最小生成树\n[problem:CodeForces - 1102E ]顺序考虑区间个数,维护区间右端点值,实时更新答案\n[problem:CodeForces - 101A ]结构体重载运算符只能重载\u003c号\n[problem:CodeForces - 1066B ] 维护一个从左边起被加热器加热的最右边的下标\n[problem:CodeForces - 990B ]排序对于有大小关系的非常有用,因为如果当前数的下一个都不满足条件,那后面的更不满足,不需考虑\n[problem:CodeForces - 893D ] 这道题意思其实是让求**两个极端**(两种极端同时贪心):-1、最小存钱次数,所以用两个值代表极端(法一);或者先考虑-1的情况:即最差情况,因为为负数的时候一定会在某次检查的当前去存钱,所以当检查时且为负数的情况就存,且因为存钱多少不一定,所以最坏情况是让他存到0,如果这样还超过d,则输出-1;如果要最小次数,则要充就充到d。*因为充的钱数是不一样的所以会造成最值,可以贪心*\n[problem:CodeForces - 161A ] 给你n\u003c\u003d1e5个a[i]和m\u003c\u003d1e5个b[i]和x、y,每个a[i]有个适配范围(a[i]-x,a[i]+y),每个b[i]如果在某个a[i]范围内即可适配而且只适配一次,问你最多能有几个b[i]适配。将a、b排个序,然后枚举a[i]和b[j]如果能适配就i++,j++,如果b[j]\u003ca[i]-x那么说明b[j]对后面的a[i]也都不能适配(因为我们已经将a按从小到大排了)就j++,否则i++\n\n**数据结构**\n[problem:51Nod - 1102 ][problem:HDU - 1506 ]单调栈[problem:51Nod - 1158 ]二维直方图最大矩形面积\n[problem:POJ - 2823 ]双端队列 滑动窗口\n[problem:CodeForces - 52C ][problem:HDU - 1166 ][problem:HDU - 1754 ][problem:HDU - 1698 ]线段树 更新节点 区间求和\n[problem:HDU - 1542 ]矩形面积并\n[problem:51Nod - 1019 ][problem:HDU - 1394 ][problem:Gym - 101853C ] (归并排序板子,求交点转化为逆序对) [problem:POJ - 2299 ]求逆序数 线段树 树状数组 归并排序 暴力\n[problem:Gym 101972G ] 可以用二维线段树求最值\n[problem:HDU - 2586 ]lca\n[problem:HDU - 1515 ]栈混洗\n[problem:CodeForces - 271D ]字典树(可以优化set标记重复的那层循环,见此题tle的解)\n[problem:CodeForces - 1104B ]括号匹配 栈\n[problem:CodeForces - 748B ]map可以用!mp[i]判空\n[problem:HDU - 1251 ]字典树板子\n\n**差分约束系统**\n[problem:POJ - 3169 ]spfa判负权环的板子\n\n**前缀和**\n[problem:HYSBZ - 1218 ]二维前缀和\n[problem:POJ - 3263 ]区间化为左右两个端点的操作\n[problem:POJ - 2018 ] 前缀和求长度有限制的连续子串\n[problem:CodeForces - 466C ] 把一个串分为前中后、前后几部分,用前缀和与后缀和一起处理\n[problem:CodeForces - 490C ] 把一个串分为前后两部分,用取模意义下的进制运算\n[problem:CodeForces - 1082C ] 二维前缀和的写法,注意sum\u003c0也为真,也进if语句\n[problem:CodeForces - 48B ][problem:CodeForces - 838A ] 二维前缀和\n\n\n**字符串**\n[problem:CodeForces - 182D ]kmp的next数组求最小循环节\n[submission:18004825 ] 判断s是否为t是子序列 翻转s\n[submission:18005727 ][submission:18005720 ]string find()\n[submission:18006613 ]读入不知 到个数的一组字符串时,用char s[maxn][maxn] r\u003d0; while(gets(s[n])!\u003dnullptr){ ……s[r++];}\n[problem:CodeForces - 1096B ]思考方式可借鉴\n[problem:CodeForces - 443B ]暴力\n[problem:CodeForces - 144C ]尺取,滑窗法\n[problem:CodeForces - 778A ]二分暴力,因为删除的时候是从前往后连续删的\n[problem:CodeForces - 1108C ]循环节可以用i%len的形式表示\n[problem:CodeForces - 1076A ]字典序要从前往后考虑\n[problem:CodeForces - 1113D ] 完全回文串,长为8-\u003e取左半边长为4,判左4个从左数和右4个从右数每个一不一样-\u003e取左半边长位2,判左2个从左……如:a|b|ba|abba再a,b处不一样,就有瑕疵,在ab后切一刀移到后面即可变成不同的新回文串;一直判到奇数则是一直回文的,如a|c|a|ca|acaca 判到aca都满足回文条件,则a是下一个,是完全回文串,切一刀不行,必须切两刀,又如aab|cbaa,aab长为3就不是回文串了;相当于 一直回文到奇数长度的串就不能\n\n**树**\n[problem:CodeForces - 763A ]套路,树上染色,找出连接不同颜色的边,然后查看是否所有连接不同颜色节点的边连接了同一个节点\n[problem:CodeForces - 902B ] 直接用树的拓扑序,不用建树\n[problem:CodeForces - 862B] 二分图染色\n[problem:CodeForces - 505B] 树上dfs 求从i到j有几条能通过的(颜色相同)的路径,多开一维保存颜色,暴力搜索(对节点i,j对不同颜色进行dfs) bool dfs\n[problem:CodeForces - 982C ]统计子树的节点个数 int dfs\n[problem:CodeForces - 639B ] d为树中任意两点之间的距离的最大值,h是这个树以1作为根节点时,树的高度(也即根节点1到其他节点的距离的最大值)。\n树中两个节点(x,y)的距离的定义是,从节点x到节点y会经过的边的个数。 则只可能d\u003d\u003dh||d\u003eh\n[problem:HDU - 4607 ] 求求从一点出发,访问k个点走过的最少边数。**树的直径,两次dfs** 1.从任意节点出发,通过BFS和DFS对树进行一次遍历,求出与出发点距离最远的节点记为p 2.从节点p出发,通过BFS或DFS再进行一次遍历,求出与p距离最远的节点,记为q。\n从p到q的路径就是树的一条直径。因为p一定是直径的一端,否则总能找到一条更长的链,与直径的定义矛盾。显然地脑洞一下即可。p为直径的一端,那么自然的,与p最远的q就是直径的另一端。","likeCnt":6,"createTime":1539161916000,"isWorkbook":false,"viewCnt":3540,"openness":1,"fav":false,"id":681,"trustable":false}