Wizmann
commented
4 years ago B. Pascal Walk
题意
给定一个帕斯卡三角。求一条从顶点开始的连续路径（六边形的临边），使得路径上面的值和为N（1 <= N <= 1e9）。路径不能重复，且总长度小于500。
思路
仍旧是签到题。而且比A题要简单。
初步思路
从组合数求和公式我们可以知道，第k行的数值之和为2^k。 所以我们可以尝试按二进制位来进行求和，使得路径上面的和为N。
进一步思考
使用二进制位的问题，在于路径必须是连续的。所以在一些行上，我们可以只访问最左边或最右边的1，而不对整行进行求和。
又由于N的范围小于1e9，所以最多不会超过32行。这里我们尝试枚举路径中，有多少行不进行整行求和。
解法
假设有U行不进行整行求和，而有V行[r1, r2... rv]进行整行求和。所以必然有：N = U + (2^r1 + 2^r2 ... 2^rv)。所以，如果N - U的二进制表示有V个1的话，那么就证明我们找到了正确的pattern。
然后我们对N-U的二进制进行补0（如果必要），使得其有V个1和U个0。对于每一个1，我们会访问这一行的所有元素（从最左到最右，或者从最右到最左）。而对于0，我们只访问最左或最右的元素，然后进入到下一行。
为什么一定有解
当然是比赛的时候暴力拍了大数据啦
最差的情况下，U可以比N的二进制表示位数还要多，所以一定可以有足够的0来补位。
A. Pattern Matching
Problem Code
题意
给定一些（2 <= N <= 50）字符串Pattern，Pattern中含有通配符（
*），通配符可以匹配任意字符（可以为空）。求任意一个字符串，能匹配所有的Pattern。如果不能的话，输出"*"。例如：
"*FOO"可以匹配"FOO", "ABCFOO"，但是不能匹配"FXX"或者"FOOXYZ"。
Pattern的长度最大为100。每个Pattern至少有一个通配符（
*）。 所求字符串的长度最大为10000。思路
本题是一道掩盖的很深的签到题。
基本思路
由于所求的字符串长度远大于所有Pattern拼接起来的长度之和，所以我们对于
*abc*和*bcd*这种情况，直接拼接成abcbcd。虽然长度上不是最优，但是也不算错。进一步思路
我们把原字符串根据星号分割开，例如
abc*cd*ef就可以分割成三段[abc*], [*cd*], [*ef]。然后在不同的字符串之间，按段匹配。对于下面几种场景分类讨论：
abc*只位于字符串的开头。意味着我们有一个确定性的前辍。所以我们需要在确定性前辍中找到一个最长的公共前辍。如果找不到，就算了（误对于前辍后面的字符串，因为我们有一个通配符，可以无视。
*abc位于字符串的结尾，意味着一个确定性后辍。和场景1一样，需要找到一个最长的。找不到的话，则表示无解。对于后辍前面的字符串，同样可以无视。
*abc*位于字符串中间，因为其前后都有星号。所以我们把这些Pattern去掉两端的星号都连起来，则一定有一个可行解。对于前辍和后辍，因为有通配符，无视之。
abc（没有*） 由于题目描述中说明了Pattern必有一个通配符，所以这种情况不存在。我们把前辍（1），后辍（2）和中间字符串（3）直接拼接起来，就完成了这一段的匹配。
举例：
[*abc, *bc*, *cd*, *def]的前辍是abc，后辍是def，中间是bccd或者cdbc随你开心。拼接起来就是abc+bccd+def。Corner Case
如果不同的字符串段的个数不一样，我们可以在里面插入
**用作占位符，反正也不会错。