竞赛总览

CSDN 编程竞赛四十四期：比赛详情 (csdn.net)

竞赛题解

题目1、相似三角形

相似三角形是彼此各边长对应成同比例的两个或者更多三角形。小艺酱当然是不会思考的啦，她想到了她的师傅鬼谷大师的真言：“SDUT这个张子昊实乃CV人才是也，这次TA改成只复制格式而忽略内容了，大家快来看一看吧”。小艺酱要找的相似三角形和上述CV方式类似，只要对应顺序的边成比例即可，而不需要排序。请根据输入的三条边边长，去掉不能构成三角形者，只保留相似三角形中最前面的一个。

#include <cstdio>
#include <vector>struct triangle {int edge [3];
}int main () {std::vector <triangle> data; triangle node;while (input (node) != EOF) {bool allow = check (node);if (allow == false) continue;for (int i = 0; i < data.size (); i++) {double retio [3]; for (int j = 0; j < 3; j++) retio [j] = (double) data [i].edge [j] / node.edge [j];if (retio [0] == retio [1] && retio [0] == retio [2]) allow = false;}if (allow) data.push_back (node);}for (int i = 0; i < data.size (); i++) {if (i > 0) printf ("\\n");for (int j = 0; j < 3; j++) {if (j > 0) printf (" ");printf ("%d", data [i].edge [j]);}}return 0;
}

这道题目会不断输入数据，每次输入一组三角形的三条边长。

输入一组三角形数据之后，首先要判断一下它能否构成三角形。判断规则为两边之和大于第三边，可以使用循环对三条边分别判定，如果三次判定都通过，说明这三条边可以构成三角形。对于不能构成三角形的情况，直接跳过，继续输入下一组数据即可。

能构成三角形时，寻找一下历史数据中有没有相似的三角形。题目中规定相似三角形只需要输出第一组，因此，如果当前这组输入数据和历史数据中的任一组能构成相似，则跳过当前这组数据。这里判断相似三角形不需要给边排序，例如(3, 4, 5)和(6, 8, 10)就可以构成相似三角形，因为对应边的比例系数全部是2。

每次得到新三角形时，将其添加到历史数据中。最后，根据记录的三角形边长，逐个输出即可。

题目2、贝博士的机械零件

贝博士是个大忙人，他在设计和制造一台非常复杂的机械式计算机。最近贝博士有一点烦恼，因为机械零件的种类繁多，磨损又快，经费不太够用了。不过，他发现有一些机械零件在磨损以后，可以用若干同一型号的磨损旧零件重新回炉熔化，以后再铸造出一个该型号的新零件。符合这样的特点的机械零件称为可翻新零件。于是贝博士请来了他的助手艾小姐，请她统计一下有多少种型号的可翻新零件，每一种目前有多少存量又能以多少个旧零件重新回炉铸造出一个新零件。要求计算出对应于每一种机械零件他最终能使用的零件总数。

这道题目的输入只有两个整数p和q。看似题目描述非常复杂，但解法却十分简单。

换成经典的啤酒瓶盖兑换啤酒，就清晰得多了！

假设有p = 10瓶啤酒和q = 3个兑换阈值。

第一次，可以换10 / 3 = 3瓶啤酒，剩余10 % 3 = 1瓶啤酒，但兑换的新啤酒又会产生额外的啤酒瓶盖，最终剩余为10 % 3 + 10 / 3 = 4瓶啤酒。

第二次，可以换4 / 3 = 1瓶啤酒，剩余4 % 3 = 1瓶啤酒，加上新增的，一共剩余4 % 3 + 4 / 3 = 2瓶啤酒。

第三次，可以换2 / 3 = 0瓶啤酒，鸡生蛋、蛋生鸡，整个过程结束。

可见，新增情况为，(10, 3) = 4。

得到规律：当 p >= q 时可以继续兑换啤酒。

新增add = p / q瓶啤酒。剩余p = p % q + add瓶啤酒。

最终需要统计出一共能喝到多少瓶啤酒，再加上本金即可。