Material X

1010 Radix （25 分)

Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is yes, if 6 is a decimal number and 110 is a binary number.

Now for any pair of positive integers N1 and N2, your task is to find the radix of one number while that of the other is given.

Input Specification:

Each input file contains one test case. Each case occupies a line which contains 4 positive integers:

1

N1 N2 tag radix

Here N1 and N2 each has no more than 10 digits. A digit is less than its radix and is chosen from the set { 0-9, a-z } where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35. The last number radix is the radix of N1 if tag is 1, or of N2 if tag is 2.

Output Specification:

For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true. If the equation is impossible, print Impossible. If the solution is not unique, output the smallest possible radix.

Sample Input 1:

1

6 110 1 10

Sample Output 1:

1

2

Sample Input 2:

1

1 ab 1 2

Sample Output 2:

1

Impossible

题解：

题目给出了两个正数N1，N2。并给出了第tag个数是radix进制，让你求另一个数的进制。（0-9代表0-9数字，a-z代表10-35数字）如果没有结果，输出Impossible。如果有多个结果，输出最小的进制。

①首先要用longlong类型应该不难看出来。
②试答案的时候不能顺序搜索，要用二分搜索。
③二分的边界要想对，最小的应该是数中最小的那个数+1，比如：123a，那么这个数最小的进制数为11（因为数中有a）。最大的边界应该为基准数的十进制值（例如：基准数的十进制为为1000000，另一个数为10，那么它可以是1000000进制的，也满足条件）。
④如果算的进制数太大时，可能会爆longlong，那么在计算中还要注意对溢出的判断（num<0）

代码如下：

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 <cstdio>
#include <string>
#include <algorithm>
#include <iostream>
#include<cmath>

using namespace std; 

long long toNum(char ch)
{
	if(ch>='0'&&ch<='9')
		return ch - '0';
	else
		return ch - 'a' + 10;
} 

long long getNum(string str, long long radix)
{
	long long wei = 1;
	long long num = 0;
	for(int i = 0; str[i]!='\0'; i++)
	{	
		num = num + toNum(str[i]) * wei;
		if (num < 0 || wei < 0)     //需要判断这个，也许进制太大了呢 
            return -1;
		wei *= radix;
	}
	return num;
}

int main()
{
	
	string N1,N2;
	long long num1 = 0;
	long long num2 = 0; 
	int tag; 
	long long radix;
	cin >> N1 >> N2 >> tag >> radix; 
	reverse(N1.begin(), N1.end());
	reverse(N2.begin(), N2.end());
	if(N1 == N2)
	{
		printf("%d\n", radix);
		return 0;
	}
	if(tag == 2)
	{
		swap(N1, N2);
	}
	
	
	num1 = getNum(N1, radix);
	radix = 2;
	for(int i = 0; i < N2.size(); i++)
	{
		radix = max(radix, toNum(N2[i])+1);	
	} 
	
	long long left, right, mid;
	left = radix;
	right = num1;
	while(right >= left)
	{
		mid = (left + right) / 2;
		long long temp = getNum(N2, mid);
		if(temp >= num1 || temp == -1)
			right = mid - 1;
		else
			left = mid + 1;
			
	}
	if(num1 == getNum(N2, left))
	{
		printf("%d\n", left);
	}
	else 
	{
		printf("Impossible\n");
	}
}

1051 Pop Sequence （25 分)

Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, …, N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if Mis 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.

Input Specification:

Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M(the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.

Output Specification:

For each pop sequence, print in one line “YES” if it is indeed a possible pop sequence of the stack, or “NO” if not.

Sample Input:

1
2
3
4
5
6

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

Sample Output:

1
2
3
4
5

YES
NO
NO
YES
NO

题解：

题目说给出一个能放入M个数的栈，Push数字1, 2, 3, …, N顺序入栈，Pop随机数量出栈。给出K个出栈的顺序，让你判断是不是这个栈的出栈顺序。

模拟题，模拟栈的操作就可以解决。将数字顺序入栈直到与给出的顺序数字相同再出栈，如果大于M还是与序列数值不同直接NO，如果全部模拟完栈为空栈为YES。

代码如下：

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

#include <cstdio>
#include <stack>
using namespace std;

int main()
{
	int nums[1001];
	int M, N, K;
	scanf("%d%d%d",&M, &N, &K);
	while(K--)
	{
		for(int i = 0; i < N; i++)
		{
			scanf("%d", &nums[i]);
		}
		stack<int> s;
		int l = 0;
		bool flag = true;//判断栈的容量是否超过m
		for(int i = 1; i <= N&&flag; i++)
		{
			s.push(i);
			if(s.size()>M)
			{
				flag = false;
			}
			while(s.size()>0&&s.top()==nums[l])
			{
				s.pop();
				l++;
			}
			
		}
		if(flag&&s.size()==0) printf("YES\n");
		else printf("NO\n");
		
	}
}

1052 Linked List Sorting （25 分)

A linked list consists of a series of structures, which are not necessarily adjacent in memory. We assume that each structure contains an integer key and a Next pointer to the next structure. Now given a linked list, you are supposed to sort the structures according to their key values in increasing order.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive N (<105) and an address of the head node, where N is the total number of nodes in memory and the address of a node is a 5-digit positive integer. NULL is represented by −1.

Then N lines follow, each describes a node in the format:

1

Address Key Next

where Address is the address of the node in memory, Key is an integer in [−105,105], and Next is the address of the next node. It is guaranteed that all the keys are distinct and there is no cycle in the linked list starting from the head node.

Output Specification:

For each test case, the output format is the same as that of the input, where N is the total number of nodes in the list and all the nodes must be sorted order.

Sample Input:

1
2
3
4
5
6

5 00001
11111 100 -1
00001 0 22222
33333 100000 11111
12345 -1 33333
22222 1000 12345

Sample Output:

1
2
3
4
5
6

5 12345
12345 -1 00001
00001 0 11111
11111 100 22222
22222 1000 33333
33333 100000 -1

题解：

题目说给出一个链表，让我们给出这个链表从小到大的排列，样例输入输出格式一样。

常规思路是节点输入操作排序，需要STL的sort。这题要注意输出的链表节点Address的格式，还要考虑到给出的链表序列是否连续，根据链表原理使用vector并sort排序。

代码如下：

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

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

struct node{
	int address; 
	int next;
	int value;
};
bool cmp(node a, node b)
{
	return a.value<b.value;
}
int main()
{
	node a[100001];
	
	int n, address;
	vector<node> l;
	scanf("%d%d", &n, &address);
	int b,c,d;
	for(int i = 0; i < n; i++)
	{
		scanf("%d%d%d", &b, &c, &d);
		a[b].address = b;
		a[b].value = c;
		a[b].next = d;	
	}
	
	while(address!=-1)
	{
		l.push_back(a[address]);
		address = a[address].next;
	}
	
	if(l.size() == 0)//测试点1 可能链表的节点连不起来
	{
		printf("0 -1\n");
		return 0;
	}
	
	sort(l.begin(), l.end(), cmp);
	
	printf("%d %05d\n", l.size(), l[0].address);//测试点3 
	int i;
	for(i = 0; i < l.size() - 1; i++)
	{
		printf("%05d %d %05d\n", l[i].address, l[i].value, l[i+1].address);
		
	}
	printf("%05d %d -1\n", l[i].address, l[i].value);

}

1086 Tree Traversals Again （25 分)

An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.

Figure 1

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: “Push X” where X is the index of the node being pushed onto the stack; or “Pop” meaning to pop one node from the stack.

Output Specification:

For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

1
2
3
4
5
6
7
8
9
10
11
12
13

6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop

Sample Output:

1

3 4 2 6 5 1

题解：

题目说中序遍历二叉树可以用非递归栈的方法遍历。输入样例给你一组中序创建二叉树的栈操作，让你给出这棵数的后序遍历。我们可以把栈操作和图Figure 1结合起来很容易地发现，原来Push进栈的顺序为先序排列，而Pop出栈的顺序为中序排列。这样，求一个树的后序排列，简单一点只要根据先序和后序递归创建树，再用递归后序遍历就行了。

代码如下：

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

#include <cstdio>
#include <malloc.h>
#include <stack>
#include <cstring>

using namespace std;

struct TreeNode{
	int value;
	TreeNode* ltree;
	TreeNode* rtree; 
}; 

int num = 0;
void postorder(TreeNode* root, int n)
{
	if(root->ltree!=NULL)postorder(root->ltree, n);
	if(root->rtree!=NULL)postorder(root->rtree, n);
	printf("%d", root->value);num++;
	if(num<n)printf(" ");
	
}

void getPerAndIn(int* perorder, int* inorder, int n)
{
	stack<int> s;
	char str[10];
	int temp;
	int per = 0;
	int in = 0;
	n = 2*n;
	while(n--)
	{
		scanf("%s",str);
		if(strcmp(str, "Push") == 0)
		{
			scanf("%d", &temp);
			s.push(temp);
			perorder[per] = temp;
			per++;
		}
		else if(strcmp(str, "Pop") == 0)
		{
			inorder[in] = s.top();
			in++;
			s.pop();
		}
	}
	
}

void buildTree(int* perorder, int* inorder, int n, TreeNode** root)
{
	if(!perorder || !inorder || n <= 0)
		return;
	
	int i;
	for( i = 0; i < n; i++)
	{
		if(perorder[0] == inorder[i])
		{
			break;	
		} 
	}
	
	*root = (TreeNode*)malloc(sizeof(TreeNode));
	if(!root)
	{
		return;	
	} 
	(*root)->ltree = (*root)->rtree = NULL;
	(*root)->value = perorder[0];
	
	buildTree(perorder+1, inorder, i, &(*root)->ltree);
	buildTree(perorder+i+1, inorder+i+1, n-i-1, &(*root)->rtree);
	 
}
int main()
{
	int n, perorder[31], inorder[31];
	scanf("%d", &n);
	getPerAndIn(perorder, inorder, n);
	TreeNode* root; 
	buildTree(perorder, inorder, n, &root);
	postorder(root, n);
	
}

1020 Tree Traversals （25 分)

Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

1
2
3

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7

Sample Output:

1

4 1 6 3 5 7 2

题解：

题目给出了二叉树的后序遍历和中序遍历的序列，让你给出该二叉树的层序遍历排列。

最容易最简单想到的是使用递归的方法。如题目给出的样例输入第二行为后序排列第三行为中序排列。比较很容易得到根节点为4，左子树的后序排列为2 3 1 右子树的后序排列为5 7 6 左子树的中序排列为1 2 3 右子树的后序排列为5 6 7。再分别对左右子树的排列做如上操作。使用递归创建该二叉树（基于二叉树先序中序后序遍历的特点）

层序遍历排列非常容易用常规的队列方法得到。

代码如下：

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

#include <cstdio>
#include <malloc.h>
#include <queue>

using namespace std;

struct TreeNode{
	int value;
	TreeNode* ltree;
	TreeNode* rtree;
};

void build(int* postorder, int* inorder, int n, TreeNode* *root)
{
	if(!postorder || !inorder || n<=0) //空
		return;
	int i;
	for( i = 0; i < n; i++)
	{
		if(inorder[i] == postorder[n - 1])	//找根节点
		{
			break;
		}
	}
	
	if(i>n)	//找不到退出
		return;
	
	*root = (TreeNode*)malloc(sizeof(TreeNode));
	if(!root)
	{
		return;
	}
	(*root)->ltree = (*root)->rtree = NULL;
	(*root)->value = postorder[n - 1];
	
	build(postorder, inorder, i, &(*root)->ltree);	//左子树
	build(postorder+i,inorder+i+1,n-i-1, &(*root)->rtree); //右子树
}

void seqorder(TreeNode* root, int n)
{
	queue<TreeNode*> q;
	q.push(root);
	while(!q.empty())
	{
		TreeNode* node = q.front();
		q.pop(); //上两行为队列的出
		n--;
		if(n==0)
		{
			printf("%d\n", node->value);
		}
		else
		{
			printf("%d ", node->value);
		}
		if(node->ltree)
			q.push(node->ltree);
		if(node->rtree)
			q.push(node->rtree);
	}
}

int main()
{
	int postorder[31], inorder[31], n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
	{
		scanf("%d", &postorder[i]);
	}
	for(int i = 0; i < n; i++)
	{
		scanf("%d", &inorder[i]);
	}
	TreeNode* root;
	build(postorder, inorder, n, &root);
	seqorder(root, n);
}

相关教程转至： 使用Hexo+Github一步步搭建属于自己的博客（基础）

本博客诞生多数操作基于此教程

相关步骤：

1、安装Node.js和配置好Node.js环境，打开cmd命令行，成功界面如下

2、安装Git和配置好Git环境，安装成功的象征就是在电脑上任何位置鼠标右键能够出现如下两个选择

注意：一般出于安全考虑，只有在Git Bash Here中才能进行Git的相关操作。如果需要在cmd命令行里调用Git，那么就要配置电脑的环境变量Path，或者在安装的时候选择use Git from the Windows Command Prompt。这个可有可无，影响不大，成功配置的界面如图

3、Github账户注册和新建项目，项目必须要遵守格式：账户名.github.io，不然接下来会有很多麻烦。并且需要勾选Initialize this repository with a README

在建好的项目右侧有个settings按钮，点击它，向下拉到GitHub Pages，你会看到那边有个网址，访问它，你将会惊奇的发现该项目已经被部署到网络上，能够通过外网来访问它。

4、安装Hexo，在自己认为合适的地方创个文件夹，我是在D盘建了一个blog文件夹。然后通过命令行进入到该文件夹里面

输入npm install hexo -g，开始安装Hexo

输入hexo -v，检查hexo是否安装成功

输入hexo init，初始化该文件夹（有点漫长的等待。。。）

看到后面的“Start blogging with Hexo！”，激动有木有！！！！！

输入npm install，安装所需要的组件

输入hexo g，首次体验Hexo

输入hexo s，开启服务器，访问该网址，正式体验Hexo

问题：假如页面一直无法跳转，那么可能端口被占用了。此时我们ctrl+c停止服务器，接着输入“hexo server -p 端口号”来改变端口号

那么出现如下图就成功了

5、将Hexo与Github page联系起来，设置Git的user name和email（如果是第一次的话）

上图是在其文件夹里面鼠标右键，点击Git Base Here。这里“feng”可以替换成自己的用户名，邮箱可以替换成自己的邮箱

输入cd ~/.ssh，检查是否由.ssh的文件夹

输入ls，列出该文件下的内容。下图说明存在

输入ssh-keygen -t rsa -C “ 929762930@qq.com”，连续三个回车，生成密钥，最后得到了两个文件：id_rsa和id_rsa.pub（默认存储路径是：C:\Users\Administrator.ssh）。

输入eval “$(ssh-agent -s)”，添加密钥到ssh-agent

再输入ssh-add ~/.ssh/id_rsa，添加生成的SSH key到ssh-agent

登录Github，点击头像下的settings，添加ssh

新建一个new ssh key，将id_rsa.pub文件里的内容复制上去

输入ssh -T git@github.com，测试添加ssh是否成功。如果看到Hi后面是你的用户名，就说明成功了

问题：假如ssh-key配置失败，那么只要以下步骤就能完全解决

首先，清除所有的key-pair
ssh-add -D
rm -r ~/.ssh
删除你在github中的public-key

重新生成ssh密钥对
ssh-keygen -t rsa -C “ xxx@xxx.com“

接下来正常操作
在github上添加公钥public-key:
1、首先在你的终端运行 xclip -sel c ~/.ssh/id_rsa.pub将公钥内容复制到剪切板
2、在github上添加公钥时，直接复制即可
3、保存

6、配置Deployment，在其文件夹中，找到_config.yml文件，修改repo值（在末尾）

repo值是你在github项目里的ssh（右下角）

7、新建一篇博客，在cmd执行命令：hexo new post “博客名”

这时候在文件夹_posts目录下将会看到已经创建的文件

在生成以及部署文章之前，需要安装一个扩展：npm install hexo-deployer-git –save

使用编辑器编好文章，那么就可以使用命令：hexo d -g，生成以及部署了

部署成功后访问你的地址：http://用户名.github.io。那么将看到生成的文章

好了，到此为止，最基本的也是最全面的hexo+github搭建博客完结。

hexo生成博文插入图片（转）

相关步骤：
把主页配置文件_config.yml 里的post_asset_folder:这个选项设置为true

在你的hexo目录下执行这样一句话npm install hexo-asset-image –save，这是下载安装一个可以上传本地图片的插件，来自dalao：dalao的git

等待一小段时间后，再运行hexo n “xxxx”来生成md博文时，/source/_posts文件夹内除了xxxx.md文件还有一个同名的文件夹 （当然也可以自己手动建）

最后在xxxx.md中想引入图片时，先把图片复制到xxxx这个文件夹中，然后只需要在xxxx.md中按照markdown的格式引入图片：

注意： xxxx是这个md文件的名字，也是同名文件夹的名字。只需要有文件夹名字即可，不需要有什么绝对路径。你想引入的图片就只需要放入xxxx这个文件夹内就好了，很像引用相对路径。

最后检查一下，hexo g生成页面后，进入public\2017\02\26\index.html文件中查看相关字段，可以发现，html标签内的语句是，而不是<img src=”xxxx/图片名.jpg>。这很重要，关乎你的网页是否可以真正加载你想插入的图片。