题解 P1720 【月落乌啼算钱】

YXH咸鱼 · 2018-10-25 17:28:43 · 题解

看到这里没有链表的题解，于是来一发

本做法的本质是用链表模拟数组递推， 可以极大的节省空间提高代码难度

优点: 1.训练思维能力 2.避免别人抄你代码

代码如下~

#include<iostream>
#include<cstdio>
#define REG register
#define LLI long long

/* 链表结构体 */
struct Node {
    LLI va;
    Node *next;
    Node(LLI x) {va = x;}
} *head;

int n;

int main() {
    REG int i; REG Node *t;

    /* 初始化 */
    head = new Node(0);
    t = head;
    head = new Node(1);
    head -> next = t;
    t = head;
    head = new Node(1);
    head -> next = t;

    /* 输入 */
    scanf("%d", &n);

    /* 递推 */
    for(i = 3; i <= n; i++) {
        /* 显然的 */
        t = new Node(head -> va + head -> next -> va);
        t -> next = head;
        head = t;
        /* 记得delete，防止内存泄漏 */
        delete head -> next -> next;
    }

    /* 防止 n <= 2 的情况，不能特判哦 */
    i--; while(i > n) head = head -> next, i--;

    /* 输出 */
    printf("%lld.00\n", head -> va);

    /* 记得delete，防止内存泄漏 */
    delete head -> next;
    delete head;
    delete t;

    return 0;
}

(NOIP初赛都用过双栈模拟数组，为什么不能用链表模拟数组)