Difference between revisions of "XX Open Cup named after E.V. Pankratiev. Grand Prix of Korea, Division 1."
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
Line 23: | Line 23: | ||
Solved by Xiejiadong. 04:40 (+10) | Solved by Xiejiadong. 04:40 (+10) | ||
− | + | 题意:每次有新的团队入住的时候,有两种情况: | |
+ | |||
+ | * 住客有无数个,那么所有住在 $x$ 房间的人移到 $2x$ ,新来的在记述房间入住; | ||
+ | * 住客有 $k$ 个,所有人向后挪出 $k$ 个空房间。 | ||
+ | |||
+ | 现在要求每个团队里某一个人在的房间以及房间里的人属于的团队。 | ||
+ | |||
+ | 题解:对于每个团队里的人可以发现所有人的间隔是相同的。 | ||
+ | |||
+ | 而对于无数个人输入,相当于间隔 *2 ,其实坐标 *2 (起始坐标是 $0$ 的话不变)。 | ||
+ | |||
+ | 对于询问房间里的人属于的团队,我们可以用无穷多的次数将团队分割开来。 | ||
+ | |||
+ | 这样对于分割开来的每一部分有限人数的团队一定在最开头部分,可以通过前缀和二分得到。如果属于后半部分的房间: | ||
+ | |||
+ | * 是奇数房间,一定是无穷的那个团队的; | ||
+ | * 否则编号一定 *2 了,那么 /2 继续做这个问题。 | ||
+ | |||
+ | 显然最多只需要做这样的 $30$ 次。 | ||
+ | |||
+ | 需要也别处理 $0$ 号房间的问题。 | ||
== Problem G == | == Problem G == |
Revision as of 09:57, 16 February 2020
Problem A
Solved by Kilo_5723. 00:14 (+)
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
Unsolved.
Problem K
Unsolved.