139 条题解
-
0
yizer16 LV 3 @ 2007-08-08 22:05:46
第九组数据我有cheat的想法
什么破题啊
真是晕死
看了数据发现
所有的近似升序
for i:=0 to n-1 do 过5个点
for i:=n-1 downto 1 do 过9个点 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms经典的搜索题。最单纯的搜索的时间复杂度为O(n!)，是会非常严重的超时的。计算机是很“笨”的，它不会思考，在盲目搜索的过程中，很容易出现这种情况：
计算机在某一位搜索出了一个算式1 + 1 = 3，并且继续搜索。
明显，人眼很容易就看出这是不合法的，但计算机不会。于是，我们想到了第一个剪枝：每次搜索的时候，从最后向前判断是否有不合法的式子。
这一个剪枝非常简单，但是效果却非常的好。因为它剪去了很多不必要的搜索。为了配合这一种剪枝更好的实行，搜索顺序的改变也成为大大提高程序效率的关键：从右往左，按照字母出现顺序搜索，有很大程度上提高了先剪掉废枝的情况，使程序的效率得到大大的提高。
有了以上两个剪枝，程序就已经可以通过大部分测试点了。但是有没有更多的剪枝呢？答案是肯定的。
根据前面的剪枝，我们可以找到类似的几个剪枝：
对于a + b = c的形式，假如：
A***|?\*|
+ B*?\*?**
C**|???*
其中*代表已知，?代表未知。那么，A + B与C的情况并不能直接确定。但是，假如(A + B) % N与(A + B + 1) % N都不等于C的话，那么这个等式一定是不合法的。因为它只有进位和不进位的两种情况。
同样，我们在一个数组里记录了Used[i]表示一个数字有没有用过，那么，对于某一位A + B = C的等式，如果已经得到了两个数，另一个数还待搜索的时候，我们还可以根据这个加入一个剪枝：
例如A + ? = C的形式，
考虑不进位的情况，则?处为P1 = (C - A + N) % N
假如考虑进位的情况，则?处为P2 = (C - A - 1 + N) % N
假如P1、P2均被使用过，那么这个搜索一定是无效的，可以剪去。有了以上的剪枝，就可以很轻松地通过所有的测试数据了。当然，还有很多值得思考的剪枝以及其他的思路，例如枚举进位、解方程（但是可能需要枚举）等，在这里就不详细讨论了。
(转自郭晓非吧)
-
0
第一次记录搜索的顺序，然后一位一位搜..
超时3个第二次改成for i:=n-1 downto 0 do
超时1个接着，硬交 Puppy 交了N次后.. Puppy也超了一了
—_—！
第三次dfs(k,1,jw) →dfs(k,2,jw) →dfs(k-1,1,jw) →dfs(k-1,2,jw)
搜索...两个加数用搜，和用两个加数来推...
分了4种情况。。。
写得龌龊了...
细节出错太多.....
又改了N次...结果：
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms共计提交20次..11次90分....
-
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 416ms
├ 测试数据 09：答案正确... 712ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：1128ms
Vivid Puppy就是快,我不懂,只能随机化搜索了,咳………… -
0
woshibaichi LV 4 @ 2007-03-27 20:03:11
解方程，高斯消元，虽然长了点...
-
0
congming789 LV 6 @ 2007-03-10 22:39:00
Blaze评测
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
纪念下.... -
0
derambroken LV 3 @ 2007-03-10 18:01:50
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 556ms
├ 测试数据 09：答案正确... 728ms
├ 测试数据 10：答案正确... 0msddddddddddddddddddddddd
faint
-
0
搜索弱滴就是这样。。。
编译通过...
├ 测试数据 01：运行超时...
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 72ms
├ 测试数据 05：运行超时...
├ 测试数据 06：运行超时...
├ 测试数据 07：运行超时...
├ 测试数据 08：运行超时...
├ 测试数据 09：运行超时...
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Unaccepted 有效得分：40 有效耗时：72ms -
0
这题的减枝太重要了，要用力减了还要减，最后.....
虫食算
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
INFINITE_Li LV 3 @ 2006-11-15 21:30:27
DFS+双重排序+减枝
注意:搜的顺序很重要! 最好从大到小搜...不然MS第8个数据很容易TLE.大概原因是更多的进位使剪枝的过程更加敏锐~编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 181ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：181msWell Done!
-
-1
Allenlai38 LV 7 @ 2018-08-13 16:25:05
基本思路就是dfs，从右往左一列列的搜
剪枝一：减少不必要的试算
我将每一列的试算分为正算和反算
例如：某一列
A
B
C
（1) 反算
定义：通过A/B和C反推B/A
条件：C已知或者A==C或者B==C
（2）正算
定义：通过A和B推出C
（3)
建议先把3个已知和2个已知的情况（不需要迭代）先考虑
剪枝二：提前判断
每次完成一列字母的填写后，判断
（1) 第一列不能进位
A+B>C 和 A>C 和 B>C （在已填写的情况下判断）
（2）某列中三个数已填写的情况下满足A+B+1=C或者A+B=C
剪枝三：数字不能重复贴出python的版本
```pydef cut(a):
p1 = f[0][n - 1]
p2 = f[1][n - 1]
p3 = f[2][n - 1]
if a[p1] + a[p2] >= n:
return False
if a[p3] < a[p1] and a[p3] != -1 and a[p1] != -1:
return False
if a[p3] < a[p2] and a[p3] != -1 and a[p2] != -1:
return False
for i in range(0, n - 1):
p1 = f[0][i]
p2 = f[1][i]
p3 = f[2][i]
if a[p1] != -1 and a[p2] != -1 and a[p3] != -1 and (a[p1] + a[p2] + 1) % n != a[p3] and (a[p1] + a[p2]) % n != \
a[p3]:
return False
return Truedef dfs(a, v, p, w):
if p == n:
for i in range(n):
print(a[i], end=' ')
exit()
p1 = f[0][p]
p2 = f[1][p]
p3 = f[2][p]
if a[p1] != -1 and a[p2] != -1:
b = (a[p1] + a[p2] + w) % n
if a[p3] == b:
dfs(a, v, p + 1, (a[p1] + a[p2] + w) // n)
elif a[p3] == -1 and v[b] == 0:
a[p3] = b
v[b] = 1
if cut(a):
dfs(a, v, p + 1, (a[p1] + a[p2] + w) // n)
a[p3] = -1
v[b] = 0
elif (a[p1] != -1 or a[p2] != -1) and a[p3] != -1:
if a[p1] == -1:
p1, p2 = p2, p1
b = (a[p3] - w - a[p1] + n) % n
if v[b] == 0:
a[p2] = b
v[b] = 1
if cut(a):
dfs(a, v, p + 1, (a[p1] + a[p2] + w) // n)
a[p2] = -1
v[b] = 0
elif a[p3] != -1 or p1 == p3 or p2 == p3:
if p2 == p3:
p1, p2 = p2, p1
for i in range(n - 1, -1, -1):
if v[i] == 0:
a[p1] = i
v[i] = 1
b = (a[p3] - a[p1] - w + n) % n
if a[p2] == b:
dfs(a, v, p + 1, (a[p1] + a[p2] + w) // n)
elif a[p2] == -1 and v[b] == 0:
a[p2] = b
v[b] = 1
if cut(a):
dfs(a, v, p + 1, (a[p1] + a[p2] + w) // n)
a[p2] = -1
v[b] = 0
a[p1] = -1
v[i] = 0
else:
if a[p1] != -1:
p1, p2 = p2, p1
for i in range(n - 1, -1, -1):
if v[i] == 0:
a[p1] = i
v[i] = 1
if a[p2] == -1:
for j in range(n - 1, -1, -1):
if v[j] == 0:
a[p2] = j
v[j] = 1
b = (a[p1] + a[p2] + w) % n
if v[b] == 0:
a[p3] = b
v[b] = 1
if cut(a):
dfs(a, v, p + 1, (a[p1] + a[p2] + w) // n)
a[p3] = -1
v[b] = 0
a[p2] = -1
v[j] = 0
else:
b = (a[p1] + a[p2] + w) % n
if v[b] == 0:
a[p3] = b
v[b] = 1
if cut(a):
dfs(a, v, p + 1, (a[p1] + a[p2] + w) // n)
a[p3] = -1
v[b] = 0
a[p1] = -1
v[i] = 0n = int(input())
f = [[] for i in range(3)]
for i in range(3):
t = input()
for j in range(n - 1, -1, -1):
f[i].append(ord(t[j]) - ord('A'))
dfs([-1 for i in range(n)], [0 for i in range(n)], 0, 0)程序又长又臭，而且还超时了好几次，哎。。
yizer16
LV 3
@ 2007-08-08 22:05:46
