Difference between revisions of "NEERC 2008, Eastern subregion quarterfinals"
Jump to navigation
Jump to search
(3 intermediate revisions by the same user not shown) | |||
Line 7: | Line 7: | ||
=== Problem C === | === Problem C === | ||
+ | |||
+ | 此题坑 | ||
+ | |||
+ | 题意:给定一条链(可能有重复结点),求一条不改变起点终点以及路径先后顺序的最短路。 | ||
+ | |||
+ | 题解:对于起点和终点跑一遍最短路,注意记录路径时要记录结点是第几个,而不是标号。 | ||
+ | |||
=== Problem F === | === Problem F === | ||
Line 16: | Line 23: | ||
=== Problem J === | === Problem J === | ||
+ | |||
+ | 题意:给定一个数字的数位和和数位平方和,求最小的不超过100位满足的数,不存在输出impossible。 | ||
+ | |||
+ | 题解:因为不超过100位,所以和以及平方和最大分别为900,8100,因此就是个裸的背包问题。 | ||
+ | |||
=== Problem K === | === Problem K === | ||
+ | |||
+ | 题意:给定一个正三角形,要求在里面加三个点,外面加三个点,使得至少有九个正三角形。 | ||
+ | |||
+ | 题解:内部加一个中心,外部加三个旁心,这样就有八个了,在在中间随便加两个能够成正三角形的点即可(三等分点)。 |
Latest revision as of 13:42, 26 March 2018
oxx1108
Problem B
题意:给定一些百万富翁初始位置和钱数,以及一些移动,求每个城市钱财和最多(不能并列)的天数。
题解:用set模拟一下即可。有两个注意的地方,一个是钱数不能除掉一百万,因为没说一定是一百万的倍数,另要注意set里只有一个元素的情况。
Problem C
此题坑
题意:给定一条链(可能有重复结点),求一条不改变起点终点以及路径先后顺序的最短路。
题解:对于起点和终点跑一遍最短路,注意记录路径时要记录结点是第几个,而不是标号。
Problem F
签到
Problem H
签到
Problem J
题意:给定一个数字的数位和和数位平方和,求最小的不超过100位满足的数,不存在输出impossible。
题解:因为不超过100位,所以和以及平方和最大分别为900,8100,因此就是个裸的背包问题。
Problem K
题意:给定一个正三角形,要求在里面加三个点,外面加三个点,使得至少有九个正三角形。
题解:内部加一个中心,外部加三个旁心,这样就有八个了,在在中间随便加两个能够成正三角形的点即可(三等分点)。