题是李科和罗耀燊出的，还是很不错的，辛苦二位了～
之前我也没看题，4点左右上来秒了3个水题，就没往下看。B题数据后来发现有问题，赛后rejudge有两个过的。
恭喜大工的胡骏获得NEUACM二月月赛第一，恭喜软信1001杨逸颢获得东大第一。但愿下次月赛东大的可以登顶。积分和新学期集训队名单适时公布。
1001. John’s Problem I
解法：DP
难度：中等
虽然只有HIT的大牛过了这个题，但是其实这并不是一个很难的dp。
可以开两个900 × 8100的数组来保存状态。分别用来记录和为i平方和为j时得到的数的最小位数和这个数的第一位(不是最后一位)。
因为可能存在位数一样但是大小不一样的情况，如果是从前往后推的话那么最后一位不同并不能决定出两个数谁大谁小，但是第一位不同则肯定一个大一个小。所以从后往前推，时间复杂度900*8100*9.
因为不可能出现含0的位。
1002. John’s problem II
解法：排序
难度：难(因为题目不仅开始描述有缺陷，后面发现数据也有问题)。
用基数排序或者按照坐标二级排序就可以解决。假设一个x轴上的点xi，如果在xi建造邮局的话，那么x坐标<=xi的人的数目应该>=总人数的一半。因为如果再往右走一步，那增加的距离和就是左边的人数减去右边的人数。所以只要按照坐标值排序，然后从最左边往最右边累加人数就行，如果人数和大于或者等于总人数的一半，就可以在这个地方建造邮局了。注意总人数为奇数的情况。
1003. A hard problem
解法：数论
难度：会者不难，难者不会
传说中有个叫哥德巴赫猜想的东西，据说是小学知识，但是我也不会。本题是Top Coder div2某次比赛的第一题。陈景润证明的“1+2”就是“任一充分大的偶数都可以表示成二个素数的和”。由此也可推出“任一大于7的奇数都可写成三个质数之和”。
1004. Choose a Way
解法：Floyd
难度：基础
Floyd的三重循环里面有一个dis[i][j] = min(d[i][j], d[i][k] + d[k][j])，
意即[i，j]之间的最短距离=min([i，j]当前距离，[I，k]之间的最小距离+[k，j]之间的最小距离)。现在只要把dis[i][j]的含义改成[i，j]之间的耗费最高的一条路的耗费，所以可以把原式改成:
dis[i][j] = min(d[i][j], max(d[i][k], d[k][j]))
我是出后4题的罗耀燊（shen 第一声）。
E题：
题意是你知道某两个未知正整数的和以及它们的最小公倍数，求出这两个数。傻傻的我出的数据量太XX弱智了以致没考出这条题目的精粹所在。结果真变成了“An Easy Problem”。
我赛后会再换个再大数量级别的数据力求大家用O(1)的算法来做出这题来，而不是比赛中很多人用到的枚举等方法水过。如果你想再做一遍的可以先跳过以下的题解，这题想着推导过程是很有意思的。
首先我们知道题目是可以列出两条式子 x+y=A 和 x*y/gcd(x,y)=B 。接着我们将用 x0*gcd(x,y) 带入x中，同样 y0*gcd(x,y)代入y中那现在 得到新的两条式子 gcd(x,y)*(x0+y0)=A 和 gcd(x,y)*x0*y0=B 。其实应该马上能反应到 gcd(A,B)==gcd(x,y) ，因为如果(x0+y0) 和 x0*y0 还能提出大于1的公因子的话 那显然原来假设gcd(x,y)就不是x和y的最大公约数了（也就是说矛盾了）。
由此我们再能得到 x0+y0=A0 x0*y0=B0 (A=gcd(A,B)*A0, B=gcd(A,B)*B0) 由此我们能得到一条一元二次方程组 (A0-x)*x=B0 x的两个解就是x0和y0了。
整理得 x^2-A0*x+B0=0 由求根公式得 当Δ=(-A0)^2-4*B0＜0时自然是没解咯。 Δ=(-A0)^2-4*B0≥0时，x=[A0±(A0^2-4*B0)^(1/2)]/2 但还要注意一些情况 ：Δ的值必须是能开根号的，否则也算无解。有些细心的同学还会问需不需要判断[A0±(A0^2-4*B0)^(1/2)]能被2整除。分析一下，无论A0是奇数还是偶数式子结果都是偶数的。最后x0*gcd(A,B) 和 y0*gcd(A,B)就是这题的解了。
这以上就是我对这题的认识。比赛中的题目数据弱是我的问题，没有让这题发挥到让大家深入去想这个问题的效果，真的很不好意思。
F题：
有类似的数学题，我是放大了数据范围，因此需要用到记忆化搜索的的技巧，当然你也可以递推。
可以假设一个函数f(m,n) 代表的意思是 m个橙子 n个盘，这n个盘里的球数是从小到大来放的。那现在 能推出 f(m,n)=f(m-n,n)+f(m,n-1) 对于第一个盘子要放就一排地放，要么不放就对剩下的n-1盘子继续。当然要对边界有些界定。n<=0时 当然是0 ，而m<0时同样也是。但m=0时应该是一种。
G题：
原本是要考察一下gcd(|x1-x2|,|y1-y2|)+1这条式子的。但后来想会不会说太偏了，就改成直接给出了。gcd(|x1-x2|,|y1-y2|)+1是(x1,y1)与(x2,y2)两点间（包括两端整数点）整数点的数目。接着就赤裸裸的MST了。应该是prim的算法比较好点。kruskal的不知道会不会超时。
H题：
是《算法导论》352 353 习题的模型。当一个最小生成树搭好后添加一条新边（没新端点的）进去后就是多了一个环，去掉这环上最长的边，就又保持最小生成树了。能去找找次小生成树的资料。在用prim的过程中能建个表Max_Edge[i][j]记录点i到点j的最长边，每次查询是就用新边和这表里头对应的值比较一下，比原来最大边大的话就还是原来最小生成树的值否则就是原数值减去原边加上新边的值了。解出这题应该没什么问题的了。（其实当初最担心的数据是这题的数据，但被大工的大神第一道秒掉的就是这题。实在是出于意外，但也帮我长抒一气）
小弟第一次出题，诸多缺漏恳请原谅。还有就多加一句：题目的模型是学习了各大oj或是书上模型，仅用于学习和交流用途。
发表回复