卢俊达

有些公司是其他公司的部分拥有者，因为他们获得了其他公司发行的股票的一部分。例如，福特公司拥有马自达公司12%的股票。据说，如果至少满足了以下三个条件之一，公司A就可以控制公司B了：

• 公司A = 公司B。
• 公司A拥有大于50%的公司B的股票。
• 公司A控制K(K >= 1)个公司，记为C1, …, CK，每个公司Ci拥有xi%的公司B的股票，并且x1+ …. + xK > 50%。

给你一个表，每行包括三个数(i,j,p)；表明公司i享有公司j的p%的股票。计算所有的数对(h,s)，表明公司h控制公司s。至多有100个公司。写一个程序读入N组数(i,j,p)，i,j和p是都在范围(1..100)的正整数，并且找出所有的数对(h,s)，使得公司h控制公司s。

开始以为是搜索，按照不同物品不同数量枚举，超时。又在这基础上剪枝，考虑了币值之间的倍数关系，想把一个货币体系化简为货币值之间互质的情形，但写了一下感觉太复杂了。又按照钱数递减搜索，每次减去某一种币值并去掉重复情况…搞了n久还是超时，唉~。最后感觉可能是动态规划，但想不出个所以然来。无奈只好求助于nocow，发现这货竟然是背包！

没往背包上想可能是因为这个背包问题没用到物品价值这一属性吧，换句话说这个背包并不是要求出某一条件下的最大价值。

有v种币值和一个钱数n，问用给定币值可以有多少种方案构成n。

给出序列1 2 3 … n，在序列的每个数字之间可以决定是否插入符号“+”、“-”。输出所有结果等于0的式子。

给出一个模式串集合和一个被匹配串，问被匹配串的前多少位可以由模式串组成。

给出一些模式串和一个被匹配串，若被匹配串包含模式串或其反转，则称该模式串感染了被匹配串。问有多少个模式串感染了被匹配串。

给出一个矩阵和一些字符串，求字符串在矩阵中出现的位置及其方向。

数列k-bonacci (k is integer, k > 1)的定义如下：

• F(k, n) = 0, for integer n, 1 ≤ n < k;
• F(k, k) = 1;
• F(k, n) = F(k, n - 1) + F(k, n - 2) + … + F(k, n - k), for integer n, n > k.

给出一个整数s，在数列中找出几个不同的元素使其和等于s。

为了写一个AC自动机模板，参考了n多blog的代码，不料所有代码都如出一辙。本想写一个风格独特的模板，至少与其他人的不一样，但是因为思路上的先入为主等原因，还真没写出什么花样，跟网上其他的模板也没什么不同。

给出n个模式串和一个被匹配串，问有多少个模式串可以成功匹配。