Difference between revisions of "2015-2016 ACM-ICPC East Central North America Regional Contest"
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
Line 42: | Line 42: | ||
Solved by Xiejiadong. 01:34 (+) | Solved by Xiejiadong. 01:34 (+) | ||
+ | |||
+ | 题意:有一些原材料地和一些需要原材料供应的地方,还有一些没有这两个限制的地方,有一些物流公司可以支持在一些地方相互的运送,但是只能运送其中某两个地方的东西,要求原材料地和需要原材料供应的地方最大的匹配。 | ||
+ | |||
+ | 题解:比较套路的最大流。 | ||
+ | |||
+ | * 把所有的物流拆成一个入点和出点,之间限流 $1$ 。 | ||
+ | |||
+ | * 原材料地连入点,流量无穷。 | ||
+ | |||
+ | * 出点连需要原材料供应的地方,流量无穷。 | ||
+ | |||
+ | * 其他的点可以用来中转原材料,出点连它,它连入点,流量均无穷大。 | ||
+ | |||
+ | * 源点连原材料地,需要原材料供应的地方连汇点,限流 $1$ ,统计答案。 | ||
== Problem G == | == Problem G == |
Revision as of 12:02, 17 May 2019
_
Xiejiadong: 抱着能 AK 的幻想。最后一个小时还是三人三线开题。三人枪机,三人三爆炸。
Problem A
Unsolved. (-2)
Problem B
Solved by Weaver_zhu. 02:17 (+1)
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 (+)
Problem F
Solved by Xiejiadong. 01:34 (+)
题意:有一些原材料地和一些需要原材料供应的地方,还有一些没有这两个限制的地方,有一些物流公司可以支持在一些地方相互的运送,但是只能运送其中某两个地方的东西,要求原材料地和需要原材料供应的地方最大的匹配。
题解:比较套路的最大流。
- 把所有的物流拆成一个入点和出点,之间限流 $1$ 。
- 原材料地连入点,流量无穷。
- 出点连需要原材料供应的地方,流量无穷。
- 其他的点可以用来中转原材料,出点连它,它连入点,流量均无穷大。
- 源点连原材料地,需要原材料供应的地方连汇点,限流 $1$ ,统计答案。
Problem G
Solved by Kilo_5723. 01:59 (+)
Problem H
Unsolved. (-3)
Problem I
Solved by Xiejiadong. 00:48 (+)
暴力翻转。温暖签到。