Educational Codeforces Round 17 做题记录

比赛的时候雪崩,幸好没记rating。。。。

A. k-th divisor

题意:求出n()的第k()个因子是什么。

反正CF是单组测试数据进行测试,所以只会sqrt(n)的暴力枚举因子。不知道有没有什么高端的方法。。。

B. USB vs. PS/2

题意:直接看题面吧,不想说了。

排个序模拟一下就做完了。

C. Two strings

题意:给出两个字符串a和b,需要在b内删除最少的连续的字符(也就是说只能删一段区间)让b变成a这个字符串的子序列。b可以被删成空串。

我们只能在b中删除一个区间,所以剩下的一定是前缀和后缀(当然这个前缀或后缀可能为空,比赛的时候这里没写清楚GG)。然后我们暴力的求出对于每个B的前缀,A中包含这个前缀作为子序列的最前面的位置a[i]。然后求出对于每个B的后缀,A中包含这个后缀作为子序列的最后面的位置b[i]。这样的话这些信息可以从前面扫一遍,从后面再扫一遍得到。

然后对于每个B的位置i,找到一个b的后缀j,使得a[i]<b[j],而且j越靠前越好。那么这个可以无脑二分得到,弱写尺取法写懵逼了,直接就二分了。

D. Maximum path

题意:给出一个3*n的矩阵,让你求出从左上角走到右下角的最大权值。一个格子四个方向都可以走,但是不可以走过已经走过的格子。

不会插头dp。。。

这个矩阵只有3行,那么他就只可能向左走一个格子,如果走两个或者以上,那么我们一定可以找到一种方法来代替。比如换成从上到下,就像这样,我们可以用红线的走法代替黑线达到同样的效果。

这个性质非常有用,我们可以设为走到第i列第j行时的最大值,然后相邻两列之间的6个格子转移。但是这些都是向上或者向右向下的转移方式。但是因为我们发现向左最多走一个格子,那么包含向左走的转移方式只能是这两种。

dp转移过程详见代码吧。。。。

 

发表评论

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