小衣同学的博客

此时乘以pi=1e5也小于1e-14，乘以1e5场也不会超过1e-9，对答案的误差不会产生影响。所以可以倒着dp这个过程，就无后效了，dp[i]表示当前参加了i场时的最大rating和，那么(1-k)的x次方，当x到一定次数就很小了，试着400多次方的时候就会小于1e-19，然后这么暴力dp是O(n^2)的，不能接受，注意到k>=0.1，1-k<=0.9。有一个浮点系数k(0.1<=k<=1)，对于n场来说系数是一样的，t(t<=1000)组样例，每次给定n(n<=1e5)场比赛，倒着看这个比赛的过程，

要么选了0，选了一个1，选了1个2，这种情况仍在f里统计，也只统计一次，从g转移回来即可。由于子序列当前和为0的时候，选ai和不选ai实际是一种方案，所以把这种情况择出来，要么选了0，选了一个1，这种情况和只选0是一样的，不在f里统计，在g里统计一次。给你一个长度为 N（N<=10）的整数序列 A=(A1,A2,⋯,AN)。做法挺巧妙的，g实际是一个辅助数组，dp还是很锻炼思维的。选ai的时候转移进g数组，不选ai的时候忽略，那么对于0 1 1 2来说，要么只选了0，还是在f里，

转移的时候，dp[i][j]要从dp[x-1][y-1]转移过来，这两维都不是固定的，实际无法完成归并。然后考虑怎么优化这个O(n^4)，还是dp[i][j]表示第一段以i结尾、第二段以j结尾的合法方案。枚举x<i，枚举y<j，[x,i]区间与[y,j]区间一共是O(n)个的，不妨按平均值从大到小归并，这样可以把所有平均值大的dp[i-1][y-1]所以，枚举x>i，枚举y<j，对区间[i,x]和区间[y,j]进行归并，容易想到O(n^4)的做法，就是枚举a的最后一段，b的最后一段，

其实想了想，和20年小米邀请赛决赛这个G题的dp思路是一样的，姑且称为sg图dp吧。本题就是先预处理f[i][j]表示i个点与j个点里至少一个点联通，按sg值从大到小dp，每次补上全局sg值-1的这些点，感觉没想到就怎么都想不到，想到了就能秒了。然后每次把j个点作为一个新sg值加进去。

确定了对应个数之后，由于每个值有[-m,m]的限制，check下是否符合对应变化范围即可。对于每个可能的和，顺序做dp，dp[i][2]表示填到第i位时，最后一位是填了P还是S。也就是说，SS确定一位，PP确定一位，PS判断是否和枚举的和相等，SP确定两位。如果第i位填了S，那么由于和是枚举的，等价于确定了前i-1位的前缀和，PS相邻一个是前缀和一个是后缀和，就可以唯一确定这个序列的和。前面补一个0，字母对应P，后面补一个0，字母对应S。如果第i位填了P，等价于确定了前i位的前缀和。

dp[i][j][1]表示颜色和最大严格不同（也就是和dp[i][j][0]的颜色不同）时次大的(和,颜色)n(n<=2e5)个球在同一行，第i个球颜色是ci(ci<=n)，值是vi(vi<=1e9)dp[i][j][2]，其中dp[i][j][0]表示前i个删了j个后最大(和,颜色)但是仔细观察发现，实际前驱颜色只需要两种，即产生最大贡献的颜色，产生次大贡献的颜色。暴力是O(n*k*k)的，枚举当前颜色是什么，枚举上一个颜色是什么。同时需要保证转移后，次大的颜色仍然不能和最大的颜色相同。

可交换次数不超过n^2时，dp状态是O(n^5)的，转移枚举三种字符，每种算增量代价是O(n)的，dp[i][e][y][k]表示前i个字母有e个E、y个Y最少交换k次的字符串的方案数。也就是说，如果第e+1个E前面，Y的字符超过y个，那么剩下的Y都需要被绕过，K同理。所以，当前字符用什么，在原串里的位置一定唯一，交换次数也能唯一确定。假设当前第i个字符填E，一定用的是串中第e+1个E，比如，之前已经用过e个E，y个Y，i-e-y个K，且需要在交换的时候绕过第e+1个E前面的其他字符，

h*w(h<=30,w<=30)的格子矩阵，第i行第j列格子权值a[i][j](1<=a[i][j]<=1e9)当前位于(i,j)，最小值是否已经出现过了，大于等于最小值的权值已经选了k个，权值和最小是多少。当前位于(i,j)，当前最小值是x，大于等于最小值的权值已经选了k个，权值和最小是多少。找到一条路径，取途中最大的k(k<h+w)个格子的权值求和后，和是所有路径中最小的。终态要么是大于最小值，要么是等于最小值，并且大于最小值的时候的值都是必取的。一开始想的是dp[i][j][x][k]表示，

比如1+23*45*56+7，mul[4]表示45*56的值，而mul[3]表示23*45*56的值。还需要处理一个形如2345*(3+34+345+3456)的东西，并加上2+23+234。sum[i]形如(3+34+345+3456)+(2+23+234+2345)，sum2[i]形如2+23+234+2345*(3+34+345+3456)，由4+45+456需要得到3+34+345+3456时，加上3333即可，不妨称3+34+345+3456这样的段，叫3456这个数的前缀贡献。

没出现的m+1-j种中，恰有一种不能选（会导致s[i]=1），其余都可以选，(m-j)*dp[i][j]->dp[i+1][j+1]如果不新选，之前有j种，本次挑一种，有j种方案，j*dp[i][j]->dp[i+1][j+1]如果s[i]=1，则有A[i]=mex(A[1],A[2],...,A[i-1])如果s[i]=0，则有A[i]≠mex(A[1],A[2],...,A[i-1])每种方案对应的选法都是唯一的，dp[i][j]->dp[i+1][j+1]其中，mex为未出现在集合内的最小正整数。

所以，dp[i]表示考虑[1,i]，i这种字母必留，考虑和ai相同的上一个必留的字母j在哪。想留a这种字母时，有可能中间的aa是要被牺牲掉的，bbbbbaaccccc整段删除。想了一个枚举哪种字母最多，然后贪心删剩下的，兑掉其他字母，再往想留的字母上面兑，能转移当且仅当[j+1,i)这段区间能被删干净，注意判断j+1==i的情况。但是假了，比如，aaaaaaaaabbbbbaaccccca，为了统一写法，可以令任意字母也能转移到dp[n+1]上，转移到dp[n+1]的时候长度加了1，减掉即可。

只需全局减1，即可删掉m+1个1，并且使得第m+2个数的值>=1，也就对应了f[i-(m+1)][j-i]②要么令所有数都+1，使得所有数都大于等于2，转移到2 2 3，f[i][j]从f[i][j-i]转移。①每次要么新增一个1，转移到1 1 1 2，f[i][j]从f[i-1][j-1]转移。原序列2 2 3，差分序列2 0 1，反转差分序列1 0 2，原序列2 2 3，差分序列2 0 1，反转差分序列1 0 2，令B[1]=A[1]，B[i]=A[i]-A[i-1]，

即dp值来源于两部分，一部分是最终栈中的dp值之和，一部分是本次弹栈的位置的dp值之和。所以可以分成两部分维护，分别维护单调栈自底到顶的dp值之和，和dp值的前缀和。dp[i]表示只考虑[1,i]，i作为最后一个元素必取时，合法的方案数。那么此时单调栈自底到顶还是单增的，栈底的值可以把上面的值再删掉。4. 操作[5,6,8,9]，用5把剩下的删了，7在5后面。3. 操作[8,9,7]，用7把9和8删了，7在6后面。2. 可以操作[9,7]，用7把9删了，7在8后面。从左到右扫完之后，求的是前缀合法的情况，

由j*k>B[j]，解得k>=B[j]/j，所以枚举k的时候，每个点从S换到T的操作只会发生一次。3. 左侧集合P与右侧集合非Q之间的边，左侧属于s的点，右侧属于t的点，断开左右点之间的边。并且划给S集合的每个点贡献是j*k，划给T集合的每个点贡献是B[j]，1. 超级源点s与集合非P之间的边，即左侧属于t的点，断开与s的边。2. 集合Q与超级汇点t之间的边，即右侧属于s的点，断开与t的边。可以任意划分，将一部分划给S集合，另一部分划给T集合，所以无需断开左侧属于t的点和右侧属于s的点之间的边，

第一条轴上给定m(m<=1000)个点，第二条轴上给定n(n<=1000)个点，点坐标x(0<=x<=1000)d即线上修建k个点，轴上n+m个点，到线的距离为s/2，每个点到最近点的距离平方的和最小。那么每个修建的点对应的肯定是一段连续的区间，枚举最后一个修建点对应了哪一段朴素dp即可。在距两条轴距离相等且平行的线上，标记k(k<=100)个位置点，使得n+m个点，点i对k个位置中距离最近的点算距离，记为xi。首先，由于轴两侧是等距的，可以把轴上的点合到其中一侧并排序，，将所求式展开，分别为。

1. 第i-1行没取的话，第i行会新增一列，dp[i-1][j-1]转移到dp[i][j]等到第n行决策完取不取后，第n+1行都会新增一列，所以dp[n+1][n-k+1]即为所求。取完之后，第i行还是会新增一列，dp[i-1][j]*j转移到dp[i][j]有dp[i][j]=dp[i-1][j-1]+dp[i-1][j]*j。dp[i][j]表示只考虑前i行还有j个空列的方案数，2. 第i-1行取了的话，从j列里挑一列取，j种方案，例如，n=3，m=2时，合法方案有7种，如下图。

具体来说，操作前是[s[l],s[l+1],...,s[r-1],s[r]]，操作后是[s[r],s[l],s[l+1],...,s[r-1]]能这样匹配，当且仅当在[j+1,n]中t[j]的出现次数cnt2，小于在[i+1,n]中相同字母的出现次数cnt1。你可以执行以下操作任意次，每次操作，可以选择s的一个子区间[l,r]，将s[r]拽到s[l]左边，s[i]和t[j]能匹配，当且仅当，匹配了这个字符之后，后面的每种字符都还够用，①s[i]=t[j]，直接匹配上，继续考虑(i-1,j-1)

②如果仅右侧有棋子，说明当前位置必胜态，同行左侧都是必胜态，同行不可能再出现必败态了，但同列下方都是必胜态，还有可能在上方出现必败态，接着考虑(x-1,y)1. (x,y)在右下角，必败，sg(x,y)=0，同时第x行左侧和第y列上侧所有sg值为1，接着考虑(x-1,y-1)当你在(x,y)位置时，下一步可以走到同一行靠右的位置(x'=x,y'>y)或同一列靠下的位置(x'>x,y'=y)2. 间接获胜的情形也是不存在的，是因为上一个必败态(x',y')产生后，接下来考虑的是(x'-1,y'-1)

如果当天学的j，没学的第一门课连续没学k天，没学的第二门课连续没学l天，状态dp[cur][j][k][l]预处理了一下，id[i][0]表示学课程i时没学的第一门课的标号，id[i][1]表示第二门课的标号。在代码实现中，dp[i][j][k][l]表示到了第i天时，第i天当天学的是第j门课，首先，用根号的思想，每根号w天不学，就会下降超过一天学的收益，不如期间用一天学一下。特别地，当k=0、l=0时，代表这门课从来没有学过，一直为0，转移的时候不扣除天数。①如果这门课没学过，即k=0，就还是k=0。

dp[i][j][k]：只考虑前i个字符，总共有j个0，子序列中有k个01子序列时的最小翻转次数。则最终交换的次数=保证0的个数还是原来的情况下，(把0翻成1的次数+把1翻成0的次数)/2。求最小的操作次数，使得串平衡（串中01子序列的个数等于10子序列的个数）所以，最终01子序列=10子序列=二者之和的一半=cnt0*cnt1/2。长为s(3<=|s|<=100)的01串，注意，交换操作不改变00和11的数量。每次操作，可以交换两个位置的数字，即把0翻成1 或者 把1翻成0。枚举第i个字符翻不翻。

则置dp[x在[1,r]里第一个出现的位置][x在[r+1,n]里第一个出现的位置]为1。再用nex[i][j]=nex[i+1][j]，求得>i的第一个字母j的位置。考虑枚举分界线r，将s分成左右两部分[1,r][r+1,n]，即nex[i][x]、nex[j][x]，x遍历26个字母即可。代码中，nex[i][j]先求出>=i的第一个字母j的位置，则可以在[i,r]、[j+1,n]中再找到一个公共字母x，且在[r+1,n]也出现，则只会在[1,r]中计数一次。答案对998244353取模。

从右到左：只有处理好了第i+1列，才能处理第i列，(i,j)涂黑当且仅当(i+1,k)涂黑，k<=j+1。从左到右：只有处理好了第i-1列，才能处理第i列，(i,j)涂黑当且仅当(i+1,k)不涂黑，k<j-1。对于任意在矩阵中的(i,j)，即1<=i<=n且1<=j<=m，②若(i+1,j+1)也在矩阵中，则(i+1,j+1)也是黑块。某一列没有黑块的情形，此时，我把最后一个黑块定到了第n+1行，①若(i+1,j)也在矩阵中，则(i+1,j)也是黑块。因为(i,j)黑块取了的话，这一列下面的黑块都会取，

+、-构成的长度为2n(n<=3000)的串，?对应的方案数为dp[i][j]，对总距离和的贡献为dp[i][j]*j。sum[i][j]表示前i个字母，+比-多j个时，所有方案的距离和。求所有的合法填写方案下，+-均贪心匹配时，所有对+-之间的距离和。dp[i][j]表示考虑前i个字母，+比-多j个的方案数，这里的没匹配，既可以是+比-多j个，也可以是+比-少j个，可以发现，每经过一个字母，还有j个字母没匹配时，，使得串中恰有n个+，n个-如果是合法栈匹配，只转移正的就可以了，

除了在之前的beatutiful串后面续上这个最短偶回文串，构成新的beautiful串以外，定义：若一个串要么是偶回文串，要么由若干个偶回文串拼接而成，则这个串是beautiful的。x到i的距离为i-x+1，将其记为len，则偶回文串长度即为2*len，为最短的。拼接的时候，只考虑拼接以i为右端点的最短的偶回文串，不然可能会计数重复。由于只需要偶回文串的长度，所以无需在其中补#号求出奇回文串的部分。1. 如果x+r[x]不能覆盖i，则也不能覆盖i+1，把x干掉。如何求这个覆盖i的最短的回文串的长度。

最后的元素（第i个元素）是否被删（0/1）时，对应的最小删除次数为dp[i][j][k]，1. 找到最小的删除次数，使得剩余没被删的元素之和等于x，输出最小删除次数。转移则类似背包，枚举最后一个元素是删了还是没删，上一个元素是删了还是没删，dp[i][j][k]表示：考虑前i个元素时，当前没被删的元素和为j，给一个长度为n(n<=3e3)的数组a(1<=ai<=3e3)，若dp[i][j][k]为INF，则表示此状态不合法。当前的01从上一次的01转移而来，四种情况。特别地，空数组元素和，认为是0。

AtCoder Beginner Contest 279 G. At Most 2 Colors(计数/组合数学/dp递推)

Educational Codeforces Round 136 (Rated for Div. 2) E.Cleaning Robot（基础dp）

2022 百度之星程序设计大赛复赛 D.子序列2(动态dp/线段树维护矩阵)

题目竞赛：2022招商银行专场竞赛D题：商店促销活动n(n<=1e5)件商品，第i件商品，要么去商店A买，花费ai(ai<=1e4)，要么去商店B买，花费bi(bi<=1e4)两个商店有不同的优惠活动，求买n件商品的最小代价和是多少商店A的优惠活动： 购买商品满三件及以上商品可以打七折（向下取整），不满三件则无任何优惠 商店B的优惠活动： 每购买三件商品，可以免去其中价格最低的一件商品的价格题解直接粘自己在leetcode写的题解好了（摆烂...

题目长度为n的序列，第i个值为ai，easy：n<=1e5，0<=ai<=500hard：n<=1e6，0<=ai<=5000对于序列中的所有严格上升子序列，每一种序列的值异或起来，得到一个值v，输出v的种类数，按增序输出所有v的可能性思路来源quality代码（hard）题解easy：暴力bitset维护可达集，每次暴力异或，1e5*500*500/64dp[i]表示当前能异或出i的序列最小值hard：dp[i][

题目bzoj1566思路来源https://www.luogu.com.cn/blog/user23116/solution-p1758第一种dphttps://blog.csdn.net/pocket_lengend/article/details/79821748第二种dp题解首先要理解一点，……理解了这一点后，有两种dp方式，一种是dp[i][j][k][l]表示第一次第一个管道取了i个，第一次第二个管道j个第二次第一个管道取了k个，第二次第二个管道取了l个的完..

题目bzoj3294在一个m(m<=30)行n(n<=30)列的棋盘里，放c(c<=10)种彩色的棋子，使得每个格子最多放一个棋子，且不同颜色的棋子不能在同一行或者同一列。求合法的方案数，答案对1e9+9取模。例如，n=m=3，有两个白棋子和一个灰棋子，下面左边两种方法都是合法的，但右边两种都是非法的。思路来源hx073269代码题解把棋盘考虑成一个二分图，对于每种颜色单独处理，考虑为第i种颜色分j行k列，则需要n行里选j行，m列里选k列，

题目你需要构造两个长度为n的排列，分别记为p，q，满足：①p的字典序比q的字典序小②p的逆序对比q的逆序对多答案对mod(1<=mod<=1e9)取模easy version：n<=50hard version：n<=500思路来源官方题解题解1f[i][j]：表示长度为i，逆序对为j对的方案数，枚举第i位填的数，考虑1-i时的从小到大的rank几，比如rank为j，则[j+1,i]与其产生了j-i个逆序对sum[i][j]：表示f

题目在N行M列的棋盘上，放若干个炮可以是0个，使得没有任何一个炮可以攻击另一个炮。请问有多少种放置方法，中国象棋中炮的行走方式大家应该很清楚吧。一个炮要能攻击另一个炮，他们必须要处于同一行或者一列且他们之间有且仅有一个棋子。思路来源蔡老师题解不存在三个炮位于同一行或者同一列，即每一行最多有两个炮，每一列最多有两个炮。于是可以考虑把棋盘考虑成一个二分图，左侧的点代表行，右侧的点代表列， 每个点的度数<=2dfs(i,j,k)表示还需要考虑右边的[1,i]列时，左边还有

A. Micro Structure Thread(最小生成树)题意比较迷惑，最后转化下来是确定一个树的父亲的排列，使得代价最小，即一棵最小生成树，点和父亲

题目链接：来源：牛客网一个完美串应该满足该串中任意长度≥2≥2≥2的子串都不是回文串，把一个字符从xxx变成yyy的代价是min(∣x−y∣,26−∣x−y∣)min(|x-y|,26-|x-y|)min(∣x−y∣,26−∣x−y∣),(∣x−y∣|x-y|∣x−y∣为asciiasciiascii码差值)，问把一个串变成完美串的最小代价保证串中只出现小写英文字母思路来源wifiiii代码题解代码...

#include<bits/stdc++.h>using namespace std;typedef pair<int,int> P;const int N=52,M=N*N+5;vector<P>e[N];bool vis[M];int now[N],ans[M],cnt,to[M];int n,k,c,x,y;char res[M];void dfs(int u){ while(now[u]<e[u].size()){ ...

题目思路来源qls题解一道很久之前的题，看当时有人问，但自己没有补，现在才彻底想明白将所求表达式考虑成这样一个匹配问题，dp[i][j][k]表示当前考虑前i个数，还有j个左边的值要连向比它们大的右边的值(同时意味着还有j个右边的值要连向比它们大的左边的值)，当前的绝对值之和是k的方案数转移即加入第i种数，此时分五种情况，以同时加入2左、2右为例，注意到比和自己小的数匹配有j种方式，①左右等，2左和2右匹配，dp[i][j][k+2*j]+=dp[i][j

题目有c1个a，c2个b，...，c26个z。你需要用这些字母构造出一个长度为n的字符串，使得不存在长度>=3的奇回文子串。输出答案对998244353取模的值。保证对于输入的所有ci来说，ci>n/3都成立。思路来源uoj群题解奇回文子串的限制，等价于s[i]!=s[i-2]。如果没有ci的限制，就变成了一个计数问题，前两个字母26种选法，后面的只要保证和s[i-2]不同，25种选法。于是，ci>n/3成为了突破口，鸽巢原理表明，最多只有两种字母会

题目长度为n(n<=1e5)的a[](0<=ai<=9)，你需要在n-1个空位填入n-1个符号，不能加小括号使原式值最大，输出最终的式子如果有多种答案，输出其中一种即可被允许的符号是一个{‘+’,'-','*'}的非空子集，由一个字符串s(1<=|s|<=3)给出思路来源官方题解题解只有一种符号显然，两种符号的时候，+-显然只用+，*-的话，除了0要减掉以外剩下的都用乘最后剩两种情况，+*和+-*，可以发现减号多余，就