链接

题意

        给你一个矩阵,多组询问，问只保留第i行到第j行删除其他行后得到的矩阵，是否存某列单调不减，

题解

        预处理每一行能保证存在一列单调不减能到达的最远其他行即可

链接

题意

        给出一个长度为N(<3e5)的数列，再给出M(<3e5)个询问，询问输入x和y，你需要输出sum(a[x+ky]) x+ky=N
        4S

题解

        对y<sqrt(n)打表，其他的暴力计算。

链接

题意

        给你长度为n的单调增数组a[]，以及一个u
        让你找一个三元组 i<j<k且a[k]-a[i]<u
        最大化(a[k]-a[j])/(a[k]-a[i])

题解

        我们考虑枚举i，j
        显然当i，j固定后这个值整体上是小于1的，
        所以k越大越好，整体值越大
        
        然后我们发现，当i,j固定后,k的值只与i有关，因为a[k]-a[i]<u
        也就是说不管我们枚举的i和j如何，k只与i有关，不妨设k=f(i)
        
        我们现在考虑枚举i，于是k的值也确定了，为f(i)
        
        这时候，j显然越小越好，于是j=i+1最优
        
        第一个做法出来了：
            枚举i，则j=i+1，根据a[k]<a[i]+u，可以二分出k
        第二个做法：
            枚举i，则j=i+1，容易证明f(i)关于i单调递增，于是用双指针扫描即可

链接

题意

        给你一个长度为n的字符串，每个点有一个删除的代价，问让字符串中不存在子序列hard的最小删除代价。
        1<=n<=1e5

题解

        设:
        dp[i][0] 前缀i不包含子序列h的最小代价
        dp[i][1] 前缀i不包含子序列ha的最小代价
        dp[i][2] 前缀i不包含子序列har的最小代价
        dp[i][3] 前缀i不包含子序列hard的最小代价
        当碰到h的时候，会影响dp[i-1][0]   若删除   转移到dp[i][0]   若不删除   转移到dp[i][1]
        当碰到a的时候，会影响dp[i-1][1]   若删除   转移到dp[i][1]   若不删除   转移到dp[i][2]
        ...

链接

题意

        有魔法石，一个魔法石可以分解为m个普通石，一个魔法师（普通石）占的空间为1，如果一个魔法石一个魔法石往容器里面装，装的时候可以选择分解魔法石为普通石或不分解，询问有多少种方法恰好占满空间为n的容器？分解顺序不同视为方法不同。
        n<1e18

题解

        设:
        dp[i]为放满体积i的方案数
        dp[n]=dp[n-1]+dp[n-m],可以用矩阵快速幂加速

链接

题意

        给你一个长度为n的字符串，每次可以把一个全是同一个字符的子串删除，
        求让字符串为空的最小删除次数。
        n<500

题解

        设:
        dp[i][j]为删掉区间[i,j]的最小代价
        区间dp套路

链接

题意

        给你一个长度为n的数组和一个x，现在可以选择至多一段子区间，让这个区间同时乘以x，之后让整个数组的最大子段和最大。

题解

        dp1[i] 前i个数以i结尾最大的连续子串 且不修改 的和 
        dp2[i] 前i个数以i结尾最大的连续子串，且修改区间以i结尾 的和
        dp3[i] 前i个数以i结尾最大的连续子串，且修改区间以1~i结尾 的和

链接

题意

        从1出发，每个人可以选择让这个数乘以2～9中的一个数字，第一个得到大于n的人胜
        （1 <= n <= 10000) 

题解

        
        sg[   2] change 1
        sg[  10] change 0
        sg[  19] change 1
        sg[ 163] change 0
        sg[ 325] change 1
        sg[2917] change 0
        sg[5833] change 1
        
        win[2:9]=1
        win[10:18]=0
        win[19:162]=1
        win[163:324]=0
        win[325:2916]=1
        win[2917:5832]=0
        win[5833:??]=1
        
        >>> 162*2
        324
        >>> 2916*2
        5832
        >>> 324*9
        2916
        >>> 
        
        sg打表 猜测区间端点 *2 与 *9 

链接

题意

        从一个n*n的角落出发，每次移动到相邻的，而且没有经过的格子上。谁不能操作了谁输。
        （1 <= n <= 10000) 

题解

        如果n为偶数，那么整个矩阵可以分为若干个1*2以及2*1的小矩形的组合，于是后手必胜
        如果n为奇数，分出的矩阵会多一个格子，于是先手变成了必败

链接

题意

        1、  总共n张牌;
        2、  双方轮流抓牌；
        3、  每人每次抓牌的个数只能是2的幂次（即：1，2，4，8，16…）
        4、  抓完牌，胜负结果也出来了：最后抓完牌的人为胜者；
        （1<=n<=1000）

题解

        sg函数表明对3取模