XX Open Cup named after E.V. Pankratiev. Grand Prix of Korea, Division 1.

Problem A

Solved by Kilo_5723. 00:14 (+)

题意：给出一个仅含 $6,7,8,9$ 数字的矩阵，求出要使矩阵中心对成，需要将多少个数字旋转 $180^\circ$。

题解：找到每个数的对称位置，判断旋转多少次能让这两个位置中心对称。特判中心位置，如果不是 $8$ 就无解。

Problem B

Unsolved.

Problem C

Unsolved.

Problem D

Unsolved.

Problem E

Unsolved.

Problem F

Solved by Xiejiadong. 04:40 (+10)

题意：每次有新的团队入住的时候，有两种情况：

• 住客有无数个，那么所有住在 $x$ 房间的人移到 $2x$ ，新来的在奇数房间入住；
• 住客有 $k$ 个，所有人向后挪出 $k$ 个空房间。

现在要求每个团队里某一个人在的房间以及房间里的人属于的团队。

题解：对于每个团队里的人可以发现所有人的间隔是相同的。

而对于无数个人输入，相当于间隔 *2 ，其实坐标 *2 （起始坐标是 $0$ 的话不变）。

对于询问房间里的人属于的团队，我们可以用无穷多的次数将团队分割开来。

这样对于分割开来的每一部分有限人数的团队一定在最开头部分，可以通过前缀和二分得到。如果属于后半部分的房间：

• 是奇数房间，一定是无穷的那个团队的；
• 否则编号一定 *2 了，那么 /2 继续做这个问题。

显然最多只需要做这样的 $30$ 次。

需要特别处理 $0$ 号房间的问题。

Problem G

Solved by Kilo_5723. 00:42 (+)

题意：给出一张有向带权图，边权不会重复，求出起点到终点字典序最小的路径。

题解：去除图中所有无法到达终点的点之后从起点出发，每次贪心走边权最小的边就是正解。如果走到了已经经过的点，说明路径无限长。

Problem H

Solved by Weaver_zhu. 00:28 (+)

题意：给两个排列，要求最少交换第一个排列的相邻元素的情况下使得各个元素只差的绝对值之和最大，求最小交换次数

题解：让小的那一半和大的那一半配上就好了，奇数偶数分一下情况

Problem I

Unsolved.

Problem J

Upsolved by Kilo_5723, Weaver_zhu.

题意：给出 $n$ 个区间，每个区间有权值，区间之间只可能互相包含或者不相交，对于 $1 \sim n$ 中的每个 $k$，选出权值最大的区间集，使得每一个位置至多被 $k$ 个区间覆盖。

题解：由于区间之间不存在相交的情况，因此可以将区间改写成树的形式，其中父节点的区间包含子节点的区间。

我们可以对每棵子树维护一个降序序列，表示新增一次区间覆盖能增加的最大权值。显然兄弟节点的区间可以将对应位置相加，而父子节点相当于把父节点的权值插入全部子节点对应序列相加之后的序列。

新增一个超级父节点，其孩子为所有根节点，用优先队列维护序列并启发式合并，超级父节点的序列就是答案序列的差分。

题解：构造树的方法是将括号序列当成区间，左端点最小右端点最大双关键字排序，然后就可以形成先序遍历。因为考虑生成这个括号序列的树，线序遍历一定按照左边最小右边最大的顺序，可以说按这个方法还原和线序遍历时严格的正反过程。

方法就是维护一个栈，栈内区间全部包含当前元素。

然后考虑对每个子树维护其dp数组，$dp_i$ 表示i 次覆盖。那么向上回溯更新dp 就符合 dp[i] = max(dp[i-1]+w, dp[i]) 的形式，无法高效更新。但是如果维护差分序列就可以用 pq + 启发式合并的方法。

PS: 场上没出是因为 Weaver_zhu 忘了怎么写启发式合并

Problem K

Unsolved.