https://vjudge.net/problem/UVALive-3295
这个题目和3720很像，尤其是在应用对称性的时候。这种题目有个很有趣的地方就是他每次都是对局部进行刻画然后得到了全局的信息，或者可以这么说，按照某一种策略使得某种属性所有的状态都被考虑进去。在这里就是计算一个共线的点的问题，按照和题目3720算法本身的推其实是只能算出来“斜率为正”的一类斜线，但是算的是“所有的斜率为正”的斜线，也就是覆盖了每一种情况，那么剩下的情况其实只有水平竖直和斜率为负的斜线，但是由对称性可知斜率为负的斜线一定和斜率为正的斜线数量相等，因此只需要*2即可，而我自己一开始一直在纠结的问题就是怎么算出来这些反向斜线，其实最后全局考虑只需要把算出来的正向斜线情况*2即可。最后的结果就是C(3,(m+1)*(n+1))-共线的三点数量。
wa的话有一个问题是，在gcd的算法中如果a和b有一个数字为0那么返回值就会是0，这种情况在这里的递推过程中是会出现问题的，需要注意让循环从2开始，也算是一个小小的坑吧。。以前没有注意到。
http://codeforces.com/contest/1061/problem/D
嗯。。。又是这种一维的区间最优化策略问题了。。。似乎已经感觉到了套路。。。（赛场上贪心有感觉就直接上了
这种题一般是先排序（以左端点或者右端点）搞出来一个顺序，然后在这个顺序的基础上逐个考虑。考察到某一段时候一般需要做决策，然后这时候可以根据具体题目来看是贪心决策还是dp，如果直觉是贪心（毕竟真正证明有时候确实不好弄），那一般决策都跟满足条件的极端值有关，比如在这里就是如果存在能合并的点（如果连最基本的两段合并后小于各买一台电视机都不满足那一定不能合并），那么一定是和这段左边最靠近他的一个点合并。具体证明可以分情况讨论，一般真的证明的时候就是得考虑，如果不这么合并，计算出来的结果和原来的结果对比，一般要考虑之后的seg的影响，在考虑的时候可以分情况讨论（反正我一般有直觉就上233
然后在实现的时候，有时候没有头绪可以想想STL！（想起了ccpc网络赛被set支配的恐惧），这个东西有时候真的有妙用，它既保持了单调的性质（可以用来贪心）又有着动态维护的特性（贪心的动态调整）。
wa点又是精度，嗯万年精度，这次竟然LL也炸了，而且是因为add的两个参数本身可以达到LL，然后一加给爆了。。。。我去
很有意思的一个组合数学题。
整个题的最核心的思想就是，两个线段共线的判断！只要有两个点就可以确定一条线段（直线），那么只要再多一个点就可以确定这个点是否在和当前的这条线段共线了！所以两种算法的思想都在于一个2
第一种方法：最纠结的问题还是在于，怎么去重。想到了枚举角度的方法却没有想到怎么去重，还是思维不行。第一种方法是每次枚举所有可能的矩形，然后计算对角线的数量，这个很好算也就是有多少个矩形，直接(n-i+1)*(m-j+1)就行了。但是我们考虑的时候首先只考虑gcd(i,j)==1的情况，这种情况一定说明这种对角线的角度第一次出现（因为我们从小到大枚举i和j），所以对答案贡献为正，还有一种情况是gcd(i,j)==2，这说明之前已经出现过了这种对角线，所以这里要减去对应的数量，注意这里是最重要的：减去的是对应的数量，然后其他的gcd值不用+也不用-。原因就在于，如果你有一个4*4的或者3*3的矩形对角线重算了，那么在清除gcd为2的那一步当中其实就已经清除了所有的重复对角线！因为这个2会按照不同的起始点一直推下去。 继续阅读“[组合数学][数论][思维][空间对称转化][充要条件] UVALive 3720 Highways”
自己写了个有点繁杂的数位dp，本来一发过还有点高兴，但是看了前排dalao代码发现自己写的太复杂了。。。。这个题其实只用组合数学就可以解emmmm
先上自己的屌丝做法：分段dp，从前往后，组合数学算下可以知道能预处理出来一段长度为n的可以包含前导0的数据的所有0的个数，我本来想的是用f(p,m,isf)表示当前是第p个数字，最大为m然后是否为上限isf表示状态，但是写着写着发现不用这么来。。。。所以其实到最后程序里的isf就没有用（在发现这一点的时候我就该想到其实不用这么“dp“），把当前位为0特判一下加上后面的所有可能数字（这个也可以预处理），算完当前这一位之后往下一位继续算。。。最后由于我在f里面的枚举都是从0开始，所以等于说算出来的是”可以包含前导0的数的0的个数“，所以在cal里面还要减去所有的前导0的个数。。。麻烦一批
再说dalao们的做法：其实这个前导0的问题很容易解决。。。从后往前算就ok了，每次算到一位的时候判断是不是0，不是0的话，可以想到当前位为0的话总共出现的次数是容易计算的：把整个数字从这个点分开成左右两段（不包括当前这一位），那么左边的数字*10^(右边的位数),如果当前为0那就不能这么算了（跟数位dp一个道理，isf的时候不能当成所有的情况来做）,但是仍然很简单：只要左边不是最大的那个数字，右边仍然可以取到所以情况，所以这时候把左边-1乘上右边的10幂，再加上右边所有的本身的上限就行了。。。还是看代码比较好说。
题意：求出给定图的生成子图里有多少个是仙人掌。
首先明确生成子图的概念：包括所有的顶点的子图（之前没有弄明白这个一直没有想出来），那么这个操作其实就很简单了，首先判断图形是否为仙人掌，如果是的话把其中所有的圈（其实在这里就是点双联通分量）所包含的边的数量算出来，Π(cnt[i]+1)即为结果（每个圈最多只能去掉一个边）。
首先，判断是否为仙人掌，这个可以利用无向图仙人掌的性质在dfs求双联通分量的时候顺便求出来：对于任意一个dfs树上的节点u，他的反向边数量+他的子节点中low值小于pre[u]的数量<2，如果大于等于2说明这个节点附近已经产生了两个环了，不可能是仙人掌，反之如果所有点都满足这个要求，那么一定是仙人掌。
其次，求每一个圈的边数。这里如果是仙人掌的话，一定每个点双联通分量都是一个圈（否则就会被判定为非仙人掌，所以这里首先保证第一步的正确性是很重要的），这样的话只需要在求点双联通分量时在退栈的时候把每个bcc对应的边的数量记录下来就可以了（注意是边的数量而不是点的）。
最后套一个无聊的高精度板子就ok了，因为格式错误wa了几次。。。UVALive貌似经常有把格式错误当成wa的。。。顺便这个对高精度的要求还挺高，1000位都满足不了开了100000位才过，至于吗呵呵
其实我用了一种操蛋的贪心试了一下，所有的cf测试数据里只有一组会错。。但是还没有搞明白为什么错了，也没有办法再继续证明正确性，所以还是放弃了去看tutorial，发现果然没思路就是dp。。。
然后这又不是一个正常的dp，甚至可以说不算是dp吧。。要从一堆数字里选出来一个集合使得gcd为1。确实，涉及到集合就很难操作。但是可以发现，如果这个集合存在，他的size是很小的，这里可以作为一个突破点去想。如果考虑枚举集合的大小，是否能有简单的计算方法。现在需要求的东西可以转化为，是否存在至少一个集合使得他的size为i然后gcd为1，当然这个也不好直接算，但如果再加一维，再枚举gcd，看看会不会有进展：这时候要求的转化为，是否存在至少一个集合，size为i，gcd为j。可以设一个dp[i][j]表示这种集合的数量，然后尝试是否可以递推。这时候可以发现这i个数字一定是从j的倍数里选出来的，所有的选法有C(cntj,i)种，其中cntj是原数列中j的倍数的数量。而这些里面又有一些不符合要求的，是因为他们的gcd=k*j，然后可以发现这些不符合要求的数量就是dp[i][k*j]，这就实现了从大问题往小问题推的转移了。。。然后就只剩下边界的问题了，这个边界也很有意思：因为只考虑k*j<=max(ai)的gcd，所以大于的就是0就可以了
emmm第一感觉好像后缀数组之类的结构，但是这个每个元素是个整数，而字符串处理中每个元素都是一个长度为1的字符，，，所以很难把他等同于字符串来处理。但是直接理解的话，要求的话一定是找到一个排列，然后考虑他的每个子段，然后再在其他所有的排列中去找有没有这个子段，直接裸暴力的话n^3*10，肯定不行，但是想一下如果仅仅是考虑所有的子段就一定是不小于n^2的了，所以起码要在这里进行优化。然后由字符串的性质就可以知道一个长度为i的串如果满足要求的话，那么他的所有子串也都是满足要求的这些子串可以不用再计算了，发现了这个之后怎么去实施这个想法？考虑以每个下标i为开始的最长子串，这里如果用暴力的方法每次从i开始递增， 然后在与其他串判断，则当然仍然是n^3的，但是可以发现与其他串判断这个过程其实有很多重复的判断，假如已经知道了i到i+k个存在的话，判断第i+k+1个时候只需要把这一个数字去和其他的串中对应的数字比较是否全部相等就可以了，这样的话把复杂度降到了n^2*10，但是仍然不够，再考虑之前说的，枚举字段中的重复假设已经知道以i开始的到i+k个数字满足要求，那么在算以i+1开始的子段的时候，可以直接从第i+1+k+1个数字开始，也就是说中间的那些都不用再考虑了，因为这些信息已经在算第i个的时候计算过了。所需要保存的只有每个序列中数字i出现的位置而已。
附上一个讲的很好的链接https://blog.csdn.net/hao_zong_yin/article/details/79807322
第一感觉是类似矩阵连乘的那种操作，写完了才意识到复杂度会是2500^3，然后果断tle了（Final的题怎么会这么简单）。然后就没有什么太好的思路了。看了题解才有点明白。
这个题第一个难点在于，他又有分割又有合并，同时考虑这两种操作的话会很难设计状态转移，但是其实可以发现这两种操作的数量是有联系的，因为最初的堆数量是确定的，最后的堆数为1，所以分割和合并的数量关系可以确定出来，这样的话只需要算出来其中一种操作的数量就可以了，我这里考虑的是合并的次数w，经过推导可以得出最后答案ans与w的关系是 ans=2*w+n-1;（这个东西其实可以很简单的算出来：直接把每一摞盘子全到一起，总共的join次数为n-1，split次数为0；然后，每次在某一摞盘子内部进行一次split操作，则必然会在最后的结果中引入一次join操作，有一一对应的关系，因此可以推出来对于任意情况都有join次数==split次数+n-1）
第二个难点就是确定了要求合并的次数之后，如何进行dp。这里我们可以借鉴汉诺塔的思想，在考虑前i个（从小到大）盘子的时候，可以把大于i的盘子当成没有一样。而由于这里我关心的只是合并次数，所以不用考虑盘子的中间态（汉诺塔里盘子只能放在某个轴上，但是这里也可以放在地上），这样的话递推方程就会变得简单了。。。只需要使得dp[i][j]表示前i个盘子全放在第j堆上（想象一下这个画面）的最小操作数（这里要求第j堆必须有i这种盘子，说”这种”是因为离散化了），则转移的时候dp[i][j]一定是从dp[i-1][k]得来，其中1<=k<=n，而这时候又有不同的情况需要讨论 ：①j==k，这时候如果有i的堆的数量为1，那么就是第j堆这个（因为我们规定只有j堆有i的时候才往这里转移），那么他就不需要动，直接dp[i][j]=dp[i-1][j]；如果有i的堆的数量大于1，那就得先把j堆上的 (1到i-1) 这一坨移走，再把其他cnt[i]-1个i类盘子合并到j堆上，再把移走的 (1到i-1) 那一坨移回来（cnt[i]代表有多少堆含有i这个种类，可以预处理出来），所以总共增加的的操作数是cnt[i]-1+1=cnt[i]，也就是这里的方程为dp[i][j]=min(dp[i-1][k]+cnt[i]); ② j!=k ，这时候好说，只需要考虑第k堆有没有i就可以了，如果有那就多了cnt[i]-1次操作，如果没有就多了cnt[i]-1+1次操作（注意约定是j堆一定有一个才能往那儿转移，所以除了那一堆里的那个i，还剩下cnt[i]-1个i）。
其他的也就是离散化的操作需要谨慎一点，我由于写错这个wa了两发。。。去重的时候先保留能保留的再去重！不然有可能导致数组扫描完了却没有存任何一个数（比如整个数组都是同一个数）
更：今天起床看了看2个月之前做的这个题，觉得当时还是naive，每次直接考虑只向含有第i种盘子的摞转移就好了，于是重写了第二种代码（其实核心思想完全一样的）
自己想的时候一直在纠结的问题是怎么保存(第k个之前的是不是0/1)的问题，纠结了很久没有get到正点上，因为单单这样的话似乎会导致状态信息不足。。会漏掉一些情况。看了绿书题解，一看到状压顿时明白了。。。k最大只有10，这样的话只要把构造串的最后k位01情况压缩起来就可以了。另外一个问题就是这样的话会不会导致有中间产生长度超过k的回文串，答案是否定的，因为回文串本身其实有着子结构的性质，如果以某个节点为最后一位的长度k的回文串没有被构造出来，那么一定不会有更长的回文串包含这个点的。
嗯。。。。果然还是那句话，直接上组合数学搞不定的组合数学，要么打表要么dp递推。
设dp[i][j][flag]表示前i数字，令最后一个数字为j时的方法数，其中flag==0表示第i-1个比第i个小，flag==1表示第i-1大于等于第i个，然后根据题目要求就是不能出现局部极大值，所以可以写出来递推式：① dp[i][j][0]=Σ(dp[i-1][k][0]+dp[i-1][k][1]) ,1<=k<j ② dp[i][j][1]=dp[i-1][j][0]+Σdp[i-1][k][1],j<=k<=200 边界条件的话是单独考虑i==1的时候，特判算一下就可以了。这个方法是n*200个状态，每次转移再*200就是40000*n，太慢，观察到是求前缀/后缀和的形式，可以每一轮算完i之后维护一个presum[j][flag]，保存这一轮的前缀和，这样的话可以O(1)转移，复杂度就变成了n*200 。
主要的思考的点就在于在满足题目条件的约束下递推，加了一维状态表示之后问题就变得很简单了，所以推不出来的时候可以考虑加维（增加dp的信息量）
由于偷懒到处取模所以代码很慢吧。。。不过dp重要的是思想hhh
继续阅读“[CF][DP][递推关系] codeforces 1068D Array Without Local Maximums”
