链接

题意

        给两个长度为n的首尾相连的序列a,b,你可以旋转他们，可以让整个序列加上一个定值，最后要最小化sigma((ai-bi)^2)
        n<5e4,
        ai,
        bi<100 

题解

        求sigma((a[i]-b[i+k]+C)^2)的最值->求sigma(a[i]*b[i+k])的最值->翻转一个串->sigma(a[n-i]*b[i+k])->fft

链接

题意

        给你两个串s,t 
        |s|<3e5 |t|<3e5
        允许对两个串进行任意次如下操作：
            选一个区间，用区间和代替整个区间的元素
        最终要求达到s==t
        要求最大化s==t时候的|s|
        若不可能，输出-1

题解

        贪心做法:
            他们俩各自一个指针，往后走，谁小谁先走，不等的话，再来谁小谁先走... 相等时让计数器加1，然后一起走,有解的话输出计数器就是答案了
        其实也是尺取法
        再细细分析
        我们发现可以dp证明，dp[i]代表s串的前i项能否匹配t串的前j项，若能匹配，为dp[i]赋值j，否则定义此dp没有意义
        我们发现有意义的dp,其值关于i单调，无意义的dp，其判断依据，也关于i单调
        于是可以O（n)完成dp
        有意义的dp值的个数就是答案

链接

题意

        给你一个01串s,|s|<1e6
        给你一个k, k<|s|
        让你求s的子串中有多少个包含了恰好k个1

题解

        dp1[i]代表以i结尾，恰好包含了k个1的最小起点
        dp2[i]代表以i结尾，恰好包含了k个1的最大起点
        显然两个dp都关于i单调不减
        
        或者这样
        pre[i]统计前i个数里面有多少个1
        然后lower_bound + upper_bound 搞pre数组

链接

题意

        给你一个长为n的数组，允许你修改一个元素，要求你最大化修改完后的最长严格单调增子串

题解

        记录f(i) 为以第i个元素为终点的严格单调增子串的长度
        记录g(i) 为以第i个元素为起点的严格单调增子串的长度
        枚举修改元素，通过f和g可以快速求出答案
        注意特判边界

链接

题意

        给你一个长为n的数组，数组元素有正有负，让你划分数组为三部分

题解

        统计前缀和为sum/3的位置，后缀和sum/3的位置，
        借此统计后缀中有多少个后缀和为sum/3的位置,计作g(i)
        转换题意为求对于每一个前缀和为sum/3的位置，求和g(i+1)
        就是答案

链接

题意

        给你一棵树，每个点上有一个flag,如果flag=0，表示这个点的权值是所有子节点权值中的最小值。如果flag=1，表示这个点的权值是所有子节点权值中的最大值。如果一共有k个叶子节点，我们可以给每一个叶子节点安排一个1-k中的权值，但是每个权值只能使用一次，现在想知道根节点权值的最大值。

题解

        dp[i]代表在以i为根节点的子树中，i的最大排名
        flag=1 dp[rt]=max(ct[rt]-ct[son]+dp[son]);
        flag=0 dp[rt]=1 , dp[rt]+=dp[son]-1;

链接

题意

        有n个格子，每个格子有01权值，1代表这个格子可以安装暖气，每个暖气可以温暖距离自己小于r的格子，问最少安装几个暖气能温暖n个格子。
        1<=n<=1e3

题解

        dp[i]代表在第i个位置放一个暖气，能温暖前i个格子的最少安装的暖气数，
        dp[i] <--- dp[j] (i-j<r)
        答案在dp[n-r+1,n]上
        明显dp可以用单调队列优化，维护一个i单调增，dp值单调减的单调队列即可。

链接

题意

        题意就是给你一个A序列和一个B序列
        让你构造一个t序列，t序列满足
        𝑎𝑖=𝑡𝑖|𝑡𝑖+1
        𝑏𝑖=𝑡𝑖&𝑡𝑖+1
        (0≤𝑎𝑖≤3)
        (0≤𝑏𝑖≤3)
        (2≤𝑛≤1e5) 

题解

        最后两个数只有四个情况，反向暴力递推

链接

题意

        给你一个字符矩阵，起点在左上角，终点在右下角，每次可以向右或者向下走，最多可以改变这个字符矩阵中的k个字符，使得这个路径构成的字符串字典序最小。矩阵n*n,1≤n≤2000,0≤k≤n^2

题解

        贪心，改完之后肯定是至少前k个都为'a',然后我们dp[i][j]，处理出每一个起点走到每一个（i,j）的路线上最多会经过多少个'a'，然后，对于每个满足dp[i][j]+k>=i+j-1的点(i,j)，构建函数f(i,j)=min(i+j-1,dp[i][j]+k),表示到达点(i,j)最长会经过的全部都是'a'的前缀的长度，取出最大的几个点，然后bfs再处理这些点到终点的的路径，取出字典序最小的，和前面的前缀组合就是答案的方案了。

链接

题意

        长度为n(1e5)的数组，值域为1到200，且每个数的旁边必有一个大于等于它的数。有些数字被擦掉了，问共有几种填充的方案满足上述要求。

题解

        dp[i][j][0] 填完了前i位且第i位填j,且第i位小于i-1位
        dp[i][j][1] 填完了前i位且第i位填j,且第i位等于i-1位
        dp[i][j][2] 填完了前i位且第i位填j,且第i位大于i-1位
        
        dp[i][j][0] <--- dp[i-1][k][0],dp[i-1][k][1],              j<k
        dp[i][j][1] <--- dp[i-1][k][0],dp[i-1][k][1],dp[i-1][k][2] j=k
        dp[i][j][2] <--- dp[i-1][k][0],dp[i-1][k][1],dp[i-1][k][2] j>k