spoj TRNGL - Make Triangle 题解

发表于 2017-01-31 | 分类于 ACM题解 |

原题

题目大意

问对于一个凸n边形，使用n-3条不相交的对角线划分成若干个三角形，有多少种方式。

分析

对于这种三角形的划分，可以看到n边形的任意一条边都对应着一个三角形。选定一条边，然后根据剩下的一个点，枚举三角形，这时这个n边形就被划分成了几个比较小的多边形，所以递推式也就成功推出了。

参考代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int mod=100007;
int n;
long long dp[1005];
int main(){
	int T;
	scanf("%d",&T);
	memset(dp,0,sizeof dp);
	dp[0]=1;
	dp[1]=1;
	dp[2]=1;
	dp[3]=1;
	dp[4]=2;
	for(int i=5;i<=1000;++i){
		for(int k=2;k<=i-1;++k){
			dp[i]+=dp[k]*dp[i-k+1];
			dp[i]%=mod;
		}
	}
	while(T--){
		scanf("%d",&n);
		printf("%lld\n",dp[n]);
	}
	return 0;
}

第2章信息的表示和处理（一）

发表于 2017-01-25 | 分类于《深入了解计算机系统》读书笔记 |

现代计算机存储和处理的信息都是二值信号，以特定的方式组合二值信号，就能表示有限集合的任意元素。这一章主要研究的就是计算机中的数字表示，即无符号编码、补码编码和浮点数编码。

2.1 信息存储

大多数计算机用字节（8位的块）作为最小的可寻址的内存单位。
每个程序对象，乃至程序本身都是一个字节序列

2.1.1 十六进制表示法

对于描述位模式而言，常用十六进制来取代过于冗长的二进制表示法，在十六进制下，一个字节的值域为 $00_{16}$ ~ $FF_{16}$

2.1.2 字数据大小

字长，指明了指针数据的标称大小，决定了虚拟地址空间的大小。
对于字长为$w$位的机器而言，虚拟地址的范围为0 ~ $2^w-1$，最多访问$2^w$歌字节。

2.1.3 寻址和字节顺序

对象的地址位为所使用字节中最小的地址。
排列表示一个对象的字节有两个通用的规则，即小端法和大端法。

小端法：最低有效字节在最前面
大端法：最高有效字节在最前面
举个例子，假设int x=0x01234567，位于地址0x100处

地址	0x100	0x101	0x102	0x103
大端法	01	23	45	67
小端法	67	45	23	01

2.1.4 表示字符串

C语言中，字符串被编码为一个以null字符结尾的字符数组。

2.1.5 表示代码

不同机器类型使用不同且不兼容的指令和编码方式，故二进制代码不兼容。

2.1.6 布尔代数简介

位向量可以很好的表示有限集合。将所有元素有序排列后，任意由这些元素组成的集合，均可用位向量表示，0代表不具有该元素，1代表具有该元素。而在这样的表示方法中布尔代数可以方便地处理集合运算，|对应集合的并，&对应集合的交，~对应集合的补集。

2.1.7 C语言中的位级运算

C语言支持按位布尔运算。

2.1.8 C语言中的逻辑运算

只需注意一下C语言中逻辑运算具有短路效应，也就是说对于&&和||，如果第一个参数求值就能确定表达式的结果，那么第二个表达式就不会计算。

2.1.9 C语言中的移位运算

左移运算：操作符<<，例如x<<k，代表x向左移动k位，丢弃最高的k位，并在右端补k个0。
右移运算：操作符<<，例如x<<k，代表x向右移动k位。但是右移一般右两种：逻辑右移和算数右移。逻辑右移是在左边补k个0，算数右移是在左端补k个最高有效位。
几乎所有编译器对有符号数使用算数右移，对无符号数，右移是逻辑的。

2.2 整数表示

本节介绍用位编码整数的两种方式

2.2.1 整数数据类型

C语言标准定义了每种数据类型必须能够表示的最小的取值范围。但是通常实际会比标准大上一些

2.2.2 无符号数的编码

对于一个$w$位的整数数据类型，不妨将其看作一个位向量$\vec x = [x_{w-1} , x_{w-2} , \cdots , x_0]$。将其视为一个二进制数就得到了无符号表示。
定义一个函数$B2U_w$（Binary to Unsigned，长度为w），用来表示由二进制转化为无符号数。

无符号数编码的定义
对向量$\vec x = [x_{w-1} , x_{w-2} , \cdots , x_0]$
$$B2U_w(\vec x) \doteq \sum_{i=0}^{w-1}x_i2^i$$

2.2.3 补码编码

在补码的定义中将最高有效位解释为负权。
定义函数$B2T_w$（Binary to Two’s-complement，长度为w），用来表示二进制转补码。

补码编码的定义
对向量$\vec x = [x_{w-1} , x_{w-2} , \cdots , x_0]$
$$B2T_w(\vec x) \doteq -x_{w-1} 2^{w-1} + \sum_{i=0}^{w-2}x_i2^i$$

最高有效位$x_{w-1}$也被成为符号位，为1时，表示值为负，为0时，表示值为非负。

2.2.4 有符号数和无符号数之间的转换

C语言中，强制类型转换保持位值不变，只改变解释这些位的方式。

补码转换为无符号数
对满足$TMin_w \leq x \leq TMax_w$的x有：
$$T2U_w(x) = \begin{cases}x + 2^w, & x < 0 \\ x, & x \geq 0 \end{cases}$$

比较粗略地说，将一个有符号数映射为相应地无符号数时，非负数保持不变，负数被转换为大正数。

同样的，考虑无符号数转换为补码

无符号数转换为补码
对满足$0 \leq u \leq UMax_w$的u有：
$$U2T_w(u) = \begin{cases}u, & u \leq TMax_w \\ u-2^w, & u > TMax_w \end{cases}$$

将一个无符号数映射为相应的有符号数，比较小的数保持不变，比较大的数变成负数。

2.2.5 C语言中的有符号数和无符号数

C语言中，当执行运算时，一个运算数为有符号，另一个为无符号，C语言会隐式地将有符号数转换为无符号数。

2.2.6 扩展一个数字的位表示

无符号数的零扩展：只要将高位用0填充即可。
补码数的符号扩展：只要将高位用符号位填充即可。

2.2.7 截断数字

截断一个数字，会直接丢弃高位，所以很可能会改变原来的值。

hihoCoder 1467 2-SAT·hihoCoder音乐节题解

发表于 2017-01-22 | 分类于 ACM题解 |

原题

传送门

题目大意

有n首歌可以在上午放或下午放，但只能放一次，每个评委有两个要求，满足其中任意一个，评委就会满意，问能否使所有评委都满意。

分析

因为只要满足任意一个要求，就能满足，所以这两个要求之间的关系为OR。又因为每个评委都要满意，所以评委之间的关系为AND，问题就转为是否能让表达式为真。不妨将歌在上午放记为x，将歌在下午放记为~x，这样表达式就能写出了。接下考虑如何寻找表达式的解。
可以将这个问题转化为一个图论的问题。a OR b可以转变为~a->b AND ~b->a，将每首歌拆成两个点，一个代表a，另一个代表~a，根据关系连有向边。例如上面的例子，应该从~a连向b，和从~b连向a，这样就构成了一张有向图。只要任意一个点拆出的两个点都不在同一个联通块中，就代表能使所有评委满意。

参考代码

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<map>
#include<climits>
using namespace std;
struct Edge{
	int to,next;
}edge[5000];
int head[500];
int tot;
void addedge(int u,int v){
	edge[tot].to=v;
	edge[tot].next=head[u];
	head[u]=tot++;
}
void init(){
	tot=0;
	memset(head,0xff,sizeof head);
}
int Low[500],DFN[500],Stack[500],Belong[500];
int Index,top;
int scc;
bool Instack[500];
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);
	}
}
int main(){
	int k;
	scanf("%d",&k);
	while(k--){
		int n,m;
		scanf("%d %d",&n,&m);
		char a[10],b[10];
		init();
		for(int j=1;j<=m;++j){
			scanf("%s %s",a,b);
			int u=0,v=0;
			for(int i=1;i<strlen(a);++i){
				u=u*10+a[i]-'0';
			}
			if(a[0]=='m'){
				u=2*(u-1);
			} else {
				u=2*(u-1)+1;
			}
			for(int i=1;i<strlen(b);++i){
				v=v*10+b[i]-'0';
			}
			if(b[0]=='m'){
				v=2*(v-1);
			} else {
				v=2*(v-1)+1;
			}
			addedge((u^1),v);
			addedge((v^1),u);
		}
		solve(2*n);
		bool flag=1;
		for(int i=0;i<n;++i){
			if(Belong[2*i]==Belong[2*i+1]){
				flag=0;
				break;
			}
		}
		if(flag){
			printf("GOOD\n");
		} else {
			printf("BAD\n");
		}
	}
	return 0;
}

第1章计算机系统漫游

发表于 2017-01-19 | 分类于《深入了解计算机系统》读书笔记 |

这一章主要是通过一个最基本的C程序：

#include<stdio.h>
int main()
{
	printf("hello,world\n");
}

反映系统在执行这个程序时内部的大观。

1.1 信息就是位+上下文

hello程序是从一个源程序开始的。源程序实际上由0和1组成的位序列。
这里需要注意一下文本文件和二进制文件的区别。
计算机系统是一个二进制系统，系统中的一切信息都是二进制表示的，也就是说都是0和1组成的位序列，所以信息的有效解读都要依赖于上下文。

1.2 程序被其他程序翻译成不同的格式

源程序是由人类创建，供人类阅读，但机器并不行。
源程序通过其他程序翻译为低级机器语言指令，并按照可执行目标程序的格式打好包。
这个翻译过程可以分为四个阶段，即预处理阶段（预处理器），编译阶段（编译器），汇编阶段（汇编器），链接阶段（链接器）（合起来就是编译系统）。

预处理阶段

在源程序中会include很多头文件，这个阶段就是读取这些头文件，直接插入程序文本中，形成新的文件，此时的扩展名通常为.i。

编译阶段

这个阶段是做翻译工作的，把上阶段得到的文本文件翻译为.s为后缀名的文本文件，关键在于包含了一个汇编语言程序。

汇编阶段

将文本翻译为机器语言指令，并打包成可重定位目标程序，保存在.o为后缀名的二进制文件

链接阶段

这个阶段将上一阶段得到的二进制文件与一些预编译好的文件合并（例如：printf.o），生成一个可执行目标文件。

1.4 处理器读并解释存储在存储器中的指令

通过shell（一个命令行解释器）加载和运行可执行目标文件。

1.4.1 系统的硬件组成

简要地介绍系统的硬件组成

这就是系统的硬件构成，更加详细的留待以后。
但简要提一下，CPU的一些简单操作

加载：将一个字节或者一个字从主存复制到寄存器
存储：将一个字节或者一个字从寄存器复制到主存
操作：将两个寄存器的内容复制到ALU（算术逻辑单元）进行运算后，重新放入寄存器
跳转：从指令本身中抽取一个字，将字复制到程序计数器（存放下一条指令所在单元的地址）中

1.4.2 运行hello程序

外壳加载可执行的hello文件，将文件中的代码和数据从磁盘复制到主存，处理器执行main程序中的机器语言指令，将“hello world\n”字符串中的字节从主存复制到寄存器文件，再从寄存器文件复制到显示设备。

至此，hello程序的运行就基本完成了。

1.5 高速缓存至关重要

复制减缓程序“真正”的工作。
处理器从寄存器读取比主存快的多，并且差距逐渐拉大。
高速缓存存储器，用来存放处理器近期可能需要的信息，避免大量使用主存，以此加快速度。

1.6 存储设备形成层次结构

总而言之，越小越快，就越贵。
速度：寄存器>L1高速缓存>L2高速缓存>L3高速缓存主存>本地二级存储（本地磁盘）>远程二级存储。
层次结构的主要思想：高一层的存储器作为低一层的存储器的高速缓存。

1.7 操作系统管理硬件

hello程序依靠操作系统输出消息，也就是说操作系统位于应用程序和硬件之间，是一种相当底层的软件。
操作系统的两个功能：1、防止硬件被失控的应用程序滥用；2、将低级硬件设备的控制统合，变得简单一致。
操作系统至关重要的几个抽象概念：进程、虚拟存储器和文件。

1.7.1 进程

进程是操作系统对一个正在运行的程序的一种抽象。
操作系统通过交错执行（上下文切换）实现并发运行多个进程。

1.7.2 线程

一个进程可以由多个线程组成。
一个线程就是一个执行单元。

1.7.3 虚拟存储器

通过虚拟存储器，使每个进程使用一致的存储器，即虚拟地址空间。

虚拟地址空间由大量区构成：

程序代码和数据：运行时固定大小，从固定地址开始
堆：运行时可动态扩展和收缩
共享库：存放共享库的代码和数据
栈：运行时可动态扩展和收缩
内核虚拟存储器：常驻内存，不允许应用程序读写和调用

1.7.4 文件

文件就是字节序列

纵观这些抽象概念，不要忘记它们都是为了实现操作系统的功能而服务的，也就是说，抽象的目的是将我们从细节中解放出来，把具体而零散的工作给统一化。

1.8 系统之间利用网络通信

网络可以看作一个I/O设备。

1.9 重要主题

系统是硬件和系统软件互相交织的集合体。

1.9.1 并发和并行

1、线程级并发
2、指令级并发
3、单指令、多数据并发

1.9.2 计算机系统中抽象的重要性

提供不同层次的抽象表示，来隐藏实际实现的复杂性。

spoj UCV2013E - Greedy Walking 题解

发表于 2017-01-18 | 分类于 ACM题解 |

原题

传送门

题目大意

给定n维起始坐标和n维结束坐标，要求从起始坐标移动到结束坐标，每次只能沿坐标轴正方向移动一个单位，问一共由多少种移动方法。

分析

不管有几个维度，当起始坐标和结束坐标给定时，其实，向每个维度走的步数也就决定了。容易求出每个维度的坐标差之和m，这就是一共要走的步数，这时发现这其实是一个排列组合问题。不妨设每一维度对应坐标差为a1，a2，……an，那么答案就是C（a1，m）C（a2，m-a1）……*C（an，m-（a1+a2+……+an-1））。

参考代码

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<map>
#include<climits>
using namespace std;
const int mod = 1000000007;
long long c[505][505];
void getc(){
	for(int i=1;i<=500;++i){
		c[1][i]=i;
		c[0][i]=1;
		c[i][i]=1;
	}
	for(int i=2;i<=500;++i){
		for(int j=2;j<i;++j){
			c[j][i]=(c[j-1][i-1]+c[j][i-1])%mod;
		}
	}
}
int a[55],b[55];
int main(){
	int n;
	getc();
	while(scanf("%d",&n)!=EOF&&n){
		long long tot=0;
		for(int i=1;i<=n;++i){
			scanf("%d",&a[i]);
		}
		for(int i=1;i<=n;++i){
			scanf("%d",&b[i]);
			tot+=(b[i]-a[i]);
		}
		long long ans=1;
		for(int i=1;i<=n;++i){
			ans=(ans*c[b[i]-a[i]][tot])%mod;
			tot-=(b[i]-a[i]);
		}
		printf("%lld\n",ans);
	}
	return 0;
}