A贪心一次消掉三个代价a一次消掉一个代价b问全部消掉的最小代价。先考虑一次消掉三个哪种性价比更高。最后不足三个了再用一次消掉三个或者一个一个消voidsolve(){intn,a,b;cinnab;intxn/3;intansmin(x*3*a,x*b);n%3;ansmin(n*a,b);coutans\n;}B前后缀分解 数论一个1-4组成的字符串想要使得任意非空子序列形成的数字都不是4的倍数问最少需要删除几个字符用到一点小学奥数结论4的倍数特征是最后两位是4的倍数因为从第三位开始基础就是100了100是4的倍数所以更高为一定都是4的倍数。考虑到只有1-4的数字能形成的不超过两位的4的倍数只有单独一个4或者一个奇数一个2的形式比如123252…对于4必须要删除所有4的出现。对于奇数2要使得所有2左侧都没有奇数这可以删除奇数也可以删除2有很多种方案。但最优方案一定形如删除一个前缀里的所有奇数删除剩余后缀里的所有2这样就已经可以满足所有2左侧没有奇数虽然前缀内可能还有2但是前缀内的奇数已经都没了同理后缀里可能还有奇数但是2都没了。但是前后缀在哪分割是最优的不确定由于确定了一个分割点可以用前缀和来O(1)O(1)O(1)计算删除元素个数所以可以枚举分割点就是一个O(n)O(n)O(n)的前后缀分解。这里的一个易错点是可能会认为所有奇数或者所有2删除是最优的而且可以通过样例、voidsolve(){string s;cins;intansinf,cnt0;for(charc:s){if(c4){cnt;}}intns.size(),c10,c20;for(charc:s){if(c2){c2;}}ansmin(ans,cntc1c2);for(charc:s){if(c2){c2--;}elseif(c1||c3){c1;}ansmin(ans,cntc1c2);}coutans\n;}C贪心第iii种元素有aia_iai​个。现在从这些所有元素里选一些拼成一个环要求环上任意三个连续的元素至少有两个元素相同。问环最大长度只有一个的元素肯定要插在另一种元素的中间让两侧元素相同才能满足要求所以把只有一个的元素都单独拿出来。对于剩下的出现次数超过1的元素。肯定越多越好并且相同元素应该挨着放这样能创造出尽量长的相同元素段每一个相同段内部可以插入一些只出现一次的元素。具体来说一段长度x的连续段可以插入(x−2)/2(x-2)/2(x−2)/2个只出现一次的元素。维护一下连续段能提供的空位个数以及出现一次的元素个数取min⁡\minmin即可。特判有两种只有一种元素则需要个数x至少3才能成环答案就是x个数不足3无法形成环如果不止一种元素但只有一种元素出现次数大于1。这个出现次数大于1的元素形成的区间在环上首尾相连能额外提供一个空位可以让出现次数1的元素插入一个。voidsolve(){intn;cinn;if(n1){intx;cinx;if(x2){cout0\n;}else{coutx\n;}return;}intc10,c20,ans0;rep(i,1,n){intx;cinx;if(x1){c1;}else{ansx;c2max((x-2)/2,0ll);}}if(c1n-1){c2;}ansmin(c2,c1);coutans\n;}D倒序dp有一个电视剧1-n集两个人看的电视台每天都会放某一集。现在要选一个时间区间两个人在这个时间段内的每一天要么都不看要么都看且看的是同一集。两个人关于看不看的规则都是如果今天播aia_iai​集并且前面的[1,ai−1][1,a_i-1][1,ai​−1]都看了那么就会看今天的否则不看。问有多少个时间区间满足这个要求要求所有合法区间一般思路就是枚举一个端点计算另一个端点的合法位置一般具有单调性也就是另一个端点的合法位置形成一个连续区间所以只要求另一个端点的合法位置的最值即可。一般枚举左右端点都行先考虑枚举右端点计算左端点最小能到哪里。一般随着右端点移动左端点并不需要暴力计算最远而是可以根据前面的结果递推。但尝试一下会发现右端点移动一下左端点最值的变化很难递推。这其实是因为我们要找的是一个从左往右的链那么每次在右侧增加一个它可能是接到某个链结尾的也可能是新开一个链这本来没什么但是我们递推要维护的值是最左的链起点接到一个链结尾或者新开一条链对于最左的起点产生的影响是难以O(1)O(1)O(1)更新的。考虑枚举左端点维护最远点右端点在哪这样的话如果我们再从右往左枚举每次增加一个在链最左端并不会影响最右端的位置也就是可以完美服用子问题的解。具体转移是fif_ifi​表示如果看了前i−1i-1i−1集接下来要看第iii集最远能看到多少天是合法的。如果某一天两个电视台放的相同这一天是两个人都能看的那么看了aia_iai​集最远能看到多少天需要更新看完第aia_iai​集后后面必须看ai1a_i1ai​1集所以从ai1a_i1ai​1转移。如果这一天两个台放的不相等可能导致两个人中某一个人在这一天看了另一个人没看这种情况发生于看到了ai−1a_i-1ai​−1或bi−1b_i-1bi​−1集这是不合法的不能往后看了那么对于这两种情况最远点就在i−1i-1i−1。对于其他的情况看到其它集了经过这一天的时候两个人都不会看可以继续没有任何影响不更新。整体框架是维护一个f(n1)f(n1)f(n1)记录当前需要看[1,n][1,n][1,n]集分别能看到最右边第几天。倒叙枚举每一天转移每一天时fff数组存的都是这一天的结果查询累加左端点为iii这一天的结果到答案。voidsolve(){intn;cinn;via(n1),b(n1),f(n2,n);rep(i,1,n){cina[i];}rep(i,1,n){cinb[i];}intans0;rep1(i,n,1){if(a[i]b[i])f[a[i]]f[a[i]1];elsef[a[i]]f[b[i]]i-1;if(f[1]i)ansf[1]-i1;}coutans\n;}类似地还有另一种dpdpdp定义设fif_ifi​表示看了第iii天的电视剧最远能看到多少天。转移思路其实是类似的区别在于这样需要找到ai1,bi1a_i1,b_i1ai​1,bi​1下一次出现在哪一天写起来比前一个做法麻烦。E分类讨论 区间rmq有一堆点(p,c)(p,c)(p,c)一些询问每个形如tp,tc,dtp,tc,dtp,tc,d这个询问给每个点一个打分问最小打分是多少打分规则如下p,cp,cp,c维度分别打分规则都是分三段的分段函数一段0一段线性一段上界。两个维度分数加起来就是一个点的最终得分。以ppp为例如果ptpp\lt tpptp那么IpI_pIp​一定是0了不用计算此时看似需要对ptpptpptp的所有点根据ccc和tc,tcdtc,tcdtc,tcd的关系分三类讨论但更简单的做法是直接求出ptpp\lt tpptp里ccc的最小值然后可以把这个最小值带入分段函数O(1)O(1)O(1)算出IcI_cIc​最小值。这是因为这个分段函数是单增的所以找到最小的ccc对应的就是最小的IcI_cIc​。如果ptpp\gt tpptp类似地查询ptpp\gt tpptp的点里的最小ccc带入分段函数。需要注意的是查询可能区间内根本没有点。此时答案应该是infinfinf才不影响答案或显式判断不在此时进行更新。对于ccc也同理进行这两个枚举此时这两个分段函数形成的8种ifelse只有tpptpdtp\lt p\lt tpdtpptpd且tcctcdtc\lt c\lt tcdtcctcd没考虑了这当然可以用支持区间查的数据结构来计算比如线段树或ST表对tpptpdtp\lt p\lt tpdtpptpd查询最小的ccc然后同样带入分段函数计算。但注意到总有答案全局最小pcpcpc区间最小pcpcpc想要让区间最小pcpcpc成为答案这两个不等号必须全部取等那么就有全局最小pcpcpc区间最小pcpcpc可以直接用全局最小来替代这个情况的查询。省去这一步的查询后会发现剩下的查询全是前后缀最小值查询直接用O(V)O(V)O(V)预处理前后缀最值即可无需复杂数据结构。voidsolve(){intn;cinn;vix(n1),y(n1);rep(i,1,n){cinx[i];}rep(i,1,n){ciny[i];}intsuminf;viprex(M,inf),prey(M,inf),sufx(M,inf),sufy(M,inf);rep(i,1,n){summin(sum,x[i]y[i]);prex[y[i]]min(prex[y[i]],x[i]);prey[x[i]]min(prey[x[i]],y[i]);sufx[y[i]]min(sufx[y[i]],x[i]);sufy[x[i]]min(sufy[x[i]],y[i]);}rep(i,1,M-10){prex[i]min(prex[i],prex[i-1]);prey[i]min(prey[i],prey[i-1]);}rep(i,M-10,0){sufx[i]min(sufx[i],sufx[i1]);sufy[i]min(sufy[i],sufy[i1]);}intm;cinm;autocal[](intx,inty,intqx,intqy,intd)-int{if(xinf||yinf)returninf;intres0;if(xqx)resmin(x,qxd);if(yqy)resmin(y,qyd);returnres;};viqx(m1),qy(m1),qd(m1);rep(i,1,m)cinqx[i];rep(i,1,m)cinqy[i];rep(i,1,m)cinqd[i];rep(i,1,m){intxqx[i],yqy[i],dqd[i];intansmin(xy2*d,sum);intmnprey[max(0,x-1)];ansmin(ans,cal(0,mn,x,y,d));mnprex[max(0,y-1)];ansmin(ans,cal(mn,0,x,y,d));mnsufy[min(xd,M)];ansmin(ans,cal(xd,mn,x,y,d));mnsufx[min(yd,M)];ansmin(ans,cal(mn,yd,x,y,d));coutans\n;}}