image frame

听寒's Blog

记录一下hexo升级

折腾记录 
1
2
3
4
5
6
7
8
9
10
cnpm install -g npm-check           # 检查之前安装的插件，都有哪些是可以升级的 
cnpm install -g npm-upgrade         # 升级系统中的插件
npm-check
npm-upgrade

# 更新 hexo 及所有插件
cnpm update

# 确认 hexo 已经更新
hexo -v

CCF201912-4 区块链

编程练习

好像还是大模拟题。。
熟练运用STL，知晓其底层所用实现效率即可。。。
跟算法倒是没多大关系。。。

因为输入的查询必定晚于输入相关节点生成，实际上确保了查询时刻升序。
为了实现查询给定时刻的状态，记录所有输入与中间的节点传输数据，直到查询时再模拟运行到查询时刻，剩下的不模拟直到下一个查询时刻输入。

链的传输操作（transmission）和新块的创建操作（creation），使用哈希表unordered_map记录。
考虑到操作记录的信息量比较大，怕爆空间，完成操作处理后，会将其从哈希表中擦除。

为了按时间顺序处理，同时保证高效率+记录的时间点不能重复，使用set记录了所有发生变化操作的时间点（timepoints）。
在模拟时，从timepoints中顺序取出，即可按照时间点顺序处理，然后查询是否有对应时刻的transmission与creation。
在完成相应时刻的模拟之后，会移除set中对应的时间点。这是为了后续再次查询时不会重复处理已经处理过的时间点。

虽然transmission和creation擦除后，对应时间点的操作记录已经为空，那么timepoints即使不擦除已处理元素，也不会再影响结果正确性。但是如果不擦除timepoints，遍历时间点时仍然会造成时运行时间上的浪费。
timepoints已处理过的时间点必须动态擦除，否则重复遍历已处理过的时间点，会导致程序运行时间超时。
注意STL容器erase方法的用法

代码长度 3.234KB
编程语言 C0X
评测结果 正确
得分 100
时间使用 3.328s
空间使用 16.00MB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;

using nodeidT = int;
using chainT = vector<nodeidT>;
using broadcastMsg = pair<nodeidT, chainT>; // 发出节点ID，主链
vector<vector<nodeidT> > rel; // 节点-邻接表{相连节点...}
vector<chainT> chain;// 节点-主链{主链节点...}
unordered_map<int, vector<pair<nodeidT, int>>> creation; // 时间- {{节点，块编号}...}
unordered_map<int, vector<broadcastMsg> > transmission; // 时间- {节点，链{接收链组成节点...｝}...}
set<int> timepoints;

int n;
int delay;

inline void gen(int node, int t, int id) {
    creation[t].push_back({node, id});
    timepoints.insert(t);
}

inline void broadcastNeighbor(int node, int tp) {
    transmission[tp + delay].push_back({node, chain[node]});
    timepoints.insert(tp + delay); // 不要忘记维护时间点表
}

inline void query(int node, int t) {
    auto it = timepoints.begin();
    for (; it != timepoints.end() && *it <= t; ++it) {
        int tp = *it;
        // 先处理接收
        if (transmission.count(tp)) {
            for (const auto &msg: transmission[tp]) {
                const auto &fromid = msg.first;
                const auto &sentchain = msg.second;
                for (const auto &toid: rel[fromid]) {
                    if (chain[toid].size() < sentchain.size()
                        || (chain[toid].size() == sentchain.size() && chain[toid].back() > sentchain.back())
                            ) {
                        chain[toid] = sentchain; // 接受更新
                        broadcastNeighbor(toid, tp); // 向邻居广播自己的主链
                    }
                }
            }
        }
        transmission.erase(tp);
        // 处理创建
        if (creation.count(tp)) {
            for (const auto &p: creation[tp]) {
                const auto &nodeid = p.first;
                const auto &blockid = p.second;
                chain[nodeid].push_back(blockid); // 主链延长
                broadcastNeighbor(nodeid, tp); // 向邻居广播自己的主链
            }
        }
        creation.erase(tp);
    }
    timepoints.erase(timepoints.begin(), it); // 此处erase使用注意，不能在循环中擦除当前key，否则当前迭代器失效无法自增至下一元素
    // 输出该时间点状态
    cout << chain[node].size();
    for (int b: chain[node]) {
        cout << " " << b;
    }
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    int m;
    cin >> n >> m;
    rel.resize(n + 1);
    chain.resize(n + 1, chainT(1, 0));
    creation.reserve(2000);
    transmission.reserve(2000);
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        rel[u].push_back(v);
        rel[v].push_back(u);
    }
    int k;
    cin >> delay >> k;
    for (int i = 1; i <= k; ++i) {
        int a, b, c;
        cin >> a >> b;
        if (cin.get() == '\n' || cin.eof()) {
            query(a, b);
        } else {
            cin >> c;
            gen(a, b, c);
        }
    }
}

CCF201912-3 化学方程式

编程练习

用到编译原理的递归下降法，类似写语法分析器，
不过不需要生成AST，只需要统计元素个数即可。

代码长度 3.673KB
编程语言 C0X
评测结果 正确
得分 100
时间使用 156ms
空间使用 632.0KB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <bits/stdc++.h>
using namespace std;
using element = string;

map<element, int> &operator+=(map<element, int> &a, const map<element, int> &b) {
    for (const auto &p : b) {
        a[p.first] += p.second;
    }
    return a;
}
map<element, int> operator*(int coef, const map<element, int> &b) {
    map<element, int> r;
    for (const auto &p : b) {
        r[p.first] = p.second * coef;
    }
    return r;
}

map<element, int> parseTerm(const string &str);
map<element, int> parseFormula(const string &str);
size_t parseCOEF(const string &str, size_t pos, int &coef);

map<element, int> parseTerm(const string &str) {
    map<element, int> r;
    if (str.front() == '(') {
        return parseFormula(str.substr(1, str.size() - 2));
    }
    ++r[str];
    return r;
}

map<element, int> parseFormula(const string &str) {
    map<element, int> r;
    size_t i = 0;
    int level = 0;
    string term;
    while (i < str.size()) {
        if (level > 0) {
            if (str[i] == '(') {
                ++level;
            } else if (str[i] == ')') {
                --level;
            }
            term += str[i];
            ++i;
        } else {

            // 在level=0，只有小写才代表上一项没有结束。
            if (islower(str[i])) {
                term += str[i];
                ++i;
            } else {
                // level=0，非小写一律代表上一个符号已经结束。
                // 此处处理
                if (!term.empty()) {
                    int co = 0;
                    i += parseCOEF(str, i, co);
                    r += co * parseTerm(term);
                    term.clear();
                }
                if (str[i] == '(') {
                    ++level;
                    term = str[i];
                    ++i;
                } else if (isupper(str[i])) {
                    term = str[i];
                    ++i;
                }
            }

        }

    }
    // 不要忘了最后可能还有一项，循环中可能没有处理。
    if (!term.empty()) {
        int co = 0;
        parseCOEF(str, i, co);
        r += co * parseTerm(term);
        term.clear();
    }
    return r;
}

// 返回coef长度
size_t parseCOEF(const string &str, size_t pos, int &coef) {
    if (pos >= str.size()) {
        coef = 1;
        return 0;
    }
    coef = 0;
    size_t i = pos;
    if (isdigit(str[i])) {
        coef = str[i] - '0';
        ++i;
        while (i < str.size() && isdigit(str[i])) {
            coef = coef * 10 + (str[i] - '0');
            ++i;
        }
    } else {
        coef = 1;
    }
    return i - pos;
}

map<element, int> parseExpr(const string &str) {
    map<element, int> r;
    size_t i = 0, ni = str.find('+');
    if (ni == string::npos) {
        int coef, coeflen;
        coeflen = parseCOEF(str, 0, coef);
        r += coef * parseFormula(str.substr(coeflen));
    } else
        while (i != string::npos) {
            int coef, coeflen;
            coeflen = parseCOEF(str, i, coef);
            if (ni != string::npos) {
                r += coef * parseFormula(str.substr(i + coeflen, ni - (i + coeflen)));
            } else {
                r += coef * parseFormula(str.substr(i + coeflen));
            }
            if (ni != string::npos) {
                i = ni + 1;
                ni = str.find('+', i);
            } else {
                i = ni;
            }
        }
    return r;
}

bool legalEquation(const string &str) {
    size_t i = str.find('=');
    if (i == string::npos) return false;
    return parseExpr(str.substr(0, i)) == parseExpr(str.substr(i + 1, str.size()));
}

int main() {
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    cin.get();
    while (n--) {
        string e;
        getline(cin, e);
        cout << (legalEquation(e) ? "Y" : "N") << endl;
    }
}

CCF201912-2 回收站选址

编程练习

代码长度 1.610KB
编程语言 C0X
评测结果 正确
得分 100
时间使用 15ms
空间使用 748.0KB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;

set<pair<int, int>> p;
vector<int> cnt(5);
set<pair<int, int>> pre;

int main() {
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    int minx = 100000, miny = 100000;
    int maxx = -1, maxy = -1;
    while (n--) {
        int xi, yi;
        cin >> xi >> yi;
        p.emplace(xi, yi);
        pre.emplace(xi, yi);
        pre.emplace(xi-1, yi);
        pre.emplace(xi+1, yi);
        pre.emplace(xi, yi-1);
        pre.emplace(xi, yi+1);
        if (xi < minx) {
            minx = xi;
        }
        if (xi > maxx) {
            maxx = xi;
        }
        if (yi < miny) {
            miny = yi;
        }
        if (yi > maxy) {
            maxy = yi;
        }
    }
    for (auto xp : pre) {
        int &xx = xp.first;
        int &yy = xp.second;
            if (p.count({xx, yy})
                && p.count({xx, yy - 1})
                && p.count({xx, yy + 1})
                && p.count({xx - 1, yy})
                && p.count({xx + 1, yy})
                    ) {
                int score = 0;
                if (p.count({xx - 1, yy - 1})) {
                    ++score;
                }
                if (p.count({xx - 1, yy + 1})) {
                    ++score;
                }
                if (p.count({xx + 1, yy - 1})) {
                    ++score;
                }
                if (p.count({xx + 1, yy + 1})) {
                    ++score;
                }
                ++cnt[score];
            }
    }
    cout << cnt[0] << endl
         << cnt[1] << endl
         << cnt[2] << endl
         << cnt[3] << endl
         << cnt[4] << endl;
}

CCF201912-1 报数

编程练习

代码长度 1.161KB
编程语言 C0X
评测结果 正确
得分 100
时间使用 0ms
空间使用 672.0KB

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
int times[4] = {0, 0, 0, 0};

bool skip(int x) {
    if (x % 7 == 0) return true;
    while (x > 0) {
        if (x % 10 == 7) return true;
        x /= 10;
    }
    return false;
}

int main() {
    assert(!skip(6)); assert(!skip(1));
    assert(skip(7));  assert(skip(17));  assert(skip(71)); assert(skip(711)); assert(skip(117)); assert(skip(171));
    ios_base::sync_with_stdio(false);
    // n: 要喊的数的数量
    // i: 要喊的数
    // cnt：已喊的数
    int n, i=1;
    cin >> n;
    for(int cnt=0; cnt<n; i++) {
        int who = (i-1)%4;
        if(skip(i)) {
            times[who]++;
        } else {
            cnt++;
        }
    }
    cout << times[0] << endl
    << times[1] << endl
    <<  times[2] << endl
    <<  times[3] << endl;
}

PAT甲级证书GET√

日常生活

一举满分。。不枉我肝了几个月的题。

第一题其实确实最简单，却诡异地通过率最低。。4%也是醉了。
猜测可能是PAT之前有几次在第一题挖坑，大家被挖怕了。
然后这题确实不好测试，测试用例不给复制。。见鬼那么长又不可能自己对着打一遍。
我是自己瞎编了个图形输入，然后复制粘贴出所需输入。。来测试。

第二题又是熟悉的链表。这次题目堵住了以前以往同类题目可以偷偷转换为顺序结构暴力解掉的小漏洞..
老老实实写链式结构反转。两个迭代变量搞即可，考逻辑思维和代码基本功。

第三题存储关系用邻接矩阵也不会爆空间，直接双重for遍历也没爆时间。。。
可以配合哈希表（unordered_set）提升查询速度，
感觉有点水。

第四题Cartesian Tree，结合了堆和树两个知识点。
我们在学习二叉树时，知道根节点和中序遍历顺序，就可以构建整个树。
这里其实对于每一颗树（包括其子树），最小的数就是根节点，这是由最小堆的性质保证的，而输入给出了中序遍历，自然可以构建出整棵树。
解析建树采用递归写法，层序输出采用队列来BFS。

go module如何发布v2及更高版本号

直接git打tag就可以发布新版本，但在发布v2以上版本时遇到了一些问题，记录一下。

在本文中，
库（被调用方）路径均以github.com/onelib/mylib代替，
业务程序（调用方）路径均以github.com/caller/myservice代替）

还是按照老方法，直接git打tag，发布。结果在调用方就出现了问题。

更新go mod时直接报错：

require github.com/onelib/mylib: version “v2.x.x” invalid: module contains a go.mod file, so major version must be compatible: should be v0 or v1, not v2

先说结论：

  • 如果你是库作者，如何处理这个错误，请见本文后续的高版本号（>=v2）如何良好支持go module特性一节。
  • 如果你是库用户，遇到这个错误，那么这属于库作者对go module特性支持不完善，请向其反馈。如果你着急使用，可以参见本文下面的临时解决方案一节。

库用户如何调用【未良好支持go module特性的库】的临时解决方法

库用户临时凑合调用的方法：在go.mod，import时在版本号后面加+incompatible，如

1
2
3
4
5
module github.com/caller/myservice

import (
	github.com/onelib/mylib v2.0.0+incompatible
)

（仅作为库未良好支持go module时，调用者可以采用的补丁方案）

但是这样做有缺点，
无法做到同时import多个版本。甚至在不同的文件里都不行，即使你一个文件或目录里只用了一个版本，整个项目也只能导入一份版本。
这样就不能让旧代码仍然使用旧版本，而必须整个项目一起升级到新版，所以有时会造成旧代码的破坏。
同时一些IDE可能由于不识别这种版本号标识而报错。

如果我们仅仅是调用者而非编写者，而实际编写者又没有支持go module时，在确定不会造成旧版本代码破坏后，我们就可以使用这种方案临时解决调用问题。

如果我们就是库的编写者，请继续看下节。

库作者发布高版本号（主版本号>=v2）如何良好支持go module特性

如果你是库作者，更完美的解决方案是：

将库的go.mod中的moulde名称后面增加版本号/vx

如
module github.com/onelib/mylib
->
module github.com/onelib/mylib/v2

注意，文件结构不需要做任何改变，不需要建立v2或者vn文件夹，增加的“/vx”仅仅用于require/import时区分主版本号。

调用时也仍以库文件中声明的package xxx为准来进行xxx.FuncX()调用，而与go.mod中module怎么写的无关。

而后重新在git中打tag v2.x.x，发布。调用方就可以愉快地使用了。

代码示例：

go.mod

1
2
3
4
5
module github.com/onelib/mylib/v2

import (
	// ...
)

文件目录结构无需改变。

调用方使用方法见下节。

这就是module发布者根据go module特性处理版本问题的正确方法。
同时，库作者请参照下节，告知库用户在require/import时加上合适的主版本号后缀。

库用户如何调用【有良好支持go module特性的库】的方法

库作者在正确支持go module特性后，库用户（调用方）的注意事项：

  1. go.mod文件中require path需要同样在结尾加上/vx。
    require github.com/onelib/mylib/v2 v2.x.x
  2. 代码（.go文件）中的import path需要同样在结尾加上/vx。
    import github.com/onelib/mylib/v2

这样，调用者可以在同一项目下import同一模块的多个不同主版本了。

但同一主版本、不同子版本仍然不能共存，这是因为由golang采用的语义化版本号(Semantic Versioning)可知，同一主版本应当是向下兼容，因此同一主版本的高子版本应当能兼容低子版本的功能。

例外：v0和v1似乎还是只能导入一个。有了v1就不能再用v0。
不过在语义化版本号中，v0代表试验的初期不稳定版本，有了v1就基本不会再有用v0的需求，问题不大。

代码示例：

go.mod

1
2
3
4
5
6
module github.com/caller/myservice
    require (
        github.com/onelib/mylib v1.0.0
        github.com/onelib/mylib/v2 v2.1.3
        github.com/onelib/mylib/v3 v3.2.1
    )

在同一项目的不同的代码文件中使用同一库的不同主版本：

代码文件1.go

1
2
3
4
   import "github.com/onelib/mylib"
func f1() {
	mylib.FuncX()
}

代码文件2.go

1
2
3
4
   import "github.com/onelib/mylib/v2"
func f2() {
	mylib.FuncX()
}

代码文件3.go

1
2
3
4
   import "github.com/onelib/mylib/v3"
func f3() {
	mylib.FuncX()
}

在同一项目的同一代码文件中使用同一库的不同主版本：
（这个需求有点少见，不过也能实现，如果各主版本包名冲突，import时指定别名即可）
代码文件x.go

1
2
3
4
5
6
7
8
9
10
11
package main
    import (
        myliba "github.com/onelib/mylib"
        mylibb "github.com/onelib/mylib/v2"
        mylibc "github.com/onelib/mylib/v3"
	)
	func main() {
		myliba.FuncX()
		mylibb.FuncX()
		mylibc.FuncX()
	}

PAT乙级证书GET√

日常生活

PAT乙级证书

有点遗憾，没有满分。
第4题的4个测试点，只通过了前两个，后两个超时。

刚开始用int做的，莫名其妙数值不对，我以为范围太大溢出了，
改用long long还是异常，就再改用了字符串进行大数运算，结果效率大幅下降。

最后仔细一读题，其实范围其实应该还在int里。数值异常应该是不知道哪里写错了。
然而意识到这点时，已经来不及改了（而且没有备份第一版直接运算的代码）。

待我有空看看到底哪里错了。

请我喝杯咖啡吧~

支付宝
微信