Codeforces Gym

Rank: 14/109

Pro: 8/8/13

给出一个$6\times 6$的棋盘,上面散布着有长度为2或3的一些玩具车.每个车为横向或者纵向放置.游戏规则和华容道比较像,问能否在10步数内将某辆车移出棋盘.

DFS爆搜+玄学剪枝

直接深搜,记录下当前棋盘的状态,和每辆车的车头的坐标,车辆长度,横纵情况.然后根据车辆移动的情况搜就行了.

中间加了一些奇奇怪怪的剪枝,同时用了一个感觉不怎么靠谱的Hash函数来记忆化棋盘,没想到居然过了.

签到题

签到题

给出一段长度为$n$的整数序列,$1 \leq n <2000$.并给出了一段求$(r-l+1)\sum_{i=l}^{r}a_{i}$的最大值的贪心代码.现在要求构造出一段这样的序列,要求正确的最大值比给出代码求出的最大值恰好大$k$.输出任意一种方案.

简单构造.

直接构造长度为1999的序列.令序列的第一位为$-1$,后面全都是非负数.这样贪心找到的子序列长度就是1998,正解找到的子序列长度是1999.设后面这些数的和为$x$.可以得到如下方程:

$$1999(x-1)-1998x=k$$

化简得,$x=k+1999$

然后把$x$随便填充到后面的空位中即可.

给出一个数$n$.求最大的$a$,使得存在$b$,满足$\frac{1}{n}=\frac{1}{a \oplus b}+\frac{1}{b}$.中间的运算符为异或.

有趣的结论题.$b=n+1$.然后反解出$a$就行了.

但是并不会证明

给出$m$个集合,每个集合中有一些正整数.现在求它的一个最小的集合子集,使得这些集合的并集中恰好包含了$n$个数.

二进制暴力枚举,拿Bitset直接通过或运算来计算并集的情况.实际运行的速度快的飞起.

签到题

给出平面上的一堆点,要求从其中找出四个点,使得这四个点围成的多边形的面积最大.(可能有重合的情况)

旋转卡壳+枚举

构造出凸包后,枚举这个四边形的一条直径,然后类似旋转卡壳那样找面积最大的情况.需要卡一下常数.

整场比赛发挥还可以,智商基本上持续在线.比如H题直接猜出了结论节省了很多时间.当然中间还是犯了一些错误,M题开场读完后以为是一个广义Lucas定理,甩给队友持续研究了半天.到最后快结束的时候才发现题目中的取模是重新定义过的,并不是板子题.导致前期开题时人手有些不够,切签到题的速度有些慢.中间推E题构造式子的时候也有些慢.A题在RE了一发之后,一直以为是递归崩栈了,改了几次无果之后才发现是数组越界,多吃了很多次罚时.最后的时间全部用来推F题,感觉是一个SPFA实数费用流模型,但是直到最后也没有完成对模型的修正,正好回头找一队问一下做法.

别人的520用来秀恩爱,我的520用来训练,我们都度过了充实的一天