2015-2016 ACM-ICPC East Central North America Regional Contest

From EOJ Wiki
Jump to: navigation, search

_

Xiejiadong: 抱着能 AK 的幻想。最后一个小时还是三人三线开题。三人枪机,三人三爆炸。

Problem A

Upsolved by Weaver_zhu

题意:一个三位空间中维护计算任一点在整数时间点相遇,坐标对数取模。

题解:数据范围可以支持不停的$n^2$判断相撞,然后直到撞不了为止。剩下的就是解模线性方程组。坑点是各种无解的情况(模数都不是互素的,一个维上坐标不变,可以是一直重合和一直相离的情况)

Problem B

Solved by Weaver_zhu. 02:17 (+1)

题意:把黑点扔进矩形,白点扔出矩形,找到一个矩形使得扔的次数最少。

题解:离散化+二维前缀和刚好$10^8$复杂度。62ms数据有点水

Problem C

Upsolved by Xiejiadong. (-2)

题意:给出 $n\times n$的方格中其中\(m\)个联通的位置,要求满足四则运算其中一个的要求,并且同行同列无相同数,每个格子只能填\(\le n\)的数。

题解:暴力搜索,加剪枝。

大致的剪枝如下:

  • 显然减法和除法 $O(n^2)$ 枚举一下就好了。
  • 当前的和(积)加(乘)所有最大数都到不了了或者加(乘)所有最小的数都超过了,直接剪枝。
  • 最后一个数可以直接推出来,搜索层数 $-1$ 。
  • 同行同列的数利用状态压缩处理掉。

最后一个问题是题目没有给 $t$ 的范围,于是我开了 long long ,这就是 TLE 的根源。

Problem D

Solved by Weaver_zhu. 00:35 (+1)

温暖的签到

Problem E

Solved by Kilo_5723. 00:46 (+)

题意:给定一个图,一开始一个点有 $1$ 的污染度。接下来,每个节点第 $t$ 秒的污染度是 $t-1$ 秒与其相连的所有节点的污染度之和,求第 $t$ 秒每个节点的污染度之和。

题解:根据题意模拟即可。

Problem F

Solved by Xiejiadong. 01:34 (+)

题意:有一些原材料地和一些需要原材料供应的地方,还有一些没有这两个限制的地方,有一些物流公司可以支持在一些地方相互的运送,但是只能运送其中某两个地方的东西,要求原材料地和需要原材料供应的地方最大的匹配。

题解:比较套路的最大流。

  • 把所有的物流拆成一个入点和出点,之间限流 $1$ 。
  • 原材料地连入点,流量无穷。
  • 出点连需要原材料供应的地方,流量无穷。
  • 其他的点可以用来中转原材料,出点连它,它连入点,流量均无穷大。
  • 源点连原材料地,需要原材料供应的地方连汇点,限流 $1$ ,统计答案。

Problem G

Solved by Kilo_5723. 01:59 (+)

题意:给定一个 $n \times m $ 的长方形,其中有一些格子不可用。问用 $1 \times 1$ 和 $1 \times 2$ 的长方形填满剩下的区域的可行解有多少。

题解:伪插头 dp。三个插头分别代表:当前块没有连接块或向左有连接块,当前块纵向有连接块和当前块向右有连接块。处理每一列的解合并即可。

Problem H

Upsolved by Kilo_5723. (-3)

题意:给定一个桌球台和三个球,要你在一个水平线段上选取一个放母球的位置,问你是否能做到母球撞球 1,球 1 撞球 3 ,球 3 进洞,母球撞球 2 ,球 2 进洞。可以的话输出方案。

题解:处理每一个球在撞击另一个球的位置,连线判撞击角度是否合法即可。注意每个球的路线不能相交。

Problem I

Solved by Xiejiadong. 00:48 (+)

暴力翻转。温暖签到。