C++信奥教学PPT：CSP_J_算法之倍增算法

1、股市追捕（Stock Chase, Africa/Middle East-Africa and Arab 2009, LA4739）股票市场需要禁止那种导致一个公司直接或者间接的控股自己的购买行为。例如，A公司购买了B公司的股票，B购买C，C再买了A。前面两个合法。但是第3个就应该被拒绝，因为这样会导致3家公司间接对自身控股。给出按照时间顺序排序的购买交易，你的程序需要一次读入并且拒绝上述非法交易，其他的交易都要接受。给出公司的个数N（0<N≤234）以及T（0<T≤100000）个交易：每个交易给出整数A、B（0<A,B≤N），表示A请求购买B的股票。输出要被拒绝的交易个数。

2、加密的密码（Encrypted Password, Africa/Middle East-Arab Contest 2012,LA6320）有一种密码加密算法，它的输入是由英文小写字母组成的密码字符串，加密步骤如下：（1）交换两个不同的字符的位置（可以做0到多次）。（2）在第1步输出结果的前面附加0到多个小写英文字母。（3）在第2步输出结果的后面附加0到多个小写英文字母。第3步的结果就是加密结果。现在给出上述算法加密后的结果以及原始密码，计算这个加密结果是否可能是原始密码加密出来的。输入字符串长度都不超过100000，由小写英文字母组成，并且原始密码的长度小于等于加密后的结果长度。

3、化学品安全（Safety in Alchemy, North America-Mid-Atlantic USA 2007,LA3923）一个罐子中装有多种化学品，两两起反应造成温度的升高。以如下的形式输入最多64对化学品以及其反应造成的温度升高值：chemical1 chemical2 heat表示1克的chemical1和1克的chemical2在一起会造成罐子升高heat（0≤heat≤100）度。化学品的名称都是小写字母组成的长度1～20的字符串。然后给出每种化学品的数量（在0～1000克之间）。计算罐子的温度最高可能升高多少度。

4、零件测试（Component Testing, North America-Mid-Atlantic USA 2012,LA6193）为n类（1≤n≤10000）零件，每一类中的零件需要相同数量的不同检查者，但是不同类的零件需要的检查者数量可能不同，每一类给出零件数量j（1≤j≤100000）和每个需要的不同的检查者个数c（1≤c≤100000）。有m类员工（1≤m≤10000）。每一类给出员工的个数k（1≤k≤100000）以及每个员工能被分配的零件个数d（1≤d≤100000）。每个员工可以检查任意一个可以是来自不同分类的零件，但是不能重复检查同一零件。计算检查这些零件，这些员工的数量是否足够。