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里。数值异常应该是不知道哪里写错了。
然而意识到这点时,已经来不及改了(而且没有备份第一版直接运算的代码)。

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

为何在散列表中除留余数法取模运算中,要尽量取素数

除留余数法

首先回顾一下什么是除留余数法。
当哈希函数产生哈希值较大,而存储值希望较小(如存储空间限制)时,可以采用模运算来限制在某个范围之内。

我们将运算值对p取余直接作为哈希值,p 一般取值小于等于哈希表长度 size 的最大质数。 选择优秀的 p 可以减少冲突的发生。

限制小于等于size是因为哈希值通常也是直接用于存储地址下标,从而不能超出存储空间长度。

下面给出一个常见的字符串hash实现(没有取质数):

1
2
3
4
5
6
7
int hash(string& value) {
int code = 0;
for (size_t i= 0; i<value.length(); i++) {
code = code * 256 + value[i] + 128;
}
return code%size;
}

考虑到避免长数据溢出问题,更常见的扩大适用版本应该是

1
2
3
4
5
6
7
int hash(string& value) {
int code = 0;
for (size_t i= 0; i<value.length(); i++) {
code = (code * 256 + value[i] + 128)%size;
}
return code;
}

为何要尽量取素数

选取质数本质上只是一个优化,选取非质数其实并不会影响算法的正确性,
只会导致较差的hash算法在特定情况下会冲突概率变大,效率变差。

良好的hash函数(或者说如果取模本身是hash函数的一部分,那么就说hash函数抛去取模的部分),其实是无所谓模什么数的,但选取质数可以较好地抵抗不好的hash函数。

只要原hash方法是线性的变换,除数取合数的话,一旦数据是以合数的某个因子为间隔增长的,那么hash值只会是几个值不停的重复,冲突很严重,而素数就不会发生这种情况。

另一方面,即使哈希函数较差,但假如关键字是完全随机分布的,那么也无所谓一定要模质数的。但在实际中往往关键字有某种规律,例如大量的等差数列,那么公差和模数不互质的时候发生碰撞的概率会变大,而用质数就可以很大程度上回避这个问题。

综合,也就是这个优化方法产生效果的场合是:1.输入数据具有明显规律性(同余某个数)2. 哈希算法除去模数以外的部分对于这种输入数据表现差,冲突高。
而即使不满足这些条件,这个优化也不会降低效率,所以为了通用性,通常不管是否符合,我们都选取质数来模。

严格的数学推理与证明需要使用到数论知识,这里仅作简单的概念性说明。

下面详细说明。

哈希函数的重要特性,就是要尽量让输出n%m等概率,从而降低碰撞的频率。

理论上,若x的分布是平均的,那么m取值多少效果都一样好。假设x平均分布在[0, k * m],那么f(x)就会平均分布于[0, m]。从排除哈希碰撞的角度看,这已经是最优的分布了。但理论归理论,实际上m最好还得是个质数,因为x的分布在实际应用中很难做到平均分布,这时候m的取值就至关重要。

首先不难看出m不能取2^t这种数,因为这样等同于把输入数据的高位截断了。如果恰好输入数据变化的只有高位(即2^a+b),那就会悲剧,所有的数据都会被分配到一个桶。比如m=256,257%256=1,513%256=1,769%256=1。

实际上,m不止在取2^t时会发生这种大量碰撞的糟糕情况。只要输入数据跟某一整数k同余(包含输入数据变化的只有高位的情况在内,k=2),而m与k的最大公因数越大,碰撞概率越大。

举例如m若取9(9并不是2^t),
输入数据4, 7, 10, 13, 16, 19, 22, 25 他们对于整数k=3同余1,
设中间哈希函数h(x)=5x-9,则他们的中间哈希值是11, 26, 41, 56, 71, 86, 101, 116, 他们对于整数k=3同余2,
则最终哈希值11%9=2, 26%9=8, 41%9=5, 56%9=2, 71%9=8, 86%9=5, 101%9=2, 116%9=8
m=9与k=3有公因数g=3。
可以看出最终哈希值分布在2, 5, 8,而并没有充分利用[0, 9)的结果空间,利用空间是公因数的倒数倍,即整个空间的1/3。

而要保证空间利用最大化,即哈希结果足够散,则需要使m与k的最大公因数g最小,即g=1,就要使m与k互质。
由于实际我们无法提前得知输入数据,从而无法得知k的取值,那么只需要将m取为质数,就可以保证m与k一定互质。

再次推广,即使输入数据不是跟某一整数n同余,但只要不是完全平均分布,那么这些数据的某个子集也会构成这种同余情况,从而一定程度上增多碰撞,通过取素数处理,也可以相应程度消除这种碰撞。
综合任意数据下的情况,输入数据集越接近这种同余情况,取素数这种处理方法的优化效果越明显。


另一种看到的数学说明如下:

Hash(N) = N % M首先,我们要明白Hash的意义在于把一个大的集合A,映射到小的集合B。比如通过取余的方式进行Hash,集合A = {0, 1, …, M, M+1, …, 2M, 2M+1, …, 3M, 3M+1, …}就会被映射到集合B = {0, 1, 2, …, M - 1}。

然后,如果集合A的元素分布是{0, 1, 2, 3, 4, …}这样的话,M取质数还是合数都可以,最后整个集合A会被均匀地映射到{0, 1, …, M-1}。

(例子)但是,很多情况下我们的元素分布是有非1步长的,比如集合A = {0, 6, 12, 18, 24, 30, 36, …},这时候就出现问题了。当M取合数时,比如M = 10,我们来看看映射的情况。0->0, 6->6, 12->2, 18->8, 24->4, 30->0, 36->6, …。此时我们很容易发现,最后映射到了集合B = {0, 6, 2, 8, 4} = {0, 2, 4, 6, 8},和我们理想中的{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}差距很大啊。

有问题我们就要去解决啊。我们回到代数形式上来看,在N与M最大公因数为1的情况下,N % M后可以得到的一系列的余数r,而全体余数r的集合R就是{0, 1, 2, …, M-1}。每个余数r代表了一个N的集合,比如在上面的例子中余数0代表了N的集合{0, 10, 20, 30, …},这个集合就叫做“同余类”。即余数集合R中有M个余数,每个余数r代表一个同余类。现在思路就很清晰了,我们最理想的方式就是将集合A映射到余数集合R上,即B = R。

接下来我们讨论一下为什么有时候无法完全利用余数集合R:

假设N = kn, M = km, N和M存在最大公因数k,此时可以将N % M = r转化为公式N = Mq + r,即kn = kmq + r。其中q是商,r是余数。“表面上”r的取值范围是{0, 1, 2, …, M-1}(忽视了只有N与M最大公因数为1时,才能取整个余数集合R的定理),一片和谐。但是可以对公式进行稍微的变换,n = mq + (r/k),由于n和mq都是整数,则(r/k)也是整数。此时我们看一看到(r/k)的取值范围是{0, 1, 2, …, m} = {0, 1, 2, …, M/k}。恢复到原式,也是就r的“实际”取值范围是{0, k, 2k, 3k, …, m*k},缩小了k倍。

一切都明了了,我们最后的目标就是保证N与M最大公因数为1。最简单的方式就是直接取M为质数!


质数并不是唯一的准则,质数的选取上还可以更加精细挑选来优化。见链接
good hash table primes

部分节选自知乎 @十一太保念技校,链接:https://www.zhihu.com/question/20806796/answer/21359160
部分节选自知乎 @林二xLINER,链接:https://www.zhihu.com/question/20806796/answer/159392465

Hash时取模一定要模质数吗?
哈希表中数组的容量为什么是质数
为何哈希函数取余法要避免2的幂?

CCF201809-3 元素选择器

题目主干

题目描述1
题目描述2
题目描述3
题目描述3

解题要点

……题目说可以用贪心策略,暂时还没接触。
直接撸了整个解析文档树

解析时需要用到递归或stack,我这里采用了stack。
层级的处理上,
如果解析到下一个元素层级比当前多1,则跟随push增加层级。
如果解析到下一个元素层级小于当前元素,则证明当前元素已没有更深的子元素,pop直到得到下一个元素的父元素,照常处理。
如果解析到下一个元素层级比当前大于1,证明文档有问题,此处题目保证输入正确其实并不会出现此情况。
需要注意的是,标签名大小写不敏感,因此需要统一转换大小写。

匹配上我用了继承多态+工厂模式,在树上进行遍历查找。
树的遍历查找上也是没有使用递归,而用了stack。
TwoGrandChildSelector是2级选择器,GrandChildSelector是无限级选择器
由于最后证明无限级写对了,所以统一交给无限级处理了,并没有调用2级的
自己写的时候如果感觉无限级没有把握,可以优先把2级的交给TwoGrandChildSelector处理
if (g.size() >= 2)拆成>2==2,把==2交给TwoGrandChildSelector)

代码示例

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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <iterator>
#include <cctype>
using namespace std;

struct Element {
string tagname;
string id;
int depth;
int line;
Element* parent;
vector<Element*> childs;
};
struct Selector {
virtual bool match(Element* elem) = 0;
};
struct SimpleSelector:Selector {};
struct ComplexSelector :Selector {};
struct TagSelector:SimpleSelector {
string tagname;
bool match(Element* elem) {
return tagname == elem->tagname;
}
};
struct IDSelector:SimpleSelector {
string id;
bool match(Element* elem) {
return id == elem->id;
}
};
struct TwoGrandChildSelector :ComplexSelector {
SimpleSelector* firstSel;
SimpleSelector* secondSel;
bool match(Element* elem) {
if (!secondSel->match(elem)) {
return false;
}
Element* e = elem->parent;
while (e != nullptr) {
if (firstSel->match(e)) {
return true;
}
e = e->parent;
}
return false;
}
};
struct GrandChildSelector :ComplexSelector {
vector<SimpleSelector*> Sels;
bool match(Element* elem) {
if (Sels.empty()) { return false; }
reverse_iterator<vector<SimpleSelector*>::const_iterator> it = Sels.crbegin();
if (!(*it)->match(elem)) {
return false;
}
it++;
while (it != Sels.crend()) {
Element* e = elem->parent;
while (e != nullptr) {
if ((*it)->match(e)) {
elem = e;
break; // 匹配下一个Selector
}
e = e->parent;
}
if (e == nullptr) {
return false; // 此Selector匹配失败
}
it++;
}
return true;
}
};
SimpleSelector* createSimpleSelector(string sel) {
if (sel.size() <= 0) {
return nullptr;
}
if (sel[0] == '#') {
auto s = new IDSelector();
s->id = sel.substr(1);
return s;
}
else {
auto s = new TagSelector();
s->tagname = sel;
transform(s->tagname.begin(), s->tagname.end(), s->tagname.begin(), ::toupper);
return s;
}
return nullptr;
}
ComplexSelector* createComplexSelector(string sel) {
if (sel.size() <= 0) {
return nullptr;
}
vector<string> g;
string::size_type last = 0;
string::size_type space = sel.find(' ');
while (space != string::npos) {
g.push_back(sel.substr(last, space-last));
last = space + 1;
space = sel.find(' ', last);
}
g.push_back(sel.substr(last));
if (g.size() >= 2) {
auto s = new GrandChildSelector();
for (auto & subSel : g) {
s->Sels.push_back(createSimpleSelector(subSel));
}
return s;
}
return nullptr;
}
Selector* createSelector(string sel) {
Selector* r = createComplexSelector(sel);
if (r == nullptr) {
r = createSimpleSelector(sel);
}
return r;
}
struct SelectResult{
SelectResult() :
Count(0), Lines()
{}
int Count;
vector<int> Lines;
};

SelectResult select(Selector* sel, Element* root) {
SelectResult result;
if (sel->match(root)) {
result.Count = 1;
result.Lines.push_back(root->line);
}
for (auto c:root->childs) {
SelectResult subResult = select(sel, c);
result.Count += subResult.Count;
result.Lines.insert(result.Lines.end(), subResult.Lines.cbegin(), subResult.Lines.cend());
}
sort(result.Lines.begin(), result.Lines.end());
return result;
}

// TODO: How to free
Element* parseElementFromS(string s) {
auto elem = new Element();
auto contentI = s.find_first_not_of('.');
auto contentEnd = s.find_first_of(' ', contentI);
auto other = s.find_first_of('#', contentEnd);
if (other == string::npos) {
elem->tagname = s.substr(contentI);
elem->id = "";
}
else {
elem->tagname = s.substr(contentI, contentEnd-contentI);
elem->id = s.substr(other+1);
}
transform(elem->tagname.cbegin(), elem->tagname.cend(), elem->tagname.begin(), ::toupper);
elem->depth = contentI / 2;
return elem;
}

int main()
{
int n, m; cin >> n >> m; cin.get();
Element* root = nullptr;
stack<Element*> chain; // stackDepth = stack.size()-1
for (int i = 0; i < n; i++) {
string s; getline(cin, s);
Element* elem = parseElementFromS(s);
elem->line = i+1;
if (chain.empty()) {
root = elem;
elem->parent = nullptr;
chain.push(elem);
}
else {
int chainDepth = chain.size() - 1;
if (elem->depth > chainDepth + 1) {
return -1;
}
while (elem->depth <= chainDepth) {
chain.pop();
chainDepth--;
}
elem->parent = chain.top();
chain.top()->childs.push_back(elem);
chain.push(elem);
}
}
for (int i = 0; i < m; i++) {
string sel; getline(cin, sel);
auto selector = createSelector(sel);
auto s = select(selector, root);
cout << s.Count;
for (auto l : s.Lines) {
cout << " " << l ;
}
cout << endl;
}
return 0;
}

CCF201809-2 买菜

小H和小W来到了一条街上,两人分开买菜,他们买菜的过程可以描述为,去店里买一些菜然后去旁边的一个广场把菜装上车,两人都要买n种菜,所以也都要装n次车。具体的,对于小H来说有n个不相交的时间段[a1, b1], [a2, b2]…[an, bn]在装车,对于小W来说有n个不相交的时间段[c1, d1], [c2, d2]…[cn, dn]在装车。其中,一个时间段[s, t]表示的是从时刻s到时刻t这段时间,时长为t - s。
由于他们是好朋友,他们都在广场上装车的时候会聊天,他们想知道他们可以聊多长时间。
输入格式
输入的第一行包含一个正整数n,表示时间段的数量。
接下来n行每行两个数ai,bi,描述小H的各个装车的时间段。
接下来n行每行两个数ci,di,描述小W的各个装车的时间段。
输出格式
输出一行,一个正整数,表示两人可以聊多长时间。
样例输入
4
1 3
5 6
9 13
14 15
2 4
5 7
10 11
13 14
样例输出
3
数据规模和约定
对于所有的评测用例,1 ≤ n ≤ 2000, ai < bi < ai + 1,ci < di < ci + 1, 对于所有的i(1 ≤ i ≤ n)有,1 ≤ ai, bi, ci, di ≤ 1000000。

解题要点

暴力求区间交集即可。
可以根据时间区间递增做少许优化。

代码示例

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct td{
int be;
int end;
};

int jtd(const td& t1, const td& t2) {
int b = max(t1.be, t2.be);
int e = min(t1.end, t2.end);
int d = e - b;
if (d < 0) {
return 0;
}
return d;
}

int main()
{
int n; cin >> n;
vector<td> t1(n), t2(n);
for (auto& d : t1) {
cin >> d.be >> d.end;
}
for (auto& d : t2) {
cin >> d.be >> d.end;
}
int ans = 0;
for (auto& d1 : t1) {
for (auto& d2 : t2) {
auto add = jtd(d1, d2);
ans += add;
}
}
cout << ans << endl;
return 0;
}
  • Copyrights © 2014-2022 听寒
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信