AtCoder Contest (ITMO Day 4)

Problem A

Solved by zerol. 00:49 (+2)

题意：总共有 $n$ 个座位围成一圈，不能有同性相邻，所以肯定有位置是空着的。在一定询问次数内确定至少一个空位置。

题解：每次确定已知座位对面的座位，从而确定空着的座位在奇数的区间内还是偶数的区间内，然后转换成子问题。一定要注意边界！

Problem B

Unsolved.

Problem C

Upsolved by ultmaster. 04:59 (-8)

题意：给一个格点三角形，问是否存在一个格点在三角形内。

题解：思路很简单。找一条边，找出最小的 $(x,y)$ 是这条边上的一个互质向量（这个名词我自己发明的）。然后求 $ax+by=1$ 的解，$(b,-a)$ 和 $(-b,a)$ 是有可能的解。可以证明所有解都具有 $(b+kx,-a+ky)$ 的形式。如果找不到，就不可能。

实际操作的时候很恶心。我是先求交点然后 test。结果各种 WA。最后求出两个交点之后取平均数，然后枚举周围的约 2k 个点，过了。（可能也是假的）

Video tutorial 中提到了另一种思路是将三角形竖着切成两半，然后等价于求一个分数满足 $lo < slope < hi$ 且分数不超过 $M$。据说用二分搜索可以做，但是不会。如果想出来了可能可以出道题。

Problem D

Upsolved by ultmater.

题意：有一个背包支持三种操作：

1. 放一个东西，东西的重量是递增的（好像并不显然）。

2. 拿掉一个质量最小的东西。

3. 查询重量和 $\bmod MOD$ 在 $[l,r]$ 内的东西的价值和的最大值。

题解：用两个栈来模拟一个队列，这样的话 pop 和 push 操作都仅会对 DP 的最上面一层产生影响。一个栈空了要把另外一个栈倒过去全部重算。合并两个栈最顶层的时候可以用滑动窗口 + 单调栈。

Problem E

Upsolved by ultmaster.

题意：每次可以选择树上的一条路径异或一个数，问要几次操作把整棵树都变成 0。

题解：大力分析。

第一步：树上的任意路径可以转换成两条到根上的路径，由于异或的特殊性，不加不减正正好好。

第二步：这样我们就可以从叶子节点往上消，每个节点到根的那条路径要异或多少也知道了。

第三步：然后两两配对，能配的先配。最后 $[0,15]$ 顶多剩 $16$ 个。暴算一下就好了。

Problem F

Solved by kblack. 02:27 (+2)

题意：在树上装 $k$ 个雷达，使得每个点对应一个 $k$ 维向量，这个向量的每一维就是到这 $k$ 个雷达的距离。现在求最小的 $k$ 把所有点区分出来。

题解：不大会。

Problem G

Unsolved.

神题。

Problem H

Unsolved.

题意：一棵有根树，每个节点上都有个权值。要在规定操作次数内使得 $a_0,\ldots,a_{N-1}$ 有序。每次操作可以选中一个节点，把这个节点到根的链做一步旋转。

Problem I

Solved by ultmaster. 03:41 (+)

题意：区间操作：加，除，求最大值。

题解：由于除法操作会使得数与数之间的差变小，多除几次就全相等的。我们不妨将除法操作转换成加法操作：也就是说，如果区间内最大值除过后与最小值除过后造成的影响（delta）相等，我们就直接执行加法操作，不然就递归。复杂度 $O(n \log n \log C)$ ，不会证。

Problem J

Unsolved.

题意：$H \times W$ 的方格纸，有 $N$ 个禁手，求剩下的 $H \times W - N$ 个格子两两之间的距离之和。

Problem K

Solved by kblack. 00:33 (+2)

题意：给一个森林，加边使得森林连通。用过的点不能再用，加边的代价是点权之和。

题解：关键在于要选哪些点，显然要选 $2(N - M - 1)$ 个点。每个连通分量里至少要有一个。剩下的乱选。选尽量小的。