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没超时)的算法,估计失败也不会如此惨痛吧。