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;
}

CCF201809-1 卖菜

问题描述
  在一条街上有n个卖菜的商店,按1至n的顺序排成一排,这些商店都卖一种蔬菜。
  第一天,每个商店都自己定了一个价格。店主们希望自己的菜价和其他商店的一致,第二天,每一家商店都会根据他自己和相邻商店的价格调整自己的价格。具体的,每家商店都会将第二天的菜价设置为自己和相邻商店第一天菜价的平均值(用去尾法取整)。
  注意,编号为1的商店只有一个相邻的商店2,编号为n的商店只有一个相邻的商店n-1,其他编号为i的商店有两个相邻的商店i-1和i+1。
  给定第一天各个商店的菜价,请计算第二天每个商店的菜价。
输入格式
  输入的第一行包含一个整数n,表示商店的数量。
  第二行包含n个整数,依次表示每个商店第一天的菜价。
输出格式
  输出一行,包含n个正整数,依次表示每个商店第二天的菜价。
样例输入
8
4 1 3 1 6 5 17 9
样例输出
2 2 1 3 4 9 10 13
数据规模和约定
  对于所有评测用例,2 ≤ n ≤ 1000,第一天每个商店的菜价为不超过10000的正整数。

解题要点

不多说,熟悉语言就没有问题,简单到炸

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>
using namespace std;

int main()
{
int n; cin >> n;
vector<int> p(n);
for (int i = 0; i < n; i++) {
cin >> p[i];
}
vector<int> np(n);
np[0] = (p[0] + p[1]) / 2;
for (int i = 1; i < n-1; i++) {
np[i] = (p[i - 1] + p[i] + p[i + 1])/3;
}
np[n-1] = (p[n-2] + p[n-1]) / 2;
for (int i = 0; i < n; i++) {
cout << np[i] << " ";
}
return 0;

}

leetcode-整数翻转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func reverse(x int) int {
const (
intMax = 2147483647
intMin = -2147483648
)
result := 0
for x != 0 {
t := x % 10
if result > intMax/10 || (result==intMax/10 && t>intMax%10) { return 0 }
if result < intMin/10 || (result==intMin/10 && t<intMin%10) { return 0 }
result = result*10 + t
x /= 10
}
return result
}

刚开始使用了一开始就计算出最高位权值,进而直接乘上到达目的位的方法。
此种方法首先要事先求出数字位数才能求各位权值,进行一次循环浪费了时间,
求权值过程中又要进行一次循环,增加时间又增加空间,后续也没有太好的方法判断溢出。
类似

1
2
3
4
5
6
7
8
9
10
11
12
numLen := getNumLen(x)
w:=1
for i:=0; i<numLen;i++ {
w*=10
}
r := 0
for x!=0 {
t := x % 10
r += w * t

w /= 10; x /= 10
}

后来看了循环乘10只需要一次循环,还省去了许多过程与变量,又高效又优雅

1
2
3
4
5
6
7
r := 0
for x!=0 {
t := x %10
x /= 10

r = r * 10 + t
}

而后是添加判断溢出的方法,需要使用数学推导。

重点在于r * 10 + t这一句需要提前判断是否会导致溢出。

假设x为正数,则溢出时有10r+t>intMax。
但是我们不能直接这么写if,因为这样判断本身也会溢出,无法正确判断。
将等式同/10,此时便可以安全判断,r+t/10>intMax/10
但是注意又有新的问题,int会取整,导致/10后范围并不正确。

t的范围是0-9的整数,/10后为[0, 1),取整后得0.
intMax/10=214748364+0.7小数部分是原个位数字,取整后丢失小数,得214748364
若r>[intMax/10],就有r>intMax/10+x(x的范围[0,1)),由于x与t范围[0, 1)一致,也有r>intMax/10+t成立,溢出。
若r==[intMax/10],则还需判断t/10和丢失的小数部分0.7的关系,才能判断原式是否成立,也即t和原intMax的个位数字7的关系,若t>7则成立,溢出。

类似的,负数有
若r<[intMin/10],就有r>intMin/10+x(x的范围(-1, 0]),由于x与t范围(-1, 0]一致,也有r>intMax/10+t成立,溢出。
若r==[intMin/10],则还需判断t/10和丢失的小数部分-0.8的关系,才能判断原式是否成立,也即t和原intMax的个位数字-8的关系,若t<-8则成立,溢出。

总结:

  • 重视数学推导,思路不清晰时可使用数学方法。
  • 计算机的类型虽然有上限,但是数学推导的时候没有范围限制。因而,可以使用数学推导方法推导条件,然后通过变形式子,使得各中间值都落入计算机的表示范围内,如此绕过数值范围问题。
  • 处理此类数值的各位数字时,不必一开始就计算出各位的权值而一次性乘上,也可以通过循环叠加*10来达到目的。

CCF2018-12-3 CIDR合并

题目描述

题目主干

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

测试用例

样例输入
2
1
2
样例输出
1.0.0.0/8
2.0.0.0/8

样例输入
2
10/9
10.128/9
样例输出

10.0.0.0/8

样例输入
2
0/1
128/1
样例输出
0.0.0.0/0

评测用例规模与约定

评测用例规模与约定1
评测用例规模与约定2

解题要点

  1. 定义存储IP前缀的结构体,并在输入时完成标准化,有助于简化后续处理. 输出时则只需要输出标准格式.

  2. 排序时,由于STL list不是随机访问容器,不能使用<algorithm>库的sort(RandomIterator begin, RandomIterator end, Compare pred)
    但STL list容器自身提供了排序方法list.sort(Compare pred)

同时,由于是自定义结构,需要自行编写STL Compare,可以使用lambda表达式,也可以使用普通函数。
注意如何编写合法的STL Compare(需满足严格弱序、返回值代表第一个参数是否比第二个参数先出现)。

  1. 位运算相关知识。
    还可能涉及整型提升(Integer Promotion)。

  2. 对题目提示阅读理解及实现
    第二步从小到大合并,即为消除被其他前缀包含的子集前缀过程的过程。
    只要按较短的一个前缀的长度len,比较两个IP前缀的前len位是否相同,相同则代表长度较长的那个是长度较短的子集。
    由于排序保证后者范围更小,因此后者是子集,保留前者,删去后者。
    (此过程中也可以两前缀的长度相同,如果前len位相同,则代表两个前缀等价。
    由于排序保证后者地址更大,因此后者地址段包含无效数据更多,也是保留前者,删去后者)

第三步同级合并,即为将两个相同长度的前缀,合并为一个更短的前缀。
只要判断两个前缀的最后一个有效位不同,且前面len-1位相同,则可以两者合并为一个len-1长度的前缀。
可以用异或运算。

以上两步都要注意,由于在循环遍历中修改了遍历对象,无论对迭代器做前进还是后退更改,都要再次考虑迭代器的有效性、是否破坏了循环过程。

  1. 由于简化过程中需要大量修改容器内容,不要使用顺序容器vector等储存,
    否则修改时造成大量元素复制时间,后几个大规模测试数据中极易超时。
    推荐使用STL的list存储。

输入时,也可以预先申请空间而不是每次输入都调用push。

代码示例

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

using IPAddr = unsigned int;
using Byte = unsigned char;
struct IPPrefix {
Byte ip[4];
short len;
bool isSubsetOf(const IPPrefix& o) {
if (this->len < o.len) {
return false;
}
auto lessLen = o.len;
IPAddr mask = 0;
for (int i = 0; i < lessLen; i++) {
mask |= 1U << (32 - (i+1));
}
IPAddr ip1 = this->getIP();
IPAddr ip2 = o.getIP();
IPAddr ip1subnet = ip1 & mask;
IPAddr ip2subnet = ip2 & mask;
return ip1subnet == ip2subnet;
}
inline IPAddr getIP() const {
return ip[0] << 24
| ip[1] << 16
| ip[2] << 8
| ip[3];
}
bool operator==(IPPrefix& rhs) const {
return this->getIP() == rhs.getIP()
&& this->len == rhs.len;
}
};

inline istream& operator>>(istream& is, IPPrefix& rhs) {
string input; is >> input;
string::size_type si = input.find_first_of('/');

string ipStr = input.substr(0, si);
string::size_type preDot = -1;
string::size_type nextDot = ipStr.find_first_of('.');
rhs.ip[0] = stoi(ipStr.substr(0, nextDot));
preDot = nextDot;
int sectionCnt = 1;
for (int i = 1; i < 4; i++) {
if (preDot == string::npos) {
rhs.ip[i] = 0;
}
else {
nextDot = ipStr.find_first_of('.', preDot + 1);
sectionCnt++;
string ipSection = ipStr.substr(preDot + 1, nextDot - (preDot + 1));
rhs.ip[i] = stoi(ipSection);
preDot = nextDot;
}
}

if (si == string::npos) {
rhs.len = 8 * sectionCnt;
}
else {
rhs.len = stoi(input.substr(si + 1));
}
return is;
}

inline ostream& operator<<(ostream& os, const IPPrefix& rhs) {
printf("%d.%d.%d.%d/%d", rhs.ip[0], rhs.ip[1], rhs.ip[2], rhs.ip[3], rhs.len);
return os;
}

inline void optimizeList(list<IPPrefix>& data) {
data.sort([](const IPPrefix& lhs, const IPPrefix& rhs) {
IPAddr ip1 = lhs.getIP();
IPAddr ip2 = rhs.getIP();
return ip1 < ip2
||
(ip1 == ip2 && lhs.len < rhs.len);
});
// 消除子集
for (auto i1 = data.begin(), i2 = ++data.begin(); i2 != data.end(); i1++, i2++) {
//clog << "compare1 " << *i1 << " & " << *i2 << endl;
while (i2!=data.end() && i2->isSubsetOf(*i1)) {
// clog << *i2 << " is subset of " << *i1 << ", erase former"<< endl;
i2 = data.erase(i2);
}
if (i2 == data.end()) {
break;
}
//clog << "compare1 " << *i1 << " & " << *i2 << endl;
}
// 合并同级
auto i1 = data.begin(), i2 = ++data.begin();
while (i2 != data.end()) {
if (i1->len == i2->len) {
IPAddr ip1 = i1->getIP();
IPAddr ip2 = i2->getIP();
auto len = i1->len;
// clog << "compare2 " << *i1 << " & " << *i2 << endl;
if ((ip1 ^ ip2) >> (32 - len) == 1U) // 前len-1位相同且第len位不同
{
// 合并
// clog << "merge " << *i1 << " &" << *i2 << endl;
i1->len--;
i2 = data.erase(i2);
// clog << "into " << *i1 << endl;
// 回退以检查合并产生的条目,与前一条目是否可以再次合并
if (i1 != data.begin()) {
// 若i1指向begin,则没有前一条,无需回退。
i1--;
i2--;
// 此处continue跳过了本次循环后面的自增操作。
continue;
}
else if (i2 == data.end()) {
// 由于减少一条目,此时i2可能已经到达表尾。
// 立即退出循环,否则再次i2自增会出错
break;
}
}
}
// 前进
i1++; i2++;
}
}

int main()
{
size_t n; cin >> n;
list<IPPrefix> list(n);
for (auto it = list.begin(); it != list.end(); it++) {
cin >> *it;
}
optimizeList(list);
for (auto it = list.cbegin(); it != list.cend(); it++) {
cout << *it << endl;
}
}

CCF2018-12-2 小明放学

题目描述

题目背景

  汉东省政法大学附属中学所在的光明区最近实施了名为“智慧光明”的智慧城市项目。具体到交通领域,通过“智慧光明”终端,可以看到光明区所有红绿灯此时此刻的状态。小明的学校也安装了“智慧光明”终端,小明想利用这个终端给出的信息,估算自己放学回到家的时间。

问题描述

  一次放学的时候,小明已经规划好了自己回家的路线,并且能够预测经过各个路段的时间。同时,小明通过学校里安装的“智慧光明”终端,看到了出发时刻路上经过的所有红绿灯的指示状态。请帮忙计算小明此次回家所需要的时间。

输入格式

  输入的第一行包含空格分隔的三个正整数 r、y、g,表示红绿灯的设置。这三个数均不超过 10^6。
  输入的第二行包含一个正整数 n,表示小明总共经过的道路段数和路过的红绿灯数目。
  接下来的 n 行,每行包含空格分隔的两个整数 k、t。k=0 表示经过了一段道路,将会耗时 t 秒,此处 t 不超过 10^6;k=1、2、3 时,分别表示出发时刻,此处的红绿灯状态是红灯、黄灯、绿灯,且倒计时显示牌上显示的数字是 t,此处 t 分别不会超过 r、y、g。

输出格式

  输出一个数字,表示此次小明放学回家所用的时间。

测试用例

样例输入

1
2
3
4
5
6
7
8
9
10
30 3 30
8
0 10
1 5
0 11
2 2
0 6
0 3
3 10
0 3

样例输出

1
46

样例说明
小明先经过第一段路,用时 10 秒。第一盏红绿灯出发时是红灯,还剩 5 秒;小明到达路口时,这个红绿灯已经变为绿灯,不用等待直接通过。接下来经过第二段路,用时 11 秒。第二盏红绿灯出发时是黄灯,还剩两秒;小明到达路口时,这个红绿灯已经变为红灯,还剩 11 秒。接下来经过第三、第四段路,用时 9 秒。第三盏红绿灯出发时是绿灯,还剩 10 秒;小明到达路口时,这个红绿灯已经变为红灯,还剩两秒。接下来经过最后一段路,用时 3 秒。共计 10+11+11+9+2+3 = 46 秒。

评测用例规模与约定

有些测试点具有特殊的性质:

  • 前 2 个测试点中不存在任何信号灯。

测试点的输入数据规模:

  • 前 6 个测试点保证 n ≤ 10^3。
  • 所有测试点保证 n ≤ 10^5。

解题要点

模拟题,比前一题稍微复杂,可在前一题基础上修改。

  1. 经过一个完整的红绿黄周期,状态相当于没有任何变化。
    因此通过对整个周期取余,可以大大节省运算时间。
    而后只要进行小于两个周期的模拟,即可得出结果。

  2. 注意模拟循环中:
    ->红->绿->黄->
    对应的数字是
    ->1->3->2->
    不要想当然认为是->1->2->3->,从而写错代码。

  3. 分析数据规模,可知:

  • r、y、g最大为10^6,n最大为10^5,使用int存储没有任何问题。
  • 但结果ans考虑最大的情况(全部遇到为黄灯刚开始)下,为ans=n*(y+r),10^5*(10^6+10^6)=2*10^11次方,
    不可以直接使用int、unsigned int,都达不到要求(可以使用的numeric_limits::min()/max()查询类型T的表示范围)。
    需要使用long long或者unsigned long long替换相关类型。
    如果没有注意数据规模问题,将导致最后两个测试点不通过。

代码示例

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

using timeDuration = unsigned long long;

int stageTime[3];
// ->1->3->2->
void nextState(int &k) {
switch (k) {
case 1: // red
k = 3;
break;
case 2: // yellow
k = 1;
break;
case 3: // green
k = 2;
break;
}
}

void preState(int &k) {
switch (k) {
case 1: // red
k = 2;
break;
case 2: // yellow
k = 3;
break;
case 3: // green
k = 1;
break;
}
}

inline int getStageTime(const int& k) {
return stageTime[k-1];
}

void calcState(timeDuration time, int& k, timeDuration& t) {
const timeDuration cycle = stageTime[0] + stageTime[1] + stageTime[2];
time %= cycle;
if (time < t) {
t -= time;
return;
}
time -= t; nextState(k); // frist part stage
bool proceed = true;
timeDuration stageTime;
while (time > 0) {
stageTime = getStageTime(k);
if (time < stageTime) {
t = stageTime - time; // final part stage
break;
}
time -= stageTime; nextState(k); // proceed entire stage
}
return;
}

int main()
{
int &r = stageTime[0], &y = stageTime[1], &g= stageTime[2];
cin >> r >> y >> g;
timeDuration n; cin >> n;
timeDuration ans = 0;
for (timeDuration i = 0; i < n; i++) {
// clog << "当前时间点:" << ans << endl;
int k; timeDuration t; cin >> k >> t;
if (k == 0) {
ans += t;
continue;
}
// clog << "初始状态:" << k << " " << t << endl;
calcState(ans, k, t);
// clog << "达到状态:" << k << " " << t << endl;
switch (k)
{
case 1: // R
ans += t;
break;
case 2: // Y
ans += t + r;
break;
case 3: // G
ans += 0;
break;
default:
break;
}
}
cout << ans << endl;
return 0;
}

请我喝杯咖啡吧~

支付宝
微信