#2932: 加快法


morris1028 (碼畜)

學校 : 國立花蓮高級中學
編號 : 3529
來源 : [114.37.59.62]
最後登入時間 :
2021-07-12 19:00:43
d562. 山寨版磁力蜈蚣 -- jack1 | From: [118.160.205.233] | 發表日期 : 2009-12-06 23:18

    這題請嘗試用一個printf 解決

速度是10倍

 
#2961: Re:加快法


xatier (一串電研的阿飄先生)

學校 : 國立臺中第一高級中學
編號 : 4282
來源 : [140.113.17.175]
最後登入時間 :
2014-12-09 21:57:44
d562. 山寨版磁力蜈蚣 -- jack1 | From: [210.60.107.233] | 發表日期 : 2009-12-11 17:09

    這題請嘗試用一個printf 解決 

速度是10倍

 
請問用"一個printf解決是什麼意思呢?" 
 
我的作法: 
//======================

#include <stdio.h>

int main () {
    int n, i, l, r, num[101];;
    while (scanf("%d", &n) != EOF) {
        for (i = 0; i < n; i++) {
            scanf("%d", &num[i]);
        }
        l = 0;
        r = n-1;
        while (l != r) {
            for (i = l; i <= r; i++) {
                printf("%d ", num[i]);
            }
            puts("");
            l++;
            if (l == r) {
                break;
            }
            for (i = r; i >= l; i--) {
                printf("%d ", num[i]);
            }
            puts("");
            r--;
        }
        printf("%d\n", num[l]);
    }
    return 0;
}
 
 
//===================
 
我是直接用模擬法從頭印過去在印回來
 
直到兩根指針重疊為止
 
AC了,但強力版會TLE
 
請問要如何用您所說的方法加速呢? 
 
我花了15X ms AC,有人只花14m 耶!他們是如何辦到的呢 = =a
 
 
 
#2962: Re:加快法


example (學姊)

學校 : 臺北市立麗山高級中學
編號 : 6634
來源 : [60.250.138.144]
最後登入時間 :
2022-08-09 17:07:42
d562. 山寨版磁力蜈蚣 -- jack1 | From: [118.166.112.155] | 發表日期 : 2009-12-11 17:28

    這題請嘗試用一個printf 解決 

速度是10倍

 
請問用"一個printf解決是什麼意思呢?" 
 
我的作法: 
//======================

#include

int main () {
    int n, i, l, r, num[101];;
    while (scanf("%d", &n) != EOF) {
        for (i = 0; i < n; i++) {
            scanf("%d", &num[i]);
        }
        l = 0;
        r = n-1;
        while (l != r) {
            for (i = l; i <= r; i++) {
                printf("%d ", num[i]);
            }
            puts("");
            l++;
            if (l == r) {
                break;
            }
            for (i = r; i >= l; i--) {
                printf("%d ", num[i]);
            }
            puts("");
            r--;
        }
        printf("%d\n", num[l]);
    }
    return 0;
}
 
 
//===================
 
我是直接用模擬法從頭印過去在印回來
 
直到兩根指針重疊為止
 
AC了,但強力版會TLE
 
請問要如何用您所說的方法加速呢? 
 
我花了15X ms AC,有人只花14m 耶!他們是如何辦到的呢 = =a


 所謂的一個 printf 就是指把結果存成一個長長的字串最後一次輸出

 ps. putchar 又比 printf 更快 !!

 
#3089: Re:加快法


xatier (一串電研的阿飄先生)

學校 : 國立臺中第一高級中學
編號 : 4282
來源 : [140.113.17.175]
最後登入時間 :
2014-12-09 21:57:44
d562. 山寨版磁力蜈蚣 -- jack1 | From: [210.60.107.233] | 發表日期 : 2009-12-22 13:11

    這題請嘗試用一個printf 解決 

速度是10倍

 
請問用"一個printf解決是什麼意思呢?" 
 
我的作法: 
//======================

#include

int main () {
    int n, i, l, r, num[101];;
    while (scanf("%d", &n) != EOF) {
        for (i = 0; i < n; i++) {
            scanf("%d", &num[i]);
        }
        l = 0;
        r = n-1;
        while (l != r) {
            for (i = l; i <= r; i++) {
                printf("%d ", num[i]);
            }
            puts("");
            l++;
            if (l == r) {
                break;
            }
            for (i = r; i >= l; i--) {
                printf("%d ", num[i]);
            }
            puts("");
            r--;
        }
        printf("%d\n", num[l]);
    }
    return 0;
}
 
 
//===================
 
我是直接用模擬法從頭印過去在印回來
 
直到兩根指針重疊為止
 
AC了,但強力版會TLE
 
請問要如何用您所說的方法加速呢? 
 
我花了15X ms AC,有人只花14m 耶!他們是如何辦到的呢 = =a


 所謂的一個 printf 就是指把結果存成一個長長的字串最後一次輸出

 ps. putchar 又比 printf 更快 !!

 

不知道我是不是誤會你的意思了,我照你的意思做結果TLE...

//=======================

#include <stdio.h>
#include <string.h>
char buf[1000], str[1000000];
int main () {
    int n, i, l, r, num[1000];

   
    while (scanf("%d", &n) != EOF) {
        for (i = 0; i < n; i++) {
            scanf("%d", &num[i]);
        }
        l = 0;
        r = n-1;
        while (l != r) {
            for (i = l; i <= r; i++) {
//                printf("%d ", num[i]);
                sprintf(buf, "%d ", num[i]);
                strcat(str, buf);
            }
//            puts("");
            sprintf(buf, "\n");
            strcat(str, buf);
            l++;
            if (l == r) {
                break;
            }
            for (i = r; i >= l; i--) {
//            printf("%d ", num[i]);
                sprintf(buf, "%d ", num[i]);
                strcat(str, buf);
            }
//          puts("");
            sprintf(buf, "\n");
            strcat(str, buf);
            r--;
        }
//      printf("%d\n", num[l]);
        sprintf(buf, "%d\n", num[l]);
        strcat(str, buf);
        printf("%s", str);
    }
    return 0;
}

//=================================

 

其他地方都沒有動

用sprintf把結果存到buffer裡,然後用strcat串接起來,最後再輸出

可是我得到TLE耶...囧TZ

//後面是很黑心的掉出了測資

/*
81
54 98 68 63 83 94 55 35 12 63 30 17 97 62 96 26 63 76 91 19 52 42 55 95 8 97 6 18 96 3 46 21 55 88 14 27 65 8 94 93 52 39 40 52 12 94 89 39 38 6 24 92 88 40 89 12 40 8 86 41 66 15 61 91 11 32 33 59 77 24 46 51 97 17 6 58 16 40 84 28 51
2
97 99
91
54 98 68 63 83 94 55 35 12 63 30 17 97 62 96 26 63 76 91 19 52 42 55 95 8 97 6 18 96 3 46 21 55 88 14 27 65 8 94 93 52 39 40 52 12 94 89 39 38 6 24 92 88 40 89 12 40 8 86 41 66 15 61 91 11 32 33 59 77 24 46 51 97 17 6 58 16 40 84 28 51 28 56 46 60 17 51 72 74 16 67
*/

 
ZeroJudge Forum