CSP-S 赛后总结

https://i.loli.net/2020/11/07/UCIc84ZM7XfSTks.jpg

考试时间2:30~6:30
蒟蒻的题解忽略就好QAQ是等老年痴呆了以后给自己看的
大佬就当看个笑话吧=_=
题目地址(民间数据,11.16之前有效)

T1

儒略历恶心到我了,刚看题干就跳了,先去看第二题,在大概4:30才回来再看.

事实证明我跳题的决策是对的,第二题很简单,调一调就过了大样例

T1实际上就是给儒略日让你用程序转成儒略历和格里历.我当时用的是一天一天模拟法但是没调出来,

到公元后就日期错误,保守估计0~20pts

解法一 : 公式法

儒略日转儒略历和格里历是有公式的.

解法二: 暴力法(80pts)

按年份-月份-日期的顺序类似倍增的思想暴力枚举
提前判断每跳一年/每跳一月/每跳一日所跳过的儒略日(即所给r)
对儒略历中公元0年特判且判断闰年时对年份先减一再判断被4整除
同时可以先算出到儒略历和格里历分界点需要的儒略日,对之前和之后分别处理
又因为是多组数据还可以先对输入数据从小到大排序然后一次暴力处理完,优化效果显著

解法三: 二分法(100pts)

此处已鸽

T2

这道题很简单,题干很长但是说白了就是让你统计一遍饲料清单再反推出能养的动物总数减去已经养
了的动物总数$n$

显然能养的动物总数为从可取的所有位(编号可以为1的位)中随机取随机个最后的可能总数

我们把这个可取的位数设为$kk$

因为每一位都可以选择为1或者0即取或不取 , 每一位取或不取相互独立 , 所以由乘法原理能养的动物总数为$2^{kk}$

我的方法是先遍历,用一个$ci$数组(bool)(第i位表示编号为i的饲料是否在清单里)记录下来买了的饲料的编号

然后再遍历一遍用$ci$反推出养的动物「编号可以为1的位的数量」$kk$

那么最后的答案就是$$2^{kk}-n$$

我具体在程序中使用的办法是记录允许养的动物中「编号不可以为1的位」的数量,因为这个容易实现,只需要遇到一个「该位需要的饲料不存在」的判断就可以确定这一位不能取1从而让统计变量$jianqu+=1$.

最后统计出「编号不可以为1的位」的数量$jianqu$,则有$kk=k-jianqu$

最后的答案就是$$2^{k-jianqu}-n$$

这里减去n是因为求的是「能额外养的动物数量」

而减去的n个动物中和编号不可取的动物交集为空因此容斥方面不会计重也就是说不会多减动物(想想为什么)

求2的kk次幂可以用位运算加速

但是最后一个数据很毒瘤,即使用了ull还是会超,出题人蒸鹅心hetui

T3

这道题没怎么看,但是要在程序中实现函数调用总觉得会很难因此在最后二十分钟输出原数组骗分了

T4

这道题蛇少的情况下只需要贪心的看第一条蛇的决策 , 3条蛇的情况要么全吃要么不吃

我做到这题的时候只剩下四五十分钟 , 于是匆匆忙忙骗了两个点大概20pts吧

实际上蛇多的情况下还需要考虑第一条蛇吃了几条蛇之后体力到了中间但是到最后也没被吃掉的情况等 , 知乎上看到有人用回溯法做 , 但是我懒得想了

所以这坑下次再填吧

总结

总的来说CSP的趋势是越来越简单了,考察暴力和搜索的频率也越来越高,难道真应了那句”暴力出奇迹,打表出省一,暴搜挂着机,骗分过样例”吗

个人感觉现在考察的更多是对一个问题找出最快速最划算的解决方法,而不是仅仅追求单一的某种算法,比方说T1其实如果记过公式很快就能写出来,考察的更多是对问题本身的分析和对问题本质的洞察力

作为半退役选手的我,是不是应该改变刷题策略了呢……