Difference between revisions of "XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Peterhof"

Latest revision as of 13:52, 11 September 2019

Problem A

Solved by Kilo_5723 01:10. (+3)

题意：给你一些六边形的棋子，要求你用六边形的框把给定数量的棋子框起来，求框的最小周长。

题解：特判 $1$ 的情况，对于其他的情况，从两个棋子的情况开始每一次扩展最长的边即可。

Problem B

Unsolved.

Problem C

Solved by Weaver_zhu. 01:18 (+)

暴力签到

Problem D

Solved by Kilo_5723. 04:54 (+2)

题意：给定一个地图，第 $i$ 圈有 $3^{i-1}$ 个节点，每一圈的相邻节点有路相连，内圈的节点向外圈的节点均匀相连，现在给定两个离原点距离不超过 $35$ 的位置，求最短路。

题解：对两个位置分别向内圈深搜出所有可能到达的位置的最短路。如果能往内圈走则不搜索往同圈走的其他方案，之后再合并答案找到最短路即可。

Problem E

Solved by Xiejiadong. 02:01 (+)

题意：一个每秒在旋转的打印条要在纸上打印，询问最短的时间打印完成。

题解：每次能打印的时候肯定就直接打印。

每次记录开始时打印条的状态，二分查找每一个位置在什么时候会打印到。即二分查找大于当前时间的一个最小值。

初始状态想清楚了就能写了。

Problem F

Problem G

Problem H

Problem I

Solved by Xiejiadong. 00:27 (+)

题意：给出一些路径记录，这个机器人只能走三个方向，走到一个机器人不能到的地方。

题解：分类讨论。

如果已知机器人的三个方向，往机器人不能走的方向走一步即可。

如果已知机器人小于等于一个方向，怎么走都可能被机器人搞。

如果已知机器人两个方向且两个方向在同一水平线，怎么走都会被机器人搞。

如果已知机器人两个方向但两个方向不在同一水平线，往另外两个方向各走一步即可。

Problem J

Upsolved by Weaver_zhu. (-8)

梦游签到

题意：判断完全平方数。

题解：二次剩余随便判几个 int 范围素数就行了。

@@ Line 1: / Line 1: @@
-= _ =
-Xiejiadong: 抱着能 AK 的幻想。最后一个小时还是三人三线开题。三人枪机，三人三爆炸。
 == Problem A ==
-Upsolved by Weaver_zhu
+Solved by Kilo_5723 01:10. (+3)
-题意：一个三位空间中维护计算任一点在整数时间点相遇，坐标对数取模。
+题意：给你一些六边形的棋子，要求你用六边形的框把给定数量的棋子框起来，求框的最小周长。
-题解：数据范围可以支持不停的$n^2$判断相撞，然后直到撞不了为止。剩下的就是解模线性方程组。坑点是各种无解的情况（模数都不是互素的，一个维上坐标不变，可以是一直重合和一直相离的情况）
+题解：特判 $1$ 的情况，对于其他的情况，从两个棋子的情况开始每一次扩展最长的边即可。
 == Problem B ==
-Solved by Weaver_zhu. 02:17 (+1)
+Unsolved.
-题意：把黑点扔进矩形，白点扔出矩形，找到一个矩形使得扔的次数最少。
+== Problem C ==
-题解：离散化+二维前缀和刚好$10^8$复杂度。62ms数据有点水
+Solved by Weaver_zhu. 01:18 (+)
-== Problem C ==
+暴力签到
-Upsolved by Xiejiadong. (-2)
+== Problem D ==
-题意：给出 $n\times n$的方格中其中\(m\)个联通的位置，要求满足四则运算其中一个的要求，并且同行同列无相同数，每个格子只能填\(\le n\)的数。
+Solved by Kilo_5723. 04:54 (+2)
-题解：暴力搜索，加剪枝。
+题意：给定一个地图，第 $i$ 圈有 $3^{i-1}$ 个节点，每一圈的相邻节点有路相连，内圈的节点向外圈的节点均匀相连，现在给定两个离原点距离不超过 $35$ 的位置，求最短路。
-大致的剪枝如下：
+题解：对两个位置分别向内圈深搜出所有可能到达的位置的最短路。如果能往内圈走则不搜索往同圈走的其他方案，之后再合并答案找到最短路即可。
-* 显然减法和除法 $O(n^2)$ 枚举一下就好了。
+== Problem E ==
-* 当前的和（积）加（乘）所有最大数都到不了了或者加（乘）所有最小的数都超过了，直接剪枝。
+Solved by Xiejiadong. 02:01 (+)
-* 最后一个数可以直接推出来，搜索层数 $-1$ 。
+题意：一个每秒在旋转的打印条要在纸上打印，询问最短的时间打印完成。
-* 同行同列的数利用状态压缩处理掉。
+题解：每次能打印的时候肯定就直接打印。
-最后一个问题是题目没有给 $t$ 的范围，于是我开了 long long ，这就是 TLE 的根源。
+每次记录开始时打印条的状态，二分查找每一个位置在什么时候会打印到。即二分查找大于当前时间的一个最小值。
-== Problem D ==
+初始状态想清楚了就能写了。
-Solved by Weaver_zhu. 00:35 (+1)
+== Problem F ==
-温暖的签到
-== Problem E ==
+== Problem G ==
-Solved by Kilo_5723. 00:46 (+)
-== Problem F ==
+== Problem H ==
-Solved by Xiejiadong. 01:34 (+)
-题意：有一些原材料地和一些需要原材料供应的地方，还有一些没有这两个限制的地方，有一些物流公司可以支持在一些地方相互的运送，但是只能运送其中某两个地方的东西，要求原材料地和需要原材料供应的地方最大的匹配。
+== Problem I ==
-题解：比较套路的最大流。
-* 把所有的物流拆成一个入点和出点，之间限流 $1$ 。
+Solved by Xiejiadong. 00:27 (+)
-* 原材料地连入点，流量无穷。
+题意：给出一些路径记录，这个机器人只能走三个方向，走到一个机器人不能到的地方。
-* 出点连需要原材料供应的地方，流量无穷。
+题解：分类讨论。
-* 其他的点可以用来中转原材料，出点连它，它连入点，流量均无穷大。
+* 如果已知机器人的三个方向，往机器人不能走的方向走一步即可。
-* 源点连原材料地，需要原材料供应的地方连汇点，限流 $1$ ，统计答案。
+* 如果已知机器人小于等于一个方向，怎么走都可能被机器人搞。
-== Problem G ==
+* 如果已知机器人两个方向且两个方向在同一水平线，怎么走都会被机器人搞。
-Solved by Kilo_5723. 01:59 (+)
+* 如果已知机器人两个方向但两个方向不在同一水平线，往另外两个方向各走一步即可。
-== Problem H ==
+== Problem J ==
-Upsolved by Kilo_5723. (-3)
+Upsolved by Weaver_zhu. (-8)
-== Problem I ==
+梦游签到
-Solved by Xiejiadong. 00:48 (+)
+题意：判断完全平方数。
-暴力翻转。温暖签到。
+题解：二次剩余随便判几个 int 范围素数就行了。