Catshao

用户名：Catshao

访问量：29119

签　名：

stO KHIN Orz

等　　级
排　　名	159
经　　验	7166
参赛次数	6
文章发表	46
年　　龄	12
在职情况	学生
学　　校	双语
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2020年第十一届省赛真题-整数小拼接
浏览：1481

蓝桥杯2020年第十一届省赛真题-BST插入节点问题
浏览：548

蓝桥杯2020年第十一届省赛真题-八次求和
浏览：557

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

建议改为：测测你的快读（雾）

　　作者: Catshao　　　　发表时间：2022-02-17 13:00:52 浏览：58　|　评论：0　

原题链接：存图必备

vector 存法：

```cpp
#include <bits/stdc++.h>
using namespace std;

namespace io {
    constexpr int IN_BUF = 1 << 18, OUT_BUF = 1 << 17; // 实测这一组 IN_BUF 和 OUT_BUF 效率最好，并不是缓冲区越大越好。
    char ibuf[IN_BUF], obuf[OUT_BUF], *i1, *i2, *o; // 因为 i1、i2 为全局变量，最开始全是 NULL ，满足 i1 == i2 。

#define STREAMBUF

class init {
    public:
        init() {
            o = obuf;
        }

~init() {
            fwrite(obuf, o - obuf, sizeof(char), stdout);
        }
    } bminit;

#ifdef STREAMBUF
    inline int gc() { // 这里返回值必须是 int ，因为 isdigit 传入参数为 int ，避免了一次强制转换；还有这里尽量压行，不压行会变慢，原因未知。本来 gc 使用的是宏定义，后来我发现写成这样效率不会变慢
        return __builtin_expect(i1 == i2, 0) && (i2 = (i1 = ibuf) + cin.rdbuf()->sgetn(ibuf, IN_BUF), i1 == i2) ? EOF : *i1++;
    }
#else
    inline int gc() { // 实际测评发现 streambuf 只比 fread 快一点
        return __builtin_expect(i1 == i2, 0) && (i2 = (i1 = ibuf) + fread(ibuf, sizeof(char), IN_BUF, stdin)), i1 == i2 ? EOF : *i1++;
    }
#endif

class fi {
    public:
        inline fi &operator>>(int &x) {
            static int ch; // isdigit 传入参数为 int ，为避免强制转换 gc 的返回值、ch 均为 int。这样输入整数的效率提高，输入字符串的效率降低（需要强制类型转换）
            static bool flag; // 包括上面，这里的 static 是必须的，否则会变慢
            flag = false; // 不可以写成 static bool flag = false;
            while (!isdigit(ch = gc())) {
                if (ch == EOF) {
                    return *this;
                }
                flag = ch == '-'; // 为了处理 "-  18" 这种情况，这时候输入的应为 18 而不是 -18。
            }
            for (x = 0; isdigit(ch); ch = gc()) {
                x = x * 10 + (ch ^ '0'); // 在 '0' ~ '9' 这个区域内正好 ch - '0' == ch ^ '0' ，其他字符不一定。
            }
            if (flag) {
                x = -x;
            }
            return *this;
        }
    } cin;

inline void pc(const char &ch) {
        if (__builtin_expect(o == obuf + OUT_BUF, 0)) {
            fwrite(obuf, OUT_BUF, sizeof(char), stdout);
            o = obuf;
        }
        *o++ = ch;
    }

class fo {
    public:
        inline fo &operator<<(int x) { // 想输出 long long 将传参改为 long long x 即可。不能写成 const int &x ，因为 x 会被修改
            if (x < 0) {
                pc('-');
                x = -x;
            }
            static int s[20], top; // LLONG_MAX 也只有 19 位，s 有 20 位，也能输出 long long
            top = 0;
            do {
                s[top++] = x % 10;
                x /= 10;
            } while (x);
            while (top) {
                pc(s[--top] + '0');
            }
            return *this;
        }

inline fo &operator<<(const char &c) {
            pc(c);
            return *this;
        }
    } cout;
}

const int MAX_V = 1000000;

vector<int> p[MAX_V + 5];

int main()
{
    int n, a;
    io::cin >> n;
    for (int i = 1; i <= n; ++i) {
        io::cin >> a;
        p[a].push_back(i);
    }
    for (int i = 1; i <= MAX_V; ++i) {
        for (const auto j : p[i]) {
            io::cout << j << ' ';
        }
        io::cout << '\n';
    }
    return 0;
}
```

链式前向星存法：

```cpp
#include <bits/stdc++.h>
using namespace std;

#define STREAMBUF

class init {
    public:
        init() {
            o = obuf;
        }

~init() {
            fwrite(obuf, o - obuf, sizeof(char), stdout);
        }
    } bminit;

inline fo &operator<<(const char &c) {
            pc(c);
            return *this;
        }
    } cout;
}

const int MAX_N = 3000100;
const int MAX_V = 1000000;

namespace myList {
    const int MAX_POOL = 3000100;

class node {
    public:
        int v;
        node *nxt;
    };

node memPool[MAX_POOL];
    node *memTop;
    node *nil;

inline node *newNode() {
        return memTop++;
    }

inline node *newNode(int v) {
        node *cur = newNode();
        cur->v = v;
        cur->nxt = nil;
        return cur;
    }

class init {
    public:
        init() {
            memTop = memPool;
            nil = newNode();
            nil->nxt = nil;
        }
    } bminit;

class list {
    public:
        node *head[MAX_N], *tail[MAX_N];

list(int n) {
            fill(head + 1, head + n + 1, nil);
        };

void append(int x, int y) {
            if (head[x] == nil) {
                head[x] = tail[x] = newNode(y);
            } else {
                tail[x]->nxt = newNode(y);
                tail[x] = tail[x]->nxt;
            }
        }
    };
}

int main()
{
    int n, a;
    io::cin >> n;
    myList::list p(MAX_V);
    for (int i = 1; i <= n; ++i) {
        io::cin >> a;
        p.append(a, i);
    }
    for (int i = 1; i <= MAX_V; ++i) {
        myList::node *cur = p.head[i];
        while (cur != myList::nil) {
            io::cout << cur->v << ' ';
            cur = cur->nxt;
        }
        io::cout << '\n';
    }
    return 0;
}
```

结论：链式前向星在单次遍历时比 vector 快，多次遍历应该会慢。

0.0分

0 人评分

新上线《蓝桥杯辅导》课程，近五年的蓝桥杯省赛与国赛真题都有，从读题开始理解题意、梳理思路、实现代码再提交评测全过程，可有效提升获奖比例甚至进国赛！课程介绍、试听请猛击这里

Catshao

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

【明明的随机数】（C语言代码）

【蟠桃记】（C语言代码）

【绝对值排序】（C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

建议改为：测测你的快读（雾）

评论区

精彩推荐

A+B for Input-Output Practice (V) （C语言代码）

1071题解

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

The 3n + 1 problem （C语言代码）

C语言程序设计教程（第三版）课后习题12.2 （C语言代码）

矩阵的对角线之和（C语言代码）

printf基础练习（C语言代码）

C二级辅导-等差数列（C语言代码）

马拦过河卒（C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

Catshao

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

【明明的随机数】 （C语言代码）

【蟠桃记】 （C语言代码）

【绝对值排序】 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

建议改为：测测你的快读（雾）

评论区

精彩推荐

A+B for Input-Output Practice (V) （C语言代码）

1071题解

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

The 3n + 1 problem （C语言代码）

C语言程序设计教程（第三版）课后习题12.2 （C语言代码）

矩阵的对角线之和 （C语言代码）

printf基础练习 （C语言代码）

C二级辅导-等差数列 （C语言代码）

马拦过河卒 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

【明明的随机数】（C语言代码）

【蟠桃记】（C语言代码）

【绝对值排序】（C++代码）

　　评论区

矩阵的对角线之和（C语言代码）

printf基础练习（C语言代码）

C二级辅导-等差数列（C语言代码）

马拦过河卒（C语言代码）