Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1年前

05/30
20:51
bfs 乱搞 暴力 模拟

Codeforces Round #354 (Div. 2)

比赛传送门:戳我QAQ

 

Problems - Codeforces_副本

A题传送门:戳我QAQ

题目大意:

给你一个1-n的排列,可以任意调换两个数的位置且只能调换一次,求1和n的最大距离。

题解:

对于1和n,要么把右边的那个调到最右边,要么把左边的那个调到最左边,比较一下即可。

 

 

Problems - Codeforces_副本

B题传送门:戳我QAQ

题目大意:

有n行杯子,第i行有i个杯子,每个杯子的容量为1。设f[i,j]为第i行的第j个杯子。每一秒钟,f[1,1]里面的水会增加1,如果一个杯子f[i,j]里面的水超过1.那么它超出1的水就会平均分成2份流到f[i+1,j]和f[i+1,j+1]中,且我们认为流动的过程是不需要花费时间的。问t秒钟后有多少个杯子是满的。

题解:

因为数据范围比较小,所以我们可以对于每一秒直接枚举所有杯子的状态,最后统计一遍,时间复杂度O(n^2*t)。

 

Problems - Codeforces_副本

C题传送门:戳我QAQ

题目大意:

给你一个长度为n的字符串,字符要么是a要么是b,最多允许更改k个字符,问更改后最长连续相同子串的长度是多少。

题解:

先假设最后连续的子串都是a,那么设f[i]为第i个b的位置,则修改的b肯定是f[i]到f[i+k-1]中的所有b,则最后的子串长度为f[i+k]-f[i-1],枚举这个i比较一下即可,如果要修改的总数小于等于k的话,则答案就是n。对于b也同样考虑一下就行了。时间复杂度O(n)

 

Problems - Codeforces_副本

D题传送门:戳我QAQ

题目大意:

给你一个n*m的网格图,让你从(st,yt)走到(xm,ym),然后每个格子有几扇门,表示可以走到哪一个和它相邻的格子。(具体的直接看题吧实在懒得翻)每个单位时间可以做两件事:1是走到一个相邻的格子(当且仅当这两个格子都有可以直接通向对方的门)2是把所有的格子顺时针旋转90度。问最少时间,如果无法走到输出-1

题解:

直接设f[i,j,k]为走到(i,j)的格子且当时旋转了k*90度的最小时间,bfs即可

(ps:实现的时候需要一点小技巧,否则代码会非常丑...)

 

Problems - Codeforces_副本

E题传送门:戳我QAQ

题目大意:

已知一个n次多项式P(x),一开始各项的系数都不确定,机器人和人类轮流操作,机器人先操作。每次操作可以任选一个未知的系数并给它一个值。现在给出中间状态,第i行为i-1次项的系数,?为未知,问是否人类有把握使P(x)=0存在一个解为x=k(所有项的系数可以是任意实数,甚至为0)

题解:

1、当k=0时,如果常数项已知,那么如果常数项为0则为yes,否则为no。如果常数项未知,那么如果下次是人类操作则为yes,机器人操作则为no

2、当k<>0时,如果所有操作都已知,那么直接判断即可。如果P(k)=0,那么对于任意非0整数x,P(k)%x=0,那么随便选几个质数作为模数看看是否为0,有一个不为0则为no。如果还有未知的操作,对于最后一次操作,一定存在且只存在一个值使得P(k)=0(相当与最后解一个一元一次方程),如果最后一步是人类操作,那么只要填上这个值,所以是yes;如果最后一步是机器人操作,那么只要不填这个值,就是no

 

Codeforces Round #354 (Div. 2)