2022-2023 ICPC, NERC, Northern Eurasia Onsite 题解

瞎胡几个题。只写了一道。被队友带飞。

持续更新（？）中。

F. Football

两队踢了场比赛，告诉你其中一队赢输球数，问最少几场平局，并给出方案。

和特判一下。其他情况容易构造出平局数为的方案。

有个方块堆成的塔，每一块上写有数字，数字各不相同。一次操作可以将一个塔从中间分成两个，或者将一个塔放到另一个塔的上面。现在需要用所有方块叠出数字从上到下递增的塔。问总操作次数最小的情况下需要进行两种操作分别几次。

贪心，把每个塔拆开再合并回去。稍加计算即可。

给定排列，构造两个排列使得且。或报告无解。

发现若确定中间状态就可以确定排列和。而为了满足限制，中间状态需要满足。

必定无解。各有一种情况无解。

对于剩下的情况，考虑对值和位置建出二分图。每个位置有不超过两个限制，因此每个点度数。

根据定理可以证明，此时一定有解。

感性理解，这样的排列有很多。直接随即可。

交互，每次可以询问第位上的值。在不超过次询问内找出。。

预处理出到的阶乘，每次询问信息熵最大的即可。需要手打出第一层的决策树。

给定，构造一张个点的无向简单连通图使得图上的点恰好有种不同度数。

点度数最大为，所以显然无解。尝试直接构造出的情况。

可以构造两个度数分别为和的点两个点之间连边。剩下的就是的子问题。

对于，在度数为的点外再接一条链即可。

需要特判。

有一棵二叉树，每个节点只有或个儿子。给定这棵树的个随机访问的中序遍历，还原这棵树的结构，或报告无解。。

考虑如何找到根。对于根，中序遍历的左右两侧分别是其两棵子树，其点集在的中序遍历中应该完全相同。维护集合哈希值即可维护。

找到根之后，对左右两半递归下去做就行了。

的网格，有些位置是障碍。问有多少种将两个空格变成障碍的方式，使得无法使用的骨牌将网格填满。保证初始状态能被填满。输出方案数向取的结果。。

典中典。

经典结论：黑白网格数相同是可以被填充的必要条件。因此，同时填充两个黑格或白格之后一定无解。

此时若方案数仍，则有空格数。

再考虑经典做法。对相邻的黑格和白格连边，有完美匹配是有解的充要条件。

下面设二分图左部和右部各有个结点。由于初始状态有解，该二分图有完美匹配。

考虑去掉左部的每一个点。此时的最大匹配一定是。若右部的某一个点必定在最大匹配上，那么删去这个点后不存在完美匹配。

之后的做法就和二分图博弈差不多了。网络流，从汇点沿边跑 dfs，搜到的点一定在最大匹配上。

接下来的题就没有场切了。

的网格中有一个点是宝藏。交互，每次可以访问一个点，可以得到“找到了！”或者与上一个点相比到宝藏的距离是更近还是更远。你并不懂当地语言，不知道回答到底是哪一种，但可以分辨“找到了！”。你需要在次询问内找到宝藏。

先考虑知道更近还是更远应该怎么做。可以每次询问一个形，这样就可以使横纵坐标分别缩小一半。

再考虑如何得到更近更远所对应的字符串。

很蠢的事情是，询问就能找到哪个是更远。因为几乎一定更远，除非答案是，或者答案在，而这种情况会收到两个相同的答复。Link

然后就做完了。询问次数卡的很死。