Codeforces Round #372 +#373 部分题解

2016年10月5日2990

用了两场比赛上Div 1感觉自己好腊鸡的说。。。以下是这两场比赛的部分题解(不得不说有个黄学长来抱大腿还是非常爽的)

Round #372 :

Div 2 A:Crazy Computer

题意:给定N个输入和一个时间长度M,每次输入屏幕上增加一个字符,若两个输入间隔大于M则屏幕上的字符会被清空,问结束时屏幕上还有多少个字符

直接模拟没有什么好说的

代码:

 Div 2 B:Complete the Word

题意:给定一个字符串,其中某些字符未知,要求给出一个可能的字符串,使得存在一个包含26个大写字母的长度为26的连续子串

这题也是直接乱搞吧大概,我的思路就是统计每个子串中是否有重复,没有就说明合理然后随便构造一个答案就行了

代码:

Div 2 C and Div 1 A:Plus and Square Root

题意:给定一个数和两个操作,一个操作为+k,另一个操作为开根号然后k=k+1,初始时数为1,k=1,求达到k=n+1时的操作数

考虑构造一个可行方案,设执行开方操作后那个数为t,那么有$t=mk,m\in \mathbb N$(若不满足则下一次无法开方)同时考虑开方操作前有$t^2=n(k-1),n \in \mathbb N$所以令$t=k(k-1)$ 即可

代码:

Div 2 D and Div 1 B:Complete The Graph

题意:给定一张图,其中某些边的长度未知,求是否存在一种方案,使得最短路为L

先分层建图,求出经过k条未知边的最短路,然后从经过未知边数从小到大开始处理,直接构造出经过k条未知边,最短路为L的路径,可以得出,若无法构造出小于k条未知边的最短路为L的路径,那么该构造方式不会出现更短的路径。

这道题在考试时没秒出来,考完才发现写成大根堆+构图构太大MLE了囧。。。(不然说不定一场DIV 1了哼~)

代码:

Round #373 :

这一场好像数据出了好多错结果Div 1 unrated了。。。。不过还好Div 2没死然后自己就上Div 1辣(开心),黄学长也因此逃过了掉rate的命运。。。

Div 2 A:Vitya in the Countryside

题意:给定一个月亮阴晴圆缺的序列,求判断接下来月亮是变圆还是变缺

直接判断序列是上升还是下降即可,注意0和15即可

代码:

Div 2 B:Anatoly and Cockroaches

题意:给定一串珠子,有两种操作:给一个珠子涂色,交换2个珠子位置,求使这串珠子黑白相间的最小操作

分黑白黑白黑和白黑白黑白考虑咯,然后每次只判断奇位或偶位,看是不是那种颜色,如果不是再考虑要涂色还是交换(有点口胡写的代码也很挫。。。)

代码:

Div 2 C and Div 1 A Efim and Strange Grade

题意:给定一个浮点数,有n次四舍五入的机会,求获得最大的数大小

从高位到低位找到第一个大于5的数位进位即可,主要注意输出格式和进位问题就没了

代码:

Div 2 D and Div 1 B

虽然是一道错题不过解法还是挺机智的

题意:有N个复印机,每个复印机复印文件要ti秒,现在有m个任务,每个任务要求需要x个副本,求复印所需要的最小时间

先把  每个复印机投入工作的时间计算出来记为si,然后二分时间T,那么时间T内的副本数就为$\sum_{i=1}^n \lfloor \frac{T-si}{ti} \rfloor$但因为复印机数太多所以还是过不了,考虑到$1<=ti<=1000$ 那么就把复印时间相同的复印机放在一起处理

Div 2 E and Div 1 C Sasha and Array

题意:给定一个序列,支持区间加法和区间求其斐波那契数之和

线段树+矩阵乘法裸题,注意点优化就行了,例如lazy直接存斐波那契数的矩阵什么的就没问题了

代码:

 

%d 博主赞过: