学海泛舟

发表于 | 分类于 |

《深入了解计算机系统》我看到了第三章了，读书笔记也写了两章。这是我第一次写电子版的读书笔记，感觉确实和我以前写在书旁的批注式的笔记相去甚远。
我原本设想将书中的知识点能够尽可能的罗列出来，并且想从自己的角度加以理解和思考。
但是通过这两章读书笔记的写作，我发现了很多问题。

首先，我觉得将书中的知识点完全罗列，既效率底下，又毫无必要，这不但拖慢读书速度，而且对于书籍的理解恐怕也没有多少帮助。
其次，我的读书笔记框架是严格遵从书本的章节，这就显得结构比较僵硬，更何况有些章节本身比较简单，知识点少，难度低，这个时候还要生硬的进行划分总结也不太合适。
最后，限于我的知识水平，可能还有没有深入思考，我自己本身的理解较少能付诸笔下，读书鲜有能够举一反三的。

当然，读书笔记也起到了一定积极的作用，起码这本书并没有躺在一边吃灰尘。

针对上述问题，我觉得我的读书笔记要进行整改。
要突破书本的章节安排，在内容上有所取舍，主要是要理清书本的脉络，尽量写下自己的一些见解。

学海泛舟

发表于 | 分类于 |

2.3 整数运算

2.3.1 无符号加法

对于两个限定范围的非负整数，它们的和通常处于一个更大的范围之中。编程语言支持限定精度的运算，故定义一种无符号数加法的运算$+^u_w$

无符号数加法
对满足$0 \leq x, y < 2^w$的x和y有：
$$x +^u_w y = \begin{cases}x + y, & x + y < 2^w \\x + y - 2^w, & 2^w \leq x + y < 2^{w+1}\end{cases}$$

只要检验无符号数加法后的结果是否比原来的两个加数小，就能够判定结果是否发生了溢出

2.3.2 补码加法

补码进行运算的时候，同样存在溢出的问题，但补码存在正负问题，形势相对复杂一些。

补码加法
对满足$-2^{w-1} \leq x, y \leq 2^{w-1} - 1$的整数x和y，有：
$$x +^t_w y = \begin{cases}x + y - 2^w, & 2^{w-1} \leq x + y \\x + y, & -2^{w-1} \leq x + y < 2^{w-1} \\x + y + 2^w, & x + y < -2^{w-1}\end{cases}$$

虽然区分无符号加法和补码加法，但是两者从位级的角度来看是相同的。这是因为对位级而言，两者都是相加后截取w位的结果。

如果x>0，y>0，但补码加法后<0，则发生了正溢出，如果x<0，y<0，但补码加法后>0，则发生了负溢出。

2.3.3 补码的非

对于$TMin_w \leq x \leq TMax_w$中的数字x，其在补码加法下的加法逆元，一般为-x，但是注意到$-TMin_w = TMax_w + 1$，这时我们从定义出发，$TMin_w$的加法逆元就是其本身。

2.3.4 无符号乘法

无符号乘法从位级上来看，仍和之前的加法类似，直接相乘的基础上截取低w位。

无符号数乘法
对满足$0 \leq x, y \leq UMax_w$的x和y有：
$$x *^u_w y = (x \cdot y) mod 2^w$$

2.3.5 补码乘法

无论是无符号乘法还是补码乘法，它们的位级表示是一样的，

补码乘法
对满足$Tmin_w \leq x, y \leq TMax_w$的x和y有：
$$x *^t_w y = U2T_w((x \cdot y)mod 2^w)$$

2.3.6 乘以常数

整数乘法指令相比于其他整数运算慢得多，故编译器会尝试用位移和加法运算代替乘以常数的运算。
通过位移运算，能够迅速计算乘以2的幂的结果，那么将要乘的数分解为2的幂的和，再通过乘法分配律，就能用位移运算和加法运算表示乘以任意一个常数的运算了。

2.3.7 除以2的幂

整数除法比整数乘法更慢。
除以2的幂也可以用位移运算实现。
无符号除法使用的是逻辑右移。
补码除法，使用算数右移，效果为向下舍入。这种舍入，在为负数时，就造成了右移和除以2的幂结果不相等的情况。为了解决这个问题，可以通过移位前偏置这个值来修正。具体的做法也很简单，假设除以的时2的k次幂，那么在右移前先给原数加上(1<<k)-1。

2.4 浮点数

目前，所有计算机都支持IEEE浮点为标准。

2.4.1 二进制小数

二进制小数的概念类比于十进制小数。
形如$b_mb_{m-1} \ldots b_1b_0 \ldotp b_{-1}b_{-2} \ldots b_{-n-1}b_{-n}$这样的二进制小数，表示的数b
$$b = \sum^m_{i=-n}2^i \times b_i$$

2.4.2 IEEE浮点表示

IEEE浮点标准用$V = (-1)^s \times M \times 2^E$表示一个数：

  • 符号 s的取值（0或者1）决定了这个数的正负
  • 尾数 M是一个二进制小数
  • 阶码 E是一个权值

这种表示方法其实类似于科学记数法，当然限于存储的位数和表示的本身，浮点数的精度是有限的，正如1/3也不可能用科学计数法精确表示。

当把这种标准具体到实际，情况要稍微复杂一些。
浮点数的位划分为三个字段：

  • 符号位s编码为符号s（直接编码）
  • k位的阶码字段exp编码为阶码E
  • n位小数字段frac编码位尾数M

根据exp的值，exp和frac的编码方式是不同的，这要划分为三种不同的情况：

  • 规格化的值
    当exp的位模式既不全是0，也不全是1，就是这种情况。
    此时，阶码E=e-Bias，其中e是一个无符号数，其位模式就是exp，Bias是$2^{k-1}-1$；尾数M=1+f，其中f的位模式是0.frac（就是在frac的位模式前面加上一个0和一个小数点）。

  • 非规格化的值
    当exp的位模式全为0时，表示的就是非规格化的值。
    此时，E=1-Bias，M=f。

  • 特殊值
    当exp的位模式全为1时，就是特殊值，其实就两种，无穷大和NaN。
    当frac全为0时，代表无穷大，否则就是NaN（不是一个数）。

2.4.4 舍入

面对实数运算时，浮点数面临了精度问题，而舍入就是在限制条件下，找到一个最接近的匹配值。IEEE浮点格式定义了四种舍入方式。

  • 向偶数舍入：这种舍入方式总是舍入为最接近该数的数，例如1.4舍入为1，3.6舍入为4。当遇到中间值时，如1.5，就朝舍入后最低有效为偶数的方向舍入，如1.5舍入为2，4.5舍入为4。
  • 向零舍入：就是朝零的方向舍入，即正数向下舍入，负数向上舍入。
  • 向下舍入
  • 向上舍入

默认采用向偶数舍入。

2.4.5 浮点运算

浮点加法具有交换性，单调性，但不具备结合性。
浮点乘法具有交换性，有单调性，但没有对加法的分配性。

学海泛舟

发表于 | 分类于 |

原题

传送门

题目大意

有一张n个点，m条边的图，每条边上有一个布尔运算符（AND，OR，XOR）和一个布尔值，问是否能在点上填入合适的布尔值，使得任意一条边所连接的两个点的布尔值经过边上的运算符运算后等于边上的布尔值。

分析

将每个点拆成两个点，分别代表取0和取1.
边连接的两个点，一共只有四种状态，即（1，0），（0，1），（0，0），（1，1）。找到不符合条件的状态，就是冲突的地方。这样就回归了2-SAT的基本模型了。

参考代码

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
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<map>
#include<climits>
#include<cmath>
using namespace std;
const int maxn=5500;
struct Edge{
	int to,next;
}edge[6000005];
int head[maxn],tot;
void addedge(int u,int v){
	edge[tot].to=v;
	edge[tot].next=head[u];
	head[u]=tot++;
}
int scc,Low[maxn],DFN[maxn],Stack[maxn],top,Index,Belong[maxn];
bool Instack[maxn];
void tarjan(int u){
	int v;
	Low[u]=DFN[u]=++Index;
	Stack[top++]=u;
	Instack[u]=true;
	for(int i=head[u];~i;i=edge[i].next){
		v=edge[i].to;
		if(!DFN[v]){
			tarjan(v);
			if(Low[u]>Low[v]) Low[u]=Low[v];
		} else if(Instack[v]&&Low[u]>DFN[v])
			Low[u]=DFN[v];
	}
	if(Low[u]==DFN[u]){
		scc++;
		do{
			v=Stack[--top];
			Instack[v]=false;
			Belong[v]=scc;
		} while(v!=u);
	}
}
void solve(int N){
	memset(DFN,0,sizeof DFN);
	memset(Instack,false,sizeof Instack);
	Index=scc=top=0;
	for(int i=0;i<N;++i)
		if(!DFN[i])
			tarjan(i);
}
void init(){
	tot=0;
	memset(head,-1,sizeof head);
}
int main(){
	int N,M;
	while(scanf("%d %d",&N,&M)!=EOF){
		init();
		char s[10];
		for(int i=0;i<M;++i){
			int a,b,c;
			scanf("%d %d %d %s",&a,&b,&c,&s);
			if(c==0){
				if(s[0]=='A'){
					addedge(b<<1|1,a<<1);
					addedge(a<<1|1,b<<1);
				} else if(s[0]=='O'){
					addedge(a<<1|1,b<<1|1);
					addedge(b<<1,a<<1);
					addedge(a<<1|1,b<<1);
					addedge(b<<1|1,a<<1);
					addedge(a<<1,b<<1);
					addedge(b<<1|1,a<<1|1);
				} else if(s[0]=='X'){
					addedge(a<<1,b<<1);
					addedge(b<<1|1,a<<1|1);
					addedge(a<<1|1,b<<1|1);
					addedge(b<<1,a<<1);
				}
			} else if(c==1){
				if(s[0]=='A'){
					addedge(a<<1|1,b<<1|1);
					addedge(b<<1,a<<1);
					addedge(a<<1,b<<1);
					addedge(b<<1|1,a<<1|1);
					addedge(a<<1,b<<1|1);
					addedge(b<<1,a<<1|1);
				} else if(s[0]=='O'){
					addedge(a<<1,b<<1|1);
					addedge(b<<1,a<<1|1);
				} else if(s[0]=='X'){
					addedge(a<<1,b<<1|1);
					addedge(b<<1,a<<1|1);
					addedge(a<<1|1,b<<1);
					addedge(b<<1|1,a<<1);
				}
			}
		}
		solve(2*N);
		bool flag=true;
		for(int i=0;i<2*N;i+=2){
			if(Belong[i]==Belong[i^1]){
				flag=false;
				break;
			}
		}
		if(flag) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}
学海泛舟

发表于 | 分类于 |

原题

传送门

题目大意

圆上有n个点，连接其中m对点，可以选择在圆外或圆内连线，问能否使所有的连线都不相交。

分析

注意到连线只有两种状态，在圆外连或者在圆内连，就很容易联想到2-SAT。
将每一条连线都看作两个点，分别代表连线处于圆内和连线处于圆外。
对于有可能相交的连线，就当作一种约束条件。
当然要注意这里是无向边。

参考代码

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
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<map>
#include<climits>
#include<cmath>
using namespace std;
const int maxn=5500;
struct Edge{
	int to,next;
}edge[500*500+100];
int head[maxn],tot;
void addedge(int u,int v){
	edge[tot].to=v;
	edge[tot].next=head[u];
	head[u]=tot++;
}
int scc,Low[maxn],DFN[maxn],Stack[maxn],top,Index,Belong[maxn];
bool Instack[maxn];
void tarjan(int u){
	int v;
	Low[u]=DFN[u]=++Index;
	Stack[top++]=u;
	Instack[u]=true;
	for(int i=head[u];~i;i=edge[i].next){
		v=edge[i].to;
		if(!DFN[v]){
			tarjan(v);
			if(Low[u]>Low[v]) Low[u]=Low[v];
		} else if(Instack[v]&&Low[u]>DFN[v])
			Low[u]=DFN[v];
	}
	if(Low[u]==DFN[u]){
		scc++;
		do{
			v=Stack[--top];
			Instack[v]=false;
			Belong[v]=scc;
		} while(v!=u);
	}
}
void solve(int N){
	memset(DFN,0,sizeof DFN);
	memset(Instack,false,sizeof Instack);
	Index=scc=top=0;
	for(int i=0;i<N;++i)
		if(!DFN[i])
			tarjan(i);
}
void init(){
	tot=0;
	memset(head,-1,sizeof head);
}
int a[2010],b[2010];
int main(){
	int n,m;
	init();
	scanf("%d %d",&n,&m);
	for(int i=0;i<m;++i){
		scanf("%d %d",a+i,b+i);
		if(a[i]>b[i]) swap(a[i],b[i]);
	}
	for(int i=0;i<m;++i)
		for(int j=i+1;j<m;++j)
			if((a[i]<=a[j]&&b[i]>=a[j]&&b[i]<=b[j])||(a[i]>=a[j]&&a[i]<=b[j]&&b[i]>=b[j])){
				addedge(i<<1,j<<1|1);
				addedge(j<<1,i<<1|1);
				addedge(i<<1|1,j<<1);
				addedge(j<<1|1,i<<1);
			}
	solve(2*m);
	bool flag=true;
	for(int i=0;i<2*m;i+=2){
		if(Belong[i]==Belong[i^1]){
			flag=false;
			break;
		}
	}
	if(flag) printf("panda is telling the truth...\n");
	else printf("the evil panda is lying again\n");
	return 0;
}
学海泛舟

发表于 | 分类于 |

原题

传送门

题目大意

对于1~n个位置，对于任意一个位置i，都有一个身高为i的小矮人。有两种操作。
1 x y：将身高x，y的小矮人交换位置
2 x y：身高x到y的小矮人们所处位置是否连续

分析

关键在于如何判断是否连续。
身高x到y的小矮人的个数是固定的，若连续排列，他们所占的位置数也是固定的。
找出身高x到y的小矮人中所处位置的最大值和最小值，将y-x的值和最大值与最小值之差相比，就可判定。
将身高作为键，位置作为值，建立线段树，即可解决问题。

参考代码

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int Maxn=200010;
int n,m;
struct SegTree{
	int minn,maxn;
}seg[Maxn<<2];
void build(int p,int l,int r){
	seg[p].minn=l;
	seg[p].maxn=r;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
}
inline void change(int p,int l,int r,int x,int y){
	if(l==r){
		seg[p].minn=seg[p].maxn=y;
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid) change(p<<1,l,mid,x,y);
	else change(p<<1|1,mid+1,r,x,y);
	seg[p].minn=min(seg[p<<1].minn,seg[p<<1|1].minn);
	seg[p].maxn=max(seg[p<<1].maxn,seg[p<<1|1].maxn);
}
int findmax(int p,int l,int r,int x,int y){
	if(x<=l&&y>=r){
		return seg[p].maxn;
	}
	int mid=(l+r)>>1;
	int ans=0;
	if(x<=mid){
		ans=max(ans,findmax(p<<1,l,mid,x,y));
	}
	if(y>mid){
		ans=max(ans,findmax(p<<1|1,mid+1,r,x,y));
	}
	return ans;
}
int findmin(int p,int l,int r,int x,int y){
	if(x<=l&&y>=r){
		return seg[p].minn;
	}
	int mid=(l+r)>>1;
	int ans=Maxn;
	if(x<=mid){
		ans=min(ans,findmin(p<<1,l,mid,x,y));
	}
	if(y>mid){
		ans=min(ans,findmin(p<<1|1,mid+1,r,x,y));
	}
	return ans;
}
int main(){
	scanf("%d %d",&n,&m);
	build(1,1,n);
	for(int i=0;i<m;i++){
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		if(a==1){
			int tmp1=findmax(1,1,n,b,b);
			int tmp2=findmax(1,1,n,c,c);
			change(1,1,n,b,tmp2);
			change(1,1,n,c,tmp1);
		} else {
			if(findmax(1,1,n,b,c)-findmin(1,1,n,b,c)==c-b){
				printf("YES\n");
			} else {
				printf("NO\n");
			}
		}
	}
	return 0;
}