首页 > 其他分享 >Educational Codeforces Round 127 (Rated for Div. 2)

Educational Codeforces Round 127 (Rated for Div. 2)

时间:2023-04-24 16:47:16浏览次数:53  
标签:Educational Rated 题目 Codeforces 同构 127 Div

题目链接

D

核心思路

首先挖掘下操作的性质吧:

x>1&&x+3<10:
1 x x+1 x+2 x+3 10
我们可以发现这样子好像对于我们的结果是没有影响的,答案还是9.
所以这个性质就挖掘出来了啊,只要我们把一段连续的插入到对应的区间里面就好了。也就是只要这个区间的左端点小于插入连续的数的最小值,右端点大于插入的连续的数的最大值。那么肯定是最优的。因为不会对我们的答案产生贡献啊。


我们可以知道的是我们插入的这一段数的最小值是1,最大值是x。

所以我们就看原序列里面的mn和mx和他们的情况。其实如果\(mn>1||mx<x\).那么其实对于答案的贡献就是插入1和插入x。

我们线性扫描看哪个位置插入1or x 对于我们的答案的影响最小就好了。

E

核心思路

这个题目确实挺不错的,其实可以理解为就是一个树形dp。从底往上跟新下答案就好了。

但是这里有个蛋疼的地方就是有可能我们的左右子树是同构,什么是同构呢,因为\(f[u]表示的以u做为子树包含的前序串的个数\)。

正常来说:\(f[u]=f[ls(u)]*f[rs(u)]*2\).但是如果是同构那么交换就没有意义,所以也就是不需要乘2.

那么怎么判断同构呢,其实很简单。我们只需要求出来以u作为子树的最小字典序就好了。

所以整个题目也就做出来了,其实也还好。不是特别的困难。

标签:Educational,Rated,题目,Codeforces,同构,127,Div
From: https://www.cnblogs.com/xyh-hnust666/p/17350025.html

相关文章

  • Codeforces Beta Round 96 (Div. 1) -- C. Logo Turtle (dp,记忆化搜索)
    记忆化搜索就是暴力,多一步优化,走过的路别走了。说实话,可能是数据水了,居然能过。constintN=510;strings;intn,ans;boolst[501][501][2][50];voiddfs(intx,intidx,intdir,intk){ if(st[x][idx][dir][k])return; st[x][idx][dir][k]=1;//走过的路不走......
  • Educational Codeforces Round 147 (A-D)
    A.Matching橘子熊:这题太简单了我不想写题面Description给定给一个带问号的字符串,求有多少种可能的数字Input多次询问,一次一个字符串Output对于每次询问,输出可能的数字的总数数据范围与约定2e5次询问,单词询问不超过5个字符思路主要思路签到题大部分情况下,一个......
  • Educational Codeforces Round 39 (Rated for Div. 2) -- D. Timetable (DP)
    写得很折磨人,每次dp都写个一个多小时,写出来明明觉得不难.题目大意:可以进行K次操作,把删除1,进行k次操作后每行第一个1和最后一个1的位置相减的绝对值加1得到的结果最小。做法:每次肯定是要从左删或者从右边删,然后顺着这个思路,先把每行的进行小于等于k次操作时,每行最小......
  • codeforces 559C Gerald and Giant Chess(dp+组合数学)
    题目链接:codeforces559C题目大意:给出一个h*r的矩阵,从左上角走到右下角,中间有一些点不能经过,问不同的路径有多少种?题目分析:首先我们考虑一个n*m的矩阵,从左上角只能向右或向下走能走到右下角的方案数,也就是C(n+m,n),就是一共要走n+m次,选出n次横着走。那么我们定义dp[i]表示在前不经......
  • codeforces 545C C. Woodcutters(dp+二分)
    题目链接:codeforces545C题目大意:给出一些树的位置和高度,每棵树可以砍倒,覆盖[xi−hi,xi]或者覆盖[xi,xi+hi],或者不砍倒,问最多砍倒多少棵树?题目分析:我们记录dp[i]表示选取到i棵树的时候用的最短的区间长度。每次枚举每棵树,二分到最大的不超过当前树位置的个数,然后利用当前树的信息......
  • codeforces 4D D. Mysterious Present(dp)
    题目连接:codeforces4D题目大意:给出n个信封,这n个信封有长和宽,给出卡片的尺寸,求取能够装入卡片的最长的序列,序列满足后一个的长和宽一定大于前一个,求最长的这个序列的长度,并且给出一组可行解。题目分析:一看这种题目就是dp的题目,状态定义dp[i]为以i结尾的序列的最大的长度,并且利用一......
  • codeforces 2B B. The least round way(dp+数论)
    题目链接:codeforces2B题目大意:给出一个n*n的矩阵,从左上角走到右下角,只能向右或向下走,问路径上的数之积末尾0最少的方案是什么。题目分析:首先我们要做两个预处理,处理出每个位置上的数包含多少个2的质因子和多少个5这个质因子然后我们统计路径上弄到最少的2的方案数和最少的5的方案......
  • codeforces 126B B. Password(kmp+dp)
    题目链接:codeforces126B题目大意:给出一个字符串,找出一个子串既是它的前缀,也是它的后缀,还是一个非后缀也非前缀的子串。题目分析:本来挺简单的一个题,最开始想复杂了,还用了后缀数组,醉了。这个题主要用的是kmp的next数组,首先我们要了解next数组的定义,next[i]表示以i为末尾的子串的后缀......
  • codeforces 118D D. Caesar's Legions(dp)
    题目链接:codeforces118D题目大意:给出n1个1,n2个2,给出k1和k2代表连续的1和2的最大长度,问能够构造的合法的不同串的数量。题目分析:能够递推,所以想到能够利用dp做。首先我们定义状态,dp[i][j][k][2]代表以1或2结尾,结尾相同的元素的数量为k,1的总数是j的当前序列长度为i的串的数量。首先......
  • codeforces 264B B. Good Sequences(dp+数论)
    题目链接:codeforces264B题目大意:给出n个数,利用这n个数构造一个好的序列,好的序列是单调增的,而且序列中相邻的两个元素都不互质,问最长的好序列的长度是多少。题目分析:首先我们定义状态dp[i]表示当前的数进行构造的序列末尾的数的质因数包含i的时候的最长的情况。然后我们从小到大枚......