NEERC 2008, Eastern subregion quarterfinals

oxx1108

Problem B

题意：给定一些百万富翁初始位置和钱数，以及一些移动，求每个城市钱财和最多（不能并列）的天数。

题解：用set模拟一下即可。有两个注意的地方，一个是钱数不能除掉一百万，因为没说一定是一百万的倍数，另要注意set里只有一个元素的情况。

Problem C

此题坑

题意：给定一条链（可能有重复结点），求一条不改变起点终点以及路径先后顺序的最短路。

题解：对于起点和终点跑一遍最短路，注意记录路径时要记录结点是第几个，而不是标号。

Problem F

签到

Problem H

签到

Problem J

题意：给定一个数字的数位和和数位平方和，求最小的不超过100位满足的数，不存在输出impossible。

题解：因为不超过100位，所以和以及平方和最大分别为900，8100，因此就是个裸的背包问题。

Problem K

题意：给定一个正三角形，要求在里面加三个点，外面加三个点，使得至少有九个正三角形。

题解：内部加一个中心，外部加三个旁心，这样就有八个了，在在中间随便加两个能够成正三角形的点即可（三等分点）。