Before

听说考得好写在简历里很不错,准备参加三月份的CSP。
仅含题解,代码详见github喜欢的话点个star

201712-1 最小差值

sb-t。随便暴力一下。

201712-2 游戏

sb-t。BUT,读题的时候没读到或其末位数(即数的个位)为k,直接当约瑟夫做了。。。
最垃圾的做法就是拿数组标记一下,手动控制环。(没错我就是这么做的,写起来还是很快的

201712-3 Crontab

还没读完题头都大了,写完第4题的第一稿才开始动手做。题目虽然很长,题意其实还是挺清晰的。
核心算法就是模拟,用了一次蔡勒公式算出星期几。输入处理简单来讲的话就是,先按‘ ’(空格)split,每段再按‘,’(逗号)split,每段再按‘-’(减号)split,然后再转换成非负整数标记到这个$crontab$对应的布尔数组,比如周一周二那就是在一周的数组中标记$1$和$2$,详见代码。最后从起始到终止一分钟一分钟往上加,每一分钟都枚举$n$个$crontab$判断一下是否满足。算了一下极限复杂度稍微有点方,不过看了一下输出不超过10000行,应该不会TLE。
思考加打代码估计有一个多小时。。。最后交上去一看,85分,难道还是TLE了?结果点进去一看是WA,有点懵逼。又读了一遍题,还是没啥发现。查了查别人代码发现好像英文缩写不区分大小写,然后回到题目里一看,中间有一句确实写着,唉。。。

201712-4 行车路线

ps. 201712-4.cpp是60分代码,201712-4S.cpp是满分代码。
其实核心思想跟之前是差不多的。首先因为小道的费用(和的平方)没有可加性,所以就要把小道全都做成$tp$(传送卷轴):启动$tp$以后可以花费一定的费用从一个点传送到另一个点。其次为了保证小道的费用不可加,要限制$tp$不能连续使用,连续使用时费用缩水($1^2+1^2<(1+1)^2$)。
具体实现是:首先用$Floyd$求出只用小道的任意点对间的距离,把这些距离的平方作为$tp$的费用存下来。然后用$SPFA$求单源最短路,分别用两个数组记录$tp$过来的($dis1$)和从大道过来的($dis0$),对于边$u\rightarrow v$,$tp$到$u$的不能再通过$tp$到$v$,其它的不作限制。最后输出$min(dis0(n),dis1(n))$即可。
ps. $Floyd+SPFA$有风险,一点不考虑常数优化的话交上去只有50分,比$dijkstra$乱搞还低。

201712-5 商路(60分)

没剩太多时间,$n^2$直接上,小数据一分没丢。yes!

201712 总结

最近的一场,比较真实地模拟了一下(最后才一起提交),结果才320分,5个题第2题最低,好SB啊。。。

  1. 仔细读题非常重要!第2题读对可以多70分,第3题完全读对可以多15分,这样勉强可以上400
  2. 想不到正解要快速把握部分分。从中学开始就喜欢比赛时先想正解,但是水平又不太行,经常会花大把时间做无用功。第4题大概改写了两三遍,如果一开始就想着先按60分的写,第2/5题分配到的时间就会再多一点。时间一多,分数就有上涨的可能,特别是第2题我还看着$k$的数据范围奇怪了一会儿,最后还是没发现那句话。。。

这两点说起来容易,其实还是挺有难度的,看来要多加训练了。。。

=========UPDATE=========
好像认证是四个小时,我一直当三个小时练的,应该不会时间太吃紧了。。。

201709-1 打酱油

sb-t。随便贪心一下。

201709-2 公共钥匙盒

小模拟,核心就是给所有事件排序。

201709-3 JSON查询

中等模拟,除了基本的split以外,涉及到了括号匹配的知识,只有同一层的括号它们才有可能组成一个JSON对象。
具体来讲,可以一边dfs一边建树,但是传个字符串递归总是很慢的,我的习惯是传一下左右边界。建树的节点都是整数标识,再用额外的数组存一下key-value。然后查询的时候一层一层地查,每层有以下几种情况:

  1. 子节点没有对应的串,一定返回“NOTEXIST”
  2. 子节点有对应的串,查询串没有下一层,要么“STRING”要么“OBJECT”
  3. 子节点有对应的串且是对象,查询串有下一层,继续递归
  4. 子节点有对应的串且是字符串,查询串有下一层,返回“NOTEXIST”

手动处理累手不累脑子

201709-4 通信网络

刚读完懵逼了,写了一大堆乱七八糟的。。。
其实就是原图和反图bfs一下,然后可达点取个并集,是全集就给答案加一。

201709-5 除法

50:暴力,每次缩小和求和都扫一遍
100:查到几个树状数组的做法,感觉复杂度完全不对,代码放了,正解待定。

201709 总结

前4题检查了一遍,第5题打了个暴力,然后啥都不想干就交了,毕竟不是真实考试。。。好在前4题都过了,第5题暴力也很成功。
第4题大改,检查很有必要。

201403-1 相反数

不会重复,直接取绝对值找出现两次的。

201312-1 出现次数最多的数

sb-t。计数随便扫一下。

201312-2 ISBN号码

sb-t。随便模拟一下。

201312-3 最大的矩形

easy mode:枚举左端点,枚举右端点,顺便维护最小值,乘一下更新一下。
medium mode:考虑枚举一个点,并使该点就是区间中最低的,那么就是要求向左向右第一个低于当前点的。这件事情可以用单调栈来搞,正反各一遍。

201312-4 有趣的数

一眼看上去想搜索,但是仔细一想。。。是个数学题,稍微懵逼了一会儿,还是要慢慢来,列列式子。
因为0都在1之前,也就是说最后一个0在第一个1之前,那么它们可以看作一个整体。又因为每个数字至少出线一次,所以第一个一定是0。23同理。
设0和1的总位数是$x$,那么首先要在$n$位中选出$x$位,又因为整个串的第一位不能是0,所以应该是$n-1$位,即$C_{n-1}^{x}$。剩下的$n-x$位分给23。然后在这x位中,只要选一个位置断开,前面是0后面是1即可。枚举最末的0,除了不能在最后都可以(必须有1)。23同理。所以答案等于$C_{n-1}^{x} C_{x-1}^{1} C_{n-x-1}^{1},2 \le x \le n-2$。$n$小于等于1000,阶乘打表或者组合数打表,随便搞搞。

201312-5 I’m stuck!

70:我以为$50^4$肯定能过的。。。直接写了个先起点bfs再每个格子bfs的。。。TLE
100:可以直接连边在图上和反图上搜。但是不太想重写,所以加了一个反向搜的函数,注意反向的时候判断的是要到的那个格子的连通方向。

201312 总结

作为全系列第一场,非常简单,甚至不需要什么算法知识就能ak。