Before

听说有些学校能抵机试,准备参加三月份的CSP。
仅含题解,代码详见github喜欢的话点个star

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。

201403-1 相反数

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