Difference between revisions of "2015-2016 ACM-ICPC East Central North America Regional Contest"
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) (Created page with "= _ = Xiejiadong: 抱着能 AK 的幻想。最后一个小时还是三人三线开题。三人枪机，三人三爆炸。 == Problem A == Unsolved. (-2) == Problem B == S...") |
Xiejiadong (talk | contribs) |
||
| Line 13: | Line 13: | ||
== Problem C == | == Problem C == | ||
| − | + | Upsolved by Xiejiadong. (-2) | |
| + | |||
| + | 题意：给出 $n\times n$的方格中其中\(m\)个联通的位置，要求满足四则运算其中一个的要求，并且同行同列无相同数，每个格子只能填\(\le n\)的数。 | ||
| + | |||
| + | 题解：暴力搜索，加剪枝。 | ||
| + | |||
| + | 大致的剪枝如下： | ||
| + | |||
| + | * 显然减法和除法 $O(n^2)$ 枚举一下就好了。 | ||
| + | |||
| + | * 当前的和（积）加（乘）所有最大数都到不了了或者加（乘）所有最小的数都超过了，直接剪枝。 | ||
| + | |||
| + | * 最后一个数可以直接推出来，搜索层数 $-1$ 。 | ||
| + | |||
| + | * 同行同列的数利用状态压缩处理掉。 | ||
| + | |||
| + | 最后一个问题是题目没有给 $t$ 的范围，于是我开了 long long ，这就是 TLE 的根源。 | ||
== Problem D == | == Problem D == | ||
Revision as of 11:57, 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 (+)
Problem G
Solved by Kilo_5723. 01:59 (+)
Problem H
Unsolved. (-3)
Problem I
Solved by Xiejiadong. 00:48 (+)