卢俊达

这里是个人技术小站,用于学习与记录,欢迎各位光临。

题目大意


有些公司是其他公司的部分拥有者,因为他们获得了其他公司发行的股票的一部分。例如,福特公司拥有马自达公司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。

Read More…

前言


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

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

题目大意


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

Read More…

题目大意


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

Read More…

题目大意


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

Read More…

题目大意


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

Read More…

题目大意


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

Read More…

题目大意


数列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。

Read More…

前言


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

题目大意


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

Read More…