20210215 CFedu104 div2

我完成的

A

竞技场里每次 2 人打架高的人等级就加 1，平局不加，打架次数不限，请问最后那些人等级能到 100^500？

我的想法：遍历，找到最小值 On，再遍历，找到最小值个数 On
题解：

B

两只猫，n 个屋子，A 猫喜欢 n、n-1……1、n、n-1、n-2……1 这样睡屋子，B 猫喜欢 1、2、3……n、1、2……n、1……n 这样睡屋子，并且加入 A 猫与 B 猫要睡同一个屋子，B 猫就让 A 猫，自己自动顺延一个屋子继续睡。问经过 k 次，B 猫在哪个屋子？

我的想法：A 猫的睡觉轨迹是永远不变的，找 B 猫最后的位置只需要知道冲突了几次最后加上即可。于是进行找规律，假设 3 个屋子、四个屋子、5 个屋子，找到如下规律：如果是偶数屋子，二者不见面；如果是 n 个（n 为奇数）屋子，二者每隔（n-1）/2 次睡觉就要碰见一次，结果为：（相遇次数 meettime+ 总次数 k）mod 屋子个数 n。B 猫最终位置还要考虑如果余数为 0，应为最后一个屋子。

题解：看成一个环，A 顺时针，B 逆时针，每隔 n/2 下取整相遇一次，偶数擦肩而过，奇数 B 跳一格相当于也擦肩而过，又回到初始情况 ab 相邻且方向相反。即对于奇数来说，每隔 n/2 步，B 多走一格。
k--
val floor = n / 2
println((k + (n % 2) * k / floor) % n + 1)
标程精妙的使用 k--，使得不用 if 判断余数是否为 0，如果是，要置为 n

未完成的

C

一些球队打比赛，所有队之间赛且仅赛一场，输的队伍 0 分，赢的 +3 分，平的 1 分，如果想让所有球队分数相同，当然都平肯定是相同的，但想让尽量少的比赛是平局，给出队伍数量，按照比赛队伍 1-2，1-3……1-n，2-3，2-4……2-n，3-n……（n-1）-n 的顺序打印出每一场比赛的结果

我的想法：首先考虑可以用邻接矩阵存储每一场比赛的结果；之后考虑像一个图论问题，似乎每一支队伍是一个节点，他指向别的节点代表赢了，别的节点指向它代表输了，尽可能地向图中添加更多边，保证两点间最多一条鞭；之后考虑添加的边必须构成一个环；之后考虑可以先将所有相邻点连成环 3 个点以上，之后连距离为 2 的点看看能不能成环，5 个点 1 个（五角星），6 个点 2 个（六芒星），7 个点 1 个，八个点两个，之后连距离为 3 的点看看能不能成环，7 个点 1 个，8 个点一个，9 个点 3 个，10 个点 1 个，之后看距离为 4 的点，9 个点 1 个，10 个点 2 个；发现如果点总数 mod 间隔==0，那么间隔数就是本间隔的圈个数；最后认为应该对于每个间隔，通过 n>=2* 间隔 +1 判断该间隔是否可以成环，找到第一个未被访问的点，访问他 + 间隔的点，一直访问直到访问到自己成功，访问到已经访问过的点失败，如果成功，之后再找到第一个未访问的点继续访问。

题解：理想情况下，如果是奇数只队伍，那每支队伍赢一半输一半就行，如果是偶数只队伍，每支队伍平一局，剩下的赢一半输一半就行。于是思考以上想法是否可行，奇数可行，让该队伍赢后面的 (n-1)/2 支队伍，输另外的队伍；偶数可行，让该队伍赢后面的 (n-2)/2 只队伍，平正对面的队伍，输其他队伍。

我的收获：
这题目思路很关键，如果按照我的想法，相当于按照整体去考虑问题，而不是一只一只的队伍考虑问题。
索引从 0 开始到 n-1 使得 modn 运算可以代表环状结构的索引