0910模拟

0910模拟

T1题解:
身为熟悉的括号匹配……,基本上都只写了个暴力拿了60分……
主要还是考虑的太局限了,可能是因为只记得括号匹配是用栈吧……
如果直接分析题意而不是带有主观思想来说,那么我们肯定会处理当前区间里有多少个合法的括号匹配,也就是我们所说的n^2暴力,怎么继续转变呢
对于[l,r]来说,我们就是[1,r]-[1,l-1]的已经合法的括号数,所以这在我们求[1,n]的过程中就已经分步实现了,那么我们只要在考虑问题的时候再全面变通一些,就会发现离线树状数组处理即可完成目标,然而如果想不到离线就会很糟糕
思维还是太窄了,可能是见得题太少?
还要多多熟悉树状数组啊

AC代码:

T2题解:
本来以为非常简单的贪心……然后因为一些细节的失误gg了……
首先,我们肯定知道先贪心出来人数cnt,那么现在的最优方案一定是用最便宜的cnt个数去复活cnt个人,对于要复活的人来说,肯定是在能用这个方法中奖励金最多的人来复活(考试的时候想得太简单,觉得肯定是用最便宜的cnt个人复活k最多的3个人……),那么我们只要造一个大根堆来维护就行了
对细节的掌握不是很好,很容易就觉得自己想得很对然后没有更深一步,这很关键……
对数据结构的灵活应用也不怎么滴

AC代码:

T3题解:
一度认为自己写的是巨对的正解……
错误解法(其实删的过程没说错……只是……):
首先我们优先删除1个p中间夹杂的其他字母,这样ans就会慢慢增加,然后再删除相邻两个p之间隔着的字母,这时ans保持最大值不变,然后再依次删去每一个p,但是这样的话每一个p的分解太过清晰,回导致ababa找aba这种字符串无法辨识,那么这个想法就被否了
所以我们其实应该很容易就想到这是一道dp,因为当举出ababa这种反例之后,我们就会考虑对于每一个字母,删还是不删对于答案的影响,所以dp转移方程应运而生:
//dp[i][j]表示前i个字符删j个的最多p
如果不删:
dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
如果删了:
dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]);
这显然不能满足所有情况,所以我们要处理一个对于位置i来说,往后删j个字符可以多出来一个p的这样一个w[i],所以
dp[i+w[i]][j+w[i]-lp]=max(dp[i][j]+1,dp[i+w[i]][j+w[i]-lp]);
这样一来考虑就周到了
//思维幼稚,考虑问题不周全,dp思想不贯彻

AC代码:

0

发表评论

电子邮件地址不会被公开。 必填项已用*标注