AtCoder Contest (ITMO Day 4)

From EOJ Wiki
Jump to navigation Jump to search

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)$ 个点。每个连通分量里至少要有一个。剩下的乱选。选尽量小的。