信息学集训队作业

1、三臂起重机（TRO）三臂起重机用来为货车装载货物。假设车厢已经按照1，2，3，编号，每一节车厢上仅可以放入一集装箱的货物。三臂起重机的工作方法很简单。它每次可以从仓库中吊出三箱货物，把它们放到编号为（i，i+p，i+p+q），或者编号为（i，i+q，i+p+q）的三节车厢中。p,q已知，且p,q1。现在我们的目的是把编号为1，2，n的车厢全部装满货物，且已知货车恰有n+p+q节车厢。为了完成这个任务，我们必须为起重机安排一个装运程序，程序中包含若干行，每一行含有三个数字x、y、z，满足1xyzn+p+q,表示此次吊起的三件货物分别放到了编号为x、y、z的车厢中。你的程序输出正确当且仅当按照输出

2、安排的吊运方法可以把编号为1，2，n的n节车厢全部装满，且每一节车厢至多装载了一箱货物。输入输入文件TRO.IN仅包含一行，这一行有三个数字p，q，n，分别是三臂起重机运货的两个参数以及需要装货的车厢数。1n300000,2p+q60000。输出输出文件TRO.OUT包含若干行，第一行为一个数字m，表示三臂起重机的装箱次数。其后有m行，每一行包含三个数字x、y、z，即为每次吊起的三间货物装入的车厢编号。容易知道，yx+p，x+q，z=x+p+q。输入样例2 3 10输出样例41 3 62 4 75 8 109 11 14TRO解题报告问题描述这是Poi2000 stage 2的一道题目。题目的

3、大意是给出了三个数p、q、n，要构造若干个三元组，要符合以下四个要求：（1）三元组必须具备形式（i，i+p，i+p+q）（i，i+q，i+p+q）之一。（2）所有三元组中的元素不得超过n+p+q。（3）1，2，n+p+q这n+p+q个数每个至多出现一次。（4）这些三元组必须涵盖1，2，n这n个自然数。n=300000，p+q=60000。算法分析初看此题，感觉数学味颇浓。题目虽然以“起重机”“装载”作为背景，但是剥去这层伪装后，我们就可以用熟悉的数学语言来加以描述了。由于n，p+q的范围比较大，我们想到用效率较高、复杂度低的构造法来解决。假设我们已经构造了若干个符合条件的三元组，如果1，2，n

4、都已经出现过则终止，否则下一步我们取出未出现过的最小的自然数x，显然xn。由于前面所有的三元组的第一个数都小于x（由构造方法易知），所以这些三元组中的元素都不超过x-1+p+q，那么x+p+q肯定没有出现过。我们的问题转化成为决定（x，?，x+p+q）中的？。一个最简单的想法是：首先尝试x+p，若没有出现过则取？=x+p，否则取？=x+q。这样做的疑点在于：是否会出现x+p、x+q都出现过无法选择的情形呢？看下面这个例子：p=3，q=2首先取没有出现过的最小自然数1，构造出三元组（1，4，6），接下来又构造出（2，5，7），这是没有出现过的最小数为3，但是3+3=6，3+2=5均已出现在前面三

5、元组中，无法选择了。这样构造宣告失败。换一个角度。P与q的地位是对称的，我们不妨假设p=q，则交换它们，不影响结果。在上面的例子中，我们会取p=2，q=3。则构造的过程为（1，3，6），（2，4，7），（5，8，10），（9，11，14）尝试了很多次，我们发现：这样做就没有反例了。于是猜想：当p=q时，上面的构造方法是正确的。下面我们来证明这一点。假设已经构造了s个三元组，分别为（），（，。我们取这些三元组中没有出现过的最小元素r，证明r+p，r+q不可能同时被使用过。采用反证法。若它们均出现过，则有如下两种情况：r+q=+p（1=i=p，则p-q=0，r=+p-q=，由于每次取的都是未出现过的最小自然数，矛盾！r+q=+p+q(1=i=s)，推出r=+p，若=+p，则r=已经出现过，矛盾。故=+q，由我们选取的规则可知，+p已经出现过（否则会选择+p而不是+q）,这又与r=+p没有出现过矛盾。综上，我们可知，r+q一定没有出现过，即不会有两种选择都违反规则的情形出现。至此，算法得证。小结本题采用的构造法在近年来的竞赛中并不多见，它的优点是