竹園論壇

標題: 7 - 加加加加加速度 [打印本頁]

---

作者: jd3    時間: 2014-6-4 23:28
標題: 7 - 加加加加加速度




題意釐清：
這題沒什麼技巧
就是看懂目的要算斜率
也就是一直差分到剩下一個值
(這敘述不好懂是我的錯...)

解題方法：
根據實測
目前設定只要IO用scanf和printf就幾乎一定會過(如果你沒有包太多函式的話)


O(N^2)做法：直接陣列差分下去爆(若改時限後可能不會過(先讓我慚愧一下))

O(N)的做法：觀察在差分時的運算
化簡後會發現最後的值會呈現很漂亮的2項式展開的係數、正負相間
要注意的是數列有機數項和有偶數項會影響是正的開頭還是負的開頭
這邊只要用a b c d往下畫出來舉個例就能瞭解了


不過就算有O(N)的解法，速度快一些，還是會可能卡IO

CODE：
O(N^2)：

#include<iostream>

#include<cstdio>

using namespace std;

int main()

{

    int t;

    int n;

    int list[100];

   

   

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        for(int i = 1 ; i <= n+1 ; i++)

            scanf("%d",&list[i]);

        

        for(int i = n ; i > 0 ; i--)

        {

            for(int j = 1 ; j <= i ; j++)

            {

                list[j] = list[j+1]-list[j];

            }

        }

   

        printf("%d\n",list[1]);

    }

   

    return 0;

}

O(N)：

#include<iostream>

#include<cstdio>

using namespace std;

int main()

{

    int t;

    int n;

    int list[100];

    int cn;

   

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        for(int i = 0 ; i <= n ; i++)

            scanf("%d",&list[i]);

        

        

        int ans = 0;

        cn = 0;   

        for(int i = 0, j = ((-(n&1))<<1)+1 ; i <= n ; i++, j*=(-1))

        {

            if(cn==0)

                cn=1;

            else

                cn = cn*(n-i+1)/i;

            ans += list[i]*cn*j;

        }

        

        printf("%d\n",ans);

    }

   

    return 0;

}

---

歡迎光臨 竹園論壇 (http://forum.tfcis.org/)

Powered by Discuz! X3.2