Blog·Tanky WooABOUTRSS

HDOJ 2515 Yanghee 的算术

24 Jul 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

呼呼,先背题目给骗了,看了刘如佳老师的《算法艺术》那本书里,在讲递推时给出了这个例题,看到方法有点麻烦,时间复杂度是O(n^3),碰巧在HDOJ上找到了这题,无奈下不了手。。。

结果和论坛的朋友一讨论,才发现自己被这题骗了,按照看清题目后的感觉来说,这题就是水题了~~~呼呼。

为什么呢?因为他输入给出的就是先把a1从a2一直加到an,然后在a2从a3一直加到an,等于顺序已经搞定,前几个数都确定了。。。就这样~~~~水过。

代码:

 // Author: Tanky Woo
// HDOJ 2515
//Accepted 2515 0MS 212K 572B C++ Tanky Woo 
#include 
using namespace std;
// www.wutianqi.com
int result[1300];
int yanghee[55];
int main()
{
    //freopen("input.txt", "r", stdin);
    int n, num;
    scanf("%d", &n;);
    num = n*(n-1)/2;
    for(int i = 1; i <= num; ++i)
        scanf("%d", &result;[i]);
    // A1+A2=R1, A1+A3=R2,A2+A3=Rn
    // A2 = (R1-R2+Rn)/2
    yanghee[2] = (result[1]-result[2]+result[n])/2;
    yanghee[1] = result[1]-yanghee[2];
    for(int i = 2; i <= n-1; ++i)
        yanghee[i+1] = result[i]-yanghee[1];
    for(int i = 1; i <= n; ++i)
        printf("%d\n", yanghee[i]);
    return 0;

}