当前位置: 代码迷 >> 综合 >> 【比赛总结】Codeforce 451 Div2
  详细解决方案

【比赛总结】Codeforce 451 Div2

热度:74   发布时间:2023-09-27 08:35:58.0

A:

B:

给出x,y,n,求xa+by=n的一组a,b的取值,要求a,b均为非负数。

本来直接暴力枚举就可以搞完的事,当场脑子抽了想写EXGCD,浪费时间不说,还WA了一次(没看到均为非负数)。

C:

给出n个人的通讯录,名字相同属于同一个人,每个人的通讯录有m个电话号码,如果一个电话号码为另一个的后缀,则改电话号码无效。
求总人数,以及最终每个人有效电话号码。

本来也是个直接暴力就可以做的题,当时又犯傻写字典树,代码量80行,浪费时间还因为类型开错WA了两次。

D:

有n个闹钟,在[1,m]某个时间响起,如果在连续m个位置有大于等于k个闹钟响起,就会醒来,求不醒来的情况下最少关掉多少闹钟。

贪心水题,从前往后处理时,消除靠后的一定比靠前的优,所以从前往后维护一个长度为m的区间,若加入某个点后,使得区间内闹钟数量大于等于k,就删去当前的点。

E:

有n堆糖果(n为偶数),有两种操作:1,将某颗糖果从A堆移动到B堆,2,在A堆加入一颗糖果,求最终n/2堆的个数为平方数,另外n/2堆的个数为非平方数的最小操作次数。//这是我当时理解的题意

有n堆糖果(n为偶数),有两种操作:1,在A堆删除一颗糖果,2,在A堆加入一颗糖果,求最终n/2堆的个数为平方数,另外n/2堆的个数为非平方数的最小操作次数。//这是我现在理解的题意

这就是我当时二十分钟没想出来的原因。

所以说就成了水题了,处理出给定数组中完全平方数的个数。

如果完全平方数更多:
显然除了0以外,任何一个平方数+1均不是平方数,所以根据这个分成0和非0来统计即可。

如果非完全平方数更多:
将每个值能更改为完全平方数的代价最小的一部分,作为答案。

总结

本场比赛是我NOIP失利以来,第一次比赛,对方法的选择过于死板,没有仔细分析时间复杂度和数据范围,盲目写自以为的正解算法,浪费了大量时间,导致E题没时间完成。不过这也正是我NOIP失利的一大原因,若能看出第二天第二题的极端暴力,却并不会超时(至少cch没超时)的算法,估计失败也不会如此惨痛吧。

  相关解决方案