OCI camp day 1

HYYW1228 · 2024-01-11 20:18:56 · 个人记录

Biridian Forest

为什么对手不走最短路径到终点直接等着呢？玩家到终点的距离必须严格小于对手才能不打架。

正确性：如果中间可以“截胡”，则可以一起到终点。

The Two Routes

直接根据问题建图然后搜就可以了。因为边很多，不如直接用邻接表方便。

Is-A? Has-A? Who Knowz-A?

这是一个传递闭包问题（两点之间的连通性关系），可以直接用floyd-warshall解决, 也可以bfs。后者不知道为啥写挂了，我是在每次query的时候bfs。后来看bfs的解实际上开头爆搜就可以了。

Binary Table (Hard Version)

自己手玩样例可以发现，对于一格2 \times 2的格子，最多四次就可以变换成0。所以\frac{NM}{4} \times 4 = NM一定可以构造。

一种最暴力的写法如下:

这样，变换的操作次数上限为(nm-n-2m) + m-2 + 4 = nm-n-m+2 < nm, (n, m \geq 2)。

缩短代码的关键在于如何写好最终的特判以及取反函数。

代码

Hiring Staffs

• 先考虑k = 1的基本情形:

• 容易想到有一个循环节在n+m+1，因为m \leq n。数据很小，直接模拟并找到循环节就好了。有一些实现上的细节：必须有人给钥匙，以及与其关联的员工分配问题。如果某一天没有人了，恰好需要一个人从上一天把钥匙带过来（可以知道在这一天前k人已经满足），然后把剩余的人补上就行，补到今天这一天。

• 如果循环只判断[1, n+m]每天的情况，注意有可能在n+m+1天任然需要有人带钥匙。

Begginer's Zelda

很直觉的想到每次和“根”合并，但是什么根呢？一种树枝较少的方式就是以合并到直径上，每次最多可以减少2叶子。但是怎么数叶子方便呢？直接找只有一度的点就好。除了特殊情况当x = 1时(题目保证至少两个点，所以不需要写)，其余情况答案都是\lfloor \frac{x+1}{2} \rfloor。