考前模板

不加剪枝倒数第二个点T，加了剪枝最后一个点莫名输入都错了，，真烦。
最后算是打表一个点，这题真jb拉低我正确率，最后还没写对。。。。。。。。。。。
顺便膜神犇hxf~~~~~~~~~~~
自己总共交了41遍。。。。
成功把这题通过率拉到4%~~~~~~~~~~

回复 @sdzwyq :

1

第一名为什么辣么快

为什么要用搜索啊，模拟水过去不行吗

bd

回复 @猎户星座 :
本水题由现任文博初二七班体委提供，欢迎指教@猎户星座

不容易啊，模拟赛小萌新花90min打了180行，拿了90分、、、
楼上才是大神犇 膜王神orz

回复 @过劳死的贤王�� :
哈哈哈，你们这群魔鬼，都是思想出问题了

回复 @lucifer :
就是用贪心做啊
输入到S这个字符串里
然后按字典序比较S和S反转后的字符串
我在POJ做过原题
POJ3716

70题留念

蜜汁位运算与剪枝。。。

回复 @leon :
这是你粘别人代码的理由吗？

真jb水的题。。@8865 出题人出来挨打

水题

搬一下官方题解
题目大意 给定 N 个数字， N 个字母。要求确定数字与字母的对应关系，使给定 M 个数字串和字符串组尽可能多的满足对应关系。
考察算法 搜索 位运算/状态压缩
算法一 枚举每个数字对应的字符，时间复杂度 O(N!)。然后通过 O(ML)的时间判断每个字符串数组是否匹配。不断更新最大值。伪代码：
DFS(dep)
If dep == N Then
Num ← Count()
If Num > Max
Max ← Num
End If
End If
For i = 1 .. N
If not used[i] Then
used[i] ← true
a[dep] ← i
DFS(dep + 1)
used[i] ← false
End If
End For
其中 dep 表示枚举到的第几个字符， a[i]表示第 i 个字符对应的数字。
时间复杂度： O(N!•ML) 期望得分： 30
算法二 在算法一的基础上加上简单的剪枝，如果当前数量已经小于已知最大值，就把当前纸
条剪掉。
DFS(dep)
Num ← Count()
If Num <= Max Then Exit
If dep == N Then
If Num > Max
Max ← Num
End If
End If
For i = 1 .. N
If not used[i] Then
used[i] ← true
a[dep] ← i
DFS(dep + 1)
used[i] ← false
a[dep] ← 0
End If
End For
时间复杂度： O(N!•ML) 期望得分： 60
算法三 此算法需要用到一点位运算的知识，阅读前请保证你已经熟练地使用位运算，否则请到 Matrix67 的 Blog 查看相关知识后再进行阅读。
通过题目数据我们可以知道 M 最大不会超过 60，而一个 long long的范围最大到 2^63-1，所以我们可以通过一个 2 进制数来表示当前字符数列组的匹配情况。
1 表示可能匹配， 0 表示不能匹配。同样需要通过全排列来枚举每个字符对应的数字，采用 DFS(dep, rest)， rest 表示当前的匹配情况状态。每次枚举一个字符所对应的数字，我们可以通过 O(1)的时间从当前状态中减去不能匹配的状态。建立数组del[i][j]表示当字母 i 对应数字 j 时，会造成那些不能匹配，比如 del[i][j]=(1001)2，表示当字母 i 对应字母 j 时，第 1、 4 字符数列组不能匹配。那么新的状态就等于 new = rest & (~del[i][j])或 new :=rest and (not del[i][j])。
然后再加上算法二的剪枝，就能够通过所有的数据。
接下来考虑如何求出 del[i][j]，依次枚举每一个字符数列组，设第 i 个字符数列组对应的 2 进制位置为 t[i]。如果在该字符数组中字母 ch 对应了数字 num，那么其他数字的 del[i][num]和 ch 对应的其他数字 del[ch][j]都应该加上 t[i]。预处理的时间复杂度为 O(MLN^2)。
最后只需要在主函数内调用 DFS(0, (1<<M)-1)即可。
时间复杂度： O(MLN+N!)/O(ML+MN^2+N!) 期望得分： 80
算法四 在算法三的基础上优化搜索顺序，记录每个字母出现的次数，按照最小到大的顺序进行搜索。由于先出现字母影响较小，可以使最后产生的结果尽可能大，很多冗余都会被剪掉。
时间复杂度： O(MLN+N!)/O(ML+MN^2+N!) 期望得分： 100

回复 @ShallowDream雨梨 :
谢睿哥的快速幂版子题，给我过了150题大关，膜大佬